Stretch a rubber band around a set of nails hammered into a board and let it snap tight: the shape it takes is the convex hull. It is the smallest convex polygon that contains every point, and its corners are always input points. It is the first step in diameter queries, collision tests, small linear programs and outlier screening.
This article builds the hull from first principles. We start with the one geometric test every hull algorithm depends on, write Andrew's monotone chain line by line, trace it on the eleven points in the figure, compare the alternatives, make it robust against collinear points, duplicates and floating-point error, and use the hull for area, diameter and containment.
A set is convex if the segment between any two of its points stays inside it. The convex hull of a finite point set S is the intersection of all convex sets containing S; for points in the plane it is a convex polygon, and the standard output is its vertices in counter-clockwise order. Points in the middle of an edge are usually excluded; we will make that a deliberate choice later.
How fast can it be done? Sorting reduces to the hull problem: map each number x to the point (x, x squared). All of these lie on a parabola, so every one is a hull vertex, and the counter-clockwise order of the hull lists them in sorted order. Any hull algorithm therefore gives a sorting algorithm, and in the algebraic decision-tree model that means Omega(n log n) comparisons in the worst case. The algorithms below that sort first and then do linear work are optimal in that sense. With h hull vertices the sharper bound is Omega(n log h), due to Kirkpatrick and Seidel, and output-sensitive algorithms meet it; since random points in a square have an expected hull size of only O(log n), the distinction is practical.
Every hull algorithm reduces to one question asked over and over: walking from point o to point a, is point b to the left, to the right, or straight ahead? The answer is the sign of a 2x2 determinant, the z-component of the cross product of the vectors o-to-a and o-to-b:
def cross(o, a, b):
"""> 0: o->a->b turns left (counter-clockwise); < 0: right; == 0: collinear."""
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])The magnitude is twice the signed area of triangle o, a, b, which is why the same function later computes polygon area; the hull needs only the sign. The test uses no angles, division or square roots, so it is faster and more exact than sorting by atan2, and everything that goes wrong numerically goes wrong inside this one function, which leaves exactly one place to make robust.
Andrew's monotone chain (1979) is the algorithm to reach for by default. Sort the points by x, breaking ties by y. The leftmost and rightmost points are certainly on the hull and split it into a lower chain and an upper chain. Build the lower chain by sweeping left to right with a stack: before pushing each new point, pop the top while the last two stack points and the new point fail to make a strict left turn. Build the upper chain the same way sweeping right to left. Concatenate, dropping the duplicated endpoints.
def convex_hull(points):
"""Counter-clockwise hull vertices, starting at the lowest-leftmost point.
Collinear boundary points are excluded; duplicates are removed."""
pts = sorted(set(points)) # O(n log n); set() removes duplicates
if len(pts) <= 2:
return pts # 0, 1 or 2 distinct points are their own hull
lower = []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop() # last point is not a strict left turn: discard
lower.append(p)
upper = []
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1] # each chain's last point starts the otherThe sweep is linear after sorting: each point is pushed once per chain and popped at most once, so the loops do O(n) total work and the sort dominates at O(n log n). Why is popping safe? If the last two stack points and the new point fail to turn left, the middle point lies inside or on the boundary of the region spanned so far, so it cannot be a hull corner, and later points, being further right, cannot resurrect it.
Two behaviours are worth stating precisely because they are design decisions. The comparison <= 0 pops collinear points, so a point in the middle of an edge is dropped; change it to < 0 to keep them, but then you must handle the all-collinear input specially, or the upper chain walks back over the lower one. And if every input point is collinear the function above returns just the two endpoints, which is the correct degenerate hull and something callers must be ready for.
Take the figure's points plus a duplicate (4,0), which set() removes. The eleven distinct points sorted by x then y are (-1,3), (0,0), (1,4), (2,0), (2,2), (2,6), (3,3), (4,0), (4,2), (5,5), (6,2). The lower sweep runs like this:
The upper sweep from (6,2) back to (-1,3) keeps (6,2), (5,5), (2,6), (-1,3). Dropping each chain's last point and concatenating gives the hull (-1,3), (0,0), (4,0), (6,2), (5,5), (2,6): six of eleven points, counter-clockwise. Running the listing on these points produces exactly this output, which is what the figure draws.
Monotone chain is the right default, but the other classic algorithms are worth knowing because each wins in a specific regime:
| Algorithm | Time | Wins when | Watch out for |
|---|---|---|---|
| Graham scan (1972) | O(n log n) | teaching; historical code | angle sort and tie-breaking around the pivot |
| Andrew's monotone chain (1979) | O(n log n) | default choice in 2D | collinear policy, all-collinear input |
| Jarvis march (gift wrapping) | O(nh) | hull is known to be tiny, e.g. h under 10 | quadratic when most points are on the hull |
| Quickhull | expected O(n log n), worst O(n squared) | random data; generalises to 3D and beyond | adversarial or circular inputs |
| Chan's algorithm (1996) | O(n log h) | large n with small h, when optimality matters | constant factors; rarely faster in practice |
| Akl-Toussaint filter | O(n) pre-pass | in front of any of the above on big data | only a heuristic; worst case unchanged |
Jarvis march wraps around one hull vertex per O(n) scan. Quickhull is divide and conquer: split by the line through the extreme points, find the farthest point from that line, discard everything inside the triangle, and recurse on the two outside sets; it is what Qhull, and therefore SciPy's ConvexHull, builds on. Chan's algorithm combines small monotone-chain hulls with gift wrapping, guessing h and squaring the guess until it succeeds. The most valuable trick is the cheapest: the Akl-Toussaint filter discards every point strictly inside the quadrilateral of the four extreme points, which on uniform data removes most points in one linear pass before any sorting.
The algorithm is correct; the arithmetic often is not. With floating-point coordinates the cross product of nearly collinear points can come out with the wrong sign, because the two products being subtracted are large and almost equal. A wrong sign can produce a non-convex or self-intersecting polygon, or drop an extreme point. Choose one of these strategies explicitly:
Deduplicate up front, as the listing does, and reject NaN or infinite coordinates at the boundary, since they poison the sort itself.
Once the hull is computed, several useful quantities fall out cheaply. Area is the shoelace formula, which is the sum of cross products around the polygon; for the example it gives 60, so the area is 30. The diameter, the largest distance between any two points of the set, is always realised by two hull vertices, so you never need the O(n squared) all-pairs scan. Rotating calipers, introduced by Shamos, finds it in O(h) by walking two antipodal pointers around the hull:
def area2(hull):
"""Twice the polygon area; positive for counter-clockwise order."""
return sum(cross((0, 0), hull[i], hull[(i + 1) % len(hull)]) for i in range(len(hull)))
def diameter_sq(hull):
"""Squared diameter via rotating calipers. hull is CCW without repeats."""
n = len(hull)
if n < 2:
return 0
if n == 2:
return dist_sq(hull[0], hull[1])
best, j = 0, 1
for i in range(n):
a, b = hull[i], hull[(i + 1) % n]
# advance j while it moves farther from edge a->b (area of triangle grows)
while abs(cross(a, b, hull[(j + 1) % n])) > abs(cross(a, b, hull[j])):
j = (j + 1) % n
best = max(best, dist_sq(a, hull[j]), dist_sq(b, hull[j]))
return best
def dist_sq(p, q):
return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2On the example the squared diameter is 50, realised by both (0,0)-(5,5) and (-1,3)-(6,2), a tie worth keeping in a test because it catches off-by-one pointer bugs. The same walk gives the width and the minimum-area enclosing rectangle. Point containment is O(log h): binary-search the fan of triangles from vertex 0 for the wedge containing the query, then do one orientation test against its outer edge, which pays off when the same hull is queried many times, as in collision broad-phase and geofencing.
Physics engines precompute hulls because separating-axis and GJK collision tests only work on convex shapes; GIS systems use hulls as cheap rejection tests, and Shapely exposes geom.convex_hull backed by GEOS. At scale, add the Akl-Toussaint filter; for streams, keep a running hull, since a new point matters only if it lies outside the current one, an O(log h) test. Because the hull of a union is the hull of the parts' hulls, shards can be processed in parallel and merged. In three dimensions use Qhull or CGAL rather than your own code; the degeneracies multiply.
Most hull bugs fall into a handful of patterns, and each has a matching test:
area2(hull) > 0 for non-degenerate output.On trade-offs: output-sensitive algorithms pay off only when h is tiny and sorting is the bottleneck, and exact arithmetic costs a constant factor where a non-convex result costs a bug report. A property-based test that compares your hull against a brute-force O(n cubed) reference on random small inputs, including deliberately collinear and duplicated points, catches nearly everything in this list. For the cost model behind these comparisons see Big-O analysis; for the sorting step, merge sort; and for the divide-and-conquer structure Quickhull and parallel merging share, divide and conquer.
cross and the monotone chain listing, and reproduce the eleven-point example exactly: six vertices, doubled area 60, squared diameter 50.