扫描线划分单调多边形

split 已经看见了上方，马上可以向上接一条合法对角线；merge 需要向下接线，但扫描还没到未来顶点，只能把这项义务存进 helper。以后有人替换这个 helper，或对应边走到终点，便在覆盖它之前先补上对角线。

每次选择左邻边并非为了“就近猜一个点”。helper 与新顶点之间的扫描条带没有被遗漏的顶点事件；若有，helper 早已被更新。由边界不相交和空条带可知，新对角线留在该条带内，并不穿越原边或先前对角线。这是可见性证据，也是局部操作能够组合成全局剖分的原因。

五类事件的实际操作 ​

令 finish(e,v) 表示：若 $\mathrm{helper}(e)$ 为 merge，就连接它与 $v$。连接始终指插入内部对角线，并同步更新DCEL公理库双向连接边表（DCEL）Doubly-connected edge list · DCEL用成对半边、面边界环与顶点关联，把平面细分的局部导航和修改组织成可检查的链接不变量。 或等价的面边界记录。

• start：插入 $e_i$，令其 helper 为 $v_i$
• end：执行 finish(e_{i-1},v_i)，然后删除 $e_{i-1}$
• split：找到 $v_i$ 正左方的活动边 $e$，连接 $v_i$ 与 helper$(e)$，把 helper$(e)$ 改为 $v_i$；再插入 $e_i$，其 helper 也设为 $v_i$
• merge：先完成并删除 $e_{i-1}$，再找正左方边 $e$，执行 finish(e,v_i)，将 helper$(e)$ 改为 $v_i$
• regular：若后继 $v_{i+1}$ 在下方，内部在扫线穿越该顶点时位于右侧，完成并删除 $e_{i-1}$，插入 $e_i$ 并令 $\mathrm{helper}(e_i)=v_i$；否则只找左邻边，完成它的旧 helper 义务并更新 helper

这些操作说明为什么不能只在遇到 merge 当时接线：它需要的下方顶点尚未出现。也不能只在 split 事件检查 helper，否则由 regular 事件接手的 merge 会永远被漏掉。

十边形的一次完整扫描 ​

沿耳切页公理库简单多边形的耳切三角剖分Ear clipping triangulation用合法耳三角形逐次缩小简单多边形，并以对角线可见性、覆盖和三角形计数核验输出。的十边形编号，采用高度 $h(x,y)=y+x/1000$，消除水平边引起的同高事件。这是可逆剪切变换，所有叉积符号保持不变；对这个有界整数实例，选择的系数确实让十个高度互不相同。

事件次序为

类型分别是

处理 $v_7$ 后，活动边 $e_9=v_9{v}_0$ 的 helper 变为 $v_7$，但暂不连接。到 $v_5$ 时，这项 merge 义务产生对角线 $v_5{v}_7$，然后 helper 变为 $v_5$。到 $v_1$ 时，regular 分支再补上 $v_1{v}_5$。最终得到三个面

沿每一面的两条边界链检查 $h$，从最高点到最低点都严格下降。这比只检查“所有凹角似乎都接了线”更直接：输出的目标就是单调性，而不是对角线数量越多越好。

水平边可以用符号剪切 $h=y+\epsilon x$ 定义事件次序，比较按 $(y,x)$ 的字典序进行；几何方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。仍使用原坐标。若采用实际有理剪切，应像本例一样证明或直接检查高度互异，不能对任意实数坐标无条件写死 ${10}^{-3}$。边界共线还需要一致的平角约定和不产生零面积分块的处理。

活动边使用支持最坏对数时间更新的平衡搜索树公理库平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。，例如 AVL 树或红黑树。每次事件只做常数次插入、删除、左邻查询；顶点先经比较排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。排列，排序及总维护时间为 $O(n\log n)$，空间 $O(n)$。边之间不相交，所以两个事件之间的横向顺序不变；这才允许比较器依赖当前高度。任意改变扫线位置、却不按事件维护顺序，会破坏树的有序性。

本单元的核验脚本故意用直接扫描活动边寻找左邻，使 helper 状态容易逐行审计；这个参考实现是 $O(n^2)$，不是平衡树实现的速度证据。它核验插入对角线可见、分块两链单调、面积和保持，再由线性栈剖分公理库单调多边形的线性栈剖分Linear-time monotone polygon triangulation合并两条单调边界链后，用未处理边界的凹链栈在线性时间输出合法对角线。验证每块的三角形数。

加入 $d$ 条对角线后，各块顶点数之和为 $n+2d=O(n)$，因为每条对角线只在两面各计一次。因此后续逐块线性剖分的总成本仍是 $O(n)$，不会把分块后的重复边界误计成 $O(n^2)$。