Convex Hull: Wrapping a Point Set in the Fewest Possible Turns

The smallest bag that fits every point

Given a scatter of points, their convex hull is the smallest convex polygon that contains all of them — imagine stretching a rubber band around the whole point set and letting it snap tight. Every point either sits on the hull's boundary or strictly inside it, and the hull vertices are exactly the points a rubber band would actually touch. It is one of the oldest and most widely used problems in computational geometry, and three genuinely different algorithms solve it, each with a different trade-off.

The one test every hull algorithm needs

All three algorithms lean on the same primitive: given three points a, b and c, which way do you turn at b when walking from a to c? The sign of the 2D cross product answers this in one multiply-and-subtract:

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

cross > 0   →  counter-clockwise (left) turn at b
cross < 0   →  clockwise (right) turn at b
cross == 0  →  a, b, c are collinear

Every hull algorithm below is, structurally, a way of choosing which points to test with this one sign check and in what order — the differences between them are entirely about efficiency, not correctness.

Graham scan: sort once, sweep once

Ronald Graham's 1972 algorithm first picks the point with the lowest y-coordinate (breaking ties by lowest x) as a fixed pivot, then sorts every other point by polar angle around that pivot. It then sweeps through the sorted points once, maintaining a stack of hull candidates and popping the top of the stack whenever adding the next point would create a clockwise (non-left) turn:

pivot = point with lowest y (then lowest x)
points = all other points, sorted by polar angle around pivot
stack = [pivot, points[0]]
for p in points[1:]:
    while cross(stack[-2], stack[-1], p) <= 0:   // not a left turn
        stack.pop()
    stack.push(p)
return stack                                     // the hull, in order

The sort costs O(n log n) and the sweep itself is O(n) — each point is pushed once and popped at most once — so the whole algorithm is O(n log n), dominated entirely by the initial sort, regardless of how many points end up on the final hull.

Jarvis march: gift wrapping, one hull edge at a time

The gift wrapping algorithm (R. A. Jarvis, 1973) works completely differently: starting from the leftmost point, it repeatedly finds the one point such that every other point lies counter-clockwise of the edge from the current point to it — literally wrapping a string around the outside of the set, one hull edge at a time — until it returns to the start.

current = leftmost point
hull = [current]
repeat:
    candidate = any other point
    for each point p:
        if cross(current, candidate, p) < 0:      // p is more clockwise
            candidate = p                          // → candidate becomes p
    hull.push(candidate)
    current = candidate
until current == hull[0]

Finding each next hull vertex costs O(n), and there are h hull vertices to find, so the total cost is O(nh). When the hull has very few vertices relative to n — a common situation for points sampled from inside a shape rather than on its boundary — Jarvis march can beat Graham scan's O(n log n). When h approaches n, it degrades to O(n²) and Graham scan wins comfortably.

Quickhull: divide, conquer, discard

Quickhull (independently developed by several authors, popularised by Barber, Dobkin and Huhdanpaa in 1996) borrows its structure directly from quicksort. Start with the two extreme points (leftmost and rightmost), which are guaranteed to be on the hull, and split the remaining points into the sets left and right of that line. For each side, find the point farthest from the line — it must also be on the hull — and recurse on the two smaller triangular regions this creates, discarding every point that falls inside the triangle formed so far, since a point inside a known hull edge's triangle can never itself be on the hull.

Quickhull's average performance is O(n log n) and its aggressive early discarding of interior points often makes it the fastest of the three in practice on typical, non-adversarial data — but like ordinary quicksort, its worst case (a carefully arranged, adversarial point distribution) degrades to O(n²).

Frequently asked questions

Try it live

Everything above runs in your browser — open Convex Hull and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.