Half-plane Intersection

Half-plane

一條直線把二維平面劃分為兩半,其中一半就是「半平面」。半平面可以包含直線,也可以不包含直線。

半平面的一些圖示方式:

實作時,通常以兩個點來記錄半平面的直線、以兩個點的順序來記錄半平面的方向。

Half-plane Intersection

「半平面交集」就是許多個半平面的交集區域。半平面交集的結果可能是:一個開放區域、一個凸多邊形、一條線、一條線段、一個點、空集合。

Half-plane Intersection: Incremental Method

演算法

一、預先使用四個半平面,設定一個極大的正方形邊界,讓半平面交集擁有邊界。
二、逐一加入每個半平面,求出當下的半平面交集(凸多邊形)。

online演算法,隨時維護一個半平面交集。每次更新需時O(N),總時間複雜度為O(N^2),N是半平面數目。

UVa 10084 10117 11265

演算法

預先排序、預先隨機排列,最差、平均時間複雜度為O(NlogN)。過程如同「Convex Hull: Incremental Method」,求切點改為求交點。

Half-plane Intersection: Divide and Conquer

演算法

時間複雜度為O(NlogN),N是半平面數目。

Divide:把半平面分成兩堆。
Conquer:分別遞迴求解。
Combine:求兩個凸多邊形的交集。O(N)

兩個凸多邊形的交集,可以用旋轉卡尺求解,也可以用掃描線求解。

Half-plane Intersection: 不知名演算法

演算法

2006年由競賽選手南京外国语学校朱泽园《半平面交的新算法及其实用价值》提出。我不清楚是否已有正式學術論文,也不確定演算法是否正確。

半平面交集是一個凸多邊形,凸多邊形的邊很有順序的沿著外圍繞行一圈,越來越傾斜。運用Graham's Scan的精神,預先排序所有半平面,依照極座標角度(不是斜率),逐步找出凸多邊形的邊。

一、所有半平面按照極座標角度排序。O(NlogN)
  角度相同的半平面只需留下最內側的一個。
二、建立一個deque,加入前面兩個半平面。O(1)
三、從第三個半平面開始,依序將半平面加入deque。O(N)
 甲、deque右端持續彈出,直到deque右端的兩個半平面的交點,位於此半平面內。
 乙、deque左端持續彈出,直到deque左端的兩個半平面的交點,位於此半平面內。
 丙、deque右端加入此半平面。
四、刪除deque兩端多餘的半平面。O(N)
 甲、deque右端持續彈出,直到deque右端的兩個半平面的交點,位於deque左端的半平面內。

時間複雜度為O(NlogN),主要取決於排序的時間。N是半平面數目。

有點類似簡單多邊形的凸包演算法Melkman's Algorithm,但是兩者並非點線對偶。