The Convex Hull category's twelfth entry, and a sixth "different question" alongside Rotating Calipers, Convex Hull Trick, Melkman's Algorithm, the Akl–Toussaint Heuristic, and Convex Layers — every one of this category's other six entries assumes the full point set is already sitting there, known and complete, before the first answer gets computed. This page doesn't get that assumption: points arrive one at a time, in whatever order they show up, and the current hull has to be correct after every single insertion, not just once at the end. Melkman's Algorithm looks similar at first glance — it also processes points one at a time — but that page's own Pitfalls section is explicit that its one-at-a- time walk only works because the points already arrive in simple-polygon order; feed it the same points in a different order and it silently produces a wrong hull. This page makes no such assumption about order at all, which means it can't get away with Melkman's trick of testing a point against only the two edges currently at a deque's ends — it has to ask, for an arbitrary new point, "how much of the existing hull does this new point make obsolete?", and the honest answer can be anywhere from zero vertices (the point just extends the boundary) to several at once (the point sees clean through a whole run of now-redundant vertices).
Nine points, A through I, inserted in that order. Press Step or Run to watch each insertion: first the incoming point is tested against every edge of the current hull, then the result — extend, remove a chain of one or more now-obsolete vertices, or do nothing at all because the point was already inside. Watch for F, which removes two vertices at once (not just the nearest one), and G, which changes nothing — it's already inside the hull built by the first five points, so the correct move is to discard it silently.
Same cross product every other entry in this category uses:
cross(o, a, b) = (a.x−o.x)(b.y−o.y) − (a.y−o.y)(b.x−o.x), positive when b is
left of the ray from o through a, negative when it's to the right, exactly
zero when the three points sit on one straight line. For a hull stored as a counterclockwise polygon,
"inside" means left-of-or-on every single edge — so a new point p is genuinely outside
the current hull if and only if some edge (u, v) has cross(u, v, p) <
0. If no edge satisfies that, p is already inside (or sitting exactly on the
boundary), and the correct action is to change nothing — this is exactly the check that makes
G a no-op above.
When p is outside, convexity guarantees something useful: the edges that
p sees straight through — where cross(u, v, p) <= 0, using
<= rather than strict < so an edge p lands exactly
on gets absorbed too, the same fewest-vertices convention Graham
Scan's strict mode uses — always form one unbroken run around the polygon, never two separate
patches. That's not a coincidence to verify per-input, it falls straight out of convexity itself: if
two disconnected runs of edges were both hidden from p, the polygon would have to bend
back on itself between them, which a convex polygon can never do. Finding that one run's two
endpoints — call them the tangent points — and splicing p in between them, while
dropping everything strictly inside the run, is the entire algorithm. F above is the
run-of-two-or-more case: it sees through both the edge into D and the edge out of
D into A, so both D and A get
dropped in the same insertion, not patched one at a time.
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
// hull: an array of {x, y} points in CCW order (or fewer than 3, see below).
// Returns the updated hull after inserting p.
function insertPoint(hull, p) {
if (hull.length === 0) return [p];
if (hull.length === 1) {
return (hull[0].x === p.x && hull[0].y === p.y) ? hull : [hull[0], p];
}
if (hull.length === 2) {
const [a, b] = hull;
const c = cross(a, b, p);
if (c === 0) {
const pts = [a, b, p].sort((u, v) => u.x - v.x || u.y - v.y);
return [pts[0], pts[2]]; // collinear: keep just the two extreme endpoints
}
return c > 0 ? [a, b, p] : [a, p, b]; // orient the new triangle CCW
}
const n = hull.length;
const cvals = hull.map((_, i) => cross(hull[i], hull[(i + 1) % n], p));
if (!cvals.some(c => c < 0)) return hull; // inside, or exactly on the boundary: no-op
const consumed = cvals.map(c => c <= 0); // edges p sees through (or lands exactly on)
let start = consumed.findIndex((c, i) => c && !consumed[(i - 1 + n) % n]);
let end = start;
while (consumed[(end + 1) % n]) end = (end + 1) % n;
const kept = [];
for (let i = (end + 1) % n; ; i = (i + 1) % n) {
kept.push(hull[i]);
if (i === start) break;
}
kept.push(p);
return kept;
}Patching only the single nearest hull vertex instead of finding the whole visible chain is wrong on 98.0% of 20,000 randomized insertion sequences — not a rare edge case, close to the default outcome. It's a tempting shortcut: "the new point is outside, so replace whatever hull vertex is closest to it" sounds plausible, and for a single, gentle extension it can even happen to land close to correct. But it fails for two separate reasons at once. First, it removes exactly one vertex whether or not exactly one vertex actually needs removing — on this page's own example set, inserting D needs to remove nothing (it's a clean extension), but the nearest-vertex patch overwrites A anyway, discarding a real hull vertex for no reason. Second, when more than one vertex genuinely is obsolete — F's real case, which correctly drops both D and A — replacing only the nearest one leaves the other stranded on what's now a concave dent instead of a hull. Run against an independent oracle (a from-scratch full recomputation after every insertion) across 20,000 random sequences of 5-20 points each, the patched version diverges from the correct hull, or produces an outright non-convex result, on 19,604 of them.
Skipping the inside check — going straight to "find the visible chain" without first
asking whether one exists at all — corrupts the hull on 82.6% of 20,000 trials, and it's a
sneakier bug than the one above because it can look correct for several insertions in a row before it
strikes. When a point really is inside, no edge satisfies cross(u, v, p) < 0,
so there's no transition from "hidden" to "visible" anywhere around the polygon for the chain-finding
step to find. A version that skips the inside check and blindly searches for that transition anyway
has to do something when the search comes up empty — and "fall back to inserting after the
first vertex" is exactly the kind of silent default that never throws, never logs anything, and just
quietly wedges the point into the hull's vertex list. On this page's own example set, this is
G's moment exactly: the correct algorithm discards it as a no-op, but the buggy
version splices it in next to B, producing a hull that fails a direct convexity check
one step after G — three consecutive points no longer turning the same way — before the very next
real insertion happens to sweep G back out again as part of its own chain removal,
erasing the evidence. A snapshot taken at the wrong moment would show a perfectly fine-looking hull on
either side of the bug and never catch it; only checking convexity immediately after every
single insertion (not just at the end) surfaces it, the same "check after every step, not just the
last one" discipline this site's demos generally lean on.
Time: O(h) per insertion, where h is the current hull's
own vertex count — every insertion has to test every existing edge once, whether or not the point
turns out to change anything. Across n insertions total, that's O(nh) in the
worst case if h keeps growing toward n — the identical shape as
Jarvis March's own bound, and for a related reason: both
pay a linear scan proportional to the hull's own size, rather than a logarithm, because neither
keeps any structure beyond a plain ordered list of vertices. The naive alternative — discard the
running hull, throw the new point into the full set, and recompute from scratch with
Graham Scan or
Monotone Chain — costs O(n log n) per
insertion instead, worse by a whole sort every single time; this page's edge-scan approach never
resorts anything, at the cost of scaling with the hull's own size instead of staying flat.
Space: O(h), just the current hull — unlike a from-scratch recompute,
nothing from a discarded interior point needs to be kept around at all. Real dynamic convex hull data
structures exist that break the O(h)-per-insertion floor entirely — balancing the hull's
own vertex list in a search tree keyed by angle, so testing and updating both become
O(log² n) instead of a linear scan — genuinely more machinery than this page's plain
array, and not built here.