概念

​半平面：有向直线左侧的区域。

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

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

​性质，半平面交一定是凸集。

• 特别地，可以加入一个相当大的边界，将交集无穷大的情况转化为有边界，这样交集可以用一个凸多边形表示。

做法

法一：朴素算法

​求出各直线的交点，判断各交点是否在所有半平面内。

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

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

法二：增量法

​每次用直线去切割当前的凸多边形。

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

法三：排序增量法

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

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

​对于方向向量同向的直线，只需要考虑最左的一个。

维护过程：

​用双端队列维护当前的半平面交。

​当加入一个新的半平面时，可能有以下几种情况。

• 队尾的一些半平面变成冗余的，从队尾弹出。
• 队首的一些半平面变成冗余的，从队首弹出。
• 半平面交变成空集

时间复杂度：$O(n\log n)$。瓶颈在于排序。

判断冗余：

队尾/首两条直线的交点在新加入的直线右侧。

外边界：

在加入外边界的前提下，半平面交中相邻各边逆时针旋转不超过 $180°$。

​当无解的情况出现时，新加入的直线与队首差。一定大于等于 $180°$，并且会把队中除队首外的直线全部弹出。

​因此，每加入一条新直线，弹出冗余半平面后与队尾比较，如果逆时针旋转大于等于 $180°$，则交集为空。

​此时，外边界的加入是必要的。

先处理队尾，再处理队首

​当出现一个可以把队列里的点全部弹出去的向量（即队列里的所有点都在该向量的右侧），则我们必须先处理队尾，再处理队首。

​原因如下：

​一般情况下，我们在队列里（队列顺序为 $\{\overrightarrow{u},\overrightarrow{v}\}$）后面加一条边（向量 $\overrightarrow{w}$），会产生一个交点 $N$，缩小 $\overrightarrow{v}$ 后面的范围。

​但是毕竟每次操作都是一般的，因为可能会有把 $M$ 点挤出去的可能。

如果此时出现了 $\overrightarrow{a}$，使得 $M$ 在 $\overrightarrow{a}$ 的右侧，那么 $M$ 就要出队了。此时如果先处理队首，显然是扩大了范围。实际上 $M$ 点是由 $\overrightarrow{u}$ 和 $\overrightarrow{v}$ 共同构成的，因此需要考虑影响到现有进程的是 $\overrightarrow{u}$ 还是 $\overrightarrow{v}$。而因为我们在极角排序后，向量是逆时针顺序，所以 $\overrightarrow{v}$ 的影响更大一点。

​就如上图，如果 $M$ 确认在 $\overrightarrow{a}$ 的右侧，那么此时 $\overrightarrow{v}$ 的影响一定不会队半平面交的答案作出任何的贡献。

​而我们排除队首的原因是 当前直线的限制比队首大，这个条件的前提是队列里有不止两个直线，不然就会出现上面的情况。

​所以一定要先排除队尾在排除队首。

交点在新加入直线上

​队尾/首两条直线的交点在新加入的直线上时，一般不认为这时的队尾/首是冗余的，这样便可区分出交集面积为 $0$ 与交集为空。

​特殊情况：多条直线交于一点。

法四：分治法

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

​$[l,r]$ 直线的半平面交是 $[l,mid]$ 半平面交和 $[mid+1,r]$ 半平面交的交集。核心在于实现 $O(n)$ 求两个凸多边形的交。

实现一：

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

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

实现二：

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