三角学/爱好者/德洛内三角剖分

平面上的德洛内三角剖分，显示外接圆

德洛内三角剖分是一种连接一组点以形成三角形网格的特殊方法。德洛内三角剖分倾向于避免细长三角形。该三角剖分由 鲍里斯·德洛内 在 1934 年发明。

应用

文件：Bush-Arnie-morph.jpg
乔治·W·布什到阿诺德·施瓦辛格的变形	流体流动问题的有限元分析解决方案

• 对于变形图像，德洛内三角剖分提供了一种“良好”的方法，可以从将要移动的点创建三角形网格。每个三角形都可以以简单的方式进行扭曲，从而导致整体图像的复杂“变形”扭曲。在显示的变形示例中，三角形形状从一个图像扭曲到另一个图像，例如，第一个图像中的头发被扭曲以适应第二个图像中的头发。同时，颜色从一种颜色“交叉淡入”到另一种颜色，因此灰色交叉淡入棕色。

内华达山脉地形图	二维三角形网格	从网格计算得出的二维解决方案

• 对于给定一组样本点来建模地形或其他物体，德洛内三角剖分提供了一组不错的三角形，可以作为模型中的多边形使用。特别是，德洛内三角剖分避免了狭窄的三角形（因为它们与它们的面积相比具有较大的外接圆）。

• 德洛内三角剖分用于许多其他应用中，在这些应用中，形状必须被分割成三角形。结构应力和应变的分析通常使用三角形网格进行。在上面的分析中，在最感兴趣的区域放置更多点，以在该区域获得更精细的更详细的分析。这也是我们在变形图像时所做的事情 - 我们在最需要控制变形细微之处的地方放置更多点。如果你想把皱眉变成微笑，在嘴周围放更多点，这样你就可以更容易地改变形状。

形式化定义

对于平面上的一组点P，德洛内三角剖分是三角剖分 DT(P)，使得P 中的任何点都不在 DT(P) 中任何三角形的外接圆内。外接圆。德洛内三角剖分最大化三角剖分中所有三角形角度的最小角度；它们倾向于避免细长三角形。

对于同一线上的一组点，不存在德洛内三角剖分（实际上，三角剖分的概念对于这种情况是未定义的）。对于同一个圆上的四个点（例如，矩形的顶点），德洛内三角剖分不是唯一的：将四边形分成两个三角形的两种可能的三角剖分都满足“德洛内条件”，即所有三角形的外接圆具有空内部的要求。

与沃罗诺伊图的关系

平面上 离散 点集 P 的德洛内三角剖分 对应于 对偶图 的 沃罗诺伊镶嵌 P。特殊情况包括线上存在三个点和圆上存在四个点。

• 
  德洛内三角剖分，显示所有外接圆及其圆心（红色）。
• 
  连接外接圆的圆心会产生 沃罗诺伊图（红色）。

特性

设 n 为点数（顶点）。

• 在平面上，每个顶点平均有六个周围的三角形。
• 在平面上，德洛内三角剖分最大化最小角。与点的任何其他三角剖分相比，德洛内三角剖分中的最小角度至少与任何其他三角剖分中的最小角度一样大。但是，德洛内三角剖分不一定最小化最大角度。
• 外接任何德洛内三角形的圆在其内部不包含三角剖分的任何其他顶点。
• 如果经过两个顶点的圆在其内部不包含任何其他顶点，则连接这两个点的线段是给定点德洛内三角剖分的边。
• 任何点 p 的最近邻 b 是德洛内三角剖分中的边 bp。 最近邻图 是德洛内三角剖分的子图，最小生成树也是如此。

凸包

• 三角剖分中所有三角形的并集是点的凸包。
• 在平面上，如果有 b 个顶点在凸包上，那么点的任何三角剖分最多有 2n − 2 − b 个三角形，加上一个外部面（参见 欧拉特征）。

可视化德洛内定义：翻转

从上面的属性中，一个重要的特征出现了：观察两个三角形 ABD 和 BCD，它们有公共边 BD（见图），如果角 α 和 γ 的和小于或等于 180°，则三角形满足德洛内条件。

这是一个重要的属性，因为它允许使用翻转技术。如果两个三角形不满足德洛内条件，则将公共边 BD 切换为公共边 AC 会产生两个满足德洛内条件的三角形

• 
  这种三角剖分不满足德洛内条件（α 和 γ 的和大于 180°）。
• 
  这种三角剖分不满足德洛内条件（外接圆包含超过 3 个点）。
• 
  翻转公共边会为这四个点产生德洛内三角剖分。

算法

许多计算德洛内三角剖分的算法依赖于快速操作来检测点是否在三角形的外接圆内，以及用于存储三角形和边的有效数据结构。在二维中，检测点 D 是否位于 A、B、C 的外接圆内的一种方法是计算 行列式:

${\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}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\\\end{vmatrix}}>0$

假设A、B 和 C 逆时针排列，当且仅当D位于外接圆内时，该值大于零。

翻转算法

如上所述，如果一个三角形是非 Delaunay 三角形，我们可以翻转其一条边。这导致了一种简单的算法：构建点的任意三角剖分，然后不断翻转边直到没有非 Delaunay 三角形。不幸的是，这可能需要 O(n²) 次边翻转，并且不能扩展到三维或更高维度。

增量法

最直接有效地计算 Delaunay 三角剖分的方法是每次添加一个顶点，并重新剖分受影响的图形部分。当添加一个顶点v 时，我们将包含v 的三角形分成三个三角形，然后应用翻转算法。如果直接执行，这将需要 O(n) 的时间：我们遍历所有三角形以找到包含v 的一个三角形，然后可能需要翻转所有三角形。因此，总的运行时间为 O(n²)。

如果我们以随机顺序插入顶点，事实证明（通过一个相当复杂的证明），每次插入平均只会翻转 O(1) 个三角形——尽管有时会翻转更多三角形。这仍然留下了需要改进的点定位时间。我们可以存储执行的分割和翻转的历史记录：每个三角形存储指向替换它的两个或三个三角形的指针。要找到包含v 的三角形，我们从一个根三角形开始，并沿着指向包含v 的三角形的指针，直到找到一个尚未替换的三角形。平均而言，这将需要 O(log n) 的时间。因此，对于所有顶点，这将需要 O(n log n) 的时间。虽然该技术可以扩展到更高维度（如 Edelsbrunner 和 Shah 证明的那样），但即使最终的 Delaunay 三角剖分很小，运行时间也可能随维度呈指数增长。

Bowyer-Watson 算法为增量构建提供了另一种方法。它为计算包含新插入顶点的 Delaunay 三角形提供了边翻转的替代方法。

分治法

二维三角剖分的分治算法由 Lee 和 Schachter 提出，后来由 Guibas 和 Stolfi，以及后来的 Dwyer 进行改进。在这个算法中，我们递归地画一条线将顶点分成两个集合。我们为每个集合计算 Delaunay 三角剖分，然后沿着分割线将两个集合合并。使用一些巧妙的技巧，合并操作可以在 O(n) 时间内完成，因此总的运行时间为 O(n log n)。

对于某些类型的点集，例如均匀随机分布，通过明智地选择分割线，可以将预期时间降低到 O(n log log n)，同时仍然保持最坏情况下的性能。

P. Cignoni、C. Montani 和 R. Scopigno 在 "DeWall：E^d 中快速的分治 Delaunay 三角剖分算法" 一文中介绍了一种在d 维中执行三角剖分的分治范式。

分治法已被证明是最快的 DT 生成技术。

扫描线法

Fortune 算法 使用扫描线技术在平面情况下实现 O(n log n) 的运行时间。

Sweephull

Sweephull 是一种快速混合技术，用于二维德劳内三角剖分，它使用径向传播的扫描包络（从径向排序的二维点集中依次创建，得到一个不重叠的三角剖分），并配以最终的迭代三角形翻转步骤。 经验结果表明，该算法的运行时间大约是 Qhull 的一半。 GPL 代码可从 获得

致谢

• 此页面最初是根据维基百科上的德劳内三角剖分创建的。