The site's fifth Convex Hull entry, and the second one that
reaches a guaranteed O(n log n), alongside
Graham Scan — but by a genuinely different sort.
Graham Scan sorts every point by the angle it makes from a chosen pivot, which needs the
pivot picked first and an atan2 call per comparison. Monotone Chain, published by
A. M. Andrew in 1979, skips the angle entirely: sort all the points by plain (x, y)
coordinate, exactly once, and then sweep that flat order twice — once left to right building
what's called the lower hull, once right to left building the
upper hull — using the same cross-product turn test and popping stack Graham Scan
uses for its single sweep. Same asymptotic class, same primitive, no pivot to choose and no
trigonometry anywhere in it.
The same eleven points as every other Convex Hull entry on this site, including the same
collinear trio — A, B, and C — along the hull's
bottom edge. Press Step or Run to watch both passes: the points
are sorted by x (ties broken by y) once up front, then swept left to
right to build the lower chain, then swept right to left to build the upper chain — each pass uses
the identical push/pop rule, just in opposite directions over the same sorted list. The checkbox
switches whether a dead-straight (collinear) triple counts as "wrong way" during either pass — see
Pitfalls for what that changes.
Same cross product as every other entry in this category:
cross(o, a, b) = (a.x−o.x)(b.y−o.y) − (a.y−o.y)(b.x−o.x), positive one way, negative
the other, exactly zero on a straight line. What's different here is what gets sorted before the
sweep even starts. Sorting by coordinate instead of angle means every point in the sorted list has
a well-defined, unambiguous position — no pivot to single out, no risk of two points landing at the
identical angle from some chosen center (the exact tiebreak Graham Scan's own page has to handle
with a secondary distance sort). The tradeoff is that one sorted pass isn't enough on its own: an
angle sort visits points in the order they'd appear walking the whole hull boundary, but an
x, y sort only ever visits them left to right, which can trace at most one side of a
convex shape. So the algorithm runs the identical push/pop sweep twice — once building the chain
that stays on one side as points are added left to right (the lower hull), once
building the chain on the other side scanning right to left (the upper hull) —
and the union of both chains, each end trimmed of its one duplicate point, is the whole polygon.
A naming surprise, checked directly against this page's own points, not assumed from the
textbook terms: "lower" and "upper" describe how each chain is built (which pass keeps
which turns), not where either one ends up on screen. On this page's own point set, the chain built
by the standard "lower hull" rule comes out to I → H → G → F → E — and every one of
those points (H at y=70, G at y=40, F at y=60) sits near the
top of the canvas, not the bottom. The "upper hull" pass produces
E → D → C → A → I, sitting near the bottom instead (C and
A both at y=300). The names are exactly backwards from what they'd suggest on this
page's own canvas — the same y-increases-downward flip
Graham Scan's own page already found turns its
clockwise-looking hull into a counterclockwise one by the textbook cross-product convention, just
showing up here as a flipped label instead of a flipped turn direction. The algorithm doesn't care
what either chain is called, only that both get built and stitched together — but it's exactly the
kind of mismatch that's easy to get backwards from memory the moment a coordinate system doesn't
match the textbook diagram it was named from.
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
pts.sort((a, b) => a.x !== b.x ? a.x - b.x : a.y - b.y); // ties broken by y, see Pitfalls
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
function buildChain(seq) {
const stack = [];
for (const p of seq) {
while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) {
stack.pop(); // wrong way, or dead straight — the middle point isn't a hull vertex
}
stack.push(p);
}
return stack;
}
const lower = buildChain(pts);
const upper = buildChain(pts.slice().reverse());
lower.pop(); // each chain's last point duplicates the other chain's first point
upper.pop();
return lower.concat(upper);
}A tie on x needs a secondary sort key, or the hull can silently drop a real
vertex — not just reorder — depending on what order the input happened to arrive in. This
is the same shape as Graham Scan's own angle-tie pitfall, but the failure is sharper here. Checked
directly: take four points forming a vertical segment plus one point off to the side —
(0,0), (0,5), (0,10), all sharing x = 0, plus
(10,5) — whose true hull is the triangle (0,0) → (10,5) → (0,10), with
(0,5) sitting exactly on its left edge. Sorted with the y tiebreak, all
three tested input orderings agree on that same 3-vertex triangle every time. Sorted without
it — comparing only by x, leaving same-x points in whatever order a stable
sort happened to receive them — two of the three orderings still land on a valid (if differently
ordered) triangle by luck, but the third produces (0,5) → (10,5) → (0,10): a hull that
keeps the interior boundary point (0,5) and drops the genuine corner
(0,0) entirely. That's not a stylistic difference, it's a wrong answer — a direct
containment check confirms (0,0) ends up outside the returned "hull" — and it's exactly
the kind of bug that looks fine on two out of three tries. See
Jarvis March's own tiebreak pitfall for the same
failure shape (a correct-looking result that depends on input order, not on the geometry) in a
completely different algorithm.
Collinear boundary points are a real design choice here too, and it's checked to land on
the same answer as every other entry in this category. The reference implementation above
pops on cross(...) <= 0, same as Graham Scan's strict mode. On this page's own point
set that pops B — sitting exactly on the line from A to
C — during the upper-hull pass, for the same 8-vertex hull
(I → H → G → F → E → D → C → A) Graham Scan and Jarvis March both land on. Loosen the
test to < 0 and B survives instead, for the identical 9-vertex
result (I → H → G → F → E → D → C → B → A) both other pages also produce in loose mode.
See Choosing a Convex Hull
Algorithm for the same question answered across every entry in the category.
Fewer than three points, or every point exactly collinear, isn't a polygon — same
edge case as Graham Scan and Jarvis March, same fix (the reference implementation's early return for
the first case). The second is handled with no special-casing at all: five collinear points,
(0,0), (10,0), (15,0), (20,0), (30,0), run through both passes unmodified, each
correctly collapse to the same two extremes, (0,0) and (30,0) — checked
directly. Same as the other two entries, that's the right answer but a 2-element result from code
that otherwise returns 3-or-more, worth guarding for explicitly downstream.
Time: O(n log n), dominated entirely by the one up-front coordinate
sort — same asymptotic shape as Graham Scan, and the
practical case for reaching for this page over that one: a numeric (x, y) comparison has
a cheaper constant factor than a per-pair atan2 call, and there's no separate
pivot-selection pass first. Both hull-building sweeps are O(n) each by the identical
amortized argument as Graham Scan's single sweep — every point is pushed onto its chain exactly once,
so the total pops across an entire pass can never exceed the total pushes. Space:
O(n) for the sorted list and the two chains. This page reaches the identical guaranteed
bound as Graham Scan by a different route — Jarvis March
trades that guarantee for an output-sensitive O(nh), Quickhull
trades it for a typically-faster but worst-case O(n²) divide-and-conquer, and
Chan's Algorithm combines pieces of both for
O(n log h) when the true hull size isn't known ahead of time.
Divide-and-Conquer Convex Hull reaches this
page's own guaranteed bound by a third route: the identical up-front coordinate sort, but merging
per-point hulls upward through tangent lines afterward instead of sweeping twice. See
Choosing a Convex Hull Algorithm for a
side-by-side comparison of all six.