·半平面：平面上的直線及其一側的部分。
基本介紹
- 中文名：半平面交
- 外文名：intersection of half-planes
- 半平面：平面上的直線及其一側的部分
- 在線上算法：輸入：n個半平面h1,h2,…hn
- 類別：專有名詞
基本概念,在線上算法,分治算法,算法1,算法2,算法3,
基本概念
·半平面可由不等式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，速度還是很快的。
