Convex Hull (Graham Scan)

The convex hull of a set of points is the smallest convex polygon that contains them all — picture stretching a rubber band around every point and letting it snap tight. The points it touches are the hull; everything else sits inside. Graham scan computes it in O(n log n) by sorting the points by angle and then sweeping them onto a stack, throwing away any point that bends the wrong way.

The turn direction comes from the cross product. For three points o, a, b, the sign of cross(o, a, b) tells you whether the path o -> a -> b turns left (counter-clockwise, positive), turns right (clockwise, negative), or goes straight (zero). Graham scan keeps only left turns.

Intuition

Imagine you are walking the boundary of the point cloud counter-clockwise, always hugging the outside. Each time you reach a new point you ask: "did I just turn left or right?" A left turn means you are still wrapping around the outside, so the previous point was a legitimate corner — keep it. A right turn means the previous point was a dent pointing inward, so back up and erase it before moving on.

Sorting by polar angle is what makes this single pass work: it guarantees you meet the points in the order you would sweep a ray counter-clockwise around the anchor, so the only correction you ever need is popping the occasional inward dent off the stack.

Walk through it

Step through the animation on the right. First we pick the lowest point, P0 — the one with the largest screen-y, sitting at the bottom. It is guaranteed to be a hull vertex, so it anchors the scan and turns green.

Next we sort the other six by polar angle around P0; the labels #1..#6 show the visiting order. Then we sweep through them, pushing each onto the stack (its contents are shown on the right) and drawing a hull edge to it. Watch what happens at point #5 (P4): the top of the stack is P6, and the turn P3 -> P6 -> P4 is clockwise, so the cross product is <= 0. P6 caves inward, so we pop it — its node dims and its edge disappears — and then push P4. When every point has been processed, the points still on the stack are exactly the convex hull, traced counter-clockwise.

The code, line by line

def cross(o, a, b):
    # > 0 left (CCW) turn, < 0 right (CW) turn, 0 collinear
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
 
def convex_hull(points):
    # 1) pivot = lowest point, then sort the rest by polar angle
    pivot = min(points, key=lambda p: (p[1], p[0]))
    rest = sorted(p for p in points if p != pivot,
                  key=lambda p: angle(pivot, p))
    hull = [pivot]
    for p in rest:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

• cross(o, a, b) returns a signed area; its sign is the turn direction. Positive is a left (counter-clockwise) turn, negative is a right (clockwise) turn, zero means the three points are collinear.
• Line 7 picks the pivot: min by (y, x) finds the lowest point, breaking ties with the leftmost. This point is always a hull vertex.
• Lines 8-9 sort the rest by polar angle around the pivot, so we visit them in counter-clockwise sweep order.
• Line 12 is the heart: while the top two stack points plus p make a clockwise or collinear turn (cross <= 0), the top point is interior — keep popping.
• Line 13 pops that interior point off the hull. The while can pop several points in a row before the turn finally goes left.
• Line 14 pushes p; it is now the freshest hull candidate. After the loop, hull holds the convex hull in counter-clockwise order.

Complexity

The scan itself is linear — every point enters the stack exactly once and leaves at most once, so the total push/pop work is bounded by 2n. The O(n log n) sort is therefore the bottleneck, making Graham scan optimal for comparison-based hull construction.

When to use / pitfalls

Practice