半平面交 学习笔记【计算几何】
点击量：441
前言
凸包和旋转卡壳都学了，平几就剩个半平面交了吧……
感觉挺有用又听说很好学，于是就学了一下。
有点像线性规划吧。（和想象中有点差距
定义
半平面
一条直线和直线的一侧。半平面是一个点集，因此是一条直线和直线的一侧构成的点集。当包含直线时，称为闭半平面；当不包含直线时，称为开半平面。
解析式一般为$ Ax+By+C\ge 0$。
在计算几何中用向量表示，整个题统一以向量的左侧或右侧为半平面。
半平面交
半平面交是指多个半平面的交集。因为半平面是点集，所以点集的交集仍然是点集。在平面直角坐标系围成一个区域。
这就很像普通的线性规划问题了，得到的半平面交就是线性规划中的可行域。一般情况下半平面交是有限的，经常考察面积等问题的解决。
它可以理解为向量集中每一个向量的右侧的交，或者是下面方程组的解。
$$
\left\{\begin{matrix}
A_1x+B_1y+C\ge 0\\
A_2x+B_2y+C\ge 0\\
\cdots
\end{matrix}\right.
$$
多边形的核
如果一个点集中的点与多边形上任意一点的连线与多边形没有其他交点，那么这个点集被称为多边形的核。
把多边形的每条边看成是首尾相连的向量，那么这些向量在多边形内部方向的半平面交就是多边形的核。
解法 – S&I算法
极角排序
以前一直不会极角排序丢死人了甚至不会写Graham求凸包
C语言有一个库函数叫做atan2(double y,double x)，可以返回$ \theta\in [-\pi,\pi]$（网上很多地方说左边是开的，不过对排序没有影响），$ \theta =\arctan \frac{y}{x}$。
直接以向量为自变量，调用这个函数，以返回值为关键字排序，得到新的边（向量）集。
排序时，如果遇到共线向量（且方向相同），则取靠近可行域的一个。比如两个向量的极角相同，而我们要的是向量的左侧半平面，那么我们只需要保留左侧的向量。判断方法是取其中一个向量的起点或终点与另一个比较，检查是在左边还是在右边。
维护单调队列
因为半平面交是一个凸多边形，所以需要维护一个凸壳。因为后来加入的只可能会影响最开始加入的或最后加入的边（此时凸壳连通），只需要删除队首和队尾的元素，所以需要用单调队列。
我们遍历排好序了的向量，并维护另一个交点数组。当单队中元素超过2个时，他们之间就会产生交点。
对于当前向量，如果上一个交点在这条向量表示的半平面交的异侧，那么上一条边就没有意义了。
如上图，假设取向量左侧半平面。极角排序后，遍历顺序应该是$ \vec a\to\vec b\to\vec c$。当$ \vec a$和$ \vec b$入队时，在交点数组里会产生一个点$ D$（交点数组保存队列中相同下标的向量与前一向量的交点）。
接下来枚举到$ \vec c$时，发现$ D$在$ \vec c$的右侧。而因为产生$ D$的向量的极角一定比$ \vec c$要小，所以产生$ D$的向量（指$ \vec b$）就对半平面交没有影响了。
还有一种可能的情况是快结束的时候，新加入的向量会从队首开始造成影响。
仍然假设取向量左侧半平面。加入向量$ \vec e$之后，第一个交点$ G$就在$ \vec e$的右侧，我们把上面的判断标准逆过来看，就知道此时应该删除向量$ \vec a$，也即队首的向量。
最后用队首的向量排除一下队尾多余的向量。因为队首的向量会被后面的约束，而队尾的向量不会。此时它们围成了一个环，因此队首的向量就可以约束队尾的向量。
得到半平面交
如果半平面交是一个凸$ n$边形，最后在交点数组里会得到$ n$个点。我们再把它们首尾相连，就是一个统一方向（顺或逆时针）的$ n$多边形。
此时就可以用三角剖分求面积了。（求面积是最基础的考法）
偶尔会出现半平面交不存在或面积为0的情况，要注意考虑边界。
代码
比较部分
friend bool operator <(seg x,seg y)
{
db t1=atan2((x.b-x.a).y,(x.b-x.a).x);
db t2=atan2((y.b-y.a).y,(y.b-y.a).x);//求极角
if(fabs(t1-t2)>eps)//如果极角不等
return t1<t2;
return (y.a-x.a)*(y.b-x.a)>eps;//判断向量x在y的哪边，令最靠左的排在最左边
}
增量部分
//pnt its(seg a,seg b)表示求线段a,b的交点
//s[]是极角排序后的向量
//q[]是向量队列
//t[i]是s[i-1]与s[i]的交点
//【码风】队列的范围是(l,r]
//求的是向量左侧的半平面
int l=0,r=0;
for(int i=1;i<=n;++i)
if((s[i]==s[i-1])==false)
{
while(r-l>1&&(s[i].b-t[r])*(s[i].a-t[r])>eps)//如果上一个交点在向量右侧则弹出队尾
--r;
while(r-l>1&&(s[i].b-t[l+2])*(s[i].a-t[l+2])>eps)//如果第一个交点在向量右侧则弹出队首
++l;
q[++r]=s[i];
if(r-l>1)
t[r]=its(q[r],q[r-1]);//求新交点
}
while(r-l>1&&(q[l+1].b-t[r])*(q[l+1].a-t[r])>eps)//注意删除多余元素
--r;
t[r+1]=its(q[l+1],q[r]);//再求出新的交点
++r;
//这里不能在t里面++r需要注意一下……
练习
POJ 1279 Art Gallery 求多边形的核
虽然上面三个可以用同一个板子水过去
说点什么