概念

设有向直线由点 $P$ 和非零方向向量 $\overrightarrow{v}$ 表示。本文把包含边界的左半平面定义为

$$H(P,\overrightarrow{v})=\{X\mid \overrightarrow{v}\times (\overrightarrow{X}-\overrightarrow{P})\ge 0\}.$$

浮点实现中的“在右侧”应按叉积小于负容限判断；容限应与参与运算的向量尺度匹配，或先对方向进行规范化。落在边界上的点仍属于该闭半平面。整数输入可以使用足够宽的中间类型进行精确方向判定。

​半平面交：多个半平面的交集。

• 半平面交涉及的直线均使用点向式表示。

半平面交一定是凸集，但结果可能为空、无界、退化为线段或点，也可能是有正面积的有界凸多边形。

可以按题意加入一个外框，把问题改成“原半平面交与该外框的交”。只有在题目本来就要求裁剪到该范围，或能够证明外框包含所有可能的有效答案时，这一变换才不影响目标结果。任意选取固定“大数”可能把非空但远离原点的交集误判为空，也会把原本无界的交集改成有限面积的多边形，因此不能用它无条件代替无界性判断。

做法

法一：朴素算法

在已知交集是有界凸多边形，或已经合法加入外框的前提下，求出各直线的交点，判断各交点是否在所有半平面内。

​对满足条件的各点求凸包。

​时间复杂度：$O(n^3)$。

法二：增量法

从一个能够覆盖目标结果的初始凸多边形开始，每次用直线切割当前多边形。若没有经过证明的初始边界，该方法只能得到裁剪后的交集，不能表示一般无界半平面交。

​时间复杂度：$O(n^2)$。

法三：排序增量法

​求凸包算法中，对点进行排序可以有效降低复杂度。

​利用凸多边形各边方向向量的有序性，同样可以对各直线进行排序后求半平面交。

对于方向向量同向的直线，只保留对应左半平面最严格的一条。具体地，对 $L_1=(P_1,\overrightarrow{v})$ 与 $L_2=(P_2,\overrightarrow{v})$：若

$$\overrightarrow{v}\times ({\overrightarrow{P}}_2-{\overrightarrow{P}}_1)>0,$$

则 $H(P_2,\overrightarrow{v})\subset H(P_1,\overrightarrow{v})$，应保留 $L_2$；叉积为 $0$ 时两条边界重合，只需保留一条。“最左”只有结合方向和左半平面定义后才有意义，不能作为独立的几何比较规则。

维护过程：

将直线按方向极角递增排序，并先合并同向平行线。双端队列中只保存仍可能成为边界的直线，其方向严格递增；插入阶段维护的是一条尚未首尾闭合的候选边界链。闭合清理完成前，不能把所有相邻直线交点或队列中半平面的交直接当作当前完整答案。

对新的半平面 $L$，一种经典的“队列只存直线、从队尾加入”实现采用以下顺序。每次准备求端部两线交点前，都必须先确认它们不平行；若平行，应转入下文的同向归并、反向相容或矛盾分支，不能继续执行交点测试。

下面的相邻交点版流程以“目标结果是有界正面积多边形”或“已经合法裁剪到外框”为接口前提。若要原生返回无界、线段、射线、直线或点，相容的反向平行线之间没有有限交点，必须改用能够表示无穷边和低维集合的额外状态；以下队列步骤本身不是处理这些结果的完整模板。

1. 当队列至少有两条直线、队尾两线不平行，且它们的交点严格位于 $L$ 的右侧时，持续弹出队尾；
2. 当队列至少有两条直线、队首两线不平行，且它们的交点严格位于 $L$ 的右侧时，持续弹出队首；
3. 检查 $L$ 与当前端部是否出现平行关系，按对应分支处理后再决定是否将 $L$ 加入队尾。

全部直线处理完后还要进行闭合清理。只有当队列至少有三条直线且待求交的端部两线不平行时，才能用队首半平面检查队尾两线的交点，或用队尾半平面检查队首两线的交点；仍不满足时继续从对应端弹出。清理结束后，也只有在相邻直线以及队尾、队首直线均不平行，并且结果已确认为有界多边形时，才能计算这些交点作为多边形顶点；其它情况应转入空、无界或退化结果分类。

这里“先弹队尾，再弹队首”是上述具体队列表示和入队方式的一部分，不是脱离实现的不变几何定理。在上述两个循环都以“队列至少有两条直线”为条件时，不能机械交换顺序：队列恰有两条线且其交点被新半平面排除时，错误地先弹队首可能删掉本应保留的约束。若改为存交点、直接裁剪凸多边形，或相应调整循环条件和队列不变量，操作顺序可以不同。关键是维护极角有序的候选边界链，并在所有输入处理后完成首尾闭合检查。

每条直线至多入队、出队各一次，合并同向线和维护队列共 $O(n)$，加上极角排序后的总时间复杂度为 $O(n\log n)$。

平行线与空集判断

求相邻直线交点前必须先判断平行，不能除以接近 $0$ 的叉积。同向平行线按前文规则只保留最严格者；反向平行线不能合并，也不能仅凭方向相差 ${180}^{\circ }$ 判空。

例如，有向直线 $(P_1=(0,0),{\overrightarrow{v}}_1=(1,0))$ 表示 $y\ge 0$，$(P_2=(0,1),{\overrightarrow{v}}_2=(-1,0))$ 表示 $y\le 1$。两方向恰好相差 ${180}^{\circ }$，交集却是非空条带 $0\le y\le 1$。

更一般地，若 ${\overrightarrow{v}}_2$ 是 $-{\overrightarrow{v}}_1$ 的正倍数，令

$$\mathrm{\Delta }={\overrightarrow{v}}_1\times ({\overrightarrow{P}}_2-{\overrightarrow{P}}_1),$$

则只考虑这两个闭半平面时：$\mathrm{\Delta }>0$ 得到非空条带，$\mathrm{\Delta }=0$ 退化为公共边界直线，$\mathrm{\Delta }<0$ 才互相矛盾。其它半平面仍可能继续缩小该交集。

方向角差本身不是一般的空集判据。没有合法外框时，队列不足三条也不表示交集为空，它还可能是整个平面、半平面、条带、直线或其它无界/退化凸集。若接口要区分 EMPTY、UNBOUNDED、退化非空集和有界多边形，必须进行相应的可行性与维数判断。

边界与退化结果

由于本文采用闭半平面，交点恰好落在新直线上时仍是可行点，不应按“右侧”弹出；浮点实现通常只在叉积小于负容限时弹出。这有助于保留零面积交集，但仅凭“不弹边界点”不能可靠地区分空集、线段和点。若需要支持多线共点等退化情况，还应去重交点并做额外的非空性和维数检查；许多只返回正面积有界多边形的模板会直接把这些情况排除在接口契约之外。

法四：分治法

​时间复杂度：$O(n\log n)$。

$[l,r]$ 直线的半平面交是 $[l,mid]$ 半平面交和 $[mid+1,r]$ 半平面交的交集。若各子问题都能按契约表示为有界凸多边形，核心在于实现 $O(n)$ 求两个凸多边形的交；无界或退化结果不能未经表示转换就直接套用这一合并。

实现一：

​使用法三求两个凸多边形半平面交得到凸多边形的交。

​因为半平面交求出的交的边是有序的，所以合并 $[l,mid]$ 和 $[mid+1,r]$ 时，两个凸多边形都是有序的，那么使用法三维护的时间复杂度瓶颈即为维护双端队列的复杂度，为 $O(n)$。

实现二：

​对两个凸多边形的顶点进行扫描线，对两相邻竖线之间的梯形求交。单次 $O(1)$，共 $O(n)$ 条竖线。