Every entry on this site so far has compared values — array elements, string characters, edge weights. This one compares directions. Given a set of points on a plane, the convex hull is the smallest convex polygon that contains all of them — stretch a rubber band around every point and let it snap tight; the points it touches are the hull. Graham Scan finds that polygon by picking one point guaranteed to be on the hull, sorting every other point by the angle it makes from there, and then walking that sorted order while a stack throws away any point that would make the boundary bend the wrong way. It's the site's first entry in a new Convex Hull category, and its first from computational geometry — a genuinely different family of problems from the graph, string, and array algorithms filed elsewhere, built on one geometric primitive instead: given three points, does the path through them turn left or right?
Eleven points on a plane, three of them — A, B, and C — deliberately placed on the same straight line along what turns out to be the hull's bottom edge. Press Step or Run to watch the scan: the pivot (lowest point, ties broken by leftmost) is fixed first, then every other point is tested in angle order against the last two points currently on the stack. A point that keeps the boundary turning the same way gets pushed; a point that would bend it back gets a pop of whatever's currently on top instead. The checkbox switches whether a dead-straight (collinear) triple counts as "wrong way" or not — see Pitfalls below for what that changes.
The one primitive everything else is built from is the cross product of two
points relative to a shared origin o: cross(o, a, b) = (a.x−o.x)(b.y−o.y) −
(a.y−o.y)(b.x−o.x). Its sign says which way the path o → a → b turns — positive
one way, negative the other, exactly zero when all three points sit on one straight line. That's
the entire test the algorithm needs.
The pivot — lowest point, ties broken leftmost — is chosen because it's guaranteed to be a hull vertex: no other point can be below and to the left of it, so nothing can ever sit "outside" a boundary that starts there. Sorting the rest by the angle they make from the pivot means the algorithm visits points in the exact order they'd appear walking around the hull's boundary if every one of them belonged on it — which is precisely the assumption the stack exists to check and correct. Each new point is compared against the last two points still on the stack: if the turn keeps bending the same way, the boundary is still convex and the point is pushed. If it would bend back, the top of the stack can't actually be a hull vertex — some other point (possibly one not yet even considered) makes a shortcut around it — so it gets popped, and the same check runs again against whatever's now on top. That popping loop is why a single linear pass over the angle-sorted points is enough: by the time every point has been tried once, every point that ever got pushed and later found not to belong has already been removed.
A coordinate-system note, checked directly against this page's own points: the usual textbook framing says a positive cross product means "counterclockwise." That's only true when y increases upward. This demo's canvas, like every pixel-based coordinate system, has y increasing downward — so a positive cross product here traces out a visually clockwise hull (walk the shipped result, G → F → E → D → C → A → I → H, and it goes top → right → bottom → left → back to top, clockwise on screen). The algorithm doesn't care which way it turns, only that it's consistent — but "clockwise" and "counterclockwise" are exactly the kind of detail that's easy to state confidently from memory and get backwards the moment the coordinate system flips underneath it.
function convexHull(points) {
const pts = Array.from(new Set(points.map(p => JSON.stringify(p))), s => JSON.parse(s));
if (pts.length < 3) return pts; // fewer than 3 points: no polygon, see Pitfalls
let pivot = pts[0];
for (const p of pts) {
if (p.y < pivot.y || (p.y === pivot.y && p.x < pivot.x)) pivot = p;
}
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
const rest = pts.filter(p => p !== pivot).sort((a, b) => {
const angleA = Math.atan2(a.y - pivot.y, a.x - pivot.x);
const angleB = Math.atan2(b.y - pivot.y, b.x - pivot.x);
if (angleA !== angleB) return angleA - angleB;
const distA = (a.x - pivot.x) ** 2 + (a.y - pivot.y) ** 2;
const distB = (b.x - pivot.x) ** 2 + (b.y - pivot.y) ** 2;
return distA - distB; // same angle: nearer point first, see Pitfalls
});
const stack = [pivot];
for (const p of rest) {
while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) {
stack.pop(); // right turn, or dead straight — the middle point isn't a hull vertex
}
stack.push(p);
}
return stack;
}Collinear boundary points are a real design choice, not a bug either way. The
reference implementation above pops on cross(...) <= 0 — a dead-straight triple
counts as "wrong way," same as an actual reversal. On this page's own point set, that rule pops
B the instant A is considered: cross(C, B, A) = 0
exactly, so B — sitting precisely on the straight line from C to A — never makes it into the final
8-vertex hull. Switch the checkbox off (pop only on cross(...) < 0, strictly
negative) and that same test keeps B instead, landing on a 9-vertex hull that includes every point
on the boundary line, not just its two endpoints. Both are legitimate convex hulls of the same
point set — the same polygon, either with or without the collinear points named as vertices — and
both were checked against an independent brute-force hull (testing every point against every
candidate edge directly) before shipping. Pick based on what the caller actually needs: fewer
vertices to store and redraw, or every boundary point accounted for.
A tie in angle needs a secondary sort key, or the hull can come out wrong, not just
differently shaped. Two points that sit on the same ray from the pivot (one nearer, one
farther) have the identical atan2 angle — the sort above breaks that tie by pushing
the nearer point first. Skip that tiebreak (or reverse it to farthest-first) and the scan can
silently produce an invalid result, not merely a stylistic difference: an offline check on the
point set {(1,7), (1,17), (4,9), (13,4), (17,3), (18,9), (19,4), (25,7)} found the
correctly tie-broken scan lands on a clean 4-vertex hull, while reversing the tiebreak lands on a
6-vertex result that fails a direct containment check — the point (25,7) ends up
outside the edge between two of the "hull" points it returned. The bug doesn't throw or loop
forever; it just returns a polygon that isn't actually convex and doesn't actually contain every
input point, which only shows up if something downstream checks.
Fewer than three points, or every point exactly collinear, isn't a polygon. The
reference implementation's early return handles the first case explicitly. The second is sneakier:
run five collinear points — (0,0), (10,0), (15,0), (20,0), (30,0) — through the full
algorithm with no special-casing at all, and the popping loop correctly strips every interior point
on its own, landing on exactly the two extremes, (0,0) and (30,0)
(checked directly). That's the right answer — a "hull" of collinear points really is just a line
segment — but it's a 2-element result from code that otherwise returns 3-or-more, and anything
downstream that assumes a polygon (computing area with the shoelace formula, say) needs to guard
for it explicitly rather than discover it from a division-by-zero or a nonsense negative area.
Time: O(n log n), dominated entirely by the angle sort — same
shape as Kruskal's algorithm being dominated by its edge
sort rather than its near-constant Union-Find calls. The scan itself is O(n): every
point is pushed exactly once, and the total number of pops across the whole run can never
exceed the total number of pushes, so the popping loop's worst case amortizes to linear despite
looking like it could be quadratic from any single point's perspective. Space:
O(n) for the sorted list and the stack. Graham Scan isn't the only way to build a
convex hull — Jarvis March (gift wrapping) finds each
hull vertex by scanning every remaining point for the most extreme angle, giving up the sort's
O(n log n) ceiling for an output-sensitive O(nh), where h is
the number of hull vertices themselves — cheaper when the hull is small relative to the input, worse
when most points end up on it. Quickhull takes a third
approach, dividing and conquering rather than sorting or wrapping — same O(n log n)
average case as this page, but its own worst case degrades to O(n²) on an unlucky
split, the same shape as Quicksort's. A fourth entry,
Chan's Algorithm, combines this page's own angle-sort
step with Jarvis March's wrap, run across small groups instead of the full point set, for
O(n log h) — never worse than this page's flat bound, at the cost of a guess-and-double
group size instead of a single up-front sort. A fifth entry,
Monotone Chain, reaches this page's own guaranteed
O(n log n) bound by a different sort entirely — plain (x, y) coordinate
order instead of angle from a pivot, trading the angle sort's atan2 calls and pivot
selection for two flat sweeps over the same sorted list. A sixth entry,
Divide-and-Conquer Convex Hull, reaches the
same guaranteed bound by a third route again — one coordinate sort just to order the split, same as
Monotone Chain, but then no further sweep at all: every point starts as its own single-point hull,
merged upward in pairs through tangent lines. See
Choosing a Convex Hull Algorithm for a
side-by-side comparison of all six.