半平面交

定义¶

半平面¶

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

解析式一般为。

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

半平面

半平面交¶

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

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

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

多边形的核¶

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

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

解法 - S&I算法¶

极角排序¶

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

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

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

维护单调队列¶

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

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

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

单调队列

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

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

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

队首影响

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

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

得到半平面交¶

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

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

偶尔会出现半平面交不存在或面积为 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 2451 Uyuw's Concert 注意边界

POJ 1279 Art Gallery 求多边形的核

洛谷 P4196 [CQOI2006]凸多边形

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用