G. Monotone Decomposition
数学大学
G. Monotone Decompositio
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
G. Monotone Decompositio
计算几何 · 03. Triangulation
Cusps
尖点（cusp）：单调化要处理的核心凹点——两条邻边同向的凹顶点。
识别
内角大于 π 且两邻边在该点同侧弯折
危害
尖点破坏 y 单调性，须加对角线劈开
Helper
辅助点（helper）：当前扫描线上、与尖点同侧的最近顶点，尖点与它连对角线。
维护
扫描线状态为每个凹点记录当前 helper
更新时机
扫过新顶点时对应区间的 helper 被替换
Helper Candidate
辅助点候选：新顶点落到某凹点区间时成为新的 helper 候选。
候选条件
与凹点同侧且是当前扫描线上最近的顶点
替换
候选替代旧 helper，关联关系随之转移
Sweep-Line Status
扫描线状态：与扫描线相交的边按 x 排序维护，支撑 helper 的定位。
有序边表
按边的 x 排序，插入删除 O(log n)
配合队列
事件按 y 降序入队驱动扫描
Possible Cases
事件顶点分六类：始点、终点、规则点（左/右）、分裂点、合并点。
分裂点
两邻边都在下方——插入新 helper 的凹点
合并点
两邻边都在上方——需与 helper 连对角线
规则点
一侧在下、一侧在上，直接换 helper
Example
例题：带尖点的多边形经单调化后变成若干单调子多边形。
演示
逐事件展示 helper 更新与对角线生成
结果
对角线条数等于尖点与合并点数之和
Analysis
复杂度：n 个顶点排序 O(n log n)，扫描线性，总体 O(n log n)。
瓶颈
事件排序是唯一超线性环节
产出
产出全部分裂与合并对角线，完成单调化
本节要点
- ✓尖点是单调化的处理对象
- ✓helper 记录区间内最近顶点
- ✓六类事件驱动，总体 O(n log n)
延伸主题：实现分裂点与合并点处理验证单调化输出的单调性
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1分裂点与合并点的本质区别是什么？
参考答案分裂点两邻边都向下，扫到它时凸区域「一分为二」，需要新建 helper；合并点两邻边都向上，两条区间「合二为一」，需要把该点的 helper 与对角线相连。一个是增、一个是并。
2分裂点的 helper 为什么一定要「新建」而不是复用？
参考答案分裂点把当前区间一分为二，两侧各自需要独立的辅助点；旧 helper 只能服务其中一侧，另一侧必须以分裂点自身作为新 helper，否则后续合并点的配对会错乱。
3合并点处理时与「哪个 helper」连对角线？
参考答案与合并点所在区间当前的 helper 相连。helper 是该区间内最近的顶点，连线必落在多边形内部——这恰好把合并点造成的凹缺填平。