·半平面：平面上的直线及其一侧的部分。
基本介绍
- 中文名：半平面交
- 外文名：intersection of half-planes
- 半平面：平面上的直线及其一侧的部分
- 在线上算法：输入：n个半平面h1,h2,…hn
- 类别：专有名词
基本概念
·半平面可由不等式ax+by+c>=0确定。
·在一个有界区域里半平面或半平面的交是一个凸多边形区域。
·n个半平面的交是一个至多n条边的凸多边形。
在线上算法
procedure intersection of half-planes
输入：n个半平面h1,h2,…hn
输出：h1∩h2∩…∩hn
初始化区域A为整个平面
依次用直线aix+biy+ci=0，i=1,2,…n切割A， 保留使不等式aix+biy+ci>=0成立的部分
输出 A
複杂度O(n^2)，在线上算法
分治算法
假设可以在O(m+n)的时间内将m个半平面的交和n个半平面的交合併，则可以有一种O(n*log(n))的分治算法求半平面的交。
Procedure intersection of half-plane (D&C)
输入：n个半平面H1,H2,…Hn
输出：H1∩H2∩…∩Hn
将H1…Hn分成两个大小近似相等的集合
在每个子问题中递归地计算半平面的交
合併两个凸多边形区域形成H1∩H2∩…∩Hn
问题的关键是怎样在O(m+n)的时间里求两个凸多边形的交。
·将两个凸多边形沿顶点切割成至多O(m+n)个平行于y轴的梯形区域
·每两个梯形区域的交可以在O(1)时间内解决
描述凸多边形的方法 ·凸多边形上方和下方的顶点分别构成一个x坐标递增序列。
·将这两个序列中的顶点分别作为一个鍊表存储,得到确定凸多边形区域的上界和下界。
算法1
procedure intersection of convex polygon
输入：两个凸多边形区域A、B
输出：C=A∩B
1.将两个凸多边形的顶点x坐标分类，得到序列xi,i=1…p
2.初始化区域C为空。
3.处理{x1}
4.依次处理区域(xi,xi+1],i=1…p-1。
5.输出C
算法2
4.依次处理区域(xi,xi+1],i=1…p-1。
4.1 计算两个多边形在此区域里截得的梯形（可能退化）:ABCD和A’B’C’D’。
4.2 求交点AB∩A’B’、AB∩C’D’、CD∩A’B’，将存在的点按x坐标排序，删除重複，添加到C的上界中。
4.3 用类似的方法求C的下界
4.4 计算此区域的右侧边界(线段的交）：EF=BC∩B’C’。将E、F分别加入到C的上界和下界中。
算法3
求n个半平面的交有三种做法：
第一种就是用每个平面去切割已有的凸多边形，複杂度O(n*n)。
第二种就是传说中的分治算法。将n个半平面分成两个部分，分别求完交之后再将两个相交的区域求交集。由于交出来的
都是凸多边形，利用凸多边形的交可以在O(n)时间内完成的性质，将複杂度降为O(nlogn)。
第三种就是ZZY大牛的那篇论文提到的他自创的排序增量算法。但是他的那种做法还是有些複杂，在网上找到evalls写
的一个很优美的版本
step1. 将所有半平面按极角排序，对于极角相同的，选择性的保留一个。 O(nlogn)
step2. 使用一个双端伫列(deque)，加入最开始2个半平面。
step3. 每次考虑一个新的半平面：
a.while deque顶端的两个半平面的交点在当前半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在当前半平面外:删除deque底部的半平面
c.将新半平面加入deque顶端
step4.删除两端多余的半平面。
具体方法是：
a.while deque顶端的两个半平面的交点在底部半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在顶端半平面外:删除deque底部的半平面
重複a,b直到不能删除为止。
step5:计算出deque顶端和底部的交点即可。
这个算法描述的非常清晰。当初写的时候有两个地方想的不太明白：step 1如何选择性的保留一个。step3如何判断交
点在半平面外。
其实这两个问题都可以用叉积来解决。首先根据给定的两点顺序规定好极角序。假定两点o1o2的输入方向是顺时针，那
幺另一点P是否在其平面内只要判断o1P这个向量是否在o1o2这个向量的右手边即可。对于相同角度的两个半平面
(a1a2，b1b2)，可以看a1b1这个向量是否在a1a2这个向量的右手边，每次都要选择更靠近右手边的那个半平面。
利用这个算法求多边形的核（PKU 1279），0.00MS，速度还是很快的。
