半平面交

定義

半平面

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

解析式一般為 \(Ax+By+C\ge 0\)。

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

半平面

半平面交

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

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

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

\[ \begin{cases} A_1x+B_1y+C\ge 0\\ A_2x+B_2y+C\ge 0\\ \cdots \end{cases} \]

多邊形的核

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

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

解法 - S&I 算法

極角排序

C 語言有一個庫函數叫做 atan2(double y,double x)，可以返回 \(\theta\in (-\pi,\pi]\)，\(\theta =\arctan \frac{y}{x}\)。

直接以向量為自變量，調用這個函數，以返回值為關鍵字排序，得到新的邊（向量）集。

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

維護單調隊列

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

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

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

單調隊列

如上圖，假設取向量左側半平面。極角排序後，遍歷順序應該是 \(\vec a\to\vec b\to\vec c\)。當 \(\vec a\) 和 \(\vec b\) 入隊時，在交點數組裏會產生一個點 \(D\)（交點數組保存隊列中相同下標的向量與前一向量的交點）。

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

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

隊首影響

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

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

得到半平面交

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

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

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

注意事項

當出現一個可以把隊列裏的點全部彈出去的向量（即所有隊列裏的點都在該向量的右側），則我們必須先處理隊尾，再處理隊首。因此在循環中，我們先枚舉 --r; 的部分，再枚舉 ++l; 的部分，才不會錯。原因如下。

一般情況下，我們在隊列（隊列順序為 \(\left\{\vec{u},\vec{v}\right\}\)）後面加一條邊（向量 \(\vec w\)），會產生一個交點 \(N\)，縮小 \(\vec{v}\) 後面的範圍。

但是畢竟每次操作都是一般的，因此可能會有把 \(M\) 點「擠出去」的情況。

如果此時出現了向量 \(\vec a\)，使得 \(M\) 在 \(\vec a\) 的右側，那麼 \(M\) 就要出隊了。此時如果從隊首枚舉 ++l，顯然是擴大了範圍。實際上 \(M\) 點是由 \(\vec u\) 和 \(\vec v\) 共同構成的，因此需要考慮影響到現有進程的是 \(\vec u\) 還是 \(\vec v\)。而因為我們在極角排序後，向量是逆時針順序，所以 \(\vec v\) 的影響要更大一些。

就如上圖，如果 \(M\) 確認在 \(\vec a\) 的右側，那麼此時 \(\vec v\) 的影響一定不會對半平面交的答案作出任何貢獻。

而我們排除隊首的原因是 當前向量的限制比隊首向量要大，這個條件的前提是隊列裏有不止兩個線段（向量），不然就會出現上面的情況。

所以一定要先排除隊尾再排除隊首。

代碼 - 比較部分

friend bool operator<(seg x, seg y) {
  db t1 = atan2((x.b - x.a).y, (x.b - x.a).x);
  db t2 = atan2((y.b - y.a).y, (y.b - y.a).x);  // 求極角
  if (fabs(t1 - t2) > eps)                      // 如果極角不等
    return t1 < t2;
  return (y.a - x.a) * (y.b - x.a) >
         eps;  // 判斷向量x在y的哪邊，令最靠左的排在最左邊
}

代碼 - 增量部分

// pnt its(seg a,seg b)表示求線段a,b的交點
// s[]是極角排序後的向量
// q[]是向量隊列
// t[i]是s[i-1]與s[i]的交點
// 【碼風】隊列的範圍是(l,r]
// 求的是向量左側的半平面
int l = 0, r = 0;
for (int i = 1; i <= n; ++i)
  if (s[i] != s[i - 1]) {
    // 注意要先檢查隊尾
    while (r - l > 1 && (s[i].b - t[r]) * (s[i].a - t[r]) >
                            eps)  // 如果上一個交點在向量右側則彈出隊尾
      --r;
    while (r - l > 1 && (s[i].b - t[l + 2]) * (s[i].a - t[l + 2]) >
                            eps)  // 如果第一個交點在向量右側則彈出隊首
      ++l;
    q[++r] = s[i];
    if (r - l > 1) t[r] = its(q[r], q[r - 1]);  // 求新交點
  }
while (r - l > 1 &&
       (q[l + 1].b - t[r]) * (q[l + 1].a - t[r]) > eps)  // 注意刪除多餘元素
  --r;
t[r + 1] = its(q[l + 1], q[r]);  // 再求出新的交點
++r;
// 這裏不能在t裏面++r需要注意一下……

練習

POJ 2451 Uyuw's Concert 注意邊界

POJ 1279 Art Gallery 求多邊形的核

「CQOI2006」凸多邊形

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：wjy-yy, Ir1d, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用