德洛内三角剖分是一种几何剖分,它将一组点连接成三角形或更高维的单纯形,并满足空外接球条件。在平面上,每个三角形的外接圆所围成的开圆盘内都不包含其他输入点。对于处于一般位置的点集,这一条件唯一确定了其凸包的三角剖分。而在退化情形下,则可能产生非单纯形的德洛内胞腔,这些胞腔可以有多种有效的三角剖分方式。
这一构造以数学家鲍里斯·德洛内的名字命名,其姓氏的拉丁字母拼写除 Delaunay 外也作 Delone。它是计算几何中的基本构造,将最近邻关系与凸性联系起来,既可用于构建高效的空间数据结构,也能为科学计算提供网格。其平面形式具有重要的角度最优性,但这一性质不能直接推广到三维四面体网格。在应用中,同样需要注意区分无约束的点集三角剖分与符合边界的计算网格。
定义、存在性与退化情形
设 是欧几里得平面上由互异点组成的有限集合,且这些点不全共线。 的直线边三角测量将其凸包划分为互不重叠的三角形,这些三角形的顶点恰好就是所有输入点。三角形之间只能在公共边或公共顶点处相交,每个输入点都必须用作顶点,且任何边若经过另一个输入点,就必须在该点处细分。三角形的外接圆是经过其三个顶点的唯一一个圆。如果剖分中每个三角形的外接开圆盘都是空的,那么该剖分就是德洛内三角剖分:其他输入点可以位于外接圆上,但不能严格位于圆内。
这里的“开”字至关重要。考虑构成一个正方形的四个点。它们位于同一个圆上,无论选择哪条对角线,都能将正方形分成两个满足空圆条件的三角形。因此,德洛内三角剖分未必唯一。在平面上,一个充分的一般位置假设是:任意三点不共线,任意四点不共圆。在这些假设下,德洛内三角剖分存在且唯一。任意三点不共线的条件简化了组合结构;而排除空圆上的共圆点配置,才是消除不同对角线选择之间歧义的关键。
在不作一般位置假设时,区分德洛内剖分与在该剖分基础上选定的三角剖分很有帮助。经过四个或更多输入点的空圆,可能对应一个凸多边形单元,而不是单个三角形。在每个这样的单元内部添加互不相交的对角线,就能得到德洛内三角剖分,但这些对角线并不能由几何条件唯一确定。共线点集本质上是一维的,无法构成各面面积为正的二维三角剖分。同样,坐标重复的点在几何上只代表同一个位置,除非具体应用赋予它们额外的非几何含义。
对于一个有 个顶点的平面三角剖分,若凸包边界上有 个顶点(包括位于边界边上的所有点),则有界三角形面的数量和边的数量分别为
这些恒等式可由平面的欧拉示性数以及对三角形与边之间关联关系的计数推导出来。它们表明,平面德洛内三角剖分只需要线性规模的输出空间。边界边属于一个三角形,内部边则属于两个三角形。
在 中,同样的定义采用 维单纯形和空外接球。一个单纯形有 个仿射无关的顶点:二维中是三角形,三维中是四面体。满维点集的凸包存在德洛内三角剖分,而低维点集则在其仿射包内处理。要保证唯一性,通常需要排除由 个共球点构成的相关配置。因此,平面三角剖分是在整个欧几里得空间中均有定义的这一构造的最简单非平凡实例。
沃罗诺伊对偶与提升构造
与德洛内三角剖分关系最密切的是沃罗诺伊图。对于一个输入点 ,它的沃罗诺伊单元为
它由这样的位置组成:按通常的欧几里得距离衡量,这些位置到 的距离不大于到任何其他输入点的距离。每一次距离比较都定义一个以垂直平分面为边界的半空间,因此每个沃罗诺伊单元都是凸的。这些单元覆盖整个空间,并在公共面上相交。位于凸包边界上的输入点具有无界的沃罗诺伊单元;严格位于凸包内部的输入点则具有有界的单元。
对于非退化的平面点集,两个输入点由德洛内边相连,当且仅当它们的沃罗诺伊单元共享一条边。三个输入点构成德洛内三角形,当且仅当它们的沃罗诺伊单元交于一个沃罗诺伊顶点。这个顶点就是该三角形的外心:它到这三个输入点的距离相等,且没有其他输入点离它更近。由此立即可得空圆条件。相互对应的德洛内边与沃罗诺伊边彼此垂直,但它们所在直线的交点未必同时落在这两条有限长的边上。钝角三角形的外心位于三角形之外,因此,这种对偶性指的是组合结构上的对应,而不是说每个对偶几何元素都位于其对应的原几何元素内部。
对于退化情形,表述需要更加谨慎。在正方形中心,有四个沃罗诺伊单元相交。与之对应的德洛内单元是一个四边形,而不是唯一确定的一对三角形。选择一条对角线,相当于添加了一次单纯形细分,而这条对角线并不对应任何长度为正的沃罗诺伊边。因此,沃罗诺伊图自然确定的是德洛内剖分;要将退化单元进一步剖分为三角形,则需要额外作出选择。
另一种解释将空圆条件转化为凸几何问题。将每个平面点 提升到三维空间中的一个抛物面上:
计算提升后各点的凸包,再将其下表面各面沿竖直方向投影回平面。这些投影就构成了德洛内剖分。为说明其中的原因,将圆心为 、半径为 的圆写成
该圆上的点提升到抛物面后,位于平面
之上。圆内的平面点提升后则落在这个平面的下方。因此,下支撑面——即所有其他提升后的输入点都位于其所在平面上或上方的面——投影得到的单元,其外接圆内部不含其他输入点。
这一构造可以推广为将 提升到 。它在德洛内剖分的计算与凸包算法之间建立了直接联系,说明了德洛内剖分的存在性,并将共圆或共球的退化情形转化为下表面上的共面情形。它还为加权德洛内构造提供了代数基础。
局部判据、角度最优性与邻近图
尽管定义具有全局性,平面德劳内三角剖分仍可通过局部检验来判定。设两个相邻三角形共用一条内部边 ,各自的对顶点为 和 。若 不在 的外接圆内部,则称这条边满足局部德劳内条件。当这两个三角形组成一个凸四边形时,等价的角度条件为
当四个顶点共圆时,等号成立。如果角度之和超过 ,就可以将对角线 替换为 ,通过这种边翻转来纠正局部条件的违反。一个平面三角剖分是德劳内三角剖分,当且仅当它的所有内部边都满足局部德劳内条件。
这一判据是著名的最大化最小角性质的基础。对于给定的平面点集,在所有以直线段为边的三角剖分中,德劳内三角剖分使三角形的最小角达到最大。更强的结论是:若将所有三角形的角按从小到大的顺序排列,其角度序列按字典序比较也是最大的。翻转一条不满足德劳内条件的边,可以改善局部角度的排序;反复进行这种改进,最终便能得到满足空圆条件的三角剖分。共圆情形下的不同剖分可能具有相同的最优角度序列。
这一性质是相对于可用顶点而言的,并不绝对保证三角形具有良好的形状。如果两个点极其接近,而周围其他点又相距很远,那么任何三角剖分都可能包含狭长三角形。同样,由输入边界所强制形成的锐角,也不会仅靠更换对角线就消失。因此,德劳内三角剖分能够避免平面中不必要的小角,却不能保证所有角都超过某个固定阈值。一般而言,它也不会使总边长最小,或使每个三角形都成为锐角三角形。
它的边还体现了重要的邻近关系。以最小总边长连接所有点的欧几里得最小生成树,可以在德劳内结构中找到。对于这棵树的每条边,以该边为直径的闭圆盘内都不含其他输入点,因此它必然也是一条德劳内边。这使得原本稠密的几何图问题可以化简为仅有 条平面边的图问题。加布里埃尔图采用相关的直径圆盘为空的判定规则,也是德劳内图的子图;确切的包含关系取决于如何处理点落在圆盘边界上的情形。
平面德劳内图还是一种几何伸展图。存在一个通用常数 ,使得任意两个输入顶点 和 之间,都能找到一条沿德劳内边行进的路径,其总长度不超过 。这是对最坏情况下绕行程度的界限,并不意味着每一对邻近点之间都有边相连,也不意味着图上的最短路径长度等于直线距离。
这些关系使德劳内三角剖分成为几何学与图论之间的桥梁。它在稀疏的平面结构中保留了有用的局部连接,同时又以三角形对连续空间进行细分。不过,上述角度定理仅适用于平面:在三维空间中,外接球为空并不能提供类似的保证,以避免出现形状不良的四面体。
构造算法与复杂度
多类算法通过不同的中间表示来构造同一个几何对象。它们的效率既取决于几何运算,也取决于如何定位每次操作所影响的区域。对于平面上的 个点,在标准的基于比较的计算模型下,最优的通用算法运行时间为 ,输出所需的存储空间为 。这里的大O记号省略了常数因子和低阶项。将输入数值对应的点放在一条合适的曲线上,再从所得的邻接结构中恢复它们的顺序,就可以把排序的时间下界与德洛内三角剖分的构造联系起来。
一种方法从任意有效的三角剖分出发,反复翻转不满足德洛内条件的边。查尔斯·劳森在20世纪70年代提出了影响深远的局部变换方法。每次翻转只改变两个相邻三角形,因此这种方法概念简单,也适合用于网格修复。然而,在平面上,朴素的翻转过程可能需要平方量级的操作次数,所以仅凭局部操作简单,并不能保证运行时间最优。维护一个可能不满足条件的边的队列,可以避免反复检查未受影响的区域。
增量算法逐个插入点。阿德里安·鲍耶和戴维·沃森于1981年分别独立发表的鲍耶–沃森算法,会删除外接圆内部包含新插入点的三角形。这些三角形的并集形成一个空腔;将空腔的各条边界边与新点相连,即可恢复德洛内三角剖分。另一种增量构造方法先分割包含插入点的三角形;如果插入点落在边上,则分割该边相邻的三角形,然后通过翻转使附近的边满足德洛内条件。这两种方法都需要对凸包变化、边界情形和精确退化情形进行特殊处理。
随机插入顺序可以带来良好的期望复杂度界。采用适当的点定位数据结构后,二维随机增量构造可实现 的期望运行时间,最终占用线性空间。这里的期望针对的是算法中的随机化,并不要求输入点本身服从随机分布。冲突图或被替换三角形的历史记录,可以帮助定位后续插入所处的区域。从附近一个先前已定位的三角形出发,沿相邻三角形逐步查找,在实践中往往很有效,但其性能取决于输入和查询顺序。
分治算法将点集划分为子集,分别进行三角剖分,再在保持空圆条件的前提下将它们合并。迈克尔·沙莫斯和丹·霍伊于1975年提出了一种最优的平面算法。列奥尼达斯·吉巴斯和豪尔赫·斯托尔菲于1985年提出的四边结构框架,为同时表示和操作平面细分及其对偶提供了一种紧凑方式。另一些方法则先计算沃罗诺伊图,再通过对偶关系得到三角剖分;史蒂文·福琼于1987年提出的扫描线算法能够在 时间内构造平面沃罗诺伊图。
提升法提供了另一条途径:在高一维的空间中计算凸包,并保留其下侧面。动态数据结构支持顶点的插入、删除和移动,而并行实现则通过分配点处理任务或划分计算区域来完成构造。实践中的最佳选择取决于维数、输入顺序、退化情形的出现频率、内存访问方式,以及后续操作是否需要完整的沃罗诺伊对偶。在更高维度中,输出本身的规模就可能超过线性量级,因此不能直接套用平面情形的复杂度界。
几何谓词与数值鲁棒性
德洛内三角剖分的实现需要根据数值坐标作出离散判断:三个点构成左转还是右转,第四个点是否位于外接圆内,以及哪些面应当相邻。仅一个符号判断错误,就可能导致边相交、三角形翻转或邻接结构损坏。因此,鲁棒性的关键与其说是算出视觉上合理的外心,不如说是对少数几个几何谓词进行一致的求值。
对于平面上的点 、 和 ,其定向由下式确定:
结果为正表示各点按逆时针顺序排列,为负表示按顺时针顺序排列,为零则表示三点共线。使用行列式,可使这一判定表示为坐标的多项式,并避免除以可能很小的量。此外,该行列式的值也是三角形有向面积的两倍。
当 按逆时针顺序排列时,圆内判定谓词取决于下式的符号:
结果为正表示 位于外接圆内,为负表示位于圆外,为零则表示位于圆上。如果将 的定向反转,上述符号约定也随之反转。这个行列式与提升后的点的定向密切相关,将实际使用的谓词与抛物面构造联系起来。
普通的浮点运算可能会对近乎共线或近乎共圆的点集作出错误判断,因为数值相消会留下一个很小的结果,其符号并不可靠。将每个结果与固定的数值容差比较,并不是通用的解决办法:相关的尺度会发生变化,而分别应用容差可能导致逻辑上不一致的判断。对于近乎共线的三角形,显式计算外心再比较距离尤其容易出问题,因为这类三角形的外心可能位于极远处。
自适应精确谓词首先快速计算近似值及其误差界。如果能够确认符号,计算便停止;否则就提高精度,直到确定所表示坐标对应的精确符号。乔纳森·谢夫丘克在20世纪90年代的工作,使浮点展开算术以及自适应定向判定和圆内判定得到了广泛应用。对有理数或整数坐标进行精确运算是另一种方法,不过中间值的大小和计算成本可能随之增长。
对于精确为零的结果,仍需明确处理。符号扰动通过一致的无穷小次序来解释退化情形,其中包括赫伯特·埃德尔斯布伦纳与恩斯特·米克于1990年提出的简单性模拟框架。另一种做法是在实现中保留非单纯形单元,或以确定性的方式选择对角线。这些策略解决的是组合结构上的歧义,并不能消除测量坐标中的不确定性。精确谓词能够保证针对已存储输入值作出的判断正确,却不能保证针对未知物理位置的判断正确。即使所有谓词都是精确的,生成新外心等几何构造也可能需要单独的精度保证。
边界约束与德劳内网格细化
无约束德劳内三角剖分会填满其输入点集的凸包,但不会自动保留海岸线、多边形边界、孔洞、材料界面或内部裂缝。表示这类特征的线段可能与无约束德劳内边相交,而区域的凹陷部分也可能被不需要的三角形填充。因此,计算网格通常需要以平面直线图为基础构造约束德劳内三角剖分:这种图由顶点和互不交叉的线段组成,用于表示必须保留的几何特征。
约束边必须出现在三角剖分中,即使它们会违反通常的空圆准则。其余三角形则满足带有可见性限制的条件。通俗地说,如果中间的约束线段阻挡了某个输入顶点与三角形之间的视线,那么这个顶点就可以位于该三角形的外接圆盘内。等价地,在有效的约束三角剖分中,每条可翻转的无约束内部边都具有局部德劳内性质。约束边不允许翻转,因为替换它们可能破坏预先规定的区域几何形状。
相容德劳内三角剖分则有所不同。它通过添加额外顶点(通常称为斯坦纳点),使所要求的线段成为普通德劳内三角剖分中的边链。约束三角剖分往往只需使用原有顶点,而相容构造可能需要大量额外顶点。如果应用要求严格保持欧氏空间中的沃罗诺伊—德劳内关系,而不只是保留边界,这一区别就十分重要。
网格生成通常还对尺寸和形状提出要求。德劳内细化会反复针对质量差的三角形或分辨不足的边界插入点,然后更新三角剖分。一种常用的三角形质量度量是外接圆半径与最短边长之比,
根据扩展正弦定理,
其中, 是最小角。因此,给 设定上界,就能保证最小角不会趋近于零。此外,还可以通过尺寸场,单独规定在界面、曲线边界或解变化剧烈的区域附近采用更小的单元。
L. 保罗·丘和吉姆·鲁珀特提出的算法,确立了具有重要影响的终止性与质量保证。典型的细化过程会先分割被侵入的边界线段,再插入劣质三角形的外心;这种优先顺序有助于保持网格与边界相容,并控制各细化步骤之间的相互影响。对于不含过小输入角、且满足适当条件的平面输入,经典分析能够保证算法在目标最小角约为 时终止,具体阈值取决于算法及其假设条件。
过小的边界角会使这类保证变得复杂,因为几何形状本身就迫使网格中出现小角。曲线边界还需要几何近似或曲边单元,而不是仅仅增加三角形。在三维情形中,基于外接球的细化可以控制某些尺寸指标,却无法消除薄片状四面体。因此,实际的网格生成器会将德劳内操作与线段保护、几何近似、平滑处理、边或面的变换,以及专门的质量改进相结合。这些都属于额外的算法,而非仅凭空圆定义就能得到的结果。
高维、权重与几何推广
在三维空间中,德洛内三角剖分将点集的凸包划分为若干四面体,每个四面体的外接球内部均不含其他输入点。在一般位置下,一个四面体对应三维沃罗诺伊图的一个顶点;一个三角形面对应一条沃罗诺伊边;而一条德洛内边则对应一个沃罗诺伊多边形面。因此,熟悉的平面对偶关系仍然成立,但输出规模和单元质量的表现却发生了显著变化。
在固定维数 下,最坏情况复杂度为
且适当的点配置确实可以达到这一量级。特别是,三维德洛内三角剖分的规模可以达到平方量级。实际工程数据集通常产生小得多的网格,但空间维数为三并不意味着最坏情况规模具有线性上界。算法必须同时考虑输入规模和生成的单纯形数量。
三维中特有的一项难题是薄片四面体:其顶点几乎共面,通常接近同一个圆,而各条边的长度仍相差不大。这种四面体的体积可能极小,二面角也可能极小或极大,但其外接球半径与最短边长之比却未必很大。因此,边长和外接球半径指标良好,并不能保证四面体具有良好的条件性。这限制了将平面中的角度论证直接用于有限元法网格生成。
带权站点会导出正则三角剖分,也称为加权德洛内三角剖分。给每个点赋予一个标量权重 ,并用幂距离代替距离平方:
各个站点使该表达式取得最小值的区域构成一个幂图。将站点提升为
并投影其下凸包,即可得到相应的正则剖分。与普通的无权情形不同,有些带权站点可能被隐藏:它们的幂单元为空,因此不会作为顶点出现在剖分中。调整权重可用于几何建模,也可用于薄片消除等方法;这类方法通过改变权重来改善四面体网格。
其他推广则改变了定义域或距离规则。周期性德洛内三角剖分将基本单元的相对边界视为重合,实际上是在平坦环面上进行三角剖分,从而避免在周期性模拟中引入人为的外部边界。分片平坦曲面上的内蕴德洛内三角剖分采用曲面几何和局部角度条件,而非不受曲面约束的周围三维空间距离。其边可以表示穿越底层曲面网格的测地路径。
受限德洛内构造则将周围空间中的沃罗诺伊图与目标曲面或区域联系起来:通过对偶沃罗诺伊几何要素与目标的相交情况来选取单纯形。在适当的采样和正则性假设下,这类构造可用于曲面重建和流形网格生成。各向异性变体引入了随方向变化的度量,通常通过度量张量来表达,但需要另行开展几何与算法分析。将距离替换为任意随空间位置变化的度量后,普通欧氏空间中的空圆定理并不会自动成立。
插值、数值模型与形状重建
德洛内三角剖分为散点测量数据的插值提供了局部框架。假设已知各采样点 处的标量值 。在顶点为 的三角形内部,可以用重心坐标将一点表示为
分片线性插值函数为
该函数在公共边处连续,因为相邻三角形上的插值函数在边的两个端点取值相同,并且沿边线性变化。不过,其梯度在这些边处通常不连续。三角剖分提供了具有几何意义的区域划分,但插值精度仍取决于采样密度、数据噪声、三角形形状以及所表示函数的性质。
在地形建模中,不规则三角网通常对水平坐标进行平面德洛内三角剖分,并将实测高程赋予各顶点。所得三角形表示一个分片平面曲面。这是承载高度函数的二维三角剖分,而不是对实测点进行的三维德洛内四面体剖分。山脊、河道以及其他地形特征线可能需要用约束边表示;否则,插值曲面可能会将重要的坡度突变平滑掉。
在偏微分方程的数值求解中,三角形和四面体网格为有限元基函数与局部积分提供支撑。德洛内几何与拉普拉斯算子的余切离散化尤为相关。对于一条内部边,若其两个对角分别为 和 ,则一种常用权重为
当与该边相接的三角形均非退化时,局部德洛内条件 可使该权重非负。非负权重对于某些离散最大值原理和扩散问题的离散格式十分重要,但最终的数值性质还取决于边界处理、材料系数以及完整的离散化方案。边界边的权重需要另行考虑。
其对偶沃罗诺伊图也可用于有限体积法。德洛内边与其对偶沃罗诺伊面之间的正交性,简化了各向同性扩散中某些两点通量近似的计算。对于各向异性系数、钝角构型和边界裁剪,可能需要采用更复杂的格式。无论是正交性还是平面角度最优性,单凭其中任何一项都不能保证对所有方程都具有精度或稳定性。
在点云分析中,德洛内结构是构造α 复形和α 形状的基础。α 复形通过半径受控的球与其对应沃罗诺伊胞的交集来选取德洛内单纯形;不能不加其他规则,仅保留外接圆半径低于某个任意阈值的所有三角形,就认为得到了 α 复形。改变尺度可以揭示连通分支、隧道和空腔。这将几何重建与代数拓扑及拓扑数据分析联系起来。
科学计算软件体现了这些多样化的用途。Triangle 实现了稳健的平面三角剖分与网格细化,CGAL 提供了丰富的三角剖分数据结构和几何算法,Qhull 则通过凸包方法计算德洛内结构。它们在退化情形、点的省略或合并、边界约束以及数值精度方面采用的约定各不相同。因此,解读用于插值、拓扑分析或仿真的三角剖分时,必须同时考虑生成该剖分时所采用的几何假设与构造规则。