单调多边形的线性栈剖分

扫过的顶点不全都需要留着。已经围成三角形的部分可以立即封存；尚未剖分的上方区域，只留下一个由一条边和一段凹链围成的口袋。栈保存这段凹链，从底到顶高度下降。

新点来到另一条链时，能从另一侧看见整段栈链，所以可以一口气剖掉这个口袋。新点仍在同一链时，只有栈顶附近的一段变得可见；顺着凸转向弹栈，遇到第一个遮挡方向便停。条件不是“边长比较”或“顶点高度更低”，而是当前未处理区域的几何形状。

这给出归纳不变量：已输出三角形内部不交；未处理区域仍由未扫描边界和栈上的凹链组成；每条新对角线位于这个区域中。异链清空和同链逐个弹出都保持它，所以无需每次重新对全部边做线段相交检测。

取单调分块页中第三个面，循环边界为

仍使用其坐标及高度 $h=y+x/1000$。从高到低的合并顺序是

初始栈为 $[8,9]$。顶点 $7$ 来自另一链，输出 $(7,8,9)$，更新栈为 $[9,7]$。顶点 $5$ 与 $7$ 同链，并且

它位于该面的右链，所以这个符号允许弹出，输出 $(5,7,9)$，栈变为 $[9,5]$。

接着处理 $v_1$，当前叉积不满足右链弹出条件，不能强行连接到 $v_9$。栈变为 $[9,5,1]$。最后最低点 $v_0$ 依次生成 $(0,1,5)$ 和 $(0,5,9)$。六个顶点得到四个三角形，正好是 $n-2$；新对角线为 $7-!9,5-!9,0-!5$。

这个历史同时包含异链清空、同链成功弹栈和同链停止三种动作。若把右链判断误写为小于零，第二步就会留下本应剖掉的口袋；若忽略链标签，只凭同一个正负号处理两侧，镜像输入会立即失败。

图中的“栈”与单调栈题里的值序列不同。这里的相邻项保存的是边界的几何凹链，并没有要求 $x$ 坐标或边长单调。普通数组极值的支配关系不能代替此处的可见性证明。

每个输入顶点只在首次扫描时加入；用于连接下一轮的旧栈顶可能被保留一次。每次非恒定工作都输出三角形或永久弹掉一个栈记录，总压栈、弹栈次数都是 $O(n)$，输出本身也有 $n-2$ 项。因此两链已排序时，执行时间和空间都为 $O(n)$。两条链各自有序，只需归并，无需重新调用 $O(n\log n)$ 排序。

本单元的独立核验程序为简化事件表使用通用排序；其所展示的栈阶段仍逐次记录压栈、弹栈，但整份参考程序的时间包含排序成本。算法的线性实现应直接归并输入边界两链，而不是用参考代码的排序步骤冒充线性。

平局先用一致的符号剪切消除，方向谓词公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。仍取原坐标。若有共线边界点，不能输出零面积三角形来凑数；可规范化连续共线点并保留映射，或采用支持边界细分的完整退化版本。非单调多边形必须先划分公理库扫描线划分单调多边形Monotone polygon partition · MakeMonotone向下扫描顶点，用活动左边界的 helper 消除 split/merge 顶点，构造互不相交的单调分块。，否则“另一链能看见整个栈”的关键性质没有依据。

与耳切公理库简单多边形的耳切三角剖分Ear clipping triangulation用合法耳三角形逐次缩小简单多边形，并以对角线可见性、覆盖和三角形计数核验输出。相比，这里的速度来自输入已经提供两条单调链这一额外结构。它既不优化最小角，也不保证 Delaunay 空圆性。用于路径查询或有限元组装时，剖分合法性和三角形质量仍是两份不同检查。