半平面交($\operatorname{halfplane intersection}$)
半平面:一条直线可以将一个平面划分成两个平面,一侧的平面称为 半平面
。
直线是有向的,不妨规定沿直线方向的左边是我们关心的直线对应的半平面(包含直线)
半平面交:多个半平面的交集。
大多数情况下,半平面交的结果是一个凸多边形。当然也可以是无界多多边形、直线、线段、点。甚至为空。
增量法
一开始先构造一个足够大的矩形,第一个半平面和它求交。然后每次拿求交的结果(一个凸多边形,由顶点集合表示)再和下一个半平面求交。
凸多边形和一个半平面如何求交:
- 按逆时针顺序对每条边进行处理
- 如果边起点位于新半平面上,则将其加入结果
- 求边与直线的交点,若有交点,则将交点添加到结果
时间复杂度:$O(n^2)$
排序增量法
在求凸包算法中,可以有效降低时间复杂度
利用凸多边形各边方向向量的有序性,同样可以对各直线进行排序后求半平面交
对于方向向量同向的直线,只考虑最靠左的直线
具体算法流程:
用双端队列维护当前的半平面交
当加入一个新的半平面时,可能有以下几种情况:
- 队尾的一些半平面变成冗余的,从队尾弹出
- 队首的一些半平面变成冗余的,从队首弹出
- 半平面交变成空集
如何判断队首/尾半平面是否冗余?
- 队首/尾两直线的交点在新加入直线的右侧
时间复杂度:$O(n\log n)$
例题1: [CQOI2006]凸多边形 /【模板】半平面交
一个凸多边形可以看成多个半平面(取左侧)的交。因此逆时针取出其所有边,则所有边删去右侧的半平面,剩下的即为此凸多边形。
而题目要求多个凸多边形的交的面积。所以把所有凸多边形的边,只取左侧的半平面,按照极角升序排序
(若极角相同,保留更优的)。之后都删去其右侧半平面的部分,剩下的即为所有半平面的交。
总结算法流程:
- 逆时针取出所有边
- 按照极角升序排序,相同极角,取更优的(更靠内侧的)
- 用双端队列存储线段集合,遍历所有线段。判断该线段加入后对半平面交的影响,此时便是
双端队列的作用
:最终的凸多边形是首尾闭合的,因此每加入一条线段后可能会切去当前形成的凸多边形的一部分,而这一部分可能在双端队列中是首尾构成的。因此要对双端队列的头部和尾部进行判断。如果当前判断的线段对新的半平面交没有影响,则从队列中剔除掉。最后剩下的线段集合,即最后要求的半平面交。