Delaunay 三角剖分生成器

Delaunay三角剖分生成器可将任何 2D 点集转换为使最小内角最大化的唯一三角剖分 —— 这是地形建模、有限元网格划分、最近邻插值和计算几何课堂的金标准。粘贴坐标（或选择快速启动模式），该工具将在服务器端运行 Bowyer-Watson 算法，根据质量为每个三角形着色，并根据需要显示空外接圆属性、凸包和 Voronoi 对偶。

如何阅读生成的网格

是什么让这个 Delaunay 三角剖分生成器与众不同

什么是 Delaunay 三角剖分？

给定一组 2D 点，通常有很多方法可以将它们连接成三角剖分（用三角形完全平铺它们的凸包，没有重叠或缝隙）。以俄罗斯数学家 Boris Delaunay (1934) 命名的 Delaunay 三角剖分是满足空外接圆属性的三角剖分：对于网格中的每个三角形，通过其三个顶点的圆不包含其他输入点。这一单一属性带来了一个显着的结果：在同一点集的所有三角剖分中，Delaunay 三角剖分使最小内角最大化。用通俗的话来说，它能产生尽可能“胖”且“平衡”的三角形。

Bowyer-Watson 算法的工作原理

1. 用一个非常大的超级三角形包围所有输入点。
2. 每次插入一个输入点。对于每个新点，找出其外接圆包含该新点的每个现有三角形 —— 这些是“坏”三角形。
3. 移除坏三角形。它们留下的孔洞具有多边形边界。
4. 将新点与该边界的每条边连接起来，形成新的三角形。
5. 插入所有点后，移除仍与超级三角形顶点接触的任何三角形。剩下的就是原始点集的 Delaunay 三角剖分。

Delaunay 三角剖分的应用领域

• 地形建模 (GIS)：高程样本（通常间距不规则，如地形站）被连接成不规则三角网 (TIN)，用于高程查询、阴影和 3D 可视化。
• 有限元网格划分：形状良好的 Delaunay 三角形可为力学、传热学和电磁学中的偏微分方程提供稳定的数值解。
• 计算机图形学：用于渲染、角色绑定和程序化地形的网格生成 —— Delaunay 的“无狭长三角形”保证避免了纹理拉伸伪影。
• 自然邻点插值：通过 Voronoi 对偶计算每个查询点的自然邻点，从而从分散的样本中重建光滑表面。
• 计算几何课程：一种经典算法，与凸包、Voronoi 图、点定位和分治法有着深厚的联系。
• 3D 打印切片机和 CNC 刀具路径：2D Delaunay（及其 3D 亲戚 Delaunay 四面体剖分）是许多切片和填充策略的基础。

Delaunay 与 Voronoi：一枚硬币的两面

Voronoi 图将平面分割为每个输入点一个胞腔，其中每个胞腔包含比任何其他点都更接近该点的所有区域。将胞腔共享边界的点连接起来，即可得到完整的 Delaunay 三角剖分。相反，相邻 Delaunay 三角形的外接圆圆心由线段连接，便形成了 Voronoi 边。在此工具上切换“Voronoi 对偶”可查看叠加在同一图表上的橙色虚线 —— 每条 Delaunay 边都与恰好一条 Voronoi 边直角相交。

质量、狭长三角形与网格细化

Delaunay 最大化了全局最小内角，通俗但它无法修复根本上糟糕的点分布。如果您的输入点几乎共线、聚集或留有较大的空白区域，某些三角形仍然会很狭长（最小角低于 20°）。解决办法是插入 Steiner 点：诸如 Ruppert 算法和 Chew 第二算法之类的算法会迭代地在狭长三角形的外接圆圆心处添加新点，每次都重新进行三角剖分，直到每个三角形都达到目标质量标准。这个生成器可以向您显示哪些三角形是狭长的，以便您在需要更精细的网格时知道在哪里添加 Steiner 点。

实例演练

点击“圆与中心”预设。该工具在圆周围放置 18 个点，并在中心放置 1 个点，然后对它们进行三角剖分。结果是在中心交汇的 18 个完美的等腰三角形扇面 —— 每个三角形在边缘处的角度为 10°，在中心处的角度为 80°–80°。最差的最小角为 10°，所有三角形都被标记为狭长，并且直方图显示所有内容都在 0°–10° 区间内。这个例子是一个极好的教学案例：即使是 Delaunay 最优三角剖分，当输入迫使其如此时，也会出现狭长三角形。现在点击“随机点云” —— 相同的算法会产生形状良好的三角形，因为点分布均匀，直方图也向右移动。

常见误区

• “Delaunay 三角剖分是唯一的”：通常是的，但如果四个输入点共圆（全部位于同一个圆上），则该组有两个有效的 Delaunay 三角剖分。生成器会始终如一地选择其中一个。
• “点越多总是意味着质量越好”：添加位置不当的点可能会引入新的狭长三角形。Steiner 点算法会小心地在外接圆圆心处放置新点，从而确保质量得到提升。
• “Delaunay 与凸包相同”：并非如此。凸包是外部边界；Delaunay 三角剖分用三角形填充内部。
• “所有三角剖分看起来都差不多”：差异是非常巨大的。从 Delaunay 边进行一次“翻转”可以将一个 25° 的三角形变成一个 5° 的三角形。该工具的质量热力图使这种差异清晰可见。

常见问题解答