Delaunay 三角剖分构造
二维 Delaunay 三角剖分的分治构造:按 x 分治,递归构造两侧后合并上下公切线之间的跨边,O(n log n)。时间 O(n log n),空间 O(n) · 标签 计算几何 / Delaunay / 三角剖分 / 分治
本页讲二维 Delaunay 三角剖分的分治构造;定义与性质见 Delaunay 三角剖分。
核心思想
按 坐标排序,相同 时用 打破平局。把点集从中间分成左右两半,递归构造各自的 Delaunay 三角剖分,最后合并。
合并的目标不是重新构造整个点集,而是补上跨过左右分界线的 Delaunay 边。两侧内部的三角剖分已经合法,合并完成后整体也应满足空圆性质。
分治框架
- 若点数不超过 ,直接构造:一个点没有边,两个点连一条边,三个不共线的点构成一个三角形。
- 按排序后的位置把点集分成左半 和右半 。
- 递归构造 和 的 Delaunay 三角剖分。
- 合并两个三角剖分,得到整体结果。
分治的难点在第四步。左右两侧距离较远,跨边不能随意添加;需要用几何判定找出所有跨过分界线的 Delaunay 边。
合并
先求左右两个凸包的下公切线和上公切线。从下公切线开始,当前跨边就是这条切线;之后沿两侧凸包向上推进:
- 候选边是从当前左端点连到右凸包的下一个顶点,或从当前右端点连到左凸包的下一个顶点;
- 用空圆判定(incircle test)选择可以加入的下一条 Delaunay 边;
- 加入这条边,并把对应端点沿凸包向前移动。
重复直到到达上公切线。合并过程只检查两侧凸包上的顶点和边,因此一次合并是线性的。
合并结束后,左右内部的三角剖分加上这些跨边,就是整个点集的 Delaunay 三角剖分。排序需要 ,合并满足递推
因此总时间为 ,额外空间为 。
正确性
归纳假设左右两侧的递归结果正确。合并从下公切线出发,每次只加入满足空圆条件的跨边;标准 merge 引理保证在两条候选边中至少有一条可以加入,并且加入后不会破坏已经处理的空圆性质。沿凸包单调推进保证新边不会与已有边相交;到达上公切线后,所有跨边都已处理,凸包也被完整覆盖。
于是递归得到的每个三角形都满足空圆性质,整体就是 Delaunay 三角剖分。
实现要点
- 排序时用 作为键,确保划分稳定。
- 合并需要访问每个点的上、下凸包邻接关系;常用 quad-edge(四边形边)或等价的双向边结构维护三角剖分。
- 空圆判定是核心谓词。整数坐标建议用 128 位整数精确计算 incircle 行列式,避免浮点误差。
- 合并只添加跨边,不要重复添加左右两侧已有的内部边。
- 共线、共圆和重复点要单独处理;共圆时可用符号扰动或一致的平局规则固定一种合法剖分。
- 点数很少时直接返回边界结构,避免递归到空集或单点。
与其他构造的取舍
分治的优点是确定性 ,适合一次性批量构造;缺点是合并、公切线和拓扑维护都比较复杂。随机增量法通常代码更短,期望时间也是 ;扫描线方法也能达到 。如果只是为 Euclidean MST 准备候选边,任选一种可靠的 构造即可。