The site's sixth Convex Hull entry, and the third to reach a
guaranteed O(n log n), alongside Graham Scan
and Monotone Chain — but by a mechanism none of the
other five share. Give every single point its own trivial one-point "hull," then repeatedly merge
two neighboring hulls into one by finding the pair of lines that touch both without crossing either
— the upper and lower tangent — and keeping only what's outside
them. Merge enough times and the whole input collapses into one hull.
Quickhull is divide-and-conquer too, but it recurses on one
growing hull, splitting the points still outside it against a baseline edge. This page
recurses on the input itself — split the points in half, solve each half completely and
independently, then combine — the same shape as Merge Sort,
the way Quickhull is already documented as the spatial analogue of Quicksort. Verified directly
against this site's own shared eleven-point set: the same eight-vertex hull as every other entry in
this category, I → H → G → F → E → D → C → A.
The same eleven points as every other Convex Hull entry on this site. Press Step
or Run to watch it: the points sort by x (ties broken by y)
once up front, same as Monotone Chain, then each one starts as its own single-point hull. Four rounds
of merges follow — pair up neighboring hulls, find their upper and lower tangent, keep only the
points outside those two lines — until one hull remains. Watch the merge-in-progress pair highlighted
in two colors, the tangent lines drawn between them, and any point they exclude fade to gray
(interior) the moment it's no longer needed. The checkbox controls the same
strict/loose collinear-boundary choice as every other entry in this category, but applied once at the
very end rather than during any individual merge — see Pitfalls for why that's a structural
difference, not just a smaller version of the same toggle.
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). A single point is trivially its
own hull — nothing to compute. Merging two hulls L and R that sit side by
side (every point of L to the left of every point of R) means finding the
two lines that touch one vertex of each hull while leaving every other point of both hulls on one
consistent side: the upper tangent and lower tangent. Once both are
known, any point of L or R that sits on the side facing the other hull is now
provably interior — enclosed by the merged shape — and only the points on the two outward-facing arcs,
plus the four tangent endpoints, survive as the merged hull's vertices.
Finding those two lines doesn't need to check every pair of points across both hulls. Start a
pointer at L's rightmost point and one at R's leftmost point — both
guaranteed close to any tangent, since a tangent line only ever touches the side of each hull facing
the other. Nudge the L pointer to its neighbor only when that neighbor is still on the
correct side of the line to R's current pointer; same for R's pointer against
L's. Repeat until neither pointer wants to move — that's the tangent. Each pointer can
advance at most as many times as its own hull has vertices before the loop has to stop, so the whole
search costs O(|L| + |R|), not O(|L| · |R|) — see Pitfalls for exactly how
much that difference matters.
Checked directly against this page's own point set, one genuinely new fact this algorithm's own merge order surfaces that the other five pages don't need to mention: point K never appears in this category's canonical eight-vertex hull, but it isn't discarded the moment the algorithm sees it, the way an algorithm that only ever tracks extreme points might suggest. K first survives one merge — paired trivially with C into its own two-point mini-hull — and is only proven interior at the very next merge, once that mini-hull meets J and G's. B and J both survive even longer: two full levels each, not proven interior until the second-to-last merge of the whole run, when the two four-and-three-point hulls carrying them finally combine. Divide-and-conquer discards interior points incrementally, the same way Quickhull's own page describes discarding as "the whole speed argument," just distributed across every merge level instead of concentrated in one baseline test each round.
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
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;
pts.sort((a, b) => a.x !== b.x ? a.x - b.x : a.y - b.y);
return hull(pts);
}
function hull(pts) {
if (pts.length === 1) return pts;
const mid = Math.ceil(pts.length / 2);
return merge(orderByAngle(hull(pts.slice(0, mid))), orderByAngle(hull(pts.slice(mid))));
}
// Recover a hull's own cyclic order from its vertex set -- valid because sorting a convex
// polygon's own vertices by angle around their centroid always recovers the right order.
function orderByAngle(hullPts) {
if (hullPts.length <= 2) return hullPts;
const cx = hullPts.reduce((s, p) => s + p.x, 0) / hullPts.length;
const cy = hullPts.reduce((s, p) => s + p.y, 0) / hullPts.length;
return hullPts.slice().sort((a, b) => Math.atan2(a.y - cy, a.x - cx) - Math.atan2(b.y - cy, b.x - cx));
}
// Walk each hull's own pointer -- at most |L| + |R| steps total -- toward the tangent line
// touching both without crossing either. sign/step pick which of the two tangents.
function walkTangent(L, R, iStep, jStep, iSign, jSign) {
const nL = L.length, nR = R.length;
const stepL = (i, s) => ((i + s) % nL + nL) % nL, stepR = (j, s) => ((j + s) % nR + nR) % nR;
let i = 0; for (let k = 1; k < nL; k++) if (L[k].x > L[i].x || (L[k].x === L[i].x && L[k].y > L[i].y)) i = k;
let j = 0; for (let k = 1; k < nR; k++) if (R[k].x < R[j].x || (R[k].x === R[j].x && R[k].y < R[j].y)) j = k;
for (let guard = 0; guard < nL + nR + 5; guard++) {
let moved = false;
while (nL > 1) {
const cand = stepL(i, iStep);
if (cand === i || Math.sign(cross(R[j], L[i], L[cand])) !== iSign) break;
i = cand; moved = true;
}
while (nR > 1) {
const cand = stepR(j, jStep);
if (cand === j || Math.sign(cross(L[i], R[j], R[cand])) !== jSign) break;
j = cand; moved = true;
}
if (!moved) break;
}
return { a: L[i], b: R[j] };
}
// If several points sit exactly on the tangent line, walk out to the farthest one on each
// side -- otherwise a point strictly between the true endpoints gets kept as if it were one.
function refineCollinear(a, b, L, R) {
const dist2 = (p, q) => (p.x - q.x) ** 2 + (p.y - q.y) ** 2;
for (let round = 0; round < 3; round++) {
let bestA = a;
for (const p of L) if (cross(b, a, p) === 0 && dist2(b, p) > dist2(b, bestA)) bestA = p;
let bestB = b;
for (const p of R) if (cross(bestA, b, p) === 0 && dist2(bestA, p) > dist2(bestA, bestB)) bestB = p;
if (bestA === a && bestB === b) return { a: bestA, b: bestB };
a = bestA; b = bestB;
}
return { a, b };
}
function merge(L, R) {
const up = walkTangent(L, R, 1, -1, -1, 1), lo = walkTangent(L, R, -1, 1, 1, -1);
const { a: au, b: bu } = refineCollinear(up.a, up.b, L, R);
const { a: al, b: bl } = refineCollinear(lo.a, lo.b, L, R);
const keep = (chord0, chord1, group, otherFirst) => {
if (chord0 === chord1) return [chord0];
const outside = Math.sign(cross(chord0, chord1, otherFirst));
return group.filter(p => p === chord0 || p === chord1 || Math.sign(cross(chord0, chord1, p)) !== outside);
};
const merged = keep(au, al, L, R[0]).concat(keep(bu, bl, R, L[0]));
return Array.from(new Set(merged));
}The obvious way to find a tangent line breaks the algorithm's own headline complexity —
checked with real counts, not just asymptotic notation. Checking every pair
(a, b) with a ∈ L, b ∈ R and testing whether it's a valid
tangent is the first thing that comes to mind, and it's correct — but it's O(|L| · |R|)
per merge, and at the top-level merge |L| and |R| can each be as large as
n/2. Measured directly: for n = 1,000 points arranged so every one sits on
the hull (a circle, the same adversarial shape Jarvis
March's own page uses to hit its worst case), the top-level merge alone checks up to 250,000
candidate pairs, each one scanning all 1,000 points to confirm — roughly 250 million point-tests for
a single merge, versus at most 2,000 steps total for the pointer walk in "Why it works." At
n = 10,000 the gap widens to roughly 250 billion versus 20,000. The brute-force version
still returns the right answer — it's not a correctness bug — but it quietly turns an
O(n log n) algorithm back into something worse than O(n²) at the very step
that was supposed to avoid that.
A tangent search that accepts the first point satisfying the "everything's on one side"
test can land on the wrong one when several points sit exactly on the tangent line — caught while
building this page, not a hypothetical. Merging a six-point left group against a four-point
right group where three real points shared a horizontal edge, an unrefined search accepted the
middle of those three collinear points as if it were the tangent endpoint, silently dropping
the true corner and producing a five-vertex result with an extra interior point instead of the correct
four-vertex hull. refineCollinear above exists specifically to fix this: after a tangent
candidate passes the side test, walk out to the farthest point still exactly on that line before
accepting it, so a true corner is never left stranded behind a collinear neighbor.
Loosening the collinear-boundary rule isn't a one-line comparison flip here, unlike every
other entry in this category. Graham Scan, Jarvis March, Quickhull, and Monotone Chain each
decide a boundary point's fate the moment they touch it, so strict-vs-loose is a single
<= vs < swap at that one comparison. This algorithm's merge step
already has to choose one side of the tangent line to keep, over and over, at every level — reopening
that choice per merge would mean re-deciding a point's fate based on tangents that don't exist yet at
the time it was dropped. Loose mode here is a separate pass, run once after the strict hull is final:
walk its edges and re-insert any of the original points that sit exactly on one, ordered by distance
from that edge's start. Checked directly on this page's own point set: the strict hull drops
B (collinear with A and C, same as every other
entry in this category), and the loose pass reinserts it in the right position for the identical
nine-vertex result, I → H → G → F → E → D → C → B → A — but structurally, this page finds
it by re-checking the finished hull's own edges, not by keeping a wider door open throughout.
Time: O(n log n), from the same recursion shape as
Merge Sort: split in half, recurse on each half, then do
O(|L| + |R|) work combining the results — T(n) = 2T(n/2) + O(n). Across any
one level of the recursion, the merges' |L| + |R| costs sum to O(n) no
matter how the points are distributed between them, and there are O(log n) levels before
recursion bottoms out at single points. Space: O(n) for the recursion and
the hull arrays at each level. This page's own demo runs the equivalent computation bottom-up instead
of top-down — building every single-point hull first, then merging neighbors level by level, the same
transformation an iterative bottom-up Merge Sort makes on its own recursion — which flattens the whole
run into the linear step trace above without changing what gets computed; a from-scratch check
confirmed the top-down recursive form above and this page's bottom-up demo agree on the exact same
eight-vertex result. Reaches the identical guaranteed bound as
Graham Scan and
Monotone Chain by a third distinct route —
Jarvis March trades that guarantee for an
output-sensitive O(nh), Quickhull trades it for
a typically-faster but worst-case O(n²), and
Chan's Algorithm combines pieces of two other entries
for O(n log h) when the true hull size isn't known ahead of time. See
Choosing a Convex Hull Algorithm for a
side-by-side comparison of all six.