Introduction

Scatter a handful of points on a page and connect them into triangles so that the triangles tile the whole convex region without overlapping. There are usually many ways to do this — and most of them are ugly. You get long, needle-thin triangles with angles close to 0° and 180°, the kind that make terrain meshes look jagged and finite-element simulations blow up numerically.

Among all those choices, one triangulation stands out. Named after the Russian mathematician Boris Delaunay, who described it in 1934, the Delaunay triangulation obeys a single elegant local rule: draw the circle that passes through the three corners of every triangle (its circumcircle), and make sure no other point of the set ever falls inside it.

That one condition — empty circumcircles, everywhere — is enough to single out a triangulation that is, in a precise sense, the "roundest" one possible. It avoids skinny triangles automatically, without ever mentioning angles at all.

Flip the Edges

Click anywhere to add a point. As soon as there are enough points, the demo triangulates them and shows every triangle's circumcircle. Any edge shared by two triangles whose circumcircle contains the opposite corner is illegal — flipping it (swapping the shared diagonal of the resulting quadrilateral) removes the violation.

<p class="hint">Click the canvas to drop points. The demo triangulates them instantly (always a valid mesh) and outlines any <b>illegal</b> edge in red — an edge whose neighboring triangle’s circumcircle isn’t empty. Flip edges to chase the empty-circumcircle rule until every edge is legal: that final mesh is the Delaunay triangulation.</p>
<svg id="canvas" class="canvas" viewBox="0 0 500 320" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Click the canvas to add points, or load the sample.</div>
<div class="btns">
  <button id="sample" type="button">Load sample points</button>
  <button id="scramble" type="button">Scramble (make it non-Delaunay)</button>
  <button id="flip" type="button">Flip one illegal edge</button>
  <button id="autofix" type="button">Auto-fix all</button>
  <button id="circles" type="button" class="ghost">Toggle circumcircles</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 .6rem; line-height: 1.45; }
.canvas { width: 100%; max-width: 500px; height: auto; aspect-ratio: 500 / 320; background: #f4f6f8;
          border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; touch-action: manipulation; }
.edge { stroke: #1d3557; stroke-width: 1.6; }
.edge.illegal { stroke: #e63946; stroke-width: 2.2; }
.circ { fill: none; stroke: #6d9dc5; stroke-width: 1; stroke-dasharray: 3 2; opacity: .55; }
.pt { fill: #1d3557; stroke: #fff; stroke-width: 1.4; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const svgNS = 'http://www.w3.org/2000/svg';
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const W = 500, H = 320;

// Circumcircle of a triangle via the standard determinant formula.
function circumcircle(a, b, c) {
  const ax = a.x, ay = a.y, bx = b.x, by = b.y, cx = c.x, cy = c.y;
  const d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
  if (Math.abs(d) < 1e-9) return null;
  const ux = ((ax*ax+ay*ay)*(by-cy) + (bx*bx+by*by)*(cy-ay) + (cx*cx+cy*cy)*(ay-by)) / d;
  const uy = ((ax*ax+ay*ay)*(cx-bx) + (bx*bx+by*by)*(ax-cx) + (cx*cx+cy*cy)*(bx-ax)) / d;
  return { x: ux, y: uy, r: Math.hypot(ux - ax, uy - ay) };
}
function inCircumcircle(p, a, b, c) {
  const cc = circumcircle(a, b, c);
  if (!cc) return false;
  return Math.hypot(p.x - cc.x, p.y - cc.y) < cc.r - 1e-7; // strictly inside, with a small epsilon to avoid float noise on cocircular points
}
function cross(o, a, b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
// A flip is only geometrically safe if the quadrilateral a-p1-b-p2 formed by the two triangles is convex.
function quadIsConvex(pts, a, b, p1, p2) {
  const q = [pts[a], pts[p1], pts[b], pts[p2]];
  let sign = 0;
  for (let i = 0; i < 4; i++) {
    const cr = cross(q[i], q[(i+1)%4], q[(i+2)%4]);
    if (Math.abs(cr) < 1e-9) continue;
    const s = Math.sign(cr);
    if (sign === 0) sign = s; else if (s !== sign) return false;
  }
  return true;
}

let points = []; // array of {x,y} in SVG coordinates
let tris = [];   // array of [i,j,k] index triples into points
let showCircles = false;

// Undirected edge key so edge (a,b) and (b,a) map to the same entry.
function key(a, b) { return a < b ? a + '_' + b : b + '_' + a; }
function edgeToTris(list) {
  const map = new Map();
  list.forEach((t, ti) => {
    [[t[0],t[1]],[t[1],t[2]],[t[2],t[0]]].forEach(([a,b]) => {
      const k = key(a,b);
      if (!map.has(k)) map.set(k, []);
      map.get(k).push(ti);
    });
  });
  return map;
}
function opposite(t, a, b) { return t.find(v => v !== a && v !== b); }
function isLegalEdge(list, ti1, ti2, a, b) {
  const p1 = opposite(list[ti1], a, b), p2 = opposite(list[ti2], a, b);
  return !inCircumcircle(points[p2], points[a], points[b], points[p1]) &&
         !inCircumcircle(points[p1], points[a], points[b], points[p2]);
}
function flipEdge(list, ti1, ti2, a, b) {
  const p1 = opposite(list[ti1], a, b), p2 = opposite(list[ti2], a, b);
  list[ti1] = [a, p1, p2];
  list[ti2] = [b, p1, p2];
}

// Bowyer-Watson incremental construction: insert points one at a time, remove triangles whose circumcircle contains the new point, and re-triangulate the resulting hole. A giant super-triangle keeps every real point inside a single starting triangle.
function triangulate(pts) {
  const superPts = [{x:-2000,y:-2000},{x:6000,y:-2000},{x:2000,y:6000}];
  const all = pts.concat(superPts);
  const n = pts.length;
  const superIdx = [n, n+1, n+2];
  let list = [[superIdx[0], superIdx[1], superIdx[2]]];
  for (let pi = 0; pi < n; pi++) {
    const p = all[pi];
    const bad = [];
    list.forEach((t, ti) => { if (inCircumcircle(p, all[t[0]], all[t[1]], all[t[2]])) bad.push(ti); });
    const edgeCount = new Map();
    bad.forEach(ti => {
      const t = list[ti];
      [[t[0],t[1]],[t[1],t[2]],[t[2],t[0]]].forEach(([a,b]) => {
        const k = key(a,b);
        edgeCount.set(k, (edgeCount.get(k)||0)+1);
      });
    });
    const boundary = [];
    bad.forEach(ti => {
      const t = list[ti];
      [[t[0],t[1]],[t[1],t[2]],[t[2],t[0]]].forEach(([a,b]) => {
        if (edgeCount.get(key(a,b)) === 1) boundary.push([a,b]);
      });
    });
    list = list.filter((_, ti) => !bad.includes(ti));
    boundary.forEach(([a,b]) => list.push([a, b, pi]));
  }
  return { tris: list.filter(t => !t.some(v => superIdx.includes(v))), all };
}

function findIllegalEdge() {
  const map = edgeToTris(tris);
  for (const [k, list] of map.entries()) {
    if (list.length !== 2) continue;
    const [a, b] = k.split('_').map(Number);
    if (!isLegalEdge(tris, list[0], list[1], a, b)) return { a, b, ti1: list[0], ti2: list[1] };
  }
  return null;
}

function scramble() {
  // Pick a random internal edge and flip it (only if the resulting quadrilateral stays convex) purely to demonstrate what a non-Delaunay-but-still-valid triangulation looks like.
  let flips = 0;
  const target = Math.min(3, Math.max(0, tris.length));
  for (let s = 0; s < target * 4 && flips < target; s++) {
    // Re-scan edges fresh after every flip, since a flip changes which triangles occupy which slots.
    const map = edgeToTris(tris);
    const candidates = [...map.entries()].filter(([,list]) => list.length === 2);
    if (!candidates.length) break;
    const [k, list] = candidates[Math.floor(Math.random() * candidates.length)];
    const [a, b] = k.split('_').map(Number);
    const p1 = opposite(tris[list[0]], a, b), p2 = opposite(tris[list[1]], a, b);
    if (quadIsConvex(points, a, b, p1, p2)) {
      flipEdge(tris, list[0], list[1], a, b);
      flips++;
    }
  }
  return flips;
}

function rebuild() {
  const { tris: t } = triangulate(points);
  tris = t;
}

function render() {
  const svg = document.getElementById('canvas');
  svg.innerHTML = '';
  const illegal = findIllegalEdge();
  if (showCircles) {
    tris.forEach(t => {
      const cc = circumcircle(points[t[0]], points[t[1]], points[t[2]]);
      if (!cc) return;
      const c = document.createElementNS(svgNS, 'circle');
      c.setAttribute('cx', cc.x); c.setAttribute('cy', cc.y); c.setAttribute('r', cc.r);
      c.setAttribute('class', 'circ');
      svg.appendChild(c);
    });
  }
  const map = edgeToTris(tris);
  map.forEach((list, k) => {
    const [a, b] = k.split('_').map(Number);
    const line = document.createElementNS(svgNS, 'line');
    line.setAttribute('x1', points[a].x); line.setAttribute('y1', points[a].y);
    line.setAttribute('x2', points[b].x); line.setAttribute('y2', points[b].y);
    const isIllegal = illegal && list.length === 2 &&
      ((illegal.a === a && illegal.b === b) || (illegal.a === b && illegal.b === a));
    line.setAttribute('class', 'edge' + (isIllegal ? ' illegal' : ''));
    svg.appendChild(line);
  });
  points.forEach(p => {
    const c = document.createElementNS(svgNS, 'circle');
    c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 5);
    c.setAttribute('class', 'pt');
    svg.appendChild(c);
  });
}

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

function refreshStatus() {
  if (points.length < 3) { setStatus('Add at least 3 points to form a triangle.', ''); return; }
  const bad = findIllegalEdge();
  if (bad) setStatus('Illegal edge found (red) — its circumcircle isn’t empty. Flip it!', 'bad');
  else setStatus('✓ Every edge is legal — this is the Delaunay triangulation.', 'ok');
}

function addPoint(x, y) {
  points.push({ x, y });
  rebuild();
  render();
  refreshStatus();
}

document.getElementById('canvas').addEventListener('click', (e) => {
  const rect = e.currentTarget.getBoundingClientRect();
  const x = (e.clientX - rect.left) * (W / rect.width);
  const y = (e.clientY - rect.top) * (H / rect.height);
  addPoint(Math.round(x), Math.round(y));
});

document.getElementById('sample').addEventListener('click', () => {
  points = [{x:80,y:70},{x:420,y:60},{x:250,y:90},{x:60,y:250},{x:430,y:260},
            {x:250,y:230},{x:150,y:160},{x:340,y:170}];
  rebuild();
  render();
  refreshStatus();
});

document.getElementById('scramble').addEventListener('click', () => {
  if (tris.length < 2) { setStatus('Add at least 3 points to form a triangle.', ''); return; }
  const flips = scramble();
  render();
  if (flips > 0) setStatus(fmt('Scrambled %n% edge(s) into illegal flips. Fix them below.', { n: flips }), 'bad');
  else refreshStatus();
});

document.getElementById('flip').addEventListener('click', () => {
  const bad = findIllegalEdge();
  if (!bad) { refreshStatus(); return; }
  flipEdge(tris, bad.ti1, bad.ti2, bad.a, bad.b);
  render();
  refreshStatus();
});

document.getElementById('autofix').addEventListener('click', () => {
  let flips = 0, guard = 0;
  let bad = findIllegalEdge();
  while (bad && guard < 500) {
    flipEdge(tris, bad.ti1, bad.ti2, bad.a, bad.b);
    flips++; guard++;
    bad = findIllegalEdge();
  }
  render();
  if (flips > 0) setStatus(fmt('✓ Auto-fixed %n% illegal edge(s) — now fully Delaunay.', { n: flips }), 'ok');
  else refreshStatus();
});

document.getElementById('circles').addEventListener('click', () => {
  showCircles = !showCircles;
  render();
});

document.getElementById('reset').addEventListener('click', () => {
  points = []; tris = []; showCircles = false;
  render();
  setStatus('Click the canvas to add points, or load the sample.', '');
});

render();
Result
Console

Press Flip illegal edges to run the classic local-improvement rule one edge at a time, or Auto-fix all to relax the whole mesh at once. Watch how a single flip can shrink a needle-thin triangle into two much rounder ones — and how the circumcircles empty out as the mesh converges to the Delaunay triangulation.

The Real Complexity

Delaunay triangulation is one of computational geometry's genuine success stories — solved, optimal, and provably so.

  • The angle-maximizing property. Among all possible triangulations of a point set, the Delaunay triangulation maximizes the smallest angle that appears anywhere in the mesh. If you sort every angle from every triangulation from smallest to largest, no triangulation beats Delaunay's worst angle. This single fact is why it produces such well-shaped triangles.
  • Local checks, global result. Whether an edge is legal depends only on the two triangles that share it: for a shared edge with opposite corners pp and qq, the edge is legal exactly when qq lies outside the circumcircle of the triangle containing pp (and vice versa). Lawson's algorithm (1977) starts from any triangulation and repeatedly flips illegal edges — a purely local fix — until none remain, and this always terminates at the Delaunay triangulation, unique up to ties.
  • Optimal running time. Building it from scratch is no harder than sorting: randomized incremental insertion and Fortune's sweep-line algorithm (1987) both run in O(nlog⁡n)O(n \log n) time, which is optimal, since the triangulation of nn points contains enough information to sort them.
  • The exact dual of a solved problem. Every edge of the Delaunay triangulation corresponds to two neighboring regions of the Voronoi diagram — the two structures determine each other completely. Whatever you can say about one, you can say about the other.

No NP-hardness lurks here. The interesting content is entirely in the proof that a simple local rule (empty circumcircles) forces a global optimum (max-min angle) — a small miracle of geometry, not a computational obstacle.

Where It Matters

Avoiding skinny triangles sounds like a cosmetic concern, but it decides whether entire numerical methods succeed or fail:

  • Finite-element simulation: solvers for stress, heat and fluid flow lose accuracy — sometimes catastrophically — on needle-thin elements, which is why mesh generators build on Delaunay triangulation and its angle guarantee.
  • Terrain and 3D surface reconstruction: turning a cloud of elevation samples or a LIDAR scan into a realistic surface starts by Delaunay-triangulating the points, so the resulting mesh has no thin, spiky artifacts.
  • Geographic and spatial analysis: because the Delaunay triangulation is the dual of the Voronoi diagram, it is a natural tool for interpolation, nearest-neighbor queries and network design over scattered geographic data.
  • Computer graphics and games: procedural terrain, navigation meshes for pathfinding, and surface reconstruction from 3D scans all lean on the same empty-circumcircle idea.

Any time a real-world computation depends on well-shaped triangles from an arbitrary set of points — and the geometry problem of Closest Pair shows how much structure a plain scatter of points can hide — Delaunay triangulation is the default, dependable answer.

Conclusion

The Delaunay triangulation is what happens when a single local, checkable rule — keep every circumcircle empty — turns out to have an enormous global consequence: the smallest angle anywhere in the mesh is as large as it can possibly be. No search, no compromise, no NP-hardness. Just flip the illegal edges and the best-shaped triangulation falls out on its own.

It is a reminder that not every hard-sounding geometric question is intractable — sometimes the elegant answer and the efficient algorithm are exactly the same thing, running in optimal O(nlog⁡n)O(n \log n) time and quietly holding up meshes, maps and simulations everywhere.

Share this article

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

Comments

Loading comments...

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