Introduction

Scatter a handful of points on a page and imagine stretching a rubber band around all of them, then letting it snap tight. The shape it traces — using only the outermost points as corners — is the convex hull. Every other point ends up trapped inside.

Computing that shape sounds like it should require checking every point against every other, but there is a shortcut with a delightfully simple idea: find the point that sticks out the farthest from a line, use it to slice the problem into two smaller pieces, and repeat. That is QuickHull, and its structure is a close cousin of quicksort — pick a pivot, split, recurse.

The reward is an algorithm that, for typical scattered inputs, wraps nn points in about O(nlog⁡n)O(n \log n) time, discarding huge chunks of the input at every step without ever looking at them again.

Try It

Below is a random cloud of points. Press Step to watch QuickHull work one recursive call at a time: it finds the point farthest from the current edge, draws the two new edges to it, and discards every point that now sits inside the triangle. Press Run to completion to see the whole hull carved out at once.

<p class="hint">Gray dots are candidate points. Each step finds the point farthest from the current edge (red dashes), turns it into a confirmed hull corner (dark blue), and discards everything trapped inside the new triangle (light gray).</p>
<svg id="canvas" class="canvas" viewBox="0 0 300 220" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Ready. Press Step to begin.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to completion</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 320px; height: 235px; background: #f4f6f8; border: 1px solid #cdd9e3;
           border-radius: 8px; display: block; }
.pt { fill: #8a94a3; }
.pt.discarded { fill: #d7dbe0; }
.pt.hull { fill: #1d3557; }
.pt.farthest { fill: #e63946; }
.edge { stroke: #1d3557; stroke-width: 2; fill: none; }
.edge.active { stroke: #e63946; stroke-width: 1.6; stroke-dasharray: 4 3; }
.tri { fill: #e63946; fill-opacity: .08; stroke: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const SVGNS = 'http://www.w3.org/2000/svg';

// Cross product: positive when p is left of the directed line o->a->b, negative when to the right.
function cross(o, a, b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
// Unnormalized distance from point o to line (a,b), used only to compare magnitudes.
function dist(o, a, b) { return Math.abs(cross(a, b, o)); }

// A fixed, hand-placed point cloud (roughly a rounded ring with a cluster of interior points).
const POINTS = [
  {x:40,y:120},{x:70,y:40},{x:120,y:20},{x:180,y:15},{x:230,y:35},
  {x:260,y:90},{x:255,y:150},{x:210,y:190},{x:150,y:200},{x:90,y:180},
  {x:130,y:100},{x:150,y:130},{x:170,y:90},{x:110,y:140},{x:190,y:120},
  {x:60,y:150},{x:200,y:60}
];
const key = (p) => p.x + ',' + p.y;

let queue = [];
let hullSet = new Set();
let discarded = new Set();
let active = null; // {a,b,farthest,triPts}
let stepsDone = 0;
let finished = false;

// First split: pick the min-x and max-x points, then partition everyone else into a 'left' set and a 'right' set of that baseline. Each set seeds one recursive branch.
function initRun() {
  let minX = POINTS[0], maxX = POINTS[0];
  for (const p of POINTS) { if (p.x < minX.x) minX = p; if (p.x > maxX.x) maxX = p; }
  const left = [], right = [];
  for (const p of POINTS) {
    if (p === minX || p === maxX) continue;
    const c = cross(minX, maxX, p);
    if (c > 0) left.push(p); else if (c < 0) right.push(p);
  }
  hullSet = new Set([key(minX), key(maxX)]);
  discarded = new Set();
  queue = [ { pts: left, a: minX, b: maxX }, { pts: right, a: maxX, b: minX } ];
  active = null;
  stepsDone = 0;
  finished = false;
}

// One recursive call, popped from the queue: find the farthest point from edge (a,b), promote it to the hull, and requeue the two smaller sub-problems it creates.
function step() {
  if (finished) return;
  if (queue.length === 0) { finished = true; render(); setStatus(i18nFmt('Done. Convex hull has %n% corners.', { n: hullSet.size }), 'done'); return; }
  const { pts, a, b } = queue.shift();
  stepsDone++;
  if (pts.length === 0) { active = null; render(); return step(); }
  let farthest = pts[0], maxD = dist(pts[0], a, b);
  for (const p of pts) { const d = dist(p, a, b); if (d > maxD) { maxD = d; farthest = p; } }
  hullSet.add(key(farthest));
  const s1 = [], s2 = [];
  for (const p of pts) {
    if (p === farthest) continue;
    if (cross(a, farthest, p) > 0) s1.push(p);
    else if (cross(farthest, b, p) > 0) s2.push(p);
    else discarded.add(key(p));
  }
  queue.push({ pts: s1, a, b: farthest });
  queue.push({ pts: s2, a: farthest, b });
  active = { a, b, farthest };
  render();
  setStatus(i18nFmt('Farthest point %far% becomes a hull corner — %n% point(s) discarded inside its triangle.', { far: '(' + farthest.x + ',' + farthest.y + ')', n: pts.length - 1 }), '');
}

function runAll() {
  let guard = 0;
  while (!finished && guard < 200) { step(); guard++; }
}

function svgEl(tag, attrs) {
  const e = document.createElementNS(SVGNS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  return e;
}

// Redraw the whole picture: the active search triangle, the hull edges found so far (approximated by sorting confirmed hull points by angle), the in-progress edges being split, and every point colored by its current status.
function render() {
  const svg = document.getElementById('canvas');
  svg.innerHTML = '';

  if (active) {
    const tri = svgEl('polygon', { points: [active.a, active.farthest, active.b].map(p => p.x + ',' + p.y).join(' '), class: 'tri' });
    svg.appendChild(tri);
  }

  const hullPts = POINTS.filter(p => hullSet.has(key(p)));
  if (hullPts.length >= 2) {
    // The hull points aren't discovered in walk order, so approximate the polygon by sorting them around their centroid just for drawing.
    for (const [ka, kb] of consecutiveHullEdges()) {
      svg.appendChild(svgEl('line', { x1: ka.x, y1: ka.y, x2: kb.x, y2: kb.y, class: 'edge' }));
    }
  }
  if (active) {
    svg.appendChild(svgEl('line', { x1: active.a.x, y1: active.a.y, x2: active.farthest.x, y2: active.farthest.y, class: 'edge active' }));
    svg.appendChild(svgEl('line', { x1: active.farthest.x, y1: active.farthest.y, x2: active.b.x, y2: active.b.y, class: 'edge active' }));
  }

  for (const p of POINTS) {
    const k = key(p);
    let cls = 'pt';
    if (active && active.farthest === p) cls += ' farthest';
    else if (hullSet.has(k)) cls += ' hull';
    else if (discarded.has(k)) cls += ' discarded';
    svg.appendChild(svgEl('circle', { cx: p.x, cy: p.y, r: 4, class: cls }));
  }
}

// Sort confirmed hull points by angle around their centroid so consecutive points in the array trace the polygon boundary — good enough for a live sketch, not a substitute for the real algorithm's edge order.
function consecutiveHullEdges() {
  const pts = POINTS.filter(p => hullSet.has(key(p)));
  let cx = 0, cy = 0;
  pts.forEach(p => { cx += p.x; cy += p.y; });
  cx /= pts.length; cy /= pts.length;
  pts.sort((p, q) => Math.atan2(p.y - cy, p.x - cx) - Math.atan2(q.y - cy, q.x - cx));
  const edges = [];
  for (let i = 0; i < pts.length; i++) edges.push([pts[i], pts[(i + 1) % pts.length]]);
  return edges;
}

function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

document.getElementById('step').addEventListener('click', step);
document.getElementById('run').addEventListener('click', runAll);
document.getElementById('reset').addEventListener('click', () => { initRun(); render(); setStatus('Ready. Press Step to begin.', ''); });

initRun();
render();
Result
Console

Watch how fast the candidate set shrinks. A single farthest point can throw away dozens of others in one shot — that is the whole trick behind QuickHull's speed on typical inputs.

The Real Complexity

QuickHull's recursion looks like this: given a line segment and a set of points known to lie on one side of it, find the farthest point pp from that line, then recurse on the points outside segment (a, p) and outside segment (p, b), discarding everyone inside triangle (a, p, b).

  • Finding the farthest point among mm candidates costs O(m)O(m) — one linear scan.
  • On well-behaved, roughly-uniform point sets, each recursive split tends to throw away a constant fraction of the remaining points, giving a recurrence close to T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n), which resolves to the familiar O(nlog⁡n)O(n \log n) — exactly like quicksort's average case.
  • The hull itself only has hh points (often h≪nh \ll n), and a refined analysis shows QuickHull actually runs in O(nlog⁡h)O(n \log h) on average, adapting to how "round" versus "spiky" the input is.
  • Worst case is O(n2)O(n^2). If the points are arranged so the farthest-point split is always maximally lopsided — for instance, points densely packed along a slight curve — QuickHull degenerates just like quicksort does on an already-sorted array with a bad pivot rule.

This is the same story as P vs NP-adjacent algorithm design in miniature: an algorithm can be provably worst-case bad and still be the practical champion, because the bad inputs are rare and the good case is so cheap. Other convex hull algorithms guarantee O(nlog⁡n)O(n \log n) always — Graham scan sorts by angle first, divide-and-conquer hull merges recursively like merge sort — trading QuickHull's occasional worst case for a fixed sort-then-sweep cost every time.

Where It Matters

Finding the tightest boundary around a set of points is one of computational geometry's most reused building blocks:

  • Collision detection and physics engines: game and robotics engines approximate complex shapes with their convex hulls because hull-vs-hull collision tests are far cheaper than exact-mesh tests.
  • Geographic information systems: drawing the outer boundary of a set of GPS points — a country's territorial extent, a delivery zone, a wildlife range — is a direct convex hull computation.
  • Statistics and outlier detection: the hull's corner points are exactly the "extreme" observations in a dataset, useful for spotting outliers or defining a feasible region in optimization.
  • A building block for richer structures: Delaunay triangulation and Voronoi diagrams can both be derived from convex hull computations via a clever lift into one higher dimension.

Learn QuickHull and you've learned the divide-and-conquer pattern behind a large slice of computational geometry — the same pivot-and-recurse idea that powers closest pair of points.

Conclusion

QuickHull turns a geometric question — what is the tightest shape around this cloud of points? — into the same recursive rhythm as quicksort: pick an extreme, split the world in two, throw away what you no longer need, repeat. That rhythm is why it is usually so fast, and why, on the right adversarial input, it can be just as slow as the algorithm it imitates.

The next time you see a shrink-wrapped outline around a scatter of dots — in a game engine, a map, or a dataset — remember that some of the fastest algorithms in computational geometry work by relentlessly asking one question: which point sticks out the most?

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quickhull/Content licensed under CC BY-NC 4.0.