Convex Hull: Jarvis vs Graham

// Two convex hull algorithms on the same point set, panel-by-panel.
// Left: Jarvis march (gift wrapping), O(nh) — one hull vertex per beat.
// Right: Graham scan, O(n log n) — sort by polar angle, then stack scan.
// Click in either panel to add a point; both restart in lockstep.

let pts = [];
let J, Gr;

function cr(o, a, b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
function d2(a, b) { const dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; }

function resetJ() {
  if (pts.length < 3) { J = { hull: pts.map((_, i) => i), cur: -1, cand: -1, done: true, start: -1, tick: 0 }; return; }
  let lo = 0;
  for (let i = 1; i < pts.length; i++)
    if (pts[i].x < pts[lo].x || (pts[i].x === pts[lo].x && pts[i].y < pts[lo].y)) lo = i;
  J = { hull: [lo], cur: lo, start: lo, cand: -1, done: false, tick: 0 };
}

function stepJ() {
  if (J.done) return;
  let best = -1;
  for (let i = 0; i < pts.length; i++) {
    if (i === J.cur) continue;
    if (best === -1) { best = i; continue; }
    const c = cr(pts[J.cur], pts[best], pts[i]);
    if (c < 0 || (c === 0 && d2(pts[J.cur], pts[i]) > d2(pts[J.cur], pts[best]))) best = i;
  }
  J.cand = best;
  if (++J.tick >= 6) {
    J.cur = best; J.tick = 0;
    if (J.cur === J.start) { J.done = true; J.cand = -1; return; }
    J.hull.push(J.cur);
    if (J.hull.length > pts.length + 2) J.done = true;
  }
}

function resetG() {
  if (pts.length < 3) { Gr = { phase: "done", stack: pts.map((_, i) => i), order: [], i: 0, sortI: 0, pivot: -1, cand: -1 }; return; }
  let lo = 0;
  for (let i = 1; i < pts.length; i++)
    if (pts[i].y > pts[lo].y || (pts[i].y === pts[lo].y && pts[i].x < pts[lo].x)) lo = i;
  const piv = pts[lo], order = [];
  for (let i = 0; i < pts.length; i++) if (i !== lo) order.push(i);
  order.sort((a, b) => {
    const da = Math.atan2(pts[a].y - piv.y, pts[a].x - piv.x);
    const db = Math.atan2(pts[b].y - piv.y, pts[b].x - piv.x);
    return da !== db ? da - db : d2(piv, pts[a]) - d2(piv, pts[b]);
  });
  Gr = { phase: "sort", pivot: lo, order, sortI: 0, stack: [lo], i: 0, cand: order[0] };
}

function stepG() {
  if (Gr.phase === "done") return;
  if (Gr.phase === "sort") {
    Gr.sortI++;
    Gr.cand = Gr.order[Math.min(Gr.sortI, Gr.order.length - 1)];
    if (Gr.sortI >= Gr.order.length) Gr.phase = "scan";
    return;
  }
  if (Gr.i >= Gr.order.length) { Gr.phase = "done"; Gr.cand = -1; return; }
  const idx = Gr.order[Gr.i];
  Gr.cand = idx;
  while (Gr.stack.length >= 2) {
    const a = pts[Gr.stack[Gr.stack.length - 2]];
    const b = pts[Gr.stack[Gr.stack.length - 1]];
    if (cr(a, b, pts[idx]) <= 0) Gr.stack.pop(); else break;
  }
  Gr.stack.push(idx);
  Gr.i++;
}

function init({ width, height }) {
  const pw = width / 2, pad = 36;
  pts = [];
  for (let i = 0; i < 18; i++) {
    pts.push({ x: pad + Math.random() * (pw - 2 * pad), y: pad + Math.random() * (height - 2 * pad) });
  }
  resetJ(); resetG();
}

function poly(ctx, ox, ids, closed, color, lw) {
  if (ids.length < 2) return;
  ctx.strokeStyle = color; ctx.lineWidth = lw;
  ctx.beginPath();
  for (let i = 0; i < ids.length; i++) {
    const p = pts[ids[i]];
    if (i === 0) ctx.moveTo(ox + p.x, p.y); else ctx.lineTo(ox + p.x, p.y);
  }
  if (closed) ctx.closePath();
  ctx.stroke();
}

function dots(ctx, ox) {
  ctx.fillStyle = "#8a90b0";
  for (let i = 0; i < pts.length; i++) {
    const p = pts[i];
    ctx.beginPath(); ctx.arc(ox + p.x, p.y, 2.5, 0, Math.PI * 2); ctx.fill();
  }
}

function dot(ctx, ox, idx, color, r) {
  if (idx < 0) return;
  const p = pts[idx];
  ctx.fillStyle = color;
  ctx.beginPath(); ctx.arc(ox + p.x, p.y, r, 0, Math.PI * 2); ctx.fill();
}

function header(ctx, ox, label) {
  ctx.fillStyle = "#cfd2e0";
  ctx.font = "12px ui-sans-serif, system-ui, sans-serif";
  ctx.fillText(label, ox + 10, 18);
}

function drawJ(ctx, ox) {
  header(ctx, ox, "Jarvis march  O(nh)   hull " + J.hull.length + (J.done ? "  done" : ""));
  if (!J.done && J.cand >= 0 && J.cur >= 0) {
    const a = pts[J.cur], b = pts[J.cand];
    ctx.strokeStyle = "rgba(255,210,90,0.7)"; ctx.setLineDash([4, 3]); ctx.lineWidth = 1;
    ctx.beginPath(); ctx.moveTo(ox + a.x, a.y); ctx.lineTo(ox + b.x, b.y); ctx.stroke();
    ctx.setLineDash([]);
  }
  poly(ctx, ox, J.hull, J.done, "rgba(120,220,160,0.95)", 2);
  dots(ctx, ox);
  dot(ctx, ox, J.done ? -1 : J.cur, "#ffe28a", 4.5);
  dot(ctx, ox, J.done ? -1 : J.cand, "#ffb84d", 3.5);
}

function drawG(ctx, ox) {
  const label = Gr.phase === "sort"
    ? "Graham scan  O(n log n)  sort " + Gr.sortI + "/" + Gr.order.length
    : Gr.phase === "scan"
    ? "Graham scan  O(n log n)  scan " + Gr.i + "/" + Gr.order.length + "  |stack| " + Gr.stack.length
    : "Graham scan  O(n log n)  done  hull " + Gr.stack.length;
  header(ctx, ox, label);
  if (Gr.phase === "sort" && Gr.pivot >= 0) {
    const piv = pts[Gr.pivot];
    ctx.strokeStyle = "rgba(120,170,255,0.4)"; ctx.lineWidth = 1;
    ctx.beginPath();
    for (let i = 0; i < Gr.sortI && i < Gr.order.length; i++) {
      const p = pts[Gr.order[i]];
      ctx.moveTo(ox + piv.x, piv.y); ctx.lineTo(ox + p.x, p.y);
    }
    ctx.stroke();
  }
  poly(ctx, ox, Gr.stack, Gr.phase === "done", Gr.phase === "done" ? "rgba(120,220,160,0.95)" : "rgba(120,170,255,0.95)", 2);
  dots(ctx, ox);
  dot(ctx, ox, Gr.pivot, "#ff7aa8", 4.5);
  if (Gr.phase !== "done") dot(ctx, ox, Gr.cand, "#9cc7ff", 3.5);
}

function tick({ ctx, width: W, height: H, input }) {
  const pw = W / 2;
  for (const c of input.consumeClicks()) {
    let lx = c.x;
    if (c.x >= pw) lx = c.x - pw;
    if (lx < 6 || lx > pw - 6 || c.y < 26 || c.y > H - 6) continue;
    if (pts.length >= 120) pts.shift();
    pts.push({ x: lx, y: c.y });
    resetJ(); resetG();
  }
  stepJ();
  stepG(); stepG();

  ctx.fillStyle = "#05060c"; ctx.fillRect(0, 0, W, H);
  drawJ(ctx, 0);
  drawG(ctx, pw);
  ctx.strokeStyle = "#1a1d2a"; ctx.lineWidth = 2;
  ctx.beginPath(); ctx.moveTo(pw, 0); ctx.lineTo(pw, H); ctx.stroke();

  ctx.fillStyle = "rgba(220,225,255,0.6)";
  ctx.font = "11px ui-sans-serif, system-ui, sans-serif";
  ctx.fillText("click to add a point", 10, H - 8);
  ctx.fillText("n = " + pts.length, pw + 10, H - 8);
}