Graham Scan (Convex Hull)

An angular-sort sweep that computes the convex hull of a planar point set in O(n log n) time.

The convex hull

The convex hull of a set of points is the smallest convex polygon containing them all. Graham scan finds it by first picking the lowest point (ties broken by x) as a pivot, sorting the remaining points by polar angle about the pivot, then walking the sorted list while maintaining a stack of hull vertices.

The turn test

Kronos motion — operating point

As each point is considered, the algorithm checks the orientation of the last two stack points with the new one using the cross product. A right turn (clockwise) means the middle point is not on the hull, so it is popped; this repeats until a left turn is restored, then the new point is pushed. Each point is pushed and popped at most once, so the scan is linear after the sort.

Orientation predicate

python

def cross(o, a, b):
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

# > 0 left turn (ccw), < 0 right turn (cw), == 0 collinear
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
    hull.pop()
hull.append(p)

Numerical care

Use exact integer arithmetic for the cross product when coordinates are integers to avoid orientation errors.
Decide deliberately whether collinear boundary points are kept or dropped.
Sorting by angle can be replaced by sorting by coordinate in the monotone-chain variant, avoiding trigonometry entirely.

Alternatives

Andrew's monotone chain sorts by coordinate instead of angle and is simpler to make numerically robust; it has the same O(n log n) bound. Output-sensitive hulls like Chan's algorithm run in O(n log h) for h hull points.