Stretch a rubber band around a scatter of points and let it snap tight — the polygon it forms is the convex hull. Andrew’s monotone chain computes it without any rubber band: sort the points left to right, then sweep once to build the lower boundary and once to build the upper, and at each step throw away any point that would make the boundary turn the wrong way. A single cross product decides every turn. Step through the two sweeps and watch the hull tighten.
O(n log n) time (the sort) · O(n) hull build · the cross product decides every turn
convex hull
The smallest convex polygon that contains every point — the rubber-band boundary.
cross product
cross(O,A,B): positive = left turn, negative = right turn, zero = collinear.
lower / upper chain
Build the bottom boundary left-to-right, then the top boundary right-to-left.
pop
Remove the last hull point whenever adding the new point makes a non-left turn.
hull.js — sort, sweep, pop the wrong turns
Ready
Points sorted left to right. We sweep building the lower chain: add each point, and while the last three make a non-left turn, pop the middle one. Then repeat for the upper chain. Step to advance.
lower
chain
0
hull points
–
last action
How it works
Every decision reduces to the sign of one cross product. For the last two points on the current chain, O and A, and the incoming point B, the value cross(O, A, B) is positive when O→A→B turns left (counter-clockwise) and negative when it turns right. A convex boundary only ever turns one way, so any point that produces the wrong sign can’t be on the hull — pop it. Doing this left-to-right builds the lower boundary; doing it right-to-left builds the upper. Joined, they wrap every point.
1
Sort points left to right
Order all points by x (ties by y). This sorting step is the O(n log n) cost; everything after is linear.
2
Sweep the lower chain
Add points one by one. While the last two hull edges make a non-left turn (cross ≤ 0), pop the middle point — it dents inward and can’t be on the hull.
3
Sweep the upper chain
Repeat right-to-left to build the top boundary with the same pop rule. The lower chain traces the bottom, the upper traces the top.
✓
Join the two chains
Concatenate the lower and upper chains (dropping the shared endpoints) to get the full convex hull — the tightest convex polygon enclosing all the points.
Time
O(n log n)
Hull build
O(n)
Decision
cross product
Output
convex polygon
The code
# Andrew's monotone chain — O(n log n)def convex_hull(pts):
pts = sorted(set(pts)) # by x, then ydef cross(o, a, b):
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
def half(points):
chain = []
for p in points:
while len(chain) >= 2 and cross(chain[-2], chain[-1], p) <= 0:
chain.pop() # non-left turn -> drop it
chain.append(p)
return chain[:-1]
return half(pts) + half(pts[::-1]) # lower + upper
Quick check
1. What does the cross product cross(O, A, B) tell you?
Its sign is the turn direction. A convex boundary turns only one way, so a point that produces the wrong sign dents the boundary inward and cannot be on the hull — which is exactly when the algorithm pops.
2. Why does the monotone chain build two separate chains?
Sweeping left-to-right with the pop rule traces the bottom boundary; sweeping right-to-left traces the top. Concatenating the two (minus shared endpoints) gives the complete convex polygon.
3. What dominates the running time?
Sorting the points is O(n log n) and dominates. Each sweep pushes and pops each point at most once, so the hull construction itself is linear.
FAQ
What is a convex hull?
The smallest convex polygon containing all the points — the shape a rubber band stretched around the outermost points would form. Every point lies inside or on it, and it never bends inward.
How does Andrew’s monotone chain work?
It sorts points by x, then sweeps left-to-right for the lower boundary and right-to-left for the upper. Each step adds a point and, while the last three make a non-left turn (cross-product test), pops the middle one. Joining the chains gives the hull in O(n log n).
How is it different from the gift-wrapping (Jarvis march) algorithm?
Gift wrapping (Jarvis march) picks each hull point by scanning all points — O(nh), fast for a small hull, slow for a large one. Monotone chain (and Graham scan) is always O(n log n) regardless of hull size — usually the better general-purpose choice.
What are convex hulls used for?
Collision detection and physics engines, bounding shapes in graphics and GIS, pathfinding around obstacles, shape analysis and clustering, and as a primitive for other geometry algorithms (point-set diameter, smallest enclosing shapes).