Convex Hulls by Monotone Chain

The convex hull of a finite point set is the smallest convex polygon containing every point. Its vertices are input points, and they appear in angular order around the set. Computing them looks like a search over an exponential number of candidate polygons, but it is a sorting problem in disguise. Order the points lexicographically by x and then by y, scan once with a stack to trace the lower boundary, scan again in reverse to trace the upper boundary, and the hull is complete. Everything costs O(n log n), and essentially all of that cost is in the sort.

The algorithm is usually attributed to Andrew, published in 1979 as a simplification of Graham’s earlier scan, which had sorted by angle around an interior point and required care when points shared an angle. Sorting by coordinates removes that difficulty: the order is total, it is cheap to compute, and it does not depend on any point being strictly inside the set.

The orientation test that drives everything

Both scans rest on one predicate. For three points o, a, b, the sign of

cross(o, a, b) = (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

says whether the path o → a → b turns left, turns right, or does neither. A positive value means a counterclockwise turn, a negative value a clockwise turn, and zero means the three points are collinear. The magnitude equals twice the signed area of the triangle, which is the only reason it is useful: the sign is a discrete fact about the geometry, and discrete facts survive rounding far better than coordinates do.

The predicate is the same one used to test whether two segments cross in segment intersection with orientation tests, and it fails in the same way. When the three points are nearly collinear, the two products in the difference are nearly equal, and subtracting them cancels most of the significant bits. A double holds 53 bits of mantissa, so a result that should be a small nonzero integer can round to zero, and a result that should be zero can round to a small nonzero value. The consequences are discussed in exact geometric predicates; for the hull, one wrong sign is enough to leave a vertex out of the output.

One scan builds the lower chain

Take the sorted points and walk left to right, maintaining a stack of points that are known to lie on the lower hull so far. The invariant is that the last three points on the stack make a left turn. When a new point arrives and the invariant breaks, the middle point cannot be on the hull: it lies above or on the segment joining its neighbours, and every future point is to the right, so nothing later can rescue it. Pop it and retest. The new point is pushed only when the stack is consistent again.

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

def lower_hull(points):
    stack = []
    for p in points:                       # points sorted lexicographically
        while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()                    # last point is not on the hull
        stack.append(p)
    return stack

Each point is pushed once and popped at most once, so the scan is linear in the number of points. The pop condition <= 0 rather than < 0 is a decision about collinear points, not about correctness of the turn test, and it is the single most consequential line in the function.

Closing the polygon with the upper chain

Running the same loop over the reversed sorted order produces the upper chain, from the rightmost point back to the leftmost. The two chains share their endpoints, the leftmost and rightmost points of the set, so concatenating them requires dropping the last point of each chain to avoid duplicates. The result is the hull in counterclockwise order.

An equivalent formulation runs both chains in one pass over the sorted array and appends to a single stack, but the two-pass version is easier to reason about and easier to debug, and the constant factor difference is small compared with the sort. Memory is O(n): one sorted copy of the input plus a stack that never exceeds n entries.

The collinearity decision

With <= 0, a point that lies exactly on the segment between its neighbours is popped. The output contains only extreme points, the corners of the hull, and an input where every point is collinear yields exactly two points: the two extremes. With < 0, collinear points are kept, and the same input yields every point, in order, as a degenerate polygon of zero area.

Neither choice is wrong; they answer different questions. Minimal vertex sets are wanted for bounding polygons and for algorithms that assume no three vertices are collinear. Maximal sets are wanted when the output feeds a routine that expects to see all boundary points, such as some polygon rasterisers. The failure to decide is what causes trouble: mixing a hull built with <= 0 into code that assumes collinear vertices were retained produces missing points that are hard to attribute, because the hull itself looks correct.

Duplicate input points need a separate guard. Sorting does not remove them, and two identical points make the cross product zero for every third point, which the pop rule then treats as collinear. Deduplicating after the sort, or skipping a point equal to the stack top, keeps the output well formed.

Where the cost goes and what the alternatives pay

The sort is O(n log n) and the two scans are O(n), so the total is O(n log n) time and O(n) space. That is optimal for this problem in the algebraic decision-tree model, by reduction from sorting: map each number x to the point (x, x²) on a parabola, and the hull of the resulting points lists them in x-order, so a hull algorithm would sort. Any hull algorithm therefore inherits the Ω(n log n) lower bound for sorting.

Gift wrapping, the alternative that walks from vertex to vertex choosing the most clockwise next point, costs O(nh) for h hull vertices. When the points are spread through the plane and h is small, it beats sorting, and it needs no extra memory. When the points lie on a circle, h equals n and the cost is quadratic. The monotone chain does not care how many vertices the hull has; it pays the same O(n log n) either way. The two are compared by the size of the hull: gift wrapping wins once h falls below about log n, and the chain wins for everything else. Uniformly random points in a convex region are the awkward case for that rule, because their hull has only O(log n) vertices, so the two algorithms are comparable there and the chain’s extra sort is not obviously worth paying for.

The hull is also the object that separating axes and support functions consume. A convex polygon’s support function in a direction is found by a linear scan, or by binary search over the vertices in angular order, and the hull is exactly the representation that makes the second option available. Computing a hull once and then answering many directional queries against it is a common shape in collision code, where the same body is tested against many others.

Failure modes beyond rounding

Presorted input is not a problem for the chain, but it is worth noting that the algorithm’s output order depends on the sort being total. Sorting by x alone, with an unstable comparison, lets points with equal x appear in arbitrary order, and the lower and upper chains can then disagree about which of them is an endpoint. Sorting by the pair (x, y) removes the ambiguity.

The other edge case is an input of one or two points. The stack logic handles them without special cases if the loop condition checks len(stack) >= 2 first, but the concatenation of the two chains does not: with a single point each chain holds that point alone, and dropping the last element of each leaves nothing. Code that assumes the two chains contribute distinct interior vertices fails only on degenerate inputs, which is why the failure is found late.

Memory layout is where implementations diverge. The stack can hold indices into the sorted point array rather than copies of points, which avoids copying and keeps the original order intact for callers that need it. With coordinates and indices both 32-bit, the scratch space for a million points is a few megabytes, and the sorted copy dominates. An in-place variant that sorts the caller’s array avoids that copy at the cost of mutating the input, the usual trade between an API that is easy to reason about and one that fits into a tight loop.

A structural note on generalisation: the two-chain formulation does not extend to three dimensions, where the hull’s boundary is a triangulated surface and the stack invariant has no direct analogue. The planar algorithm’s value is that it is small enough to reimplement from memory and fast enough that a library dependency is rarely justified; code that needs the 3D case takes a full hull library and gets the planar case along with it.

Nearly collinear runs of points are the practical hazard. A chain of points sampled along a slightly curved boundary can produce cross products whose true values are smaller than the rounding error of the two products being subtracted, so the sign is decided by noise rather than by geometry. The hull then depends on the rounding, and two runs on the same data with different summation orders can disagree. Exact arithmetic for the predicate, or a consistent filtered evaluation, is the only fix that does not merely move the threshold.