数学大学
H. Construction
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
H. Construction
计算几何 · 05. Delaunay Triangulation
Subtended Arc
对弧定理的几何视角：同一弧上任意点看弦的夹角相等——空圆判据的几何根基。
对角相等
同弧所对的圆周角处处相同
空圆联系
外接圆为空 ⇔ 对边张角达到最大
Angle Vector
角度向量：剖分全部三角形内角排成的向量，比较剖分质量的工具。
排序比较
按字典序比较角度向量，大者优先
Delaunay 地位
Delaunay 的角度向量字典序最大
Maximizing The Minimum A
Delaunay 的等价刻画：使最小角最大化——质量导向的定义。
最大化最小角
局部翻转即全局最大化最小角
工程意义
饱满三角形让数值方法更稳定
Evolution By Edge Flippi
边翻转演化：任意三角剖分经有限次翻转可达到 Delaunay。
翻转合法性
凸四边形内对角线可交换
单调收敛
每次翻转严格增大角度向量
Strategies
构造策略对比：增量翻转、分治、扫描线各有适用场景。
增量翻转
实现简单，随机序下期望高效
分治/扫描
确定性 O(n log n)，工程主流
本节要点
- ✓对弧相等是空圆判据的几何根基
- ✓Delaunay = 最小角最大化
- ✓边翻转单调收敛到 Delaunay
延伸主题：手算一次角度向量比较实现边翻转演示
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1「最大化最小角」为什么是网格生成的黄金标准？
参考答案数值方法（有限元）的误差与三角形最小角正相关：细长三角形让刚度矩阵病态、误差放大。最大化最小角就是系统性地消除最差单元，让整个网格的质量下限被抬高。
2角度向量的字典序比较在实现上如何操作？
参考答案把剖分全部内角升序排列成向量，两个剖分逐位比较，第一个不同处较大者胜。实现上可用优先队列或排序后对比，也可等价地用「检验每条边是否 Delaunay 合法」替代。
3边翻转演化一定会终止吗？会不会来回振荡？
参考答案会终止：每次合法翻转严格增大角度向量（按字典序），而可能的向量只有有限个——严格单调有界必收敛。不存在振荡回路，这是 Delaunay 唯一性的体现。