半平面交

·半平面可由不等式ax+by+c>=0確定。

·在一個有界區域裏半平面或半平面的交是一個凸多邊形區域。

·n個半平面的交是一個至多n條邊的凸多邊形。

輸入：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))的分治算法求半平面的交。

輸入：n個半平面H1,H2,…Hn

輸出：H1∩H2∩…∩Hn

將H1…Hn分成兩個大小近似相等的集合

在每個子問題中遞歸地計算半平面的交

合併兩個凸多邊形區域形成H1∩H2∩…∩Hn

問題的關鍵是怎樣在O(m+n)的時間裏求兩個凸多邊形的交。

·將兩個凸多邊形沿頂點切割成至多O(m+n)個平行於y軸的梯形區域

·每兩個梯形區域的交可以在O(1)時間內解決

描述凸多邊形的方法 ·凸多邊形上方和下方的頂點分別構成一個x座標遞增序列。

·將這兩個序列中的頂點分別作為一個鏈表存儲,得到確定凸多邊形區域的上界和下界。

輸入：兩個凸多邊形區域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

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的上界和下界中。

求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，速度還是很快的。