Convex Hull — The Atlas of Algorithms

What you're seeing

Imagine stretching a rubber band around a scatter of pins and letting go: it snaps to the outermost points and ignores everything inside. That taut loop is the convex hull. The algorithm here, Andrew's monotone chain, first sorts the points left to right, then sweeps across building the lower boundary, and sweeps back building the upper boundary. Each time a new point would make the boundary bend inward (a right turn), it pops the offending vertex back off — you can watch the chain retract and re-extend as it keeps itself convex.

The rule

monotone_chain(points):
    sort points by (x, then y)
    build lower hull, left → right:
        for each point p:
            while last two hull points + p turn right (or straight):
                pop the last hull point
            push p
    build upper hull, right → left:  (same rule)
    hull = lower chain + upper chain

The turn test is one cross product: cross(O,A,B) = (A−O)×(B−O). Positive means a left turn (keep), ≤ 0 means right or straight (pop).

The invariant

The chain under construction is kept so that every consecutive triple of its vertices makes a left turn — i.e. it is always convex. The while loop enforces it: before pushing a new point, any vertex that would create a non-left turn is removed, and since removing a vertex can only expose an earlier turn that might now also be wrong, the loop repeats until convexity is restored. Two consequences make the final answer correct. Convex: by the invariant, the completed loop turns the same way the whole way around. Encloses everything: the lower chain is the lower boundary of all points (nothing sorted-in-between dips below it) and the upper chain the upper boundary, so every point sits between them — inside or on the hull. Sorting plus a monotone left-turn sweep is all it takes; this entry's test checks both properties and cross-checks the vertex set against an independent gift-wrapping algorithm.

The cost

Monotone chainGift wrapping TimeO(n log n)O(n·h) SpaceO(n)O(h)

The sort dominates at O(n log n); the two sweeps are linear, because each point is pushed once and popped at most once across each chain. That beats the simpler gift-wrapping (Jarvis march) at O(n·h) — fine when the hull has few vertices h, but quadratic when most points are extreme. The output-sensitive champion, Chan's algorithm, reaches O(n log h), the best possible.

In the wild

Convex hulls are a workhorse primitive of computational geometry: collision detection and physics engines (hulls are cheap to test for overlap), GIS and the smallest enclosing region of map features, pattern recognition and the shape of a point set, the first step of many Delaunay triangulation / Voronoi constructions, and a building block in linear programming and statistics (e.g. the convex hull of data points). The 3-D generalization (QuickHull) wraps meshes for graphics and CAD. Wherever "the outline of these points" matters, the hull is the answer.

Try this

Step through with ▶| and watch the blue chain occasionally retract — that's the while loop popping a vertex that a new point just made non-convex. Add more points and notice the hull barely grows: most new points fall inside and never join it, which is exactly why the hull is a useful summary of a cloud.

References

Andrew, A. M. "Another efficient algorithm for convex hulls in two dimensions." Information Processing Letters 9(5):216–219, 1979. The monotone chain.
Graham, R. L. "An efficient algorithm for determining the convex hull of a finite planar set." Information Processing Letters 1(4):132–133, 1972 — the Graham scan.
de Berg, Cheong, van Kreveld & Overmars. Computational Geometry: Algorithms and Applications, 3rd ed., Ch. 1. Springer, 2008.
Chan, T. "Optimal output-sensitive convex hull algorithms in two and three dimensions." Discrete & Computational Geometry 16, 1996 — the O(n log h) result.