Convex hull (Graham scan)

Cost and properties

time	O(n log n)
dominated by	the sort
scan	O(n) — each point pushed and popped once
primitive	the ccw test

Reference: Sedgewick & Wayne, §2.5; Graham 1972.

Convex hull (Graham scan) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import math

def convex_hull(points):
    pts = sorted(set(points))
    start = min(pts, key=lambda p: (p[1], p[0]))   # lowest y, then lowest x

    def ccw(a, b, c):                     # > 0 left turn, < 0 right turn
        return (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0])

    rest = [p for p in pts if p != start]
    rest.sort(key=lambda p: (math.atan2(p[1]-start[1], p[0]-start[0]),
                             (p[0]-start[0])**2 + (p[1]-start[1])**2))

    hull = [start]
    for p in rest:
        while len(hull) > 1 and ccw(hull[-2], hull[-1], p) <= 0:
            hull.pop()                    # not a left turn: discard
        hull.append(p)
    return hull

Why it works

Reduction: geometry to sorting

The hull is a sorting problem in disguise. Once the points are ordered by polar angle around the lowest point, the hull vertices appear in that order, so a single linear scan suffices. The lesson generalises: much of the value of a sort is the structure it creates for the next step.

The ccw primitive

ccw(a,b,c) is the sign of a 2×2 determinant — the cross product of b−a and c−a. Positive means the turn a→b→c is counter-clockwise, negative clockwise, zero collinear. It uses only multiplication and subtraction, so with integer inputs it is exact: no floating-point error, no epsilon, no wrong answers on degenerate input. Computing angles and comparing them would forfeit that.

Why the scan is linear

The while loop looks like it could be quadratic, but every point is appended once and popped at most once, so the total number of pops over the whole run is at most n. The scan is O(n) and the sort dominates: O(n log n) overall.

Degenerate cases

The <= 0 test discards collinear points, so the result has no redundant vertices — try the collinear points preset. Using < 0 instead keeps them, which some applications require. The secondary sort key (distance) matters for the points sharing the smallest angle: without it, ties can make the scan discard a genuine hull vertex.

What to try in the animation

12 points or fewer keeps the scan readable. Interior points get popped — watch the hull shrink before it grows.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• mixed cloud — 1,1 3,9 8,2 9,7 5,5 2,6 7,4 4,2 6,8 2,3 8,9 5,1
• square + interior — 0,0 9,0 9,9 0,9 4,4 5,5 3,6 6,3
• all on the hull — 0,0 5,1 9,4 8,8 4,9 1,5
• collinear points — 0,0 2,0 4,0 6,0 3,5 6,5 0,5

Open Convex hull (Graham scan) in the player →