A. Point Set Triangulation
数学大学
A. Point Set Triangulati
计算几何 · 05. Delaunay Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Point Set Triangulati
计算几何 · 05. Delaunay Triangulation
Definition
点集三角化：用不相交的边把点集连成覆盖凸包的三角形网。
组成
顶点为输入点，边互不交叉
数量
h 个凸包顶点时三角形数 = 2n−2−h
Edge Flipping
边翻转改善三角化：凸四边形内一条对角线换成另一条。
翻转判据
内角和小于 π 时翻转更优
收敛
翻转至所有边局部最优（Delaunay）
Upper Bound
三角化数量上界：n 个点的三角化至多 C(2n−5, n−2) 个。
指数
数量随 n 指数增长
应用
穷举法只适用于很小的 n
Lower Bound
三角化数量下界：至少存在一种构造方式，数量随 n 线性起步。
至少一个
任何三角剖分算法都能产出至少一个
意义
上下界之间是搜索优化与枚举的空间
本节要点
- ✓三角化 = 不交叉边的三角形覆盖
- ✓边翻转逼近 Delaunay
- ✓数量上界指数级，枚举不可行
延伸主题：实现边翻转算法验证与 Delaunay 的关系
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1边翻转为什么最终会收敛到 Delaunay 三角剖分？
参考答案每次翻转严格减小全图的角度向量和（按排序比较），而可能的三角剖分数量有限，因此过程终止；终止时所有边都满足空圆性质——即 Delaunay 三角剖分。
2边翻转算法的最坏翻转次数是多少？
参考答案O(n²)：n 个点的三角剖分共有 O(n) 条边，每条边至多翻转一次（每次翻转严格增大角度向量）。实际数据通常远少于最坏值。
3为什么说 Delaunay 三角剖分是「最均匀」的三角化？
参考答案边翻转的目标就是最大化最小角——Delaunay 三角剖分使最小角达到所有三角剖分中的最大值。最大最小角意味着三角形尽量饱满，避免细长扁平的病态三角形。