无需登录 数据私有 本地保存

Delaunay 三角剖分演示 - 空圆特性

几何 教育 Delaunay 三角剖分 演示 算法
34
0
0
0

Delaunay 三角剖分 · 空圆特性演示

悬停三角形查看外接圆 · 拖拽顶点实时更新 · 空圆内无其他点

顶点 0 三角形 0
顶点（可拖拽） 三角剖分边 外接圆（空圆） 悬停三角形

关于 Delaunay 三角剖分与空圆特性

什么是 Delaunay 三角剖分？
Delaunay 三角剖分是一种将平面点集划分为三角形的方法，使得任意三角形的外接圆内不包含任何其他点（空圆特性）。它由 Boris Delaunay 于1934年提出，是计算几何中最优雅的结构之一，广泛应用于有限元分析、地形建模、计算机图形学等领域。
什么是"空圆特性"（Empty Circle Property）？
空圆特性是 Delaunay 三角剖分的核心定义：对于剖分中的每一个三角形，其外接圆（经过三个顶点的唯一圆）内部不包含点集中的任何其他点。在这个演示中，悬停任意三角形即可看到其外接圆——如果三角剖分是正确的 Delaunay 剖分，外接圆内永远不会有其他点。这是 Delaunay 剖分"最优质"的数学保证。
Delaunay 三角剖分有什么实际应用？
Delaunay 三角剖分在众多领域有重要应用：有限元分析（生成高质量网格）、计算机图形学（曲面重建、地形渲染）、地理信息系统GIS（TIN地形模型）、路径规划（导航网格）、三维重建（点云处理）、无线传感器网络（覆盖优化）等。其"最大化最小角"的特性保证了网格质量。
如何判断一个三角剖分是否是 Delaunay 剖分？
只需检查每条边是否满足局部 Delaunay 条件：对于共享一条边的两个三角形，检查其中一个三角形的外接圆是否包含另一个三角形的对角顶点。如果所有边都通过检查，则整个剖分是 Delaunay 剖分。此外，Delaunay 剖分还等价于最大化所有三角形的最小内角，避免产生细长的"瘦三角形"。
Bowyer-Watson 算法是如何工作的？
本演示使用 Bowyer-Watson 算法（增量算法）：从一个覆盖所有点的超级三角形开始，逐个插入点。每次插入时，找到所有外接圆包含新点的"坏三角形"，移除它们形成空洞，然后将新点连接到空洞边界的所有顶点。最后移除与超级三角形相关的三角形。该算法时间复杂度为 O(n²)，对于实际应用通常表现良好。
🔧 相关工具