“它们面积和为 $38$,内部对角线成对出现。单调划分给出对角线 $(5,7)$、$(1,5)$;第三面 $(5,7,8,9,0,1)$ 的栈剖分以方向值 $\operatorname{ori…”
形式陈述
怎样把任意无孔简单多边形切成容易线性剖分的几块?称一个多边形为
输入顶点
| 邻居位置 | 凸角 | 凹角 |
|---|---|---|
| 两邻居都在下方 | start | split |
| 两邻居都在上方 | end | merge |
| 一上一下 | regular | regular |
split 让一个横截区间分裂,merge 让两个横截区间合并。没有 split 或 merge 的简单多边形就是单调多边形:若某水平线切出两个区间,沿两区间之间的凹口边界向上或向下走,必然遇到一个凹的局部最高点或最低点,恰是这两类之一。
状态只保存横截区间的左边界。每条活动边 helper(e):它是已处理区域中,与
直觉
split 已经看见了上方,马上可以向上接一条合法对角线;merge 需要向下接线,但扫描还没到未来顶点,只能把这项义务存进 helper。以后有人替换这个 helper,或对应边走到终点,便在覆盖它之前先补上对角线。
每次选择左邻边并非为了“就近猜一个点”。helper 与新顶点之间的扫描条带没有被遗漏的顶点事件;若有,helper 早已被更新。由边界不相交和空条带可知,新对角线留在该条带内,并不穿越原边或先前对角线。这是可见性证据,也是局部操作能够组合成全局剖分的原因。
例子与边界
五类事件的实际操作
令 finish(e,v) 表示:若
- start:插入
,令其 helper 为 - end:执行
finish(e_{i-1},v_i),然后删除 - split:找到
正左方的活动边 ,连接 与 helper ,把 helper 改为 ;再插入 ,其 helper 也设为 - merge:先完成并删除
,再找正左方边 ,执行finish(e,v_i),将 helper 改为 - regular:若后继
在下方,内部在扫线穿越该顶点时位于右侧,完成并删除 ,插入 并令 ;否则只找左邻边,完成它的旧 helper 义务并更新 helper
这些操作说明为什么不能只在遇到 merge 当时接线:它需要的下方顶点尚未出现。也不能只在 split 事件检查 helper,否则由 regular 事件接手的 merge 会永远被漏掉。
十边形的一次完整扫描
沿耳切页的十边形编号,采用高度
事件次序为
类型分别是
处理
沿每一面的两条边界链检查
水平边可以用符号剪切
推论与应用
活动边使用支持最坏对数时间更新的平衡搜索树,例如 AVL 树或红黑树。每次事件只做常数次插入、删除、左邻查询;顶点先经比较排序排列,排序及总维护时间为
本单元的核验脚本故意用直接扫描活动边寻找左邻,使 helper 状态容易逐行审计;这个参考实现是
加入
参考资料
- Mark de Berg 等,Computational Geometry: Algorithms and Applications,第 3 版,2008,§3.2,Lemma 3.4、MakeMonotone 及五类事件处理,印刷 pp.49–55。课程原书
- Dave Mount,Polygon Triangulation,2026,单调分块与两阶段剖分。讲义使用水平单调方向;本页选择竖直扫描并明确剪切约定。