Delaunay 三角剖分 | Codeboy's Blog

形式陈述

在带标准 Euclidean 内积的实平面上，设 $S$ 为有限且不全共线的点集。Delaunay 三角剖分是一份顶点集恰为 $S$ 的直线平面嵌入：其有界面均为非退化三角形，这些闭三角形覆盖凸包，且每个三角形的开外接圆不含 $S$ 中其他点。一般位置下，两站点 $p,q$ 之间存在 Delaunay 边，当且仅当它们的闭Voronoi cell 共享一条一维边，每个 Voronoi vertex 对偶于一个 Delaunay 三角形。共圆退化时，一个 Voronoi vertex 可对偶于多边形 Delaunay 面；为得到三角剖分而补的对角线只对应 Voronoi cells 在该顶点相交。

若没有四点共圆，Delaunay 三角剖分唯一。对凸四边形的一条内部对角线，局部 Delaunay 条件是对边顶点不落在相邻三角形的开外接圆内；非法对角线可通过 edge flip 换成另一条。增量算法插入点后找到受其影响、外接圆包含该点的三角形 cavity，删除后把 cavity 边界与新点连接。用随机增量构造时，还要证明所选定位与局部更新的成本，才能得到期望 $O(n\log n)$ 界。确定性最坏 $O(n\log n)$ 可由适当的分治构造实现；仅给任意增量过程配一个定位结构，并不会自动得到这份最坏保证。

直觉

空圆条件偏好避免极瘦三角形：若某点落入邻接三角形外接圆，翻转公共边会改善局部最小角。Voronoi 图按最近站点分区，Delaunay 则连接会在某处并列最近的站点，把距离区域的对偶关系变成三角网。

定义是全局空圆性质，edge flip 是维持它的局部操作；两者通过四点共圆判定连接。方向测试和内接圆判定的符号约定必须一致。

例子与边界

三个不共线点只有一个三角形，其开外接圆内没有其他站点，因此三角剖分自动是 Delaunay。四个构成非共圆凸四边形的点有两种对角线；恰有一条满足局部空圆条件，翻转非法边得到唯一 Delaunay 结果。

正方形四点共圆时，两条对角线都满足“开圆内无其他点”，所以 Delaunay 三角剖分不唯一；对应 Voronoi 图中心有四个 cell 相交。算法若要求唯一输出，需要固定 symbolic perturbation 或 tie-break，而不能宣称几何条件已经选定一条。

全体点共线时不存在覆盖二维凸包的三角形，应返回退化的一维结构或拒绝输入。浮点in-circle 行列式接近零时容易翻转符号，可能产生交叉边或非终止翻转；鲁棒谓词是正确性要求，不只是数值优化。

推论与应用

Delaunay 三角剖分用于网格生成、地形建模、插值和最近邻结构。平面最近点对必为某条 Delaunay 边，因此构造后只需检查线性条边，但若唯一目的只是最近点对，直接分治通常更简单。

Delaunay 剖分最大化所有三角形中的最小角；在没有四点共圆时，唯一的 Delaunay 剖分还把升序排列的全部三角形角度向量按字典序最大化。后一种更强陈述不能直接套给任意共圆平局选择。例如单位圆上按极角 $0^\circ,20^\circ,60^\circ,120^\circ$ 取四点，两条对角线都满足空开圆条件，却分别得到升序角度向量

(10,20,30,30,120,150),\qquad (10,20,30,50,120,130)

（单位为度）。最小角同为 $10^\circ$ ，第二个向量的字典序却更大。空圆条件本身没有在这两个合法剖分中选出角度向量更大者。这些性质也不表示每个三角形都接近等边，或自动满足有限元对边长和区域约束的全部要求。

参考资料

Boris Delaunay, “Sur la sphère vide,” Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles, 1934, pp. 793–800.
Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Ch. 9.
ETH Zürich，Geometry: Combinatorics & Algorithms，2020，§6.6 Theorems 6.20、6.22：无四点共圆时的角度向量最优性，以及共圆情形保留的最小角结论。

形式陈述 ​

反向链接

形式陈述