Voronoi vs Delaunay

const N = 20;
const R = 9;
let pts = [];
let dragIdx = -1;
let dragOff = { x: 0, y: 0 };
let bw = 0, bh = 0;

function init({ width, height }) {
  pts = [];
  bw = width; bh = height;
  const pad = 40;
  for (let i = 0; i < N; i++) {
    pts.push({
      x: pad + Math.random() * (width - 2 * pad),
      y: pad + Math.random() * (height - 2 * pad),
    });
  }
  dragIdx = -1;
}

function circumcircle(ax, ay, bx, by, cx, cy) {
  const d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
  if (Math.abs(d) < 1e-10) return null;
  const a2 = ax * ax + ay * ay;
  const b2 = bx * bx + by * by;
  const c2 = cx * cx + cy * cy;
  const ux = (a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)) / d;
  const uy = (a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)) / d;
  const dx = ax - ux, dy = ay - uy;
  return { x: ux, y: uy, r2: dx * dx + dy * dy };
}

function bowyerWatson(points, width, height) {
  // Super-triangle large enough to contain all points
  const M = Math.max(width, height) * 20;
  const cxs = width / 2, cys = height / 2;
  const st = [
    { x: cxs - M, y: cys + M },     // index N
    { x: cxs + M, y: cys + M },     // index N+1
    { x: cxs,     y: cys - M },     // index N+2
  ];
  // mutable copy with super-triangle vertices appended
  const verts = points.slice();
  const sBase = verts.length;
  verts.push(st[0], st[1], st[2]);

  let tris = [];
  const t0 = makeTri(verts, sBase, sBase + 1, sBase + 2);
  if (t0) tris.push(t0);

  for (let i = 0; i < points.length; i++) {
    const p = verts[i];
    const bad = [];
    const remain = [];
    for (let t = 0; t < tris.length; t++) {
      const tri = tris[t];
      const dx = p.x - tri.cc.x, dy = p.y - tri.cc.y;
      if (dx * dx + dy * dy < tri.cc.r2) bad.push(tri); else remain.push(tri);
    }
    // build polygon hole: edges that appear in exactly one bad triangle
    const edges = [];
    for (let b = 0; b < bad.length; b++) {
      const t = bad[b];
      pushEdge(edges, t.a, t.b);
      pushEdge(edges, t.b, t.c);
      pushEdge(edges, t.c, t.a);
    }
    tris = remain;
    for (let e = 0; e < edges.length; e++) {
      if (edges[e].count !== 1) continue;
      const nt = makeTri(verts, edges[e].u, edges[e].v, i);
      if (nt) tris.push(nt);
    }
  }
  // strip triangles containing super-triangle vertices
  const out = [];
  for (let t = 0; t < tris.length; t++) {
    const tr = tris[t];
    if (tr.a >= sBase || tr.b >= sBase || tr.c >= sBase) continue;
    out.push(tr);
  }
  return out;
}

function makeTri(verts, a, b, c) {
  const va = verts[a], vb = verts[b], vc = verts[c];
  const cc = circumcircle(va.x, va.y, vb.x, vb.y, vc.x, vc.y);
  if (!cc) return null;
  return { a, b, c, cc };
}

function pushEdge(edges, u, v) {
  const lo = u < v ? u : v, hi = u < v ? v : u;
  for (let i = 0; i < edges.length; i++) {
    if (edges[i].u === lo && edges[i].v === hi) { edges[i].count++; return; }
  }
  edges.push({ u: lo, v: hi, count: 1 });
}

function tick({ ctx, width, height, input }) {
  bw = width; bh = height;

  // input: drag handling
  if (input.mouseDown) {
    if (dragIdx === -1) {
      let best = -1, bestD = (R + 8) * (R + 8);
      for (let i = 0; i < pts.length; i++) {
        const dx = pts[i].x - input.mouseX, dy = pts[i].y - input.mouseY;
        const d2 = dx * dx + dy * dy;
        if (d2 < bestD) { bestD = d2; best = i; }
      }
      if (best >= 0) {
        dragIdx = best;
        dragOff.x = pts[best].x - input.mouseX;
        dragOff.y = pts[best].y - input.mouseY;
      }
    } else {
      pts[dragIdx].x = Math.max(4, Math.min(width - 4, input.mouseX + dragOff.x));
      pts[dragIdx].y = Math.max(4, Math.min(height - 4, input.mouseY + dragOff.y));
    }
  } else {
    dragIdx = -1;
  }

  // recompute Delaunay every frame (N=20 is cheap)
  const tris = bowyerWatson(pts, width, height);

  // background
  ctx.fillStyle = "#0b1020";
  ctx.fillRect(0, 0, width, height);

  // Voronoi edges: for each Delaunay edge shared by two triangles, draw
  // the segment between their circumcenters.
  const edgeMap = new Map();
  for (let t = 0; t < tris.length; t++) {
    const tr = tris[t];
    addEdgeMap(edgeMap, tr.a, tr.b, t);
    addEdgeMap(edgeMap, tr.b, tr.c, t);
    addEdgeMap(edgeMap, tr.c, tr.a, t);
  }
  ctx.strokeStyle = "rgba(90,160,255,0.85)";
  ctx.lineWidth = 1.4;
  ctx.beginPath();
  edgeMap.forEach((arr) => {
    if (arr.length === 2) {
      const c1 = tris[arr[0]].cc, c2 = tris[arr[1]].cc;
      ctx.moveTo(c1.x, c1.y);
      ctx.lineTo(c2.x, c2.y);
    }
  });
  ctx.stroke();

  // Delaunay edges in soft orange
  ctx.strokeStyle = "rgba(255,170,90,0.55)";
  ctx.lineWidth = 1;
  ctx.beginPath();
  edgeMap.forEach((_, key) => {
    const u = key >>> 16, v = key & 0xffff;
    const a = pts[u], b = pts[v];
    if (!a || !b) return;
    ctx.moveTo(a.x, a.y);
    ctx.lineTo(b.x, b.y);
  });
  ctx.stroke();

  // sites
  for (let i = 0; i < pts.length; i++) {
    const p = pts[i];
    const hot = i === dragIdx;
    ctx.fillStyle = hot ? "#fff5d6" : "#e8ecff";
    ctx.beginPath();
    ctx.arc(p.x, p.y, hot ? R + 1 : R - 2, 0, Math.PI * 2);
    ctx.fill();
    ctx.strokeStyle = "rgba(0,0,0,0.5)";
    ctx.lineWidth = 1;
    ctx.stroke();
  }

  // HUD
  ctx.fillStyle = "rgba(0,0,0,0.45)";
  ctx.fillRect(8, 8, 240, 56);
  ctx.fillStyle = "rgba(90,160,255,1)";
  ctx.fillRect(14, 18, 14, 3);
  ctx.fillStyle = "#e8ecff";
  ctx.font = "12px ui-sans-serif, system-ui, sans-serif";
  ctx.fillText("Voronoi cell edges", 34, 22);
  ctx.fillStyle = "rgba(255,170,90,1)";
  ctx.fillRect(14, 34, 14, 3);
  ctx.fillStyle = "#e8ecff";
  ctx.fillText("Delaunay triangulation", 34, 38);
  ctx.fillStyle = "rgba(220,225,255,0.7)";
  ctx.fillText("drag any point", 14, 56);
}

function addEdgeMap(map, u, v, triIdx) {
  const lo = u < v ? u : v, hi = u < v ? v : u;
  const key = (lo << 16) | hi;
  const arr = map.get(key);
  if (arr) arr.push(triIdx); else map.set(key, [triIdx]);
}