2D drawing algorithm

make_polygon.py

# python3 -mvenv venv && source venv/bin/activate && pip install matplotlib
# python3 make_polygon.py
import matplotlib.pyplot as plt
import math

def make_polygon(vertices):
    # compute centroid
    average_x = sum([vertex[0] for vertex in vertices]) / len(vertices)
    average_y = sum([vertex[1] for vertex in vertices]) / len(vertices)
    centroid = [average_x, average_y]
    # compute angle of all vertices from centroid (the centroid being the origin)
    vertices_with_angles = [(vertex, math.atan2(vertex[0] - centroid[0], vertex[1] - centroid[1])) for vertex in vertices]
    # order by angle
    return [x[0] for x in sorted(vertices_with_angles, key=lambda vertex_with_angle: vertex_with_angle[1])]

# A little more complicated but no trigonometry
def make_polygon_no_trigo(vertices):
    # compute centroid
    def quadrant(vertex, centroid):
        dx = vertex[0] - centroid[0]
        dy = vertex[1] - centroid[1]
        if dx >= 0 and dy >= 0:
            return 0
        if dx < 0 and dy >= 0:
            return 1
        if dx < 0 and dy < 0:
            return 2
        return 3

    def cross(v1, v2, centroid):
        d1x = v1[0] - centroid[0]
        d1y = v1[1] - centroid[1]
        d2x = v2[0] - centroid[0]
        d2y = v2[1] - centroid[1]
        return d1x * d2y - d1y * d2x

    def dist_sq(vertex, centroid):
        return (vertex[0] - centroid[0])**2 + (vertex[1] - centroid[1])**2

    # order by quadrant, then by cross product and then by distance from centroid
    average_x = sum([vertex[0] for vertex in vertices]) / len(vertices)
    average_y = sum([vertex[1] for vertex in vertices]) / len(vertices)
    centroid = [average_x, average_y]
    # order by quadrant, then by cross product and then by distance from centroid
    def cmpfn(a, b):
        qa = quadrant(a, centroid)
        qb = quadrant(b, centroid)
        if qa != qb:
            return qa - qb
        # in same quadrant: sort by cross product
        c = cross(a, b, centroid)
        if c != 0:
            return -1 if c > 0 else 1
        # Collinear points: sort by distance from centroid
        d1 = dist_sq(a, centroid)
        d2 = dist_sq(b, centroid)
        return d1 - d2
    import functools
    return sorted(vertices, key=functools.cmp_to_key(cmpfn))

#vertices = [(1, 1), (4, 3), (2, 5), (6, 7)]
import random
vertices = [(random.randint(0, 999), random.randint(0, 999)) for _ in range(100)]

vertices = make_polygon_no_trigo(vertices)

# Plotting the initial polygon
x = [vertex[0] for vertex in vertices]
y = [vertex[1] for vertex in vertices]
plt.plot(x + [x[0]], y + [y[0]], color='black')
plt.show()

scanfill.py

# A rewrite over the deranged https://medium.com/@dillihangrae/scanline-filling-algorithm-852ad47fb0dd
# python3 -mvenv venv && source venv/bin/activate && pip install matplotlib
# python3 scanfill.py
import numpy as np
import matplotlib.pyplot as plt

class Edge:
    min_y = 0
    max_y = 0
    x_min_y = 0
    slope = 0

    def __init__(self, min_y, x_min_y, max_y, slope):
        self.min_y = min_y
        self.x_min_y = x_min_y
        self.max_y = max_y
        self.slope  = slope

    def __repr__(self):
        return f'(min_y={self.min_y} x_min_y={self.x_min_y} max_y={self.max_y} slope={self.slope})'

# Define a function to calculate the slope of an edge
def calculate_slope(x0, y0, x1, y1):
    return (y0 - y1) / (x0 - x1)

# Define a function to initialize all edges of the polygon
def initialize_edges(vertices):
    edges = []
    num_vertices = len(vertices)
    for i in range(num_vertices):
        x0, y0 = vertices[i]
        x1, y1 = vertices[(i + 1) % num_vertices]
        min_y = min(y0, y1)
        max_y = max(y0, y1)
        x_min_y = x0 if y0 <= y1 else x1
        slope = calculate_slope(x0, y0, x1, y1)
        edges.append(Edge(min_y, x_min_y, max_y, slope))
    return edges

# Define a function to initialize the global edge table
def initialize_global_edge_table(edges):
    global_edge_table = sorted(edges, key=lambda edge: (edge.min_y, edge.x_min_y))
    # We eliminate flat edges
    global_edge_table = [edge for edge in global_edge_table if edge.slope != 0]
    return global_edge_table

# Select the edges that will be used for the scanline scan_line
def get_active_edge_table(source_table, scan_line):
    active_edge_table = [edge for edge in source_table if edge.min_y <= scan_line and edge.max_y > scan_line]
    active_edge_table.sort(key=lambda edge: (edge.x_min_y, -edge.slope))
    return active_edge_table

# Define a function to fill the polygon
def fill_polygon(vertices):
    edges = initialize_edges(vertices)
    global_edge_table = initialize_global_edge_table(edges)

    # Initialize scan-line and active edge table
    scan_line = edges[0].min_y
    active_edge_table = get_active_edge_table(global_edge_table, scan_line)

    # Plotting the initial polygon
    x = [vertex[0] for vertex in vertices]
    y = [vertex[1] for vertex in vertices]
    plt.plot(x + [x[0]], y + [y[0]], color='black')

    # Iterate over each scan-line until active edge table is empty
    while active_edge_table:
        # Determine odd and even parity edge pairs
        odd_edges = [edge for i, edge in enumerate(active_edge_table) if i % 2 == 1]
        even_edges = [edge for i, edge in enumerate(active_edge_table) if i % 2 == 0]

        assert len(even_edges) == len(odd_edges)

        # Draw pixels between x-values of odd and even parity edge pairs
        for i in range(len(even_edges)):
            x_start = round((scan_line - even_edges[i].min_y) / even_edges[i].slope + even_edges[i].x_min_y)
            x_end = round((scan_line - odd_edges[i].min_y) / odd_edges[i].slope + odd_edges[i].x_min_y)
            plt.plot(range(x_start, x_end + 1), [scan_line] * (x_end - x_start + 1), color='blue')

        # Update scan-line and active edge table
        scan_line += 1
        active_edge_table = get_active_edge_table(global_edge_table, scan_line)

# Example usage
vertices = [(1, 1), (2, 5), (6, 7), (4, 3)]
fill_polygon(vertices)
plt.gca().set_aspect('equal', adjustable='box')
plt.show()