6章 Delaunay三角剖分
在第2章中，我们讨论了简单多边形的三角剖分。三角剖分巧妙地将多边形分割为三角形，使得计算面积或进行多边形的守卫变得简单。另一个常见的应用场景是使用三角剖分T进行插值：假设函数f在多边形P的顶点上定义，我们希望将其“合理且连续”地扩展到P的内部。对于点p ∈ P内，找到包含p的三角形t。由于p可以表示为t的顶点v1, v2, v3的凸组合λ1v1 + λ2v2 + λ3v3，我们可以使用相同的系数来获得函数值的插值f(p) = λ1f(v1) + λ2f(v2) + λ3f(v3)。
如果三角剖分在处理多边形时是一个有用的工具，那么它也可能对处理其他几何对象，比如点集，同样有用。但点集的三角剖分是什么呢？多边形有一个明确的内部，自然适合被小多边形，如三角形，覆盖。而点集没有内部，除非……这时候凸包的概念就派上用场了，因为它允许我们将点集视为一个凸多边形——它的凸包——可能在其内部有一些“洞”——即内部的点。理想的三角剖分应该划分凸包，同时尊重内部的点，如图6.1b所示。
(a) 简单多边形的三角剖分。
(b) 点集的三角剖分。
(c) 不是三角剖分。
图6.1: (非)三角剖分的例子。
相反，图6.1c中的例子很好地细分了凸包，但不应该被视为三角剖分：两个内部的点没有被尊重，而是被一个大三角形“吞噬”。
这种解释直接引出了Delaunay三角剖分的概念。Delaunay三角剖分是一种特殊类型的三角剖分，其中没有一个内点位于任何三角形的圆内，换句话说，每个三角形的外接圆不包含除了其顶点之外的任何点。这样的规定确保了内部的点不会被大三角形“吞没”，并且三角形的分布相对均匀，从而在插值和其他几何操作中保持良好的性质。
Delaunay三角剖分的应用广泛，包括但不限于：
1. 地形建模：在地理信息系统（GIS）中，Delaunay三角剖分用于构建地形表面的离散表示，以便进行高度数据的插值和分析。
2. 计算机图形学：在三维渲染中，Delaunay三角剖分可以创建平滑的表面，并优化光照计算。
3. 数据可视化：通过Delaunay三角剖分，可以将数据点集转换为连续的网格，方便展示和理解数据分布。
4. 网格生成：在数值计算中，Delaunay三角剖分被用于生成高质量的有限元网格，用于求解偏微分方程。
5. 模型构建：在机器学习中，Delaunay三角剖分可以用于构建邻域结构，如局部敏感哈希（LSH），用于近似最近邻搜索。
Delaunay三角剖分的构造通常涉及以下算法：
- Bowyer-Watson算法：这是一种动态算法，用于从点集生成Delaunay三角剖分。每次添加新点时，检查并更新受影响的三角形，直到达到稳定状态。
- Incremental构建：从一个初始三角形开始，逐步添加点并调整三角剖分，以保持Delaunay性质。
- Divide-and-Conquer算法：将点集分为两半，分别构建Delaunay三角剖分，然后合并它们并解决边界上的冲突。
在实际应用中，Delaunay三角剖分的性能和效率至关重要，因此优化算法和数据结构（如半平面表示法）被用来提高计算速度和内存效率。
Delaunay三角剖分是一种强大的几何工具，它在处理点集和其他复杂形状时提供了有效的解决方案，特别是在需要插值、网格生成和数据解析的场景中。通过理解和利用其特性，我们可以构建更高效、准确的算法来处理各种计算问题。
