半平面交
定义:
半平面:
顾名思义,就是平面的一半。一条直线会把平面分成两部分,就是两个半平面。对于半平面,我们可以用直线方程式如:
表示,更常用的是用直线表示。
半平面交:
顾名思义,就是多个半平面求交集。其结果可能是一个凸多边形、无穷平面、直线、线段、点等。
多边形的核:
如果多边形中存在一个区域使得在区域中可以看到多边形中任意位置(反之亦然),则这个区域就是多边形的核。可以用半平面交来求解。
极点:
点
与原点的连线与 轴的夹角,其范围为 [0,360].
为了方便求解我们假设所有的直线的左侧为我们所需要的半平面。
一般来说求解半平面交有两种方法
① 分治法
② 增量法
但是在这里由于分治法常数较大,代码实现较第二种复杂,所以我们着重介绍第二种方法。
算法流程
① 将所有直线极角排序,角度相同的保留下需要的一个
② 用一个双端队列存储当前半平面交,每次通过判断队首与队尾第一个交点是否满足当前直线来更新
③ 先用队尾判定队首交点是否合法,再用队首判断队尾交点是否合法
④ 最后求出来的半平面交是一个凸多边形
极角排序
如下图排序后
所以我们可以更方便的逆时针依次构造,半平面交
由于我们规定了所有的直线的左侧为我们所需要的半平面
所以极角相同的直线,我们保留最靠左的。
构造半平面交
我们可以依照以下流程来构造一个半平面交,并且构造完成的半平面交有多种情况
① 直线、线段、点不合法
② 凸多边形,无穷平面(可以增加4个用于限制的半平面,使得平面变得有限)
我们维护两个双端队列
一个储存当前有用的直线(半平面),一个储存半平面交的点。
我们依次加入每一条直线(半平面),在加入之前先将之前保存了的点,但不是最终半平面交中的点弹出队列
xxxxxxxxxx Point get_nearest_point_on_segment(Point a,Line a1){ Point b=a1.s,c=a1.e; double t=dot(a-b,c-b)/dot(c-b,c-b); if(dcmp(t)!=-1&&dcmp(1-t)!=-1)return Vector(b.x+(c.x-b.x)*t,b.y+(c.y-b.y)*t); if(dist(a,b)<dist(a,c))return b; return c;}cpp
那么加入 直线
所以只要一个点在加入的这条直线的右边我们就将它弹出。
为什么我们要使用双端队列?
可以明显的发现,双端队列的中的点是逆时针排列的
且满足一定的单调性(这个需要自己画图思考,或者配合以下图片思考)
当前加入一条直线,存放点的队列中相邻的两个元素,所对应的直线的极角满足
( 对应点的在队列中的位置位置小于 ) 那么也就是说,这条直线要么使队首的点处于半平面外,要么使队尾的点处于半平面外
但是因为构造半平面交是环形的构造,如下图
我们顺次处理
删去不合法的点
最后队首和队尾都会剩下一些点,它们在半平面交之外
如下图,由于半平面交构造时实际是一个上凸壳和下凸壳,然后是环形的,所以说,会发现某些情况下,有些点多余了
我们需要用队首的直线,判断一下多余的队尾队首的点。
POJ2451模板题,求半平面交面积
AC代码,有注释
1 |
|
- Title: 半平面交
- Author: Reaepita
- Created at: 2022-09-09 19:47:59
- Updated at: 2023-08-06 15:21:43
- Link: https://harrybh.github.io/2022/09/09/半平面交详解/
- License: This work is licensed under CC BY-NC-SA 4.0.