Graham Scan

Introduction

Scatter a handful of points on a page and ask for the convex hull — the tightest rubber band that wraps them all — and you need a plan for which points to keep and in what order to connect them. In 1972, mathematician Ronald Graham published a strikingly clean plan, now called the Graham scan.

The idea is almost sneaky in its simplicity: pick the lowest point as an anchor, sort every other point by the angle it makes with that anchor, and then walk through the sorted list carrying a stack. Each time the last three points on the stack would force a right turn, the middle one cannot be on the hull — pop it and check again. Keep going until only left turns remain.

No angles are ever recomputed mid-walk, no point is revisited more than a couple of times, and the sort dominates the running time: O(n log n), and provably as fast as any comparison-based algorithm can do this job.

Build the Hull

Click anywhere on the canvas to drop points. Once you have at least three, press Run Graham scan to watch it work: it finds the lowest point, sorts the rest by angle around it, then walks the sorted order one step at a time, popping the stack every time a right turn shows up.

<p class="hint">Click the canvas to add points (gray). Then run Graham scan: it picks the lowest point as a pivot, sorts every other point by angle around it, and sweeps through, pushing points onto a stack and popping the last one whenever it would create a right turn.</p>
<canvas id="board" class="board" width="560" height="360"></canvas>
<div class="status" id="status">Click to add at least 3 points.</div>
<div class="btns">
  <button id="run" type="button">Run Graham scan</button>
  <button id="step" type="button">Step</button>
  <button id="reset" type="button" class="ghost">Clear</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; }
.board { width: 100%; max-width: 560px; height: auto; aspect-ratio: 560 / 360; background: #f4f6f8;
         border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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: not-allowed; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const canvas = document.getElementById('board');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');
const runBtn = document.getElementById('run');
const stepBtn = document.getElementById('step');
const resetBtn = document.getElementById('reset');

let points = []; // all points placed by the user, in click order
let order = [];  // points sorted by angle around the pivot (built once, on run/first step)
let stack = [];  // the hull-so-far, as a stack of points
let cursor = 0;  // index of the next point in `order` to process
let phase = 'idle'; // idle -> running -> done
let lastPop = null; // the point most recently removed from the stack, for highlighting

function setStatus(t, cls) { statusEl.textContent = t; statusEl.className = 'status ' + (cls || ''); }

// Cross product sign test: > 0 left turn, < 0 right turn, 0 collinear.
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) { const dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; }

// Pick the lowest-then-leftmost point as pivot, sort the rest by polar angle (ties broken by distance).
function prepareOrder() {
  let pivot = points[0];
  for (const p of points) {
    if (p.y > pivot.y || (p.y === pivot.y && p.x < pivot.x)) pivot = p;
  }
  const rest = points.filter(p => p !== pivot);
  rest.sort((a, b) => {
    const c = cross(pivot, a, b);
    if (c !== 0) return -c; // sort counter-clockwise around the pivot
    return dist2(pivot, a) - dist2(pivot, b);
  });
  order = [pivot, ...rest];
  stack = [];
  cursor = 0;
  lastPop = null;
}

// Process the next point in angle order: pop every right turn, then push.
function advance() {
  if (cursor >= order.length) { phase = 'done'; finish(); return; }
  const p = order[cursor];
  lastPop = null;
  while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) {
    lastPop = stack.pop();
  }
  stack.push(p);
  cursor++;
  draw();
  if (lastPop) {
    setStatus(i18nFmt('Point #%n% caused a right turn — popped from the stack.', { n: lastPop.i }), '');
  } else {
    setStatus(i18nFmt('Point #%n% is a left turn — pushed onto the hull stack.', { n: p.i }), '');
  }
  if (cursor >= order.length) finish();
}

function finish() {
  phase = 'done';
  setStatus(i18nFmt('Hull closed with %n% point(s) on the boundary.', { n: stack.length }), 'ok');
  stepBtn.disabled = true;
  runBtn.disabled = true;
  draw();
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // draw the current stack as the hull-in-progress
  if (stack.length > 1) {
    ctx.beginPath();
    ctx.moveTo(stack[0].x, stack[0].y);
    for (let i = 1; i < stack.length; i++) ctx.lineTo(stack[i].x, stack[i].y);
    if (phase === 'done') ctx.closePath();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 2;
    ctx.stroke();
  }
  // draw every point; highlight the stack and the last popped point
  for (const p of points) {
    const onStack = stack.includes(p);
    ctx.beginPath();
    ctx.arc(p.x, p.y, 6, 0, Math.PI * 2);
    ctx.fillStyle = p === lastPop ? '#c92f3c' : (onStack ? '#1d3557' : '#8d99ae');
    ctx.fill();
  }
}

canvas.addEventListener('click', (e) => {
  if (phase !== 'idle') return;
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const x = (e.clientX - rect.left) * scaleX;
  const y = (e.clientY - rect.top) * scaleY;
  points.push({ x, y, i: points.length + 1 });
  draw();
  setStatus(i18nFmt('%n% point(s) placed.', { n: points.length }), '');
});

runBtn.addEventListener('click', () => {
  if (points.length < 3) { setStatus('Add at least 3 points first.', 'bad'); return; }
  if (phase === 'idle') { phase = 'running'; prepareOrder(); }
  // run every remaining step immediately
  while (cursor < order.length) advance();
});

stepBtn.addEventListener('click', () => {
  if (points.length < 3) { setStatus('Add at least 3 points first.', 'bad'); return; }
  if (phase === 'idle') { phase = 'running'; prepareOrder(); draw();
    setStatus('Order fixed by angle. Press Step to sweep one point at a time.', ''); return; }
  if (phase === 'running') advance();
});

resetBtn.addEventListener('click', () => {
  points = []; order = []; stack = []; cursor = 0; phase = 'idle'; lastPop = null;
  runBtn.disabled = false; stepBtn.disabled = false;
  draw();
  setStatus('Click to add at least 3 points.', '');
});

draw();

<p class="hint">Click the canvas to add points (gray). Then run Graham scan: it picks the lowest point as a pivot, sorts every other point by angle around it, and sweeps through, pushing points onto a stack and popping the last one whenever it would create a right turn.</p>
<canvas id="board" class="board" width="560" height="360"></canvas>
<div class="status" id="status">Click to add at least 3 points.</div>
<div class="btns">
  <button id="run" type="button">Run Graham scan</button>
  <button id="step" type="button">Step</button>
  <button id="reset" type="button" class="ghost">Clear</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; }
.board { width: 100%; max-width: 560px; height: auto; aspect-ratio: 560 / 360; background: #f4f6f8;
         border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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: not-allowed; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const canvas = document.getElementById('board');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');
const runBtn = document.getElementById('run');
const stepBtn = document.getElementById('step');
const resetBtn = document.getElementById('reset');

let points = []; // all points placed by the user, in click order
let order = [];  // points sorted by angle around the pivot (built once, on run/first step)
let stack = [];  // the hull-so-far, as a stack of points
let cursor = 0;  // index of the next point in `order` to process
let phase = 'idle'; // idle -> running -> done
let lastPop = null; // the point most recently removed from the stack, for highlighting

function setStatus(t, cls) { statusEl.textContent = t; statusEl.className = 'status ' + (cls || ''); }

// Cross product sign test: > 0 left turn, < 0 right turn, 0 collinear.
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) { const dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; }

// Pick the lowest-then-leftmost point as pivot, sort the rest by polar angle (ties broken by distance).
function prepareOrder() {
  let pivot = points[0];
  for (const p of points) {
    if (p.y > pivot.y || (p.y === pivot.y && p.x < pivot.x)) pivot = p;
  }
  const rest = points.filter(p => p !== pivot);
  rest.sort((a, b) => {
    const c = cross(pivot, a, b);
    if (c !== 0) return -c; // sort counter-clockwise around the pivot
    return dist2(pivot, a) - dist2(pivot, b);
  });
  order = [pivot, ...rest];
  stack = [];
  cursor = 0;
  lastPop = null;
}

// Process the next point in angle order: pop every right turn, then push.
function advance() {
  if (cursor >= order.length) { phase = 'done'; finish(); return; }
  const p = order[cursor];
  lastPop = null;
  while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) {
    lastPop = stack.pop();
  }
  stack.push(p);
  cursor++;
  draw();
  if (lastPop) {
    setStatus(i18nFmt('Point #%n% caused a right turn — popped from the stack.', { n: lastPop.i }), '');
  } else {
    setStatus(i18nFmt('Point #%n% is a left turn — pushed onto the hull stack.', { n: p.i }), '');
  }
  if (cursor >= order.length) finish();
}

function finish() {
  phase = 'done';
  setStatus(i18nFmt('Hull closed with %n% point(s) on the boundary.', { n: stack.length }), 'ok');
  stepBtn.disabled = true;
  runBtn.disabled = true;
  draw();
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // draw the current stack as the hull-in-progress
  if (stack.length > 1) {
    ctx.beginPath();
    ctx.moveTo(stack[0].x, stack[0].y);
    for (let i = 1; i < stack.length; i++) ctx.lineTo(stack[i].x, stack[i].y);
    if (phase === 'done') ctx.closePath();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 2;
    ctx.stroke();
  }
  // draw every point; highlight the stack and the last popped point
  for (const p of points) {
    const onStack = stack.includes(p);
    ctx.beginPath();
    ctx.arc(p.x, p.y, 6, 0, Math.PI * 2);
    ctx.fillStyle = p === lastPop ? '#c92f3c' : (onStack ? '#1d3557' : '#8d99ae');
    ctx.fill();
  }
}

canvas.addEventListener('click', (e) => {
  if (phase !== 'idle') return;
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const x = (e.clientX - rect.left) * scaleX;
  const y = (e.clientY - rect.top) * scaleY;
  points.push({ x, y, i: points.length + 1 });
  draw();
  setStatus(i18nFmt('%n% point(s) placed.', { n: points.length }), '');
});

runBtn.addEventListener('click', () => {
  if (points.length < 3) { setStatus('Add at least 3 points first.', 'bad'); return; }
  if (phase === 'idle') { phase = 'running'; prepareOrder(); }
  // run every remaining step immediately
  while (cursor < order.length) advance();
});

stepBtn.addEventListener('click', () => {
  if (points.length < 3) { setStatus('Add at least 3 points first.', 'bad'); return; }
  if (phase === 'idle') { phase = 'running'; prepareOrder(); draw();
    setStatus('Order fixed by angle. Press Step to sweep one point at a time.', ''); return; }
  if (phase === 'running') advance();
});

resetBtn.addEventListener('click', () => {
  points = []; order = []; stack = []; cursor = 0; phase = 'idle'; lastPop = null;
  runBtn.disabled = false; stepBtn.disabled = false;
  draw();
  setStatus('Click to add at least 3 points.', '');
});

draw();

Result

Console

Use Step to go one point at a time and see exactly when a pop happens — that's the moment the algorithm realizes a previously "promising" point was actually tucked inside the hull all along.

The Real Complexity

Graham scan's cost splits cleanly into two pieces:

The sort. Pick the point with the lowest $y$ -coordinate (breaking ties by lowest $x$ ) as the pivot $p_0$ . Sort the remaining $n-1$ points by the polar angle they make with $p_0$ , which costs $O(n \log n)$ with any comparison sort.
The scan. Walk the sorted points, keeping a stack of hull candidates. For each new point, test whether the last two stack entries and the new point form a right turn using the sign of a 2D cross product: $(p_1 - p_0) \times (p_2 - p_0) = (x_1 - x_0)(y_2 - y_0) - (y_1 - y_0)(x_2 - x_0)$ A non-positive result means a right turn (or straight line) — pop the middle point and test again with the new top of the stack. A positive result means a left turn — push the new point and move on.

The scan is $O(n)$ overall, not $O(n^2)$ , because every point is pushed exactly once and popped at most once — a classic amortized-analysis argument, the same trick that keeps a stack-based bracket matcher linear.

That leaves $O(n \log n)$ total, and this is not just a good algorithm — it is an optimal one. Any comparison-based convex hull algorithm needs $\Omega(n \log n)$ time in the worst case, because sorting itself can be reduced to computing a hull (arrange points on a parabola $y = x^2$ and the hull order is the sorted order). Graham scan meets that lower bound exactly, putting it in the same company as the sorting lower bound that any comparison sort must respect.

Where It Matters

Wrapping a point cloud in its tightest boundary shows up constantly once you start looking:

Collision detection and physics engines: convex shapes are cheap to test for overlap, so games and simulators wrap complex objects in their convex hull as a fast first check.
Geographic information systems: drawing the outer boundary of a set of sensor readings, GPS pings or territory markers is a direct convex hull query.
Pattern recognition and image processing: the hull of a cluster of feature points gives a robust outline for shape matching, even when a few points are noisy.
Robot motion planning: hulls of obstacles simplify path-finding, since avoiding a convex shape is far easier to reason about than avoiding an arbitrary polygon.

Learn Graham scan and you've learned the template for a whole family of geometric algorithms: reduce the input to a good order, then sweep it once with a simple local test — the same spirit behind building a minimum spanning tree by sweeping edges in sorted order.

Conclusion

Graham scan is a small masterpiece of algorithm design: reduce a geometric question to a sort, then answer it with one linear pass and a stack that only ever pushes or pops. No point is ever examined more times than the amortized analysis allows, and the whole thing lands exactly on the $\Omega(n \log n)$ floor that any comparison-based hull algorithm must respect.

So the next time you see an outline snapped tight around a scatter of points, remember it might just be a sorted angle list and a stack quietly throwing away every point that tried to poke outward and got left behind by a right turn. It's the same instinct that runs through the convex hull problem as a whole — order first, then sweep.

Comments

Loading comments...

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

Cookies & privacy

One sort, one stack, one convex hull