凸多边形的逐半平面裁剪

一条边从外面进到窗口，必须先从门口进入，所以先写交点再写终点；从里面离开，则只写最后还留在窗口里的交点。整条轮廓被一条直线切开后，新轮廓沿原边界走一部分，再沿切口连接回来。凸性保证保留部分只有一个连通轮廓。

第 $j$ 轮的不变量是：当前顶点序列准确表示

初始 $j=0$ 成立。一条边与半平面相交只有上述四种情形，按循环次序连接保留下来的边段就得到与下一半平面的交。归纳后，处理完窗口的全部边，得到的恰是 $P\cap W$。

取

先处理 $x\ge 0$。第一条边 $(-1,1)\to (2,-1)$ 从外进入，交点是 $(0,1/3)$；最后一条边 $(2,4)\to (-1,1)$ 从内离开，交点是 $(0,2)$。当前轮廓依次为

下一轮 $x\le 3$ 把右侧两条边截在 $(3,0)$ 和 $(3,10/3)$。处理 $y\ge 0$ 时，左下边又产生 $(1/2,0)$；最后处理 $y\le 2$，得到

因此交集不是整个矩形：左下角的一小块原本就不属于 $P$。用鞋带公式求面积为 $71/12$，也等于矩形面积 $6$ 减去底为 $1/2$、高为 $1/3$ 的三角形面积 $1/12$。这个独立面积核对能发现漏交点或顶点顺序错误。

若改用窗口 $[5,6]\times [1,3]$，交集只有点 $(5,2)$；再把左边移到 $x=6$，交集为空。不能把“少于三个顶点”一律解释为无交，也不能给一个单点输出伪造面积非零的闭环。线段可以用两个端点表示，继续裁剪时按线段与半平面相交处理即可。

此页让两个输入都凸。若被裁对象是凹多边形，一刀可能留下多个分离部分；单个顶点环会用重合桥连接它们，不能再当成一个普通简单多边形返回。若裁剪窗口本身非凸，更不能直接把所有边的左半平面相交当成该窗口：那样得到的是一个凸集。

单个半平面裁剪含 $k$ 个顶点的凸轮廓需要 $O(k)$ 工作和输出存储。一次裁剪至多新增两个交点，而边数最多增加一；经过 $j$ 个半平面后至多有 $n+j$ 个顶点。因此裁一个 $n$ 顶点凸多边形到 $m$ 边窗口的直接界是

辅助轮廓存储为 $O(n+m)$。窗口边数固定时为 $O(n)$。对于两个都很大的凸多边形，存在更专门的线性求交算法；本页不把逐边扫描的成本写成那种算法的界。

所有内外分支都由方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。决定，几何符号必须一致。整数坐标可用足够宽的精确整数求方向，有理交点则保留分子分母；浮点坐标需要带误差保证的谓词。把所有“接近零”都强行算成内部，会改变边界并可能在连续裁剪中留下自相矛盾的点序。

裁剪与点在多边形内判定公理库点在多边形内判定Point in polygon · Point-in-polygon test先识别边界，再以射线横截奇偶或绕数把查询点分类为简单多边形内部、外部或边界。的输出不同：后者只回答一个点的位置，前者构造整个交集。对于给定窗口、绘图区域和局部可行域，逐边裁剪的每个中间状态都能直接画出并检查。