Convex Hull (Graham Scan)

The convex hull

The convex hull of a set of points is the smallest convex polygon that contains all of them. Picture nails in a board and a rubber band snapped around them: the band touches only the outermost nails. Convex hulls are used in collision detection for games and robots, in image processing (the outline of a shape), in geographic data and as a building block for many other geometry algorithms.

The one tool: the cross product

For points o, a and b,

cross(o, a, b) = (a.x − o.x)(b.y − o.y) − (a.y − o.y)(b.x − o.x)

Sign	o → a → b
> 0	turns left (counter-clockwise)
< 0	turns right (clockwise)
= 0	goes straight (the three points are collinear)

It uses only multiplication and subtraction, so with integer coordinates it is exact, with no trigonometry and no rounding.

Graham scan

pivot ← the lowest point (leftmost if tied)
sort the other points by angle around the pivot (nearer first if the angle is equal)
stack ← [pivot]
for each point p in that order:
    while the stack has ≥ 2 points and (second-to-top, top, p) is NOT a left turn:
        pop the top
    push p
the stack is the hull, counter-clockwise

Walking around a convex polygon counter-clockwise you only ever turn left. So whenever adding p would create a right turn, the point on top of the stack is a dent: it lies inside the triangle formed by its neighbours and the pivot, and cannot be a corner.

The default points

Pivot P = (4, 0), the lowest point. Sorted by angle:

(9, 1), (7, 2), (10, 7), (8, 5), (5, 3), (6, 6), (5, 9), (3, 5), (2, 8), (0, 4), (1, 1)

(5, 3) and (6, 6) lie on the same ray from P, so the nearer one, (5, 3), comes first.

New point	Pops	Why
(10, 7)	(7, 2)	(9, 1) → (7, 2) → (10, 7) turns right
(5, 3)	(8, 5)	(10, 7) → (8, 5) → (5, 3) turns right
(6, 6)	(5, 3)	(10, 7) → (5, 3) → (6, 6) turns right
(5, 9)	(6, 6)	(10, 7) → (6, 6) → (5, 9) turns right
(2, 8)	(3, 5)	(5, 9) → (3, 5) → (2, 8) turns right

Result: the hull (4, 0) → (9, 1) → (10, 7) → (5, 9) → (2, 8) → (0, 4) → (1, 1), with 7 corners; 5 points were popped.

Running time

Sorting is O(n log n). In the scan, every point is pushed once and popped at most once, so the while loop runs at most n times in total even though it is nested: O(n) (an example of amortised analysis, as in a monotonic stack). Overall O(n log n), which is optimal for comparison-based algorithms, because sorting can be reduced to finding a convex hull.

Collinear points

With ≤ 0 in the test, points that lie on an edge of the hull (in the middle of a straight side) are dropped, giving only the true corners. Use < 0 if you want to keep them, but then the points on the last ray from the pivot must be sorted in reverse, a classic source of bugs.

Other algorithms

Algorithm	Idea	Time
Graham scan	sort by angle, then scan with a stack	O(n log n)
Andrew’s monotone chain	sort by x, build the lower and upper hull with the same turn test	O(n log n)
Jarvis march (gift wrapping)	from a hull corner, find the point with the smallest turn, repeat	O(n · h)
Quickhull	divide and conquer, like quick sort	O(n log n) average, O(n²) worst
Chan’s algorithm	combines Graham and Jarvis	O(n log h)

Here h is the number of points on the hull. If only a handful of points are on the hull, output-sensitive algorithms like Jarvis march and Chan’s beat O(n log n).

Code

from functools import cmp_to_key

def cross(o, a, b):
    """> 0: o -> a -> b turns left (counter-clockwise); < 0: right; 0: straight."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def graham_scan(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))             # lowest point (leftmost if tied)
    def by_angle(a, b):                                          # smaller angle around the pivot first
        c = cross(pivot, a, b)
        if c:
            return -1 if c > 0 else 1
        da = (a[0] - pivot[0]) ** 2 + (a[1] - pivot[1]) ** 2       # same direction: nearer first
        db = (b[0] - pivot[0]) ** 2 + (b[1] - pivot[1]) ** 2
        return -1 if da < db else 1 if da > db else 0
    rest = sorted((p for p in points if p != pivot), key=cmp_to_key(by_angle))
    stack, pops = [pivot], 0
    for p in rest:
        while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()                                          # right turn (or straight): not on the hull
            pops += 1
        stack.append(p)
    return stack, pops

POINTS = [(1, 1), (4, 0), (7, 2), (9, 1), (8, 5), (10, 7), (6, 6), (3, 5), (5, 9), (2, 8), (0, 4), (5, 3)]
hull, pops = graham_scan(POINTS)
print('hull (counter-clockwise):', hull, '| pops:', pops)
# hull (counter-clockwise): [(4, 0), (9, 1), (10, 7), (5, 9), (2, 8), (0, 4), (1, 1)] | pops: 5

On 500 random sets of integer points, this gives exactly the same corners as scipy.spatial.ConvexHull.

Common mistakes

• Sorting by angle with atan2 and floating point. It works, but ties and rounding cause subtle bugs. The cross-product comparison is exact.
• Popping on left turns. Pop when the turn is to the right (or straight); keep left turns.
• Checking only once. After a pop, the new triple must be checked again: the loop is a while, not an if.
• Choosing an arbitrary first point. The pivot must be extreme (lowest, or leftmost), or the angular sort does not walk around the hull.
• Calling the algorithm O(n²) because of the nested loop. Each point is popped at most once, so the scan is linear.