delaunay三角剖分 是一种根据点集获得满足一定良好性质的三角剖分方式，等价于 上举映射(lifting map) 后，其 下凸壳（Lower Convex Hull） 在原平面的投影。如果点集中不存在四点共圆的情况（退化情况），Delaunay 三角剖分是唯一的。

1. 定义和性质

定义：

• delaunay 三角剖分： 三角形的外接圆（不包括边界，以下的讨论都不包括边界）内不包含其他顶点。（空球性质）
• 边是delaunay的： 边存在不包含其他顶点的外接圆。
• 边是局部delaunay的：边存在不包含包含该边的三角形的其他顶点的外接圆。严谨的说法：如果边 $e$ 是两个三角形 $T_1, T_2$ 的公共边，且这两个三角形组成一个凸四边形，那么 $e$ 是局部 Delaunay 的，当且仅当 $T_1$ 的顶点不在 $T_2$ 的外接圆内（反之亦然）。如果组成的四边形是凹的，则该边默认满足局部 Delaunay。

性质：

• 最大化最小角 (Max-Min Angle)： 在所有可能的三角剖分中，Delaunay 剖分的最小角是最大的。
• 唯一性： 如果点集中不存在四点共圆的情况，Delaunay 三角剖分是唯一的。

2. Delaunay引理

以下三条性质等价：

• (a) delaunay 三角剖分
• (b) 每条边都是delaunay的
• (c) 每条边都是局部delaunay的

证明：

• (a) => (b): 由定义，因为是delaunay三角剖分，所以三角形的外接圆都能表明任意边都是delaunay的。
• (b) => (c): 边是delaunay的 => 边是局部delaunay的
• (c) => (a): 上举映射(lifting map)，将平面上的点映射到抛物面 $z = x^2 + y^2$ ，则平面上的圆映射为平面（圆方程带入z）与抛物面的交线。每条边都是局部delaunay的即每个点在抛物面上都是局部凸的（所有点都在该外接圆映射的平面上或上方），而局部凸=>全局凸，得证。（三角形的外接圆=>平面，相邻的平面总是向上折的）

3. 算法

• Lawson算法（增量算法）（三维及以上不好扩展）
  • 先在包围盒构造俩大三角形
  • 依次加点进去连成三角形，如果加入点之后，有边不是局部delaunay的，则翻转边（四边形的对角线换成另外一条对角线，之前对顶角之和大于180，翻转后小于180）。
  • 删去构造的包围盒已经连接的边。
• Bowyer-Watson算法（增量算法）
  • 基本同Lawson算法，但是加入点之后先删除不再是delaunay的边（或者实现上，内部边：外接球包含新增点的三角形的共用边），形成Delaunay Cavity，再直接星形连接。
• 上举映射后求凸包（因为求凸包有健全的库）

附：

In-circle Test 的行列式（上举映射后判断点与平面的相对位置）
：比直接计算几何中心更稳健。

$$\det \begin{vmatrix} A_x & A_y & A_x^2 + A_y^2 & 1 \\ B_x & B_y & B_x^2 + B_y^2 & 1 \\ C_x & C_y & C_x^2 + C_y^2 & 1 \\ D_x & D_y & D_x^2 + D_y^2 & 1 \end{vmatrix}$$

4. Voronoi 图

Voronoi 图是 Delaunay 图的对偶图。Delaunay图外接圆圆心(三角形<->点)的连线（边<->边）得到(点<->面)。

上举映射的抛物面上，点的切面形成的包络面映射回平面也能得到 Voronoi 图。因为平面上的点到抛物面的距离减去切平面的距离等于该点到站点距离的平方：

设站点为 $P_i = (x_i, y_i)$ ，抛物面为 $f(P) = |P|^2$ 。在 $P_i$ 处的切平面方程为：

$$z = L_i(x, y) = 2x_i x + 2y_i y - (x_i^2 + y_i^2)$$

对于任意点 $P(x, y)$ ，抛物面高度与切平面高度之差为：

$$\begin{aligned} f(P) - L_i(P) &= (x^2 + y^2) - (2x_i x + 2y_i y - x_i^2 - y_i^2) \\ &= (x-x_i)^2 + (y-y_i)^2 \\ &= \|P - P_i\|^2 \end{aligned}$$

这个差值正好是 $P$ 到 $P_i$ 的欧几里得距离的平方。

结论： 离 $P$ 最近的站点 $P_i$ ，对应的正是那个让切平面高度最高的 $L_i$ 。因此，Voronoi 图就是这些切平面组成的 上包络面（Upper Envelope） 的投影。

参考

1. 技术分享：Delaunay三角剖分算法介绍 - 知乎
2. Delaunay triangulation, Wikipidea