JSFiddle - React, Tailwind, and code Playground

by Darby Rathbone

JavaScript

function delaunayTriangulate(points) {
  // Super triangle (large triangle that contains all points)
  const minX = Math.min(...points.map(p => p[0]));
  const minY = Math.min(...points.map(p => p[1]));
  const maxX = Math.max(...points.map(p => p[0]));
  const maxY = Math.max(...points.map(p => p[1]));

  const dx = maxX - minX;
  const dy = maxY - minY;
  const deltaMax = Math.max(dx, dy);
  const midx = (minX + maxX) / 2;
  const midy = (minY + maxY) / 2;

  let triangles = [
    [
      points.push([midx - 20 * deltaMax, midy - deltaMax]) - 1,
      points.push([midx, midy + 20 * deltaMax]) - 1,
      points.push([midx + 20 * deltaMax, midy - deltaMax]) - 1
    ]
  ];

  function circumcircle([ax, ay], [bx, by], [cx, cy]) {
    const A = bx - ax, B = by - ay;
    const C = cx - ax, D = cy - ay;

    const E = A * (ax + bx) + B * (ay + by);
    const F = C * (ax + cx) + D * (ay + cy);
    const G = 2 * (A * (cy - by) - B * (cx - bx));

    if (Math.abs(G) < 1e-12) return null;

    const cx2 = (D * E - B * F) / G;
    const cy2 = (A * F - C * E) / G;

    const dx2 = cx2 - ax;
    const dy2 = cy2 - ay;
    const r2 = dx2 * dx2 + dy2 * dy2;

    return { x: cx2, y: cy2, r2 };
  }

  for (let p = 0; p < points.length - 3; p++) {
    const edges = [];
    const point = points[p];

    triangles = triangles.filter(t => {
      const cc = circumcircle(points[t[0]], points[t[1]], points[t[2]]);
      if (!cc) return true;

      const dx = point[0] - cc.x;
      const dy = point[1] - cc.y;
      const inside = dx * dx + dy * dy < cc.r2;

      if (!inside) return true;

      // Collect edges for re-triangulation
      edges.push([t[0], t[1]], [t[1], t[2]], [t[2], t[0]]);
      return false;
    });

    // Remove duplicate edges
    const uniqueEdges = edges.filter(
      (e1, _, arr) =>
        arr.filter(e2 => (e1[0] === e2[0] && e1[1] === e2[1]) ||
                         (e1[0] === e2[1] && e1[1]...