Add draw.aalines width argument

[mzivic7]

trafficstars

This PR adds width argument to draw.aalines with miter edges. Closes #1225 Left: draw.lines without miter edges, Right: draw.aalines with miter edges.

draw.lines will get miter edges in new PR, and draw.aapolygon in #3126.

Sample code

import pygame
points = [
    [70, 121],
    [100, 100],
    [200, 160],
    [120, 205],
    [160, 250],
    [130, 250],
    [100, 250],
]
pygame.init()
screen = pygame.display.set_mode((300, 300))
clock = pygame.time.Clock()
run = True
while run:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False
    screen.fill("black")
    pygame.draw.aalines(screen, "white", True, points, 16)
    pygame.display.flip()
    clock.tick(60)
pygame.quit()

How it works, pseudocode

First, draw normal lines
For each point:
    Point actually represents a line, starting from previous point and ending in this
    Calculate this lines endpoints (called initial points)
        This is two pairs of points assembling 2 lines: left and right
    Also have those endpoints from previous point
    Then make for both, this and previous point, same pairs but with slightly lower width (called inner, starts with in_)

    Find what corner points are wrong:
        If both left and right lines for this and previous line have same end points at this corner, it's fine, but if any of them are intersecting it's not fine
    If only left or only right ones have same endpoints at this corner or both have same endpoints but intersect each other then:
        Extend lines infinitely and calculate their intersection
        This intersection is now new corner point for both previous and this line
    Do the same for inner points

    Append selected endpoints to 2 lists, one for left and second for right points
    Draw aalines with those lists
    Handle corners:
        Take selected points from this line and previous line, those are inner points
        Draw polygon with them
        Take selected points from this line and before it was modified with new corners, those are inner points
        Draw aapolygon with them (regular polygon with aalines)
    Because loop is over, append final points to draw last line


Inner points:
Drawn aapolygons must be smaller than aalines surrounding them, so their antialiased pixels do not overlap. That is why width is decreased by 1.5 for them. This value might need tuning.

Why 2 polygons on corners:
First polygon is created from left and right corner (calculated by intersecting lines) and points provided by previous lines. This will usually fill only half of the gap.
If there is no gap, do not draw second polygon.
Second polygon is created from same left and right corners, but with points provided by this line, those are points before they were changed after intersecting.

Working python implementation

import pygame


def is_intersect(a, b, c, d):
    """Returns True if 2 line segments are intersecting.
    a and b are points of first line, c and d are points of second line"""
    def ccw(a, b, c):
        return (c[1] - a[1]) * (b[0] - a[0]) > (b[1] - a[1]) * (c[0] - a[0])
    return ccw(a, c, d) != ccw(b, c, d) and ccw(a, b, c) != ccw(a, b, d)


def is_left(a, b, n):
    """Returns True of point n is on left side of line given by points a and b"""
    return (b[0] - a[0]) * (n[1] - a[1]) - (b[1] - a[1]) * (n[0] - a[0]) > 0


def intersect_point(a, b, c, d):
    """Finds intersection coordinates of 2 lines.
    a and b are points of first line, c and d are points of second line"""
    x1, y1 = a
    x2, y2 = b
    x3, y3 = c
    x4, y4 = d
    det = (y2-y1)*(x3-x4)-(y4-y3)*(x1-x2)
    if not det:
        return a
    x = ((x1*y2-x2*y1) * (x3-x4) - (x3*y4-x4*y3) * (x1-x2)) / det
    y = ((y2-y1) * (x3*y4-x4*y3) - (y4-y3) * (x1*y2-x2*y1)) / det
    return (x, y)


def line_width_corners(prev_point, point, width):
    """Returns 4 points, representing corners of pygame.draw.line
    first two points assemble left line and second two - right line"""
    from_x, from_y = int(prev_point[0]), int(prev_point[1])
    to_x, to_y = int(point[0]), int(point[1])
    aa_width = (width / 2)
    extra_width = (1 - (int(width) % 2)) / 2
    steep = abs(to_x - from_x) <= abs(to_y - from_y)
    if steep:
        left_from = (from_x + extra_width + aa_width, from_y)
        left_to = (to_x + extra_width + aa_width, to_y)
        right_from = (from_x + extra_width - aa_width, from_y)
        right_to = (to_x + extra_width - aa_width, to_y)
    else:
        left_from = (from_x, from_y + extra_width + aa_width)
        left_to = (to_x, to_y + extra_width + aa_width)
        right_from = (from_x, from_y + extra_width - aa_width)
        right_to = (to_x, to_y + extra_width - aa_width)

    # sort left and right points, _l is always left
    if is_left(prev_point, point, right_from):
        left_from, right_from = right_from, left_from
        left_to, right_to = right_to, left_to

    return left_from, left_to, right_from, right_to


def draw_aalines(surface, color, closed, points, width):
    """draws antialiased lines, with filled corners."""
    points = points.copy()
    width = int(width)
    left_points = []
    right_points = []
    prev_point = points[0]
    last_point = points[-1]
    prev_left_from, prev_left_to, prev_right_from, prev_right_to = line_width_corners(last_point, prev_point, width)
    in_prev_left_from, in_prev_left_to, in_prev_right_from, in_prev_right_to = line_width_corners(last_point, prev_point, width-1.5)

    if width < 2:
        pygame.draw.aalines(surface, color, closed, points)
        return

    # extra iteration to allow filling gaps on closed aaline
    if closed:
        points.append(prev_point)

    for num, point in enumerate(points[1:]):

        left_from, left_to, right_from, right_to = line_width_corners(prev_point, point, width)
        in_left_from, in_left_to, in_right_from, in_right_to = line_width_corners(prev_point, point, width-1.5)
        in_orig_left_from = in_left_from
        in_orig_right_from = in_right_from

        # find and change corners
        if num or (not num and closed):
            # LEFT
            if left_from != prev_left_to:
                right_from = intersect_point(right_from, right_to, prev_right_from, prev_right_to)
                in_right_from = intersect_point(in_right_from, in_right_to, in_prev_right_from, in_prev_right_to)
            else:
                if is_intersect(left_from, left_to, prev_right_from, prev_right_to):
                    right_from = intersect_point(right_from, right_to, prev_left_from, prev_left_to)
                    in_right_from = intersect_point(in_right_from, in_right_to, in_prev_right_from, in_prev_right_to)
            # RIGHT
            if right_from != prev_right_to:
                left_from = intersect_point(left_from, left_to, prev_left_from, prev_left_to)
                in_left_from = intersect_point(in_left_from, in_left_to, in_prev_left_from, in_prev_left_to)
            else:
                if is_intersect(right_from, right_to, prev_left_from, prev_left_to):
                    # special case where both points are mismatched
                    left_from = intersect_point(left_from, left_to, prev_right_from, prev_right_to)
                    in_left_from = intersect_point(in_right_from, in_left_to, in_prev_right_from, in_prev_right_to)

        # for aalines
        left_points.append(left_from)
        right_points.append(right_from)

        # fill gaps in corners
        if closed or num:
            # this line
            edge_points = [in_left_from, in_orig_left_from, in_right_from, in_orig_right_from]
            int_edge_points = []
            for edge_point in edge_points:
                int_edge_points.append((round(edge_point[0]), round(edge_point[1])))
            pygame.draw.polygon(surface, color, int_edge_points)
            pygame.draw.aalines(surface, color, True, edge_points)
            # previous line
            if in_orig_left_from != in_prev_left_to and in_orig_right_from != in_prev_right_to:
                edge_points = [in_left_from, in_prev_left_to, in_right_from, in_prev_right_to]
                int_edge_points = []
                for edge_point in edge_points:
                    int_edge_points.append((round(edge_point[0]), round(edge_point[1])))
                pygame.draw.polygon(surface, color, int_edge_points)
                pygame.draw.aalines(surface, color, True, edge_points)

        # data for the next iteration
        prev_point = point
        prev_left_from = left_from
        prev_right_from = right_from
        prev_left_to = left_to 
        prev_right_to = right_to
        in_prev_left_from = in_left_from
        in_prev_right_from = in_right_from
        in_prev_left_to = in_left_to
        in_prev_right_to = in_right_to

    # last point for open aalines
    if not closed:
        left_points.append(left_to)
        right_points.append(right_to)

    # drawing
    pygame.draw.lines(surface, color, closed, points, width)
    pygame.draw.aalines(surface, color, closed, left_points)
    pygame.draw.aalines(surface, color, closed, right_points)