Convex hull

The convex hull of a set of points is the smallest convex shape that contains them all. Picture a rubber band stretched around nails: it touches only the outermost ones. Those are the hull's corners.

A hull that follows the points

Gift wrapping finds the hull one corner at a time. It starts at the leftmost point, which must be a corner. From the current corner, the next corner is the point with every other point on its left. It repeats until it is back at the start.

pie.clear()
import numpy as np
coords = np.random.default_rng(3).uniform(-4, 4, size=(14, 2)).round(2)
pts = [pie.point(x, y, fill='crimson') for x, y in coords]

def cross(o, a, b):
    """Above 0 if b is left of the line from o to a, below 0 if right, 0 if on it."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def farther(o, a, b):
    """True if b is farther from o than a is."""
    return np.hypot(b[0] - o[0], b[1] - o[1]) > np.hypot(a[0] - o[0], a[1] - o[1])

def wrap(ps):
    """The positions in ps of the hull's corners, counterclockwise from the leftmost point."""
    start = min(range(len(ps)), key=lambda i: ps[i][0])
    hull = [start]
    for _ in range(len(ps)):
        here = ps[hull[-1]]
        best = (hull[-1] + 1) % len(ps)
        for r in range(len(ps)):
            turn = cross(here, ps[best], ps[r])
            # r is right of the line to best, or on it but farther: r is the better next corner.
            if turn < 0 or (turn == 0 and farther(here, ps[best], ps[r])):
                best = r
        if best == start:
            break
        hull.append(best)
    return hull

def padded(hull, n):
    """`hull`, made n long by repeating its first corner, so the array keeps its size as points move."""
    return hull + [hull[0]] * (n - len(hull))

def corners(*ps):
    return np.array(ps)[padded(wrap(ps), len(ps))]

def next_corners(*ps):
    """The corner after each corner, so each corner and its next one make an edge."""
    hull = wrap(ps)
    return np.array(ps)[padded(hull[1:] + hull[:1], len(ps))]

def describe(*ps):
    return f'{len(wrap(ps))} of {len(ps)} points are corners'

cs = pie.lift(corners, pie.Array[pie.Point])(*pts, hidden=True)
ns = pie.lift(next_corners, pie.Array[pie.Point])(*pts, hidden=True)
pie.triangle(cs[0], cs, ns, fill='rgba(13, 148, 136, 0.15)', stroke='none')
pie.line(cs, ns, stroke='teal')
pie.text(pie.lift(describe, str)(*pts), 0, 4.8, 14, stroke='#1c1917')

Drag any point. Pull an inside point out past the edge and it becomes a corner. Push a corner inside and the hull lets go of it.

corners and next_corners return arrays of points, so pie.line(cs, ns) draws one edge per pair. The shading is a fan of triangles that all share the first corner. The hull has fewer corners than there are points, so the arrays are padded by repeating the first corner. The padded edges and triangles have zero size, so they don't show.

Gift wrapping, step by step

This runs the same algorithm on a new random set of points every time, and animates every check. Run it after the editor above, which defines cross and farther.

pie.clear()
import numpy as np
gray, amber, teal = '#a8a29e', '#f59e0b', 'teal'
coords = np.random.default_rng().uniform(-4, 4, size=(9, 2)).round(2)
n = len(coords)
ps = [pie.point(x, y, fill=gray) for x, y in coords]

start = min(range(n), key=lambda i: coords[i][0])
here = pie.point(*coords[start], hidden=True)   # the corner we wrap from
best = pie.point(*coords[start], hidden=True)   # the best next corner so far
probe = pie.point(*coords[start], hidden=True)  # the point being checked
lines = [pie.line(here, probe, stroke=gray), pie.line(here, best, stroke=amber)]
pie.set_fill(ps[start], teal)

def move(nodes, i):
    """Glide a node, or every node in a list, to point i."""
    nodes = nodes if isinstance(nodes, list) else [nodes]
    pie.translate_point_to(nodes, [coords[i][0]] * len(nodes), [coords[i][1]] * len(nodes), animate=True)

h, checks = start, 0
for _ in range(n):
    b = (h + 1) % n
    move([best, probe], b)
    for r in range(n):
        if r in (h, b):
            continue
        move(probe, r)
        checks += 1
        pie.text(f'checks: {checks}', 0, 4.8, 14, out='checks')
        turn = cross(coords[h], coords[b], coords[r])
        if turn < 0 or (turn == 0 and farther(coords[h], coords[b], coords[r])):
            b = r
            move(best, b)
    pie.line(ps[h], ps[b], stroke=teal)
    if b == start:
        break
    pie.set_fill(ps[b], teal)
    move([here, best, probe], b)
    h = b
pie.hide(lines)

The amber line points at the best next corner so far, and the gray line at the point being checked. When the checked point is to the right of the amber line, the amber line swings to it. After all points are checked, the amber line is a hull edge and turns teal.

Every corner checks every other point, so a hull with $h$ corners around $n$ points takes about $n \times h$ checks. That is fast when the hull has few corners, and slow when most points are corners.