数学大学
E. Triangulation
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
E. Triangulation
计算几何 · 03. Triangulation
Existence
三角剖分存在性：任何简单多边形都能被不相交的对角线剖成三角形。
结论
n 个顶点的多边形剖成 n−2 个三角形，用 n−3 条对角线
依据
由两耳定理归纳保证存在
Ear & Mouth
耳与嘴：耳是凸三顶点组成的可切除三角形；嘴是凹方向的内凹缺刻。
耳
相邻三顶点构成对角线在多边形内的三角形
嘴
凹顶点处的内凹区域，非耳
Two-Ear Theorem
两耳定理：任何多于三个顶点的简单多边形至少有两个不相邻的耳。
内容
至少存在两个互不相邻的耳顶点
用途
为切除法提供必然可切的前提
Well-Order
良序化：给顶点排序以便归纳——如按 y 坐标为第一关键字。
排序目的
让归纳有确定的先后次序
多关键字
y 相同用 x 打破并列
Ear Candidate
耳候选点：排序后依次检验的顶点，满足耳条件即切下。
检验
对角线在多边形内且不与其他顶点冲突
切除
切耳产生一条新对角线并少一个顶点
Induction
归纳证明三角剖分：两耳定理保证每步可切，递推到三角形。
归纳基础
三角形本身即自身的剖分
归纳步骤
切掉一耳后剩余仍是简单多边形
Well-Order (Again)
良序再次登场：切除后重新排序或维护次序，支持后续归纳步骤。
次序维护
切除影响邻域顶点的相对关系
一致性
保持排序键的一致使归纳严密
Properties
剖分的性质：n−3 条对角线、n−2 个三角形、对角线互不交叉。
数量关系
对角线数 = n−3，三角形数 = n−2
度数和
剖分对偶图的性质可辅助设计算法
本节要点
- ✓两耳定理保证任何简单多边形可剖分
- ✓切耳归纳：每步割下一个三角形
- ✓n−3 条对角线、n−2 个三角形
延伸主题：实现切耳法三角剖分验证对角线与三角形的数量关系
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1两耳定理的证明核心是什么？
参考答案取 y 坐标最低的凸顶点 v：若其相邻两点的连线落在多边形内，v 即为耳；否则该连线与边界围出的区域内必有更低的凹顶点，其相邻两点构成另一只耳。
2切耳法与单调三角化如何分工？
参考答案切耳法对任意简单多边形通用但 O(n²)；先把多边形单调化再线性三角化总量 O(n log n)。工程上常走「单调化 + 分链三角化」的组合路线。
3耳与嘴在三角剖分算法中扮演什么角色？
参考答案耳是唯一可以「安全切除」的局部结构，切耳归纳靠它推进；嘴（凹区）则是判断某顶点不是耳的反例来源。算法的每一轮都在寻找并切除下一只耳。