Delaunay Triangulation: Definition, Properties, and Divide‑and‑Conquer Algorithm Implementation in TypeScript

Delaunay triangulation (DT) is a way to divide a set of points P into triangles such that no point lies inside the circumcircle of any triangle, which avoids skinny triangles and yields high‑quality meshes widely used in 3D rendering, image processing, and artificial intelligence.

Definition : The triangulation is unique when no four points are cocircular, and each triangle’s circumcircle contains no other points from P.

Empty‑circle property: DT(P) is unique; no other point lies inside any triangle’s circumcircle.

Maximize the minimum angle: among all possible triangulations, Delaunay maximizes the smallest angle of the triangles.

The outer edges form the convex hull of the point set.

Edges never intersect; each triangle is formed by the three nearest points.

The result is independent of the construction order (provided no four points are cocircular).

Local updates affect only neighboring triangles when a point is added, removed, or moved.

Delaunay triangulation is the dual of the Voronoi diagram.

Algorithm (Divide‑and‑Conquer) : The method recursively splits the sorted point set (by x‑coordinate) until subsets contain at most three points, triangulates these base cases, and then merges the left and right triangulations. Merging involves selecting a base edge (the lowest edge that does not intersect either side), finding candidate points that form angles less than 180° with the base edge and whose circumcircles contain no other points, and repeatedly adding new base edges while deleting intersecting edges until no candidates remain.

The main steps are:

Sort all points by x‑coordinate.

Recursively split the array into two halves until each subset has ≤3 points.

Triangulate each small subset directly.

Merge the two triangulations by repeatedly finding a base edge, selecting the next candidate point on each side using cross‑product and in‑circle tests, updating the base edge, and removing intersecting edges.

Code Implementation (TypeScript) :

/**
 * 下面有几个工具函数没有列出，这里说明一下
 * dist(a, b) - 计算两点之间的距离
 * cross(0, a, b) - 计算向量OA和OB的叉积
 * inCircle(a, b, c, p) - 点P是否在点a,b,c三点的外接圆内
 * intersection(a, b, c, d) - 判断线段ab，cd是否相交
 */
function delaunayTriangulation(l: number, r: number, points: Point[], edges: Edge[]) {
  if (r - l <= 2) {
    // 将所有的点两两相连
    for (let i = l; i <= r; i++) {
      for (let j = i + 1; j <= r; j++) {
        addEdge(i, j, edges);
      }
    }
    return;
  }
  let mid = ~~((l + r) / 2);
  delaunayTriangulation(l, mid, points, edges);
  delaunayTriangulation(mid + 1, r, points, edges);
  let founded = false;
  let currentL = l,
    currentR = r;
  // 查找基线(base edge)
  while (!founded) {
    founded = true;
    const pL = points[currentL],
      pR = points[currentR];
    // 查找左子集最底部的点
    for (let i = 0; i < edges[currentL].next.length; i++) {
      const tIdx = edges[currentL].next[i];
      const t = points[tIdx];
      const d = cross(pR, pL, t);
      if (d > 0 || (d === 0 && dist(pR, t) < dist(pR, pL))) {
        currentL = tIdx;
        founded = false;
        break;
      }
    }
    if (!founded) continue;
    // 查找右子集最底部的点
    for (let i = 0; i < edges[currentR].next.length; i++) {
      const tIdx = edges[currentR].next[i];
      const t = points[tIdx];
      const d = dir(pL, pR, t);
      if (d < 0 || (d === 0 && dist(pL, t) < dist(pR, pL))) {
        currentR = tIdx;
        founded = false;
        break;
      }
    }
  }
  // 添加base edge
  addEdge(currentL, currentR, edges);
  while (true) {
    const pL = points[currentL],
      pR = points[currentR];
    let potential = -1,
      side = 0;
    // 查找可能点， 可能点与base edge小于180°， 可能点和base edge两个端点构成的圆内不能包含其他的点
    for (let i = 0; i < edges[currentL].next.length; i++) {
      const tIdx = edges[currentL].next[i];
      const t = points[tIdx];
      if (cross(pL, pR, t) > 0 && (potential == -1 || inCircle(pL, pR, points[potential], points[tIdx]) < 0)) {
        potential = tIdx;
        side = -1;
      }
    }
    for (let i = 0; i < edges[currentR].next.length; i++) {
      const tIdx = edges[currentR].next[i];
      const t = points[tIdx];
      if (cross(pR, t, pL) > 0 && (potential == -1 || inCircle(pL, pR, points[potential], points[tIdx]) < 0)) {
        potential = tIdx;
        side = 1;
      }
    }
    if (potential == -1) break;
    // 删除与下一条base edge相交的边
    if (side == -1) {
      for (let i = 0; i < edges[currentL].next.length; i++) {
        const tIdx = edges[currentL].next[i];
        const t = points[tIdx];
        if (intersection(pL, t, pR, points[potential])) {
          edges[currentL].next.splice(i, 1);
          i--;
        }
      }
      currentL = potential;
    } else {
      for (let i = 0; i < edges[currentR].next.length; i++) {
        const tIdx = edges[currentR].next[i];
        const t = points[tIdx];
        if (intersection(pR, t, pL, points[potential])) {
          edges[currentR].next.splice(i, 1);
          i--;
        }
      }
      currentR = potential;
    }
    addEdge(currentL, currentR, edges);
  }
}

For further reading, see the Wikipedia page on Delaunay triangulation and the University of Illinois geometry project links provided at the end of the article.