Delaunay 三角剖分

Delaunay 三角剖分(Delaunay Triangulation)是计算几何中对点集进行三角剖分的一种经典方法,由苏联数学家鲍里斯·德劳内(Boris Delaunay)于 1934 年提出。它要求剖分中每个三角形的外接圆内部都不包含任何其他输入点,这一性质称为空圆性质。

概述

对同一组点可以有许多种三角剖分,但质量差异很大:细长的尖三角形会给数值计算带来误差。Delaunay 三角剖分在所有剖分中最大化了最小内角,得到的三角形整体上最接近正三角形,因而成为网格生成的默认选择。它与 Voronoi 图(沃罗诺伊图)互为对偶:连接 Voronoi 图中相邻区域的站点,得到的正是 Delaunay 三角剖分。

核心特点

• 空圆性质:任一三角形的外接圆内不含其他点,这是判定与构造的核心准则。
• 最大化最小角:在所有可能剖分中避免最尖锐的角,数值稳定性好。
• 唯一性:当没有四点共圆时,剖分唯一确定。
• 包含最近邻图与欧几里得最小生成树:后者的边都是 Delaunay 边,可借此在 O(n log n) 内求平面点集最小生成树。

常用构造算法包括:逐点插入的 Bowyer-Watson 算法(配合翻边操作恢复空圆性质)、分治算法,以及借助 Fortune 扫描线先求 Voronoi 图再取对偶,理论最优复杂度均为 O(n log n)。

应用场景

有限元分析与计算流体力学需要高质量网格,Delaunay 剖分及其约束版本是主流生成手段;地理信息系统用它把离散高程点构成不规则三角网(TIN)来表示地形;此外它还用于散点数据插值、无线传感网络拓扑构建、三维重建与游戏地图生成等。

常见问题

问:Delaunay 三角剖分和 Voronoi 图到底什么关系？答:二者互为对偶图,求出其中一个就能在线性时间内导出另一个;Voronoi 图刻画“离谁最近”,Delaunay 剖分刻画“谁与谁相邻”。

问:四点共圆时怎么办？答:此时剖分不唯一,任选一条对角线均满足空圆性质,工程实现常用符号扰动技术保证结果确定。

问:能否强制保留指定边？答:可以,这称为约束 Delaunay 三角剖分,常用于必须保留边界轮廓的网格生成场景,但空圆性质会被局部放宽。