半平面交的定义和解法

一、定义

半平面交是什么？

我们知道一条直线可以把平面分为两部分，其中一半的平面就叫半平面。那半平面交，就是多个半平面的相交部分。我们在学习线性规划时就有用过。

（1）半平面

一条直线和直线的一侧。半平面是一个点集，因此是一条直线和直线的一侧构成的点集。当包含直线时，称为闭半平面；当不包含直线时，称为开半平面。

解析式一般为。

在计算几何中用向量表示，整个题统一以向量的左侧或右侧为半平面。

（2）半平面交

半平面交是指多个半平面的交集。因为半平面是点集，所以点集的交集仍然是点集。在平面直角坐标系围成一个区域。

这就很像普通的线性规划问题了，得到的半平面交就是线性规划中的可行域。一般情况下半平面交是有限的，经常考察面积等问题的解决。

它可以理解为向量集中每一个向量的右侧的交，或者是下面方程组的解。

多边形的核

如果一个点集中的点与多边形上任意一点的连线与多边形没有其他交点，那么这个点集被称为多边形的核。

把多边形的每条边看成是首尾相连的向量，那么这些向量在多边形内部方向的半平面交就是多边形的核。

二、解法

1. 极角排序

C 语言有一个库函数叫做 atan2(double y,double x)，可以返回。

直接以向量为自变量，调用这个函数，以返回值为关键字排序，得到新的边（向量）集。

排序时，如果遇到共线向量（且方向相同），则取靠近可行域的一个。比如两个向量的极角相同，而我们要的是向量的左侧半平面，那么我们只需要保留左侧的向量。判断方法是取其中一个向量的起点或终点与另一个比较，检查是在左边还是在右边。

2. 维护单调队列

因为半平面交是一个凸多边形，所以需要维护一个凸壳。因为后来加入的只可能会影响最开始加入的或最后加入的边（此时凸壳连通），只需要删除队首和队尾的元素，所以需要用单调队列。

我们遍历排好序了的向量，并维护另一个交点数组。当单队中元素超过 2 个时，他们之间就会产生交点。

对于当前向量，如果上一个交点在这条向量表示的半平面交的异侧，那么上一条边就没有意义了。

如上图，假设取向量左侧半平面。极角排序后，遍历顺序应该是→→。当和入队时，在交点数组里会产生一个点D（交点数组保存队列中相同下标的向量与前一向量的交点）。

接下来枚举到时，发现D在的右侧。而因为产生D的向量的极角一定比要小，所以产生D的向量（指）就对半平面交没有影响了。

还有一种可能的情况是快结束的时候，新加入的向量会从队首开始造成影响。

仍然假设取向量左侧半平面。加入向量之后，第一个交点G就在的右侧，我们把上面的判断标准逆过来看，就知道此时应该删除向量，也即队首的向量。

最后用队首的向量排除一下队尾多余的向量。因为队首的向量会被后面的约束，而队尾的向量不会。此时它们围成了一个环，因此队首的向量就可以约束队尾的向量。

3. 得到半平面交

如果半平面交是一个凸 n 边形，最后在交点数组里会得到 n 个点。我们再把它们首尾相连，就是一个统一方向（顺或逆时针）的 n 多边形。

此时就可以用三角剖分求面积了。（求面积是最基础的考法）

偶尔会出现半平面交不存在或面积为 0 的情况，注意考虑边界。

三、 求解半平面交的步骤(S&I算法 O(nlogn))

我们试着来解决“求解一个区域，可以看到给定图形的各个角落。”为了叙述方便，我们把这个区域叫做多边形的核。

1. 选取一个正方向。(一般为逆时针)

我们用这个一个不规则图形举例子。

首先我们选逆时针方向做为有向线段。

这样选取的好处是，保证核在有向线段的左边。

2. 把有向线段通过极角排序(与 x 轴的夹角)(-180°,180°]

排序结果如下所示。

按照极角排序的原因是写代码方便，排序之后的线段是有序的，可以在双端队列里进行操作。(下面会再解释)。

3. 按顺序遍历每条线段，取左边区域，删右边区域

我们用这个S&I算法求解半平面交时，用的是删减法，首先我们假设全部平面都是半平面交，然后不断加入直线，不断删去右边区域，保留左边区域。最后剩下的区域就是需要求的半平面交。

（1）全部平面都是半平面交。

（2）加入第一条直线，保留左边区域，删除右边区域。

（3）加入第二条线段，保留左边区域，删除右边区域。

（4）依次加入3 - 10线段，保留左边区域，删除右边区域。

（5）加入最后一条线段，保留左边区域，删除右边区域。

（6）剩下的蓝色部分，就是多边形的和，也就是所有直线的半平面交，在蓝色区域的任何一点，都可以看到多边形的每一个角落。

（7）这时我们得到的是围成这个蓝色区域的直线集合。

L={2，5，7，9，11} ，如果至少有三条边，就说明该多边形有核(三条以上时，核为全部直线围成的凸包。)如果要求面积，我们可以将直线的交点求出来，然后再用叉积求凸包面积。

4. 如果题目要求求面积。

我们可以发现求出来的直线的集合是有序的L={2，5，7，9，11}，这些直线刚好是逆时针围着这个半平面交。(这就是按极角排序的好处)。如果要求面积，我们可以把所有L[i] 和L[i+1] 的交点求出来，然后用叉乘求凸包面积。

5. 总结

总体而言，求半平面交其实就是维护线段的集合 L，遍历每一条线段，判断这条线段加入后对于半平面交的影响，然后在集合 L 中剔除掉对半平面交没有决定作用的边，留下起决定作用的边。即最终目的是维护半平面交的线段集合 L。