半平面交的双端队列算法

方向次序把凸边界变成一条只能向同一方向转弯的链。新约束的方向排在所有旧方向后面，因此它可能截掉的候选角点集中在链的两端；中间不能留下“先删一块、再保留一块、再删一块”的交替缺口，否则一条直线与凸链的相交次序会违背凸性。

这里保存的是尚可能属于最终边界的方向有序链。在扫描尚未闭合一圈时，交集可能无界，不能把当前相邻交点草率称为一个已经正确闭合的多边形。末尾的首尾清理正是把开放链变成真实有界边界的必要步骤。

删除队尾的局部理由可以从三条方向递增的线看出：若旧两线交点被新半平面排除，旧尾线在这一端留下的可行边段被夹空；旧前线和新线接起来即可代表这一端的约束边界。队首的论证相同，只发生在方向序列的另一端。这个判断反复应用，保留的每一条边界都有非空的相邻可行段；合约中的最终正面积和有界性保证闭合后至少有三条有效边界。

一条暂存、随后被删的约束 ​

按逆时针顺序取五个点

它们相邻连边的左半平面恰围出这个凸五边形。再加入直线

其方向为 $(4,1)$，保留区域为 $y\ge x/4-5/4$，所以它实际上不切掉五边形。

方向排序后，$AB$ 先入队，接着是 $h$。二者交于 $(5,0)$。加入 $BC$ 时，这个交点在 $BC$ 的右侧，因为

于是 $h$ 被弹出，队尾改由 $AB,BC$ 构成，交点回到真正的顶点 $B$。后续 $CD,DE,EA$ 加入，闭合后得到 $A,B,C,D,E$。这一次删除不是根据 $h$ 的“看起来很远”，而是有精确的局部违反证书。

共点与其他退化边界 ​

例如三角形 $(0,0),(4,0),(0,4)$ 的三条逆时针边，再加入过 $(0,0)$、方向为 $(1,-2)$ 的线，保留半平面 $2x+y\ge 0$。四条边界两两不平行，交集仍是原三角形。新线仅接触 $(0,0)$，严格删除条件不会将它弹出；末尾相邻求交会连续给出两次 $(0,0)$，合并后才得到三个不同顶点。这个规范化只需再扫描一次，不改变线性队列阶段的界。

同向平行约束可以先保留更紧的一条。例如 $y\ge 0$ 与 $y\ge 2$ 只需保留后者。但反向平行线可能围出条带，也可能矛盾；仅按“平行”就报空会把 $0\le y\le 2$ 判错。本页给出的最简求交函数会拒绝平行边界，不能把除零后的数值继续当顶点。

两个相反半平面也可能把可行域压成直线；若再加入其他限制，还可能只剩线段或单点。方向队列最后少于三个普通角点，并不能区分这些情况与空集。因此若接口允许它们，应增加独立的可行性与维数分类，再使用相应的无界/低维输出类型；正面积版本仅返回二维有界多边形；扩大输入范围时，应同时扩大输出类型和判定步骤。

已知有界也不是“任选一个大数作框”。若真正解含坐标 ${10}^{12}$，边长 ${10}^6$ 的框会悄悄删掉它。只有问题本身提供合法边界，或已有证明给出足够的坐标界，才可以把框的四个半平面作为输入的一部分。

比较排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。花 $O(n\log n)$。每条线进入队列一次，离开至多一次，所以所有首尾清理合计 $O(n)$ 次；不能把每次 while 的最坏长度相加成 $O(n^2)$。每次判断只用常数次求交和方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。。这里的算术操作数界以有理数运算为单位，大整数分子分母的位成本需要另外核算。

它把多面体的 H-表示公理库多面体与多胞形Polyhedron · Polytope分别由有限线性不等式交与有限点凸包描述，并由 Minkowski–Weyl 定理连接的凸几何对象。转换成二维顶点表示；而逐半平面裁剪公理库凸多边形的逐半平面裁剪Sutherland–Hodgman clipping for convex polygons · Convex polygon clipping逐条窗口边扫描顶点流，以进入、离开、留在内部三种输出动作构造两个凸多边形的交。从一份已知有界轮廓出发，更容易保留点、线段和空集状态。两种算法的输入合约、状态和保证不同。对于已经按方向排列的凸轮廓约束，排序可以省略；队列阶段本身保持线性。