The idea: a rubber band around nails

Hammer nails into a board at some points, stretch a rubber band around all of them and let go. The band snaps to the convex hull: the smallest convex polygon that holds every point. Its corners are some of the points; the others sit inside and do not matter.

Twelve points A to L; a blue polygon through A, B, C, D, E, F and G wraps them, with H, I, J, K and L inside.
The hull of the page's 12 points has 7 corners; the 5 points inside never touch the band.

The page uses points with whole-number coordinates on a 20 × 16 grid, so every number it shows can be checked by hand. n is the number of points and h the number of hull corners.

The orientation test

Both algorithms ask one question again and again: walking from a to b and then to c, do we turn left or right? The answer is the sign of the cross product of the two vectors b − a and c − a:

cross(a, b, c) = (bx − ax)·(cy − ay) − (by − ay)·(cx − ax)
  • cross > 0: a left turn (counter-clockwise); c is on the left of the line a→b.
  • cross < 0: a right turn (clockwise); c is on the right.
  • cross = 0: a, b and c lie on one line.
Three cases: G to H to K gives cross 16, a left turn; A to I to B gives minus 22, a right turn; K to H to I gives 0, collinear.
The sign of one number decides left, right or straight: no angles, no square roots.

The value is twice the signed area of the triangle a, b, c. It uses only multiplication and subtraction, so with whole numbers it is exact (Demo: the orientation test). The cross product of two vectors is explained in vectors, the dot product and the cross product.

Graham scan

  1. Take the lowest point (the leftmost one on a tie). It must be a corner of the hull. Call it the pivot.
  2. Sort the other points by angle around the pivot, counter-clockwise. Comparing two points p and q is again one test: p comes first if cross(pivot, p, q) > 0.
  3. Go through the points in that order with a stack. Before pushing a point c, look at the top two stack points a and b. If a → b → c is not a left turn, b cannot be a corner: pop it and check again. Then push c.
  4. When all points are done, the stack holds the hull, in counter-clockwise order.
Left: the stack is A B C L and J arrives; C to L to J turns right, so L is popped. Right: B to C to J turns left, so J is pushed onto A B C.
A right turn means the top of the stack is a dent in the band: pop it, then test again.

On the 12 points, the sort takes 26 comparisons and the scan 15 turn tests; L, J, I, H and K are pushed and later popped (Demo: Graham scan on 12 points). Each point is pushed once and popped at most once, so the scan is O(n). The sort is O(n log n), and that is the cost of the whole algorithm.

Gift wrapping (Jarvis march)

Gift wrapping walks around the hull like paper being wrapped around a gift. From a hull point p, it looks for the next corner q: the point with every other point on its left. It takes any point as the first candidate q, then tests each other point r. If r is right of p→q (cross < 0), r becomes the new candidate. After one pass over all points, q is the next corner. Repeat from q until it gets back to the start.

Each round costs n − 2 tests and there are h rounds, so the cost is O(nh). On the 12 points, h = 7: 7 × 10 = 70 tests (Demo: gift wrapping on the same 12 points). It needs no sort and is simple, and it is fast when the hull has few corners.

Collinear points

When three points lie on one line, cross = 0. The page keeps only the corners: Graham scan pops on cross ≤ 0, and on a sort tie the closer point goes first, so a middle point is always popped. Gift wrapping takes the farther point on a tie. On the collinear set, the 12 points give a hull of only 4 corners, A, D, F and I; B, C, E, G, H and J lie on its edges and are dropped (Demo: collinear points). Some programs want the edge points too; they pop only on cross < 0 and must then handle the last ray of the sort with care.

Which is faster?

Point setnhGraham scan (sort + scan)Gift wrapping (h × (n − 2))
12 scattered points12726 + 15 = 417 × 10 = 70
Collinear points12421 + 16 = 374 × 10 = 40
All 10 points on the hull101013 + 8 = 2110 × 8 = 80

Graham scan is O(n log n) whatever the points are. Gift wrapping is O(nh): better when h is smaller than log n, but O(n²) when every point is on the hull, its worst case (Demo: all points on the hull). Chan's algorithm combines the two and runs in O(n log h), which is the best possible.

Where it is used

Convex hulls show up in collision detection (a quick test with the hull before the exact shape), in finding the two farthest points of a set, in image processing, and as a first step in other geometry algorithms. Maps and spatial indexes ask similar "which points are where" questions; see quadtrees and geohashes for "restaurants near me". The angle sort is an ordinary comparison sort, as in comparison sorting.

See also Travelling Salesman Heuristics: in a shortest tour the hull cities appear in hull order, and 2-opt removes every crossing.

The same left-or-right test, run on all three edges of a triangle, decides which pixels a GPU colours: see Rasterization.

What the page leaves out

The page skips floating-point coordinates, where a cross product near 0 can get the wrong sign from rounding and robust programs use exact or adaptive arithmetic. It also leaves out Andrew's monotone chain (sort by x instead of angle), QuickHull, Chan's algorithm, the hull in 3D, and fewer than 3 points or all points on one line.