Convex hull

O(n log n)

The convex hull of a set of points is the smallest convex polygon that encloses them all — imagine stretching a rubber band around a board of nails and letting it snap tight. Andrew's monotone chain finds it efficiently: sort the points left to right, then sweep once building the lower edge and once building the upper edge. At each new point it checks the turn the last two hull points make with it — if that turn isn't a left turn (the cross product is zero or negative, i.e. straight or clockwise), the middle point can't be a corner, so it's popped off. Joining the two chains gives the hull. The sort dominates, so it runs in O(n log n). Convex hulls underlie collision detection, shape analysis, and as a first step in many other geometry algorithms. Click the plane to drop your own points.

Click the plane to add a point
Points
Edit the input and press Play

How it works

  1. Sort the points from left to right (ties broken by y).
  2. Sweep left to right, building the lower edge.
  3. Pop any point where the last three make a right turn (it can't be a corner).
  4. Sweep back right to left for the upper edge; the two chains joined are the hull.

Pseudocode

1convexHull(points):                 # O(n log n)2  sort points by x, then y3  lower = []                          # build the bottom edge4  for p in points (left → right):5    while last two + p turn right (or straight): pop6    lower.push(p)7  upper = []  (same sweep, right → left)8  hull = lower (drop last) + upper (drop last)