The site's second Convex Hull entry, and a genuinely different
approach from Graham Scan: instead of sorting every
point once and sweeping through that order with a stack, Jarvis March — also called
gift wrapping — builds the hull one vertex at a time. Start at a point guaranteed
to be on the hull, then repeatedly ask "which remaining point keeps every other point on one
consistent side?" and that point is the next hull vertex. Keep going until the walk returns to
where it started. It's literally wrapping a string taut around the outside of the points, one pull
at a time. Same primitive as Graham Scan (the cross product, "which way does this turn"), same
convex hull as a result — this page uses the exact same 11 points, and both algorithms land on the
identical hull — but a different cost shape: O(nh) where h is the number
of hull vertices themselves, not O(n log n) from a sort.
The same eleven points as the Graham Scan page, including the same collinear trio — A, B, and C — along the hull's bottom edge. Press Step or Run to watch the wrap: starting at the leftmost point, every other point is tested in turn against the current best guess for "next hull vertex," and any point that turns out to be more extreme takes the lead. Once every point has been checked, the current leader is confirmed and the walk moves on from there. The checkbox switches how an exact three-way tie (a point sitting precisely on the current best-guess line) is broken — see Pitfalls for why this one matters more than it looks.
Same cross product as Graham Scan: 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 when o, a, and
b sit on one straight line. Graham Scan uses it to test whether a boundary bends the
right way; Jarvis March uses the same sign to compare two candidates for the next hull
point. Given the current hull vertex and a tentative next point, any other point n
with cross(current, candidate, n) < 0 is "more clockwise" than the candidate —
which means the candidate can't actually be the next hull vertex, because n would end
up outside the edge current→candidate. So n takes over as the new candidate, and the
same test runs again against whatever's left. By the time every other point has been checked once,
whatever candidate survived is provably the most extreme point as seen from current —
nothing can be outside the edge to it, which is exactly what "next hull vertex" means.
The starting point matters the same way Graham Scan's pivot does: it has to be a point no other
point can be "more extreme than" in the direction the walk starts, so it's guaranteed to be on the
hull with no test needed. Graham Scan picks the lowest point (smallest y); this page picks the
leftmost point (smallest x, ties broken by smallest y) instead — a different but
equally valid extreme, deliberately not matching Graham Scan's own convention, to make the point
that any direction works as long as it's used consistently. Both starting choices land the walk on
the same hull, just entered from a different vertex: Graham Scan's own verified order is
G → F → E → D → C → A → I → H; this page's own step trace below confirms
I → H → G → F → E → D → C → A — the identical eight-point cycle, just read starting
from a different point in 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 start = pts[0];
for (const p of pts) {
if (p.x < start.x || (p.x === start.x && p.y < start.y)) start = p;
}
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
function dist2(a, b) {
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2;
}
const hull = [start];
let current = start;
while (true) {
let candidate = pts.find(p => p !== current);
for (const p of pts) {
if (p === current || p === candidate) continue;
const c = cross(current, candidate, p);
if (c < 0) {
candidate = p; // p is more clockwise: it's the new best guess
} else if (c === 0 && dist2(current, p) > dist2(current, candidate)) {
candidate = p; // exact tie: prefer the farther point, see Pitfalls
}
}
if (candidate === start) break; // wrapped all the way around
hull.push(candidate);
current = candidate;
}
return hull;
}Skipping the exact-tie tiebreak doesn't just change the output — it makes the output
depend on input order, which a correct geometric algorithm should never do. This is a
sharper failure than Graham Scan's own collinear pitfall: Graham Scan's strict-vs-loose checkbox is
a legitimate design choice either way (fewer vertices vs. every boundary point, both independently
verified as valid hulls of the same point set). Skipping Jarvis March's tiebreak entirely — updating
the candidate only on cross(...) < 0 and doing nothing at all when
cross(...) === 0 — isn't a design choice, it's a bug, and a genuinely deceptive one
because it can look correct for a while. Reusing Graham Scan's own offline 8-point counterexample
({(1,7), (1,17), (4,9), (13,4), (17,3), (18,9), (19,4), (25,7)}, which contains two
exact-collinear triples), a from-scratch check found: with no tiebreak at all, the walk lands on the
correct 4-vertex hull (1,7) → (17,3) → (25,7) → (1,17) when the points are supplied in
their original order — but a 6-vertex result that wrongly includes two interior-looking points,
(13,4) and (19,4), when the exact same points are supplied in a different
order. Add the farther-point tiebreak back in and both orderings — plus a third, shuffled order,
also checked — agree on the same 4-vertex hull every time. The points and the true hull never
changed; only the answer did, purely as a function of array order, which is precisely the kind of
bug that survives a single test run and only shows up when something feeds the algorithm the same
data a different way.
Skipping the tie entirely by only checking distance, with no cross-product
check at all, breaks the geometry, not just the tie. The tiebreak only fires when
cross(...) === 0 — it's a refinement of the turn test, not a replacement for it.
Comparing every candidate purely by distance from current would pick the single
farthest point in the whole set on the very first comparison, regardless of direction, which has
nothing to do with convexity at all.
Fewer than three points, or every point exactly collinear, isn't a polygon —
same edge case as Graham Scan, same fix (the reference implementation's early return), and the same
sneaky version: all-collinear input never triggers that early return (there are "enough" points) but
still isn't a polygon. Unlike Graham Scan, this shows up as a real risk in Jarvis March specifically:
the walk's termination condition is "candidate equals the start point again," and on a perfectly
straight line of points there is no well-defined "most clockwise" direction to turn back — every
comparison returns exactly zero. Checked directly: five collinear points,
(0,0), (10,0), (15,0), (20,0), (30,0), walked with the farther-point tiebreak from
(0,0), correctly reach (30,0) and then correctly reach back to
(0,0) — the tiebreak that fixes the order-dependence bug above is doing double duty
here, since without it the walk has no principled way to pick a direction to turn around in and
risks cycling between the two endpoints forever instead of terminating.
Time: O(nh), where n is the number of input points and
h is the number of points that end up on the hull — each of the h hull
vertices costs a full O(n) scan over the remaining points to find the next one.
Measured, not just asserted: on 11-160 randomly generated points arranged so every point sits on the
hull (a circle, so h = n), total point-comparisons scaled roughly with n²
(360 at n=20, 1,520 at n=40, 6,240 at n=80, 25,280 at n=160 — each doubling of n roughly
quadrupling the count, exactly what n·h predicts when h grows with
n). On 20-320 points arranged as a fixed triangle (h = 3) with the rest
placed randomly strictly inside it, the same measurement scaled roughly linearly instead (54, 114,
234, 474, 954 — each doubling of n only roughly doubling the count), because
h stayed constant. That's the actual tradeoff against Graham Scan's
O(n log n): cheaper when the hull is small relative to
the input (a scattered cloud of points with only a handful on the boundary), worse when most points
end up on it (points already arranged near-convex, or literally on a circle) — Jarvis March can
degrade to O(n²) exactly where Graham Scan's sort-based cost never moves.
Space: O(h) for the output hull itself, notably less than Graham
Scan's O(n) sorted-list-plus-stack, since Jarvis March never needs to hold onto points
that don't end up on the hull. A third approach, Quickhull,
divides and conquers instead of wrapping or sorting — its own worst case is also O(n²),
but triggered by an unlucky recursive split rather than by how many points end up on the hull. A
fourth entry, Chan's Algorithm, gets this page's own
output-sensitivity without needing to already know h is small: it wraps in the same
style as this page, but across small Graham-Scanned groups instead of every point, doubling the
group size whenever a guess turns out too small, for O(n log h) — never as bad as this
page's own worst case. A fifth entry, Monotone Chain,
reaches Graham Scan's own guaranteed bound by a different sort — plain coordinate order instead of
angle from a pivot — rather than this page's output-sensitive tradeoff. A sixth entry,
Divide-and-Conquer Convex Hull, reaches that
same guaranteed bound too, but by merging small per-point hulls upward through tangent lines after
its own coordinate sort, rather than sweeping the sorted list even once. See
Choosing a Convex Hull Algorithm for a
side-by-side comparison of all six.