一、定義

半平面交是什么？

我們知道一條直線可以把平面分為兩部分，其中一半的平面就叫半平面。那半平面交，就是多個半平面的相交部分。我們在學習線性規(guī)劃時就有用過。

（1）半平面

一條直線和直線的一側(cè)。半平面是一個點集，因此是一條直線和直線的一側(cè)構(gòu)成的點集。當包含直線時，稱為閉半平面；當不包含直線時，稱為開半平面。

解析式一般為。

在計算幾何中用向量表示，整個題統(tǒng)一以向量的左側(cè)或右側(cè)為半平面。

（2）半平面交

半平面交是指多個半平面的交集。因為半平面是點集，所以點集的交集仍然是點集。在平面直角坐標系圍成一個區(qū)域。

這就很像普通的線性規(guī)劃問題了，得到的半平面交就是線性規(guī)劃中的可行域。一般情況下半平面交是有限的，經(jīng)常考察面積等問題的解決。

它可以理解為向量集中每一個向量的右側(cè)的交，或者是下面方程組的解。

多邊形的核

如果一個點集中的點與多邊形上任意一點的連線與多邊形沒有其他交點，那么這個點集被稱為多邊形的核。

把多邊形的每條邊看成是首尾相連的向量，那么這些向量在多邊形內(nèi)部方向的半平面交就是多邊形的核。

二、解法

1. 極角排序

C 語言有一個庫函數(shù)叫做 atan2(double y,double x)，可以返回。

直接以向量為自變量，調(diào)用這個函數(shù)，以返回值為關(guān)鍵字排序，得到新的邊（向量）集。

排序時，如果遇到共線向量（且方向相同），則取靠近可行域的一個。比如兩個向量的極角相同，而我們要的是向量的左側(cè)半平面，那么我們只需要保留左側(cè)的向量。判斷方法是取其中一個向量的起點或終點與另一個比較，檢查是在左邊還是在右邊。

2. 維護單調(diào)隊列

因為半平面交是一個凸多邊形，所以需要維護一個凸殼。因為后來加入的只可能會影響最開始加入的或最后加入的邊（此時凸殼連通），只需要刪除隊首和隊尾的元素，所以需要用單調(diào)隊列。

我們遍歷排好序了的向量，并維護另一個交點數(shù)組。當單隊中元素超過 2 個時，他們之間就會產(chǎn)生交點。

對于當前向量，如果上一個交點在這條向量表示的半平面交的異側(cè)，那么上一條邊就沒有意義了。

如上圖，假設(shè)取向量左側(cè)半平面。極角排序后，遍歷順序應(yīng)該是→→。當和入隊時，在交點數(shù)組里會產(chǎn)生一個點D（交點數(shù)組保存隊列中相同下標的向量與前一向量的交點）。

接下來枚舉到時，發(fā)現(xiàn)D在的右側(cè)。而因為產(chǎn)生D的向量的極角一定比要小，所以產(chǎn)生D的向量（指）就對半平面交沒有影響了。

還有一種可能的情況是快結(jié)束的時候，新加入的向量會從隊首開始造成影響。

仍然假設(shè)取向量左側(cè)半平面。加入向量之后，第一個交點G就在的右側(cè)，我們把上面的判斷標準逆過來看，就知道此時應(yīng)該刪除向量，也即隊首的向量。

最后用隊首的向量排除一下隊尾多余的向量。因為隊首的向量會被后面的約束，而隊尾的向量不會。此時它們圍成了一個環(huán)，因此隊首的向量就可以約束隊尾的向量。

3. 得到半平面交

如果半平面交是一個凸 n 邊形，最后在交點數(shù)組里會得到 n 個點。我們再把它們首尾相連，就是一個統(tǒng)一方向（順或逆時針）的 n 多邊形。

此時就可以用三角剖分求面積了。（求面積是最基礎(chǔ)的考法）

偶爾會出現(xiàn)半平面交不存在或面積為 0 的情況，注意考慮邊界。

三、 求解半平面交的步驟(S&I算法 O(nlogn))

我們試著來解決“求解一個區(qū)域，可以看到給定圖形的各個角落?！?span style="text-indent: 2em;">為了敘述方便，我們把這個區(qū)域叫做多邊形的核。

1. 選取一個正方向。(一般為逆時針)

我們用這個一個不規(guī)則圖形舉例子。

首先我們選逆時針方向做為有向線段。

這樣選取的好處是，保證核在有向線段的左邊。

2. 把有向線段通過極角排序(與 x 軸的夾角)(-180°,180°]

排序結(jié)果如下所示。

按照極角排序的原因是寫代碼方便，排序之后的線段是有序的，可以在雙端隊列里進行操作。(下面會再解釋)。

3. 按順序遍歷每條線段，取左邊區(qū)域，刪右邊區(qū)域

我們用這個S&I算法求解半平面交時，用的是刪減法，首先我們假設(shè)全部平面都是半平面交，然后不斷加入直線，不斷刪去右邊區(qū)域，保留左邊區(qū)域。最后剩下的區(qū)域就是需要求的半平面交。

（1）全部平面都是半平面交。

（2）加入第一條直線，保留左邊區(qū)域，刪除右邊區(qū)域。

（3）加入第二條線段，保留左邊區(qū)域，刪除右邊區(qū)域。

（4）依次加入3 - 10線段，保留左邊區(qū)域，刪除右邊區(qū)域。

（5）加入最后一條線段，保留左邊區(qū)域，刪除右邊區(qū)域。

（6）剩下的藍色部分，就是多邊形的和，也就是所有直線的半平面交，在藍色區(qū)域的任何一點，都可以看到多邊形的每一個角落。

（7）這時我們得到的是圍成這個藍色區(qū)域的直線集合。

L={2，5，7，9，11} ，如果至少有三條邊，就說明該多邊形有核(三條以上時，核為全部直線圍成的凸包。)如果要求面積，我們可以將直線的交點求出來，然后再用叉積求凸包面積。

4. 如果題目要求求面積。

我們可以發(fā)現(xiàn)求出來的直線的集合是有序的L={2，5，7，9，11}，這些直線剛好是逆時針圍著這個半平面交。(這就是按極角排序的好處)。如果要求面積，我們可以把所有L[i] 和L[i+1] 的交點求出來，然后用叉乘求凸包面積。

5. 總結(jié)

總體而言，求半平面交其實就是維護線段的集合 L，遍歷每一條線段，判斷這條線段加入后對于半平面交的影響，然后在集合 L 中剔除掉對半平面交沒有決定作用的邊，留下起決定作用的邊。即最終目的是維護半平面交的線段集合 L。