F. Triangulating Monotone Polygons
数学大学
F. Triangulating Monoton
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
F. Triangulating Monoton
计算几何 · 03. Triangulation
Monotone Polygon
单调多边形：存在一个方向，任何与该方向垂直的直线与边界至多交两点。
单调方向
通常取 y 轴方向作为单调方向
意义
单调多边形可在线性时间三角化
Monotonicity Testing
单调性测试：沿边界行进，区分左链与右链，检查是否始终单调。
双链
从最高点到最低点分出左链与右链
判定
每条链自身 y 坐标单调即可
Strategy
三角化策略：顶点按 y 降序入队，逐个与对侧链的顶点连接对角线。
队列
维护已处理顶点的凸序列
分情形
同侧与异侧的处理规则不同
Stack-Chain Consistency
栈链一致性：栈内顶点始终保持为同一条链上的一段凸链。
不变式
栈序列是左链或右链的凸子链
作用
保证对角线都在多边形内部
Same Side + Reflex
新顶点与栈顶同链且为凹点：不连对角线，只把新点压栈。
压栈
凹点保留，等待后续与对侧连接
条件
判断新点相对栈顶两点的转向
Same Side + Convex
新顶点与栈顶同链且为凸点：连续弹栈连对角线，再把新点压栈。
弹栈连对角线
每弹一个顶点连一条对角线
止于
弹到栈中仅剩一个顶点或转为凹为止
Opposite Side
新顶点来自另一条链：直接与栈中全部顶点连对角线。
全连
异侧时栈内所有顶点都可见
清栈
连完后弹空，压入新点
Example
单调三角化完整例题：从剖分前的单调多边形出发逐步连出全部对角线。
走查
逐顶点演示压栈弹栈与对角线连接
图形验证
对角线互不交叉且覆盖整个多边形
Analysis
复杂度分析：每个顶点压栈一次弹栈至多一次，扫描线性。
压栈
n 个顶点各压栈一次
弹栈摊还
弹栈总数不超过压栈总数，总 O(n)
本节要点
- ✓单调多边形可 O(n) 三角化
- ✓栈链不变式保证对角线合法
- ✓同链分凹凸、异链全连三种情形
延伸主题：实现单调三角化对比切耳法与单调法的效率
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么单调多边形可以线性时间三角化，一般多边形却需要 O(n log n)？
参考答案单调性使顶点天然分成左右两条有序链，扫描一次即能确定全部对角线。一般多边形需先单调化（切出凹点、加对角线），这一预处理本身要 O(n log n)。
2同链凸点连续弹栈为什么不会连出越界对角线？
参考答案栈链是凸链且新点在同侧的更远处：凸链上任何顶点与新点的连线都落在多边形内部（单调区域内的可视性由凸性保证）。这正是栈链不变式存在的意义。
3单调化过程中「劈开凹点」加的对角线算进三角剖分吗？
参考答案算。单调化加的对角线与后续三角化的对角线合在一起构成完整剖分，两部分都不交叉。复杂度分析也因此分两段：单调化 O(n log n) 加三角化 O(n)。