cf.completefrontend
MATH & GEOMETRY · ADVANCED

Convex hull

Find the smallest convex outline around a set of points, as if stretching a rubber band around pins on a board.

Time O(n log n)Space O(n)2 practice problemsStep-through picture

The idea

Given some points, the convex hull is the outline you'd get by stretching a rubber band around all of them and letting it snap tight. Points on the band are hull corners; points inside don't matter. "Convex" means the outline never dents inward.

The tool that makes this work is the cross product of three points o, a, b: (a.x - o.x) × (b.y - o.y) - (a.y - o.y) × (b.x - o.x). Its sign says which way you turn when walking from o to a to b. Positive is a left turn (counterclockwise), negative is a right turn, and zero means the three points are on one line.

Andrew's monotone chain method sorts the points by x (then y) and builds the bottom half of the outline from left to right, then the top half from right to left. While adding a point, it removes earlier points that would make the outline turn the wrong way. Joining the halves gives the hull in counterclockwise order.

An everyday example

A rubber band around pins

Push pins into a board and stretch a rubber band around all of them. When you let go, it snaps onto the outer pins and skips the inner ones. Building the hull is like laying the band pin by pin from left to right: whenever the newest pin shows that the last band corner was dented inward, you lift the band off that corner.

How the example maps to the code
In the exampleIn the code
The pins on the boardpoints
Laying the band from left to rightthe loop that builds lower
Noticing a corner dents inwardcross(...) <= 0
Lifting the band off that cornerlower.pop()
The finished bandlower.concat(upper)

From the slow way to convex hull

  1. Start with the obvious way: a pair of points forms an edge of the hull when every other point lies on the same side of the line through them. Try every pair and check every other point. That's n² pairs times n checks, O(n³): for 1,000 points, about a billion side checks.
  2. Each side check is cheap thanks to the cross product. cross(o, a, b) is positive when the walk o, then a, then b turns left, negative when it turns right, and 0 when the three points are on one line. So the real question is how to make fewer of them.
  3. Sort the points by x. Walking along the bottom of the outline from left to right, a convex shape only ever turns left. So keep the bottom outline as a stack. When a new point arrives and the last two points plus the new one make a right turn or go straight, the last point is a dent: it's inside the shape, so pop it. Keep popping until the turn is left again, then push the new point.
  4. Do the same from right to left for the top half. The two halves meet at the leftmost and rightmost points, so drop each half's last point before joining them. Sorting plus two stack passes is Andrew's monotone chain, a convex hull method.

How it works

  1. Sort the points by x, and by y when x is equal.
  2. Build lower: for each point p left to right, while the last two points in lower and p don't make a left turn (cross <= 0), pop the last point. Then push p.
  3. Build upper the same way, going through the points from right to left.
  4. Each half ends where the other begins, so remove the last point of each.
  5. Join them: lower.concat(upper) is the hull in counterclockwise order, starting at the leftmost point.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function cross(o, a, b) {
  2. return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
  3. }
  5. function convexHull(points) {
  6. const sorted = [...points].sort((p, q) => p[0] - q[0] || p[1] - q[1]);
  7. if (sorted.length <= 2) return sorted;
  8. const lower = [];
  9. for (const p of sorted) {
  10. while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0) {
  11. lower.pop();
  12. }
  13. lower.push(p);
  14. }
  15. const upper = [];
  16. for (let i = sorted.length - 1; i >= 0; i--) {
  17. const p = sorted[i];
  18. while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p) <= 0) {
  19. upper.pop();
  20. }
  21. upper.push(p);
  22. }
  23. lower.pop();
  24. upper.pop();
  25. return lower.concat(upper);
  26. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting is O(n log n). After that, every point is pushed and popped at most once per half, which is O(n). The halves together hold at most n + 1 points.

  • Best caseO(n)

    The points already arrive sorted by x then y. JavaScript engines sort an already-sorted array in about n comparisons, and the stack passes are always O(n).

  • Average caseO(n log n)

    Points in random order: sorting costs O(n log n) and dominates the two O(n) stack passes.

  • Worst caseO(n log n)

    Still the sort. Even when every point is on the hull, like points around a circle, nothing is popped and the passes stay O(n).

Common mistakes

  • Sorting only by x. Points with the same x end up in random order, which can break the hull.
  • Using < 0 when duplicates are possible. Equal points have a cross product of 0 and can stay in the hull twice.
  • Forgetting to drop the last point of each half, so the first and last points repeat.
  • Flipping the sign of the turn test because screen y grows downward. The math is the same; only the meaning of clockwise flips when you draw it.

When to use it

Look for these clues in a problem:

  • The question asks for the outline, boundary, or fence around a set of points.
  • You need the farthest pair of points, the smallest enclosing shape, or whether a polygon is convex.
  • Points are given as [x, y] pairs and the answer involves turns, orientation, or perimeter.
  • A brute-force check of every triangle of points would be far too slow.

Check yourself

Answer each one in your head first, then open it.

What does cross([0, 4], [1, 1], [3, 3]) = 8 tell you?

That walking from (0,4) to (1,1) and then to (3,3) turns left. On the bottom half that's allowed, so (1,1) stays on the stack.

Why is (3, 3) not on the hull?

When (4,0) arrived, (1,1), (3,3), (4,0) made a right turn (cross -8), so (3,3) was a dent and was popped. It is inside the outline.

What goes wrong if the points are sorted only by x, for [[0,4], [0,0], [3,1], [3,5], [3,2]]?

Points with the same x keep their input order, so the passes see them in the wrong order. It returns (0,4) (0,0) (3,1) (3,2), missing the corner (3,5) and including (3,2), which is not a corner. Breaking ties by y gives the right hull.

Why must each half drop its last point before joining?

The bottom half ends at the rightmost point, where the top half starts, and the top half ends at the leftmost point, where the bottom half starts. Without the pops, those two corners would appear twice.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The bottom pass keeps one rule: after handling the first few sorted points, lower is the bottom outline of just those points, so every three neighboring points on it turn left. With zero, one, or two points there's nothing to check, so the rule starts out true.

Each new point p keeps the rule. Since the points are sorted, p is the rightmost point so far, so it must be on the outline: it's pushed. If the last point c on the stack, after b, makes cross(b, c, p) <= 0, then c lies on or above the straight line from b to p, so it is inside the outline or on a straight edge, and popping it loses no corner. Popping repeats until the turn is left, which restores the rule. A popped point can never come back, because every later point is even further right.

Each point is pushed once and popped at most once per half, so both passes together take O(n) steps after the sort. The top pass is the same reasoning walking right to left. The bottom half ends at the rightmost point and the top half ends at the leftmost point, each of which already starts the other half, so dropping one point from each leaves every corner exactly once, in counterclockwise order.

Going deeper

3 more ideas

What the cross product tells you

cross(o, a, b) is positive when b is to the left of the line from o to a, negative when it's to the right, and zero when all three are on one line. For o = [0, 0], a = [2, 0], b = [2, 1]: (2 - 0) × (1 - 0) - (0 - 0) × (2 - 0) = 2, a left turn, which matches walking east and then turning north.

Why popping keeps the outline convex

Walking along the bottom half from left to right, a convex outline only turns left. If adding p makes a right turn or goes straight at the last corner, that corner lies above the line from the corner before it to p, so it is inside the final hull. Removing it can't lose a hull corner, and repeating until the turn is left again restores the rule.

The cost and collinear points

Sorting takes O(n log n). Each point is pushed once and popped at most once per half, so building the halves is O(n). Using <= 0 removes points that sit in the middle of a straight edge. Use < 0 instead if the problem wants those points kept, but take care with duplicates.

Work it by hand

Every step in a table, with why

Find the hull of 6 points. Each half pops points, and one point, (3, 3), ends up inside.

points = [[6, 2], [1, 1], [3, 3], [4, 6], [0, 4], [4, 0]]

StepHalfpPopped (cross)Stack afterWhat happensWhy
1sort---sort by x, then ysorted is (0,4) (1,1) (3,3) (4,0) (4,6) (6,2). (4,0) comes before (4,6) because their x ties and 0 < 6.
2lower(0,4)-(0,4)pushFewer than two points on the stack, so there is no turn to check.
3lower(1,1)-(0,4) (1,1)pushStill only one point before it, so push.
4lower(3,3)-(0,4) (1,1) (3,3)cross is 8: left turnGoing down to (1,1) and then up to (3,3) turns left, so (1,1) stays.
5lower(4,0)(3,3) (-8)(0,4) (1,1) (4,0)pop, then push(1,1), (3,3), (4,0) turns right, so (3,3) is a dent and is popped. Then (0,4), (1,1), (4,0) turns left (8), so stop.
6lower(4,6)-(0,4) (1,1) (4,0) (4,6)cross is 18: pushStraight up from (4,0) to (4,6) is a left turn, so it's pushed for now.
7lower(6,2)(4,6) (-12)(0,4) (1,1) (4,0) (6,2)pop, then push(4,0), (4,6), (6,2) turns right, so (4,6) doesn't belong on the bottom half.
8upper(6,2)-(6,2)pushThe top half starts from the rightmost point and walks left.
9upper(4,6)-(6,2) (4,6)pushOne point before it, so push.
10upper(4,0)-(6,2) (4,6) (4,0)cross is 12: pushWalking left, a left turn is still the rule, and this is one.
11upper(3,3)(4,0) (-6)(6,2) (4,6) (3,3)pop, then push(4,0) is part of the bottom half, not the top, so it gets popped here.
12upper(1,1)(3,3) (-4)(6,2) (4,6) (1,1)pop, then push(3,3) is popped again: it's inside the hull.
13upper(0,4)(1,1) (-14)(6,2) (4,6) (0,4)pop, then push(1,1) belongs to the bottom half, so the top half drops it.
14join-last of each(0,4) (1,1) (4,0) (6,2) (4,6)pop both, concatlower ends with (6,2), where upper starts, and upper ends with (0,4), where lower starts. Dropping each half's last point removes those repeats.

The hull is (0,4) (1,1) (4,0) (6,2) (4,6), five corners in counterclockwise order starting at the leftmost point. (3,3) was pushed and popped in both halves, because it is inside the outline.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Convex hullO(n log n)O(n)The default: short, handles ties when sorted by x then y, and gives corners in order.
Check every pair of pointsO(n³)O(n)Only for a handful of points, or to check a faster version in tests.
Gift wrappingO(n · h)O(n)The hull is known to have very few corners h, such as a cloud of points inside a triangle.
Graham scanO(n log n)O(n)Same speed; pick it if your code already sorts points by angle around a pivot.

Extra memory: O(n): the sorted copy of the points, plus lower and upper, which hold at most n points each.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Convex hull and the other approaches, on a scale where each line up is 10 times more steps.
  • Convex hull, Graham scan O(n log n)
  • Check every pair of points O(n³)
  • Gift wrapping O(n · h)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Convex hull339,96620 million
Check every pair of points1,0001 billionmore than a quadrillion
Gift wrapping1001 million1 trillion
Graham scan339,96620 million

Inputs that need care

5 tricky inputs
Fewer than 3 points: [] or [[5, 5]]
sorted.length <= 2, so the sorted points are returned as they are: [] and [[5, 5]]. Two points give a segment, not a shape.
All points on one line: [[0, 0], [1, 1], [3, 3]]
Every cross product is 0, so the middle point is popped from both halves and it returns [[0, 0], [3, 3]], the two ends. Callers should be ready for a hull with only two points.
A point in the middle of an edge: [[0,0], [2,0], [4,0], [4,4], [0,4]]
With <= 0, (2,0) makes a straight line and is popped, giving the 4 corners of the square. With < 0, it's kept, giving 5 points.
Repeated points: [[2, 2], [2, 2], [2, 2]]
It returns [[2, 2], [2, 2]]: the same point twice. With < 0 and more copies, the result can repeat points even more. Remove duplicates before building the hull.
Screen coordinates, where y grows downward
The math doesn't change, but the picture is flipped vertically, so "counterclockwise" in math looks clockwise on screen. Don't flip the sign of the cross product to fix it.

Variations and follow-ups

Twists interviewers add

Keep points on straight edges

Change both tests to < 0, so points exactly on an edge are kept. Remove duplicates first; otherwise repeated points are also kept, because their cross product is 0.

Graham scan

Start from the lowest point and sort the others by the angle they make with it, then run one stack pass with the same left-turn rule. It's also O(n log n), but sorting by angle needs care with ties and collinear points.

Gift wrapping

Start at the leftmost point and repeatedly pick the point that makes every other point lie to the left, like wrapping a ribbon. It takes O(n × h), where h is the number of hull corners, which beats sorting when the hull has only a few corners.

What the hull is used for

Lasso selection draws the hull of the chosen points. The two points farthest apart are always hull corners, so "rotating calipers" find them by walking the hull once. Collision checks often test hulls before exact shapes.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "fence around all the trees", "smallest convex polygon containing the points", "outline of a set of points", or "the two points farthest apart".
  • Explain it as: "Sort by x. Build the bottom half with a stack, popping any point that makes a right turn, using the cross product. Do the top half backwards, then join them." Mention that it's a monotonic stack.
  • Test fewer than three points, all points on a line, repeated points, and a square with one point inside. Most bugs show up as a missing corner or a repeated point.
  • Expect "what if points on the edges must be included?". Change <= 0 to < 0 and remove duplicates first, and explain why duplicates then become a problem.

Where frontend code uses it

The same idea in real UI code
  • d3's d3.polygonHull (in d3-polygon) computes the convex hull of points, for example to draw a shape around a cluster in a scatter plot.
  • Map clustering plugins such as Leaflet.markercluster can show the outline of the area a cluster covers when you hover it, which is a hull of the markers' positions.
  • Design and whiteboard tools use hulls to draw a tight outline around a group of selected shapes or a freehand lasso.

Related algorithms