計算幾何之旋轉卡殼算法

一、目錄

一些曆史：

1978年， M.I. Shamos’s Ph.D. 的論文”Computational Geometry”标志着計算機科學的這一領域的誕生。 當時他發表成果的是一個尋找凸多邊形直徑的一個非常簡單的算法， 即根據多邊形的一對點距離的最大值來确定。 

後來直徑演化為由一對對踵點對來确定。 Shamos提出了一個簡單的 O(n) 時間的算法來确定一個凸 n 角形的對踵點對。 因為他們最多隻有 3n/2 對， 直徑可以在 O(n) 時間内算出。 

如同Toussaint後來提出的， Shamos的算法就像繞着多邊形旋轉一對卡殼。 是以就有了術語“旋轉卡殼”。 1983年， Toussaint發表了一篇論文， 其中用同樣的技術來解決許多問題。 從此， 基于此模型的新算法就确立了， 解決了許多問題。 

他們包括： 

• 計算距離
  • 凸多邊形直徑
  • 凸多邊形寬
  • 凸多邊形間最大距離
  • 凸多邊形間最小距離
• 外接矩形
  • 最小面積外接矩形
  • 最小周長外接矩形
• 三角剖分
  • 洋蔥三角剖分
  • 螺旋三角剖分
  • 四邊形剖分
• 凸多邊形屬性
  • 合并凸包
  • 找共切線
  • 凸多邊形交
  • 臨界切線
  • 凸多邊形矢量和
• 最薄截面
  • 最薄橫截帶

二、計算距離

1.凸多邊形直徑

我們将一個多邊形上任意兩點間的距離的最大值定義為多邊形的直徑。 确定這個直徑的點對數可能多于一對。 事實上， 對于擁有 n 個頂點的多邊形， 就可能有 n 對“直徑點對”存在。 

一個多邊形直徑的簡單例子如左圖所示。 直徑點對在圖中顯示為被平行線穿過的黑點 （紅色的一對平行線）. 直徑用淺藍色高亮顯示。

顯然， 确定一個凸多邊形 P 直徑的點對不可能在多邊形 P 内部。 故搜尋應該在邊界上進行。 事實上， 由于直徑是由多邊形的平行切線的最遠距離決定的， 是以我們隻需要查詢對踵點。 Shamos (1978) 提供了一個 O(n) 時間複雜度計算n點凸包對踵點對的算法。直徑通過周遊頂點清單， 得到最大距離即可。 如下是1985年發表于 Preparata 和 Shamos 文章中的 Shamos 算法的僞代碼。 

輸入是一個多邊形 P={p1,…,pn}. 

begin
     p0:=pn;
     q:=NEXT[p];
     while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do
          q:=NEXT[q];
          q0:=q;
          while (q != p0) do
               begin
                    p:=NEXT[p];
                    Print(p,q);
                    while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do
                         begin
                              q:=NEXT[q];
                              if ((p,q) != (q0,p0)) then Print(p,q)
                              else return
                         end;
                    if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then
                      if ((p,q) != (q0,p0)) then Print(p,NEXT[q])
                      else Print(NEXT[p],q)
               end
end.      

此處 

Print(p,q)

 表示将 (p,q) 作為一個對踵點對輸出， 

Area(p,q,r)

 表示三角形 pqr 的有向面積。 

雖然直覺上看這個過程與正常旋轉卡殼算法不同， 但他們在本質上是相同的， 并且避免了所有角度的計算。 

如下是一個更直覺的算法：

1. 計算多邊形 y 方向上的端點。 我們稱之為 ymin 和 ymax 。
2. 通過 ymin 和 ymax 構造兩條水準切線。 由于他們已經是一對對踵點， 計算他們之間的距離并維護為一個目前最大值。
3. 同時旋轉兩條線直到其中一條與多邊形的一條邊重合。
4. 一個新的對踵點對此時産生。 計算新的距離， 并和目前最大值比較， 大于目前最大值則更新。
5. 重複步驟3和步驟4的過程直到再次産生對踵點對 (ymin,ymax) 。
6. 輸出确定最大直徑的對踵點對。

至此， 上述的過程（僞代碼中的）顯得十分有用， 我們可以從對踵點對中得到其他的資訊， 如多邊形的寬度 。

2. 凸多邊形的寬度

凸多邊形的寬度定義為平行切線間的最小距離。 這個定義從寬度這個詞中已經略有展現。 雖然凸多邊形的切線有不同的方向， 并且每個方向上的寬度（通常）是不同的。 但幸運的是， 不是每個方向上都必須被檢測。 

    我們假設存在一個線段 [a,b]， 以及兩條通過 a 和 b 的平行線。 通過繞着這兩個點旋轉這兩條線， 使他們之間的距離遞增或遞減。 特别的， 總存在一個 特定旋轉方向 使得兩條線之間的距離通過旋轉變小。 

    這個簡單的結論可以被應用于寬度的問題中： 不是所有的方向都需要考慮。 假設給定一個多邊形， 同時還有兩條平行切線。 如果他們都未與邊重合， 那麼我們總能通過旋轉來減小他們之間的距離。 是以， 兩條平行切線隻有在其中至少一條與邊重合的情況下才可能确定多邊形的寬度。 

    這就意味着 “對踵點 點-邊”以及 “邊-邊”對需要在計算寬度過程中被考慮。 

一個凸多邊形寬度的示意圖。 直徑對如圖由平行切線（紅線）穿過的黑點所示。 直徑如高亮的淡藍色線所示。

    一個與計算 直徑問題非常相似的算法可以通過周遊多邊形對踵點對清單得到， 确定頂點-邊以及邊-邊對來計算寬度。 選擇過程如下:

1. 計算多邊形 y 方向上的端點。 我們稱之為 ymin 和 ymax。
2. 通過 ymin 和 ymax 構造兩條水準切線。如果一條（或者兩條）線與邊重合， 那麼一個“對踵點 點-邊”對或者“邊-邊”對已經确立了。 此時， 計算兩線間的距離， 并且存為目前最小距離。
3. 同時旋轉兩條線直到其中一條與多邊形的一條邊重合。
4. 一個新的“對踵點 點-邊”對（或者當兩條線都與邊重合，“邊-邊”對）此時産生。 計算新的距離， 并和目前最小值比較， 小于目前最小值則更新。
5. 重複步驟3和步驟4（卡殼）的過程直到再次達到最初平行邊的位置。
6. 将獲得的最小值的對作為确定寬度的對輸出。

    更為直覺的算法再次因為需要引進角度的計算而展現出其不足。 然而， 就如在凸多邊形間最大距離問題中一樣， 有時候更為簡單、直覺的旋轉卡殼算法必須被引入計算。

3.凸多邊形間最大距離

給定兩個凸多邊形 P 和 Q， 目标是需要找到點對 (p,q) （p 屬于 P 且 q 屬于 Q） 使得他們之間的距離最大。 

很直覺地，這些點不可能屬于他們各自多邊形的内部。 這個條件事實上與直徑問題非常相似： 

兩凸多邊形 P 和 Q 間最大距離由多邊形間的對踵點對确定。 

雖然說法一樣， 但是這個定義與給定凸多邊形的對踵點對的不同。 

與凸多邊形間的對踵點對本質上的差別在于切線是有向且反向的。 下圖展示了一個例子： 

上述結論暗示不單純隻是頂點對需要檢測， 而僅僅是特定的頂點對需要被考慮到。 事實上他們隻檢測一個基于旋轉卡殼模式的算法确立的平行切線。 

考慮如下的算法， 算法的輸入是兩個分别有 m 和 n 個順時針給定頂點的凸多邊形 P 和 Q。

1. 計算 P 上 y 坐标值最小的頂點（稱為 yminP ） 和 Q 上 y 坐标值最大的頂點（稱為 ymaxQ）。
2. 為多邊形在 yminP 和 ymaxQ 處構造兩條切線 LP 和 LQ 使得他們對應的多邊形位于他們的右側。 此時 LP和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個對踵點對。
3. 計算距離(yminP,ymaxQ) 并且将其維護為目前最大值。
4. 順時針同時旋轉平行線直到其中一個與其所在的多邊形的邊重合。
5. 一個新的對踵點對産生了。 計算新距離， 與目前最大值比較， 如果大于目前最大值則更新。 如果兩條線同時與邊發生重合， 此時總共三個對踵點對（先前頂點和新頂點的組合）需要考慮在内。
6. 重複執行步驟4和步驟5， 直到新的點對為(yminP,ymaxQ)。
7. 輸出最大距離。

旋轉卡殼模式確定了所有的對踵點對都被考慮到。 此外， 整個算法擁有線性的時間複雜度， 因為（除了初始化）， 執行步數與頂點數相同。

類似的算法可以被用于凸多邊形間最小距離問題中。

4.凸多邊形間最小距離

給定兩個非連接配接（比如不相交）的凸多邊形 P 和 Q， 目标是找到擁有最小距離的點對 (p,q) （p 屬于 P 且 q 屬于Q）。 

事實上， 多邊形非連接配接十分重要， 因為我們所說的多邊形包含其内部。 如果多邊形相交， 那麼最小距離就變得沒有意義了。 然而， 這個問題的另一個版本， 凸多邊形頂點對間最小距離對于相交和非相交的情況都有解存在。 

回到我們的主問題： 直覺的， 确定最小距離的點不可能包含在多邊形的内部。 與最大距離問題相似， 我們有如下結論： 

兩個凸多邊形 P 和 Q 之間的最小距離由 多邊形間的對踵點對确立。 存在凸多邊形間的三種 多邊形間的對踵點對， 是以就有三種可能存在的最小距離模式：

1. “頂點-頂點”的情況
2. “頂點-邊”的情況
3. “邊-邊”的情況

換句話說， 确定最小距離的點對不一定必須是頂點。 下面的三個圖例表明了以上結論： 

給定結果， 一個基于旋轉卡殼的算法自然而然的産生了: 

考慮如下的算法， 算法的輸入是兩個分别有 m 和 n 個順時針給定頂點的凸多邊形 P 和 Q。

1. 計算 P 上 y 坐标值最小的頂點（稱為 yminP ） 和 Q 上 y 坐标值最大的頂點（稱為 ymaxQ）。
2. 為多邊形在 yminP 和 ymaxQ 處構造兩條切線 LP 和 LQ 使得他們對應的多邊形位于他們的右側。 此時 LP和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個對踵點對。
3. 計算距離(yminP,ymaxQ) 并且将其維護為目前最小值。
4. 順時針同時旋轉平行線直到其中一個與其所在的多邊形的邊重合。
5. 如果隻有一條線與邊重合， 那麼隻需要計算“頂點-邊”對踵點對和“頂點-頂點”對踵點對距離。 都将他們與目前最小值比較， 如果小于目前最小值則進行替換更新。 如果兩條切線都與邊重合， 那麼情況就更加複雜了。 如果邊“交疊”， 也就是可以構造一條與兩條邊都相交的公垂線（但不是在頂點處相交）， 那麼就計算“邊-邊”距離。 否則計算三個新的“頂點-頂點”對踵點對距離。 所有的這些距離都與目前最小值進行比較， 若小于目前最小值則更新替換。
6. 重複執行步驟4和步驟5， 直到新的點對為(yminP,ymaxQ)。
7. 輸出最大距離。

旋轉卡殼模式保證了所有的對踵點對（和所有可能的子情況）都被考慮到。 此外， 整個算法擁有現行的時間複雜度， 因為（除了初始化）， 隻有與頂點數同數量級的操作步數需要執行。 

最小距離和最大距離的問題表明了旋轉卡殼模型可以用在不同的條件下（與先前的直徑和寬度問題比較）。 這個模型可以應用于兩個多邊形的問題中。 

“最小盒子”問題（ 最小面積外接矩形）通過同一多邊形上兩個正交切線集合展示了另一種條件下旋轉卡殼的應用。 

三、外接矩形

1.凸多邊形最小面積外接矩形

給定一個凸多邊形 P ， 面積最小的能裝下 P （就外圍而言）的矩形是怎樣的呢？ 從技術上說， 給定一個方向， 能計算出 P 的端點并且構由此造出外接矩形。 但是我們需要測試每個情形來獲得每個矩形來計算最小面積嗎？ 謝天謝地， 我們不必那麼幹。 

對于多邊形 P 的一個外接矩形存在一條邊與原多邊形的邊共線。 

上述結論有力地限制了矩形的可能範圍。 我們不僅不必去檢測所有可能的方向， 而且隻需要檢測與多邊形邊數相等數量的矩形。 

圖示上述結論： 四條切線（紅色）， 其中一條與多邊形一條邊重合， 确定了外接矩形（藍色）。

一個簡單的算法是依次将每條邊作為與矩形重合的邊進行計算。 但是這種構造矩形的方法涉及到計算多邊形每條邊端點， 一個花費 O(n) 時間（因為有 n 條邊）的計算。 整個算法将有二次時間複雜度。 

一個更高效的算法已經發現。 利用旋轉卡殼， 我們可以在常數時間内實時更新， 而不是重新計算端點。 

實際上， 考慮一個凸多邊形， 擁有兩對和 x 和 y 方向上四個端點相切的切線。 四條線已經确定了一個多邊形的外接矩形。 但是除非多邊形有一條水準的或是垂直的邊， 這個矩形的面積就不能算入最小面積中。 

然而， 可以通過旋轉線直到條件滿足。 這個過程是下屬算法的核心。 假設按照順時針順序輸入一個凸多邊形的n 個頂點。 

1. 計算全部四個多邊形的端點， 稱之為 xminP， xmaxP， yminP， ymaxP。
2. 通過四個點構造 P 的四條切線。 他們确定了兩個“卡殼”集合。
3. 如果一條（或兩條）線與一條邊重合， 那麼計算由四條線決定的矩形的面積， 并且儲存為目前最小值。 否則将目前最小值定義為無窮大。
4. 順時針旋轉線直到其中一條和多邊形的一條邊重合。
5. 計算新矩形的面積， 并且和目前最小值比較。 如果小于目前最小值則更新， 并儲存确定最小值的矩形資訊。 
6. 重複步驟4和步驟5， 直到線旋轉過的角度大于90度。
7. 輸出外接矩形的最小面積。

因為兩對的“卡殼”确定了一個外接矩形， 這個算法考慮到了所有可能算出最小面積的矩形。 進一步， 除了初始值外， 算法的主循環隻需要執行頂點總數多次。 是以算法是線性時間複雜度的。 

一個相似但是鮮為人知的問題是最小周長外接矩形問題。 有趣的是這兩個問題是完全不同的問題， 因為存在（盡管極少）最小面積外接矩形和最小周長外接矩形多邊形不重合的多邊形。

2.凸多邊形最小周長外接矩形

這個問題和最小面積外接矩形相似。 我們的目标是找到一個最小盒子（就周長而言）外接多邊形 P 。 

有趣的是通常情況下最小面積的和最小周長的外接矩形是重合的。 有人不禁想問這是不是總成立的。 下面的例子回答了這個問題： 多邊形（灰色的）及其最小面積外接矩形（左邊的）和最小周長外接矩形（右邊的）。 

現在， 給定一個方向， 我們可以算出 P 的端點， 以此來确定一個外接矩形。 但是， 就如同面積問題中一樣， 由于有下面的結論， 我們不必檢測每個狀态來獲得擁有最小周長的矩形： 

凸多邊形 P 的最小周長外接矩形存在一條邊和多邊形的一條邊重合。 

這個結論通過枚舉多邊形的一條重合邊有力地限制了矩形的可能範圍。 

圖示上述結論： 四條切線（紅色）， 其中一條與多邊形邊重合， 确定了外接矩形（藍色）。

因為與其面積問題相當， 這個問題可以通過一個基于旋轉卡殼的相似的算法來解決。 

下屬算法的輸入是順時針順序給定的一個凸多邊形的 n 個頂點。 

1. 計算全部四個多邊形的端點， 稱之為 xminP， xmaxP， yminP， ymaxP。
2. 通過四個點構造 P 的四條切線。 他們确定了兩個“卡殼”集合。
3. 如果一條（或兩條）線與一條邊重合， 那麼計算由四條線決定的矩形的面積， 并且儲存為目前最小值。 否則将目前最小值定義為無窮大。
4. 順時針旋轉線直到其中一條和多邊形的一條邊重合。
5. 計算新矩形的周長， 并且和目前最小值比較。 如果小于目前最小值則更新， 并儲存确定最小值的矩形資訊。 
6. 重複步驟4和步驟5， 直到線旋轉過的角度大于90度。
7. 輸出外接矩形的最小周長。

因為兩對的“卡殼”确定了一個外接矩形， 這個算法考慮到了所有可能算出最小周長的矩形。 進一步， 除了初始值外， 算法的主循環隻需要執行頂點總數多次。 是以算法是線性時間複雜度的。 

問題處理同樣包含三角形。 有兩個特例， 具體參見洋蔥三角剖分和螺旋三角剖分。

四、三角剖分

1.洋蔥三角剖分

給定一個平面上的點集， 目标是構造一個點集的三角剖分。 

從Lennes 1911年二次時間複雜度的源算法到Chazelle 1991線性時間複雜度的算法， 前人已經做了許多關于提高三角剖分算法效率的研究。 

這裡的焦點是關于一種特殊的三角剖分， 一種基于對點集進行“剝洋蔥皮”操作。 

考慮平面上一個有 n 個點的集合 S 。 計算 S 的凸包， 并且設 S’ 為在凸包内的點集。 然後計算 S’ 的凸包并且反複執行這個操作直到沒有點剩下。 最後剩下了一個像鳥巢一樣層層覆寫的凸包序列， 稱為洋蔥皮集合 S 。 感謝Chazelle的算法， 這個結構能夠在 O(n log n) 時間操作内實作。 

一個點集的洋蔥皮。 注意除了凸多邊形外， 最裡面的結構可能是一條線段或者是一個單一點。 這個圖給出了點的層次資訊， 比如點間哪個相對更“深”。

兩個嵌套的凸包廂的區域稱為一個環面。 Toussaint在1986年發表了一個利用旋轉卡殼計算環面三角剖分的簡單算法。 利用這個方法， 一旦構造出洋蔥皮， 就能在現行時間内構造出三角剖分。 進一步， 這個三角剖分有兩個特點： 他的子圖仍然是洋蔥皮， 并且他是一個哈密爾頓圖， 即三角剖分圖的頂點可以是鍊狀的。 

一個環面的三角剖分算法是非常簡單的。 算法輸入一個被凸包 P 包裹的凸包 Q， 他們的頂點都是順時針序的。

1. 将凸包的邊作為三角剖分的邊插入。
2. 計算 P 和 Q 的 x 坐标最小的點， 分别稱為 xmin(P) 和 xmin(Q) 。
3. 在 xmin(P) 和 xmin(Q) 處構造兩條鉛垂切線， 稱之為 LP 和 LQ 。
4. 将 (xmin(P), xmin(Q)) 作為三角剖分的一條邊插入。
5. 目前 LP 和 LQ 對應的 p 和 q 點分别是 xmin(P) 和 xmin(Q)。
6. 将線順時針旋轉直到其中一個與一條邊重合。 一個新的頂點由此被一條線“擊”出。
   • 如果他屬于 P （稱為 p’）， 插入 (p’, q) 到三角剖分中。 更新目前的點為 p’ 和 p’ 。
   • 如果他屬于 Q （稱為 q’）， 插入 (p, q’) 到三角剖分中。 更新目前的點為 p 和 q’ 。
   • 對于平行邊的情況， 兩條切線都和邊重合， 并且兩個新的頂點被“擊”出（稱他們為 p’ 和 q’）。 然後插入 (p’, q’) ， 以及 (p, q’) 和 (p’, q) 到三角剖分中。 更新目前的點為 p’ 和 q’ 。
7. 重複執行上述步驟直到達到開始的最小點。

一個換面的三角剖分如下所示：

上述的算法擁有線性時間複雜度。 當對于一個點集進行三角剖分的時候， 一個凸包在整個過程中周遊（最多）兩次， 最裡面和最外部的凸包都隻執行周遊一次。 是以對于一個 n 個點的三角剖分的總運作時間是 O(n) 。 

另一個有效且與三角剖分有關的問題是基于點集的凸螺旋線的螺旋三角剖分。 

2.螺旋三角剖分

點集的螺旋三角剖分是基于集合螺旋凸包的三角剖分圖。 

凸螺旋線可以通過如下方法構造：

1. 從一個特定的端點開始（比如給定方向上的最小點）， 這裡取有最小 x 坐标的點。
2. 通過那個點構造一條鉛垂線。
3. 按照一個給定的方向旋轉線（總保持順時針或者是逆時針方向）， 直到線“擊” 出另一個頂點。
4. 将兩個點用一條線段連接配接。
5. 重複步驟3和步驟4， 但是總忽略已經擊出的點。

大體上， 這個過程類似于計算凸包的卷包裹算法， 但是不同在于其循環永遠不會停止。 對于一個凸包上有 h 個點的點集， 存在 2h 個凸螺旋線： 對于每個起點有順時針和逆時針螺旋線兩種。 

一個點集（左邊）， 及其順時針凸螺旋線， 以最小的 x 坐标點作為初始點。

有趣的是， 一個點集的凸螺旋線和洋蔥皮可以線上性時間内互相轉換。 進一步的， 類似于洋蔥三角剖分， 我們可以定義一個點集的子圖為凸螺旋線的螺旋三角剖分。 

構造螺旋三角剖分的算法， 雖然是基于環面三角剖分的， 但是卻更為複雜， 因為螺旋線必須被分割為合适的凸包鍊。 假設輸入是一個點集的順時針凸螺旋線 C ， 且有 C = { p1 , … , pn } 。

1. 将凸螺旋線的邊作為三角剖分的邊插入。
2. 從 p1 開始， 尋找點集凸螺旋線上的最後一個點 ph 。
3. 延長凸螺旋線上的最後一條邊 [p(n-1),pn] 直到其與凸螺旋線相交。 标記交點為 q’ 。
4. 構造與 C 切于點 q’ 的切線。 逆時針旋轉那條線直到他與 C 相交于一點 q 并且平行于 [p(n-1),pn] 。
5. 将 [p(n-1),q] 插入三角剖分中。
6. 此操作後将凸螺旋鍊分割稱了兩個部分： 鍊外的部分和鍊内的多邊形區域。 設 Co = { p1 , … , q } 且 Ci = { ph , … , q , … , pn } 。 這個構造過程如下圖所示：

   

   左上角： 構造過程。 右上角： 螺旋外和内部的多邊形區域。 底部： 外部和内部的凸鍊 Co 和Ci 。
7. 外部螺旋區域可以如環面一樣進行三角剖分。 Co 和 Ci 此時可以被看成一個嵌套凸包。
8. 内部的多邊形區域可以很容易的在 pn 處星型劃分形成三角剖分。
9. 這兩個三角剖分的組合構成了整個螺旋三角剖分的結構。

一個螺旋凸包的例子和其三角剖分如下所示：

上述的算法是線性時間複雜度的， 算法的時間依賴于環面剖分的運作時間。

3.四邊形剖分

雖然三角剖分是一個更常用的結構， 但最近四邊形剖分在某些特定條件下顯得更适用， 比如 scattered data interpolation 以及 finite element method 等。 

一個四邊形剖分實際上是一個點集的四邊形分割。 一些與三角剖分本質上的差別（除了特别明顯的）應該引起注意： 

首先， 不是所有的點集都存在四邊形剖分。 事實上， 隻有偶數點集才有。 對于奇數點集， 有時需要附加點（稱為Steiner點）到原集合中， 進而構造一個四邊形剖分。 

同時， 人們經常期望四邊形剖分構造擁有一些“好的”性質， 比如凸的。 這個與三角剖分是不同的。 

有許多簡單的四邊形剖分算法。 比如， 首先考慮點集的三角剖分， 然後加入一個Steiner點到每個三角形内部， 以及每條邊的中間。 連接配接這些新點構成了四邊形剖分（這是DeBerg提出的）。 

Bose 和 Toussaint 在1997年提出從一個點集的螺旋三角剖分開始， 來構造一個o四邊形剖分。 

如果點集是偶數的， 那麼每隔一個的對角線（在螺旋三角剖分算法中加入的）移除， 構造了一個四邊形剖分。 如果是奇數個點， 那麼從最後一條對角線開始每個隔一條對角線（比如最後一個， 倒數第三個等）進行移除， 在被移除的第一條對角線附近加入一個Steiner點。 下圖展示第一種情況（偶數個點的點集）。 螺旋三角剖分（左邊）， 和最終的四邊形剖分（右邊）。 

因為對角線的移除過程（和必要的更新）花費 O(n) 的時間， 這個四邊形剖分算法與螺旋三角剖分有相同的時間複雜度。 這個算法的優點在于便于了解與實作（一旦凸螺旋線建立）， 并且事實上其産生了一個比許多競争者“更好的”四邊形剖分算法。 

下一個問題集是關于凸多邊形， 特别的， 關于凸包上的操作， 比如合并凸包。

五、凸多邊形屬性

1.合并凸包

考慮如下問題： 給定兩個凸多邊形， 包含他們并的最小凸多邊形是怎樣的？ 答案即合并凸包後得到的凸多邊形。 

合并凸包可以通過一個低效的方式實作： 給定兩個多邊形的所有頂點， 計算這些點對應的凸包。 更高效的方法是存在的， 他依賴于多邊形間的 橋 的查找。 下圖描述了這個概念： 

兩個不相交的凸多邊形。 合并後的凸包包含兩個多邊形中的凸包鍊（途中藍色粗實線）， 通過多邊形間的橋進行連接配接（途中藍色虛線）

給定兩個不相交的多邊形， 在多邊形間存在兩條橋。 多邊形相交時， 擁有和頂點數同樣數量的橋， 如下圖所示： 

兩個相交的凸多邊形。 合并凸包隻包含多邊形間的橋（圖中虛線所示）。 存在連接配接八個頂點的八個橋。

合并操作的核心是分治方法。 他同樣用于多邊形中。 一個擷取凸包的十分簡單的方法是将點集分為兩部分， 分别計算兩個較小點集的凸包， 并且将他們合并。 每個集合再次被分割， 直到元素的個數足夠小（比如說三個或者更少） 是以凸包就能被很容易獲得了。 

Toussaint 提出利用旋轉卡殼來尋找兩個凸多邊形間的橋。 這個方法的主要優點在于其利用回溯， 并且多邊形可以交疊（其他的算法要求多邊形不相交）。 下述結論是他的算法的主要過程： 

給定凸多邊形 P = { p(1) , … , p(m) } 和 Q = { q(1) , … , q(n) }，一個點對 (p(i), q(j)) 形成 P 和 Q 之間的橋當且僅當：

1. (p(i), q(j)) 形成一個并踵點對。
2. p(i-1), p(i+1), q(j-1), q(j+1) 都位于由 (p(i), q(j)) 組成的線的同一側。

假設多邊形以标準形式給出并且頂點是以順時針序排列， 算法如下：

1. 分别計算 P 和 Q 擁有最大 y 坐标的頂點。 如果存在不止一個這樣的點， 取 x 坐标最大的。
2. 構造這些點的遂平切線， 以多邊形處于其右側為正方向（是以他們指向 x 軸正方向）。
3. 同時順時針旋轉兩條切線直到其中一條與邊相交。 得到一個新的并踵點對 (p(i), q(j)) 。 對于平行邊的情況， 得到三個并踵點對。
4. 對于所有有效的并踵點對 (p(i), q(j))： 判定 p(i-1), p(i+1), q(j-1), q(j+1) 是否都位于連接配接點 (p(i), q(j)) 形成的線的同一側。 如果是， 這個并踵點對就形成了一個橋， 并标記他。
5. 重複執行步驟3和步驟4直到切線回到他們原來的位置。
6. 所有可能的橋此時都已經确定了。 通過連續連接配接橋間對應的凸包鍊來構造合并凸包。

上述的結論确定了算法的正确性。 運作時間受步驟1，5，6限制。 他們都為 O(N) 運作時間（N 是頂點總數）。 是以算法擁有現行的時間複雜度。 

一個凸多邊形間的橋實際上确定了另一個有用的概念：多邊形間公切線。 同時， 橋也是計算凸多邊形交的算法核心。

2.找共切線

公切線是同時與多邊形相切的簡單直線， 并且兩個多邊形都位于線的同一側。 換句話說， 一條公切線是一條與兩個多邊形都相切的線。 一個例子如下圖所示： 

兩個不相交的凸多邊形和一條他們的公切線

事實上， 公切線可以通過多邊形間的一些确定橋的點對來确立。 是以， 給定兩個不相交的多邊形， 就存在兩個多邊形間兩條公切線， 并且當多邊形相交時， 還有可能存在與頂點數一樣多的公切線。 

用來計算兩多邊形間橋的算法（如歸并算法）同樣可以用來确定公切線。 

另一個“版本”的兩多邊形的公切線是關鍵切線。 那種情況下多邊形分立于線的兩側。 

橋可以用來計算多邊形的交。

3.凸多邊形交

給定兩個多邊形， 我們第一個需要讨論的問題應該是：“他們相交嗎？”。 Chazelle 和 Dobkin 1980年在他們的一篇叫做“Detection is easier than computation”的論文中發表了一個對數時間級的算法（論文的名字很貼切）。 對于多邊形的交， 許多算法能計算出交集。 有趣的是一個結論（由Guibas提出）證明了多邊形交點和和他們之間的橋是一一對應關系。 

兩個多邊形（淺紅色和藍色）和他們的交集（淺紫色）。 交點以紅色标記。 每個交點與一個多邊形之間的橋（标記為紅色點劃線）有關。

Toussaint在1985年的文獻中利用Guibas的結論， 加上他先前的關于 查找橋的算法來計算交點集。 他的算法利用橋來計算交點集。 一旦他們被找到， 與合并凸包的操作類似， 凸鍊以及交點集形成了多邊形的交集。 

算法的細節， 特别是從橋到交點的計算可以在Toussaint的論文中找到： 

G.T. Toussaint.  A simple linear algorithm for intersecting convex polygons.  The Visual Computer.  1: 118-123. 1985. 

下一個問題設計尋找兩個凸多邊形的 臨界切線。

4.臨界切線

兩個凸多邊形間的臨界切線（一般被叫做CS線）是使得兩個多邊形分居線不同側的切線。 換句話說， 他們分隔了多邊形。

CS線可以應用于motion planning， visibility 和 range fitting。 

下圖是關于兩個多邊形和他們的兩條臨界切線。  

這裡要注意的一點是假設資料是以标準形式給出的， CS線隻會在兩個頂點處與兩個多邊形相交。 是以， 一條CS線由多邊形間頂點對确定。 

如下的結論描述了這個點對： 

給定兩個凸多邊形 P， Q， 兩個頂點 p(i), q(j) （分别屬于 P 和 Q） 确定一條CS線當且僅當：

1. p(i), q(j) 構成多邊形間對踵點對。
2. p(i-1),p(i+1) 位于線 (p(i), q(j)) 一側，同時q(j-1),q(j+1) 位于另一次。

利用這個結論， CS線可以很容易地确定。 隻有多邊形間的對踵點對才需要進行測試。 是以， Toussaint建議使用旋轉卡殼。 假設多邊形是以标準形式給出并且是順時針序排列頂點， 考慮如下過程：

1. 計算 P 上 y 坐标值最小的頂點（稱為 yminP ） 和 Q 上 y 坐标值最大的頂點（稱為 ymaxQ）。
2. 為多邊形在 yminP 和 ymaxQ 處構造兩條切線 LP 和 LQ 使得他們對應的多邊形位于他們的右側。 此時 LP 和 LQ擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個對踵點對。
3. 令 p(i)= yminP， q(j)= ymaxQ。 (p(i), q(j)) 構成了多邊形間的一個對踵點對。 檢測是否有 p(i-1),p(i+1) 線上 (p(i),q(j)) 的一側， 并且 q(j-1),q(j+1) 在另一側。 如果成立， (p(i), q(j)) 确定了一條CS線。
4. 旋轉這兩條線， 直到其中一條和其對應的多邊形的邊重合。
5. 一個新的對踵點對确定了。 如果兩條線都與邊重合， 總共三對對踵點對（原先的頂點和新的頂點的組合）需要考慮。 對于所有的對踵點對， 執行上面的測試。
6. 重複執行步驟4和步驟5， 直到新的點對為(yminP,ymaxQ)。
7. 輸出CS線。

這個算法基本通過繞着多邊形旋轉切線， 順序查找所有多邊形間的對踵點對。 每次一對對踵點确定後， 執行所有必要的測試。 在上述過程執行完後， 所有的臨界切線都被找到了。 

算法的運作時間由步驟1和步驟6決定， 他們都花費  O(n) 的時間（所有的檢測都花費常數時間。 因為有  O(n) 的對踵點對， 總的花費為  O(n)）。 

關于凸多邊形的學習， 最後的操作是 凸多邊形矢量和。

5.凸多邊形矢量和

給定平面上兩個凸多邊形  P 和  Q ，  P 和  Q 的矢量和， 記為  P +  Q 定義如下： P +  Q = {  p +  q } 所有的分别屬于  P 和  Q 的  p 和  q 。

多邊形矢量和在 motion planning 中也稱為 Minkowski 總數。 

考慮上述的定義， 許多問題可以通過詢問集合  P +  Q 的組成， 他擁有的性質等等。 下屬結果幫助我們描述多邊形矢量和。

1. P + Q 是一個凸多邊形。
2. 頂點集 P + Q 是頂點集 P 和 Q 的和。
3. 頂點集 P + Q 是 P 和 Q 間的并踵點對集。
4. 給定分别有 m 和 n 個頂點的 P 和 Q ， P + Q 有不多于 m + n 個頂點。

最後， 下屬結論不僅僅描述了這個問題， 同時也提供了一個一個個頂點的增量式計算矢量和的計算方法。 

給定 P + Q 集合的第 k 個向量 z(k)， 滿足 z(k) = p(i) + q(j)。 構造在 p(i) 和 q(j) 處構造兩條平行切線， 使得多邊形同時位于各自線的右側。 兩條線分别在 p(i) 和 q(j) 處确定了角 theta(i) 和 phi(j) （如下圖所示）

是以下一個向量 z(k+1) 等于：

• p(i+1) + q(j) 若 theta(i) < phi(j)
• p(i) + q(j+1) 若 theta(i) > phi(j)
• p(i+1) + q(j+1) 若 theta(i) = phi(j)

下述的多邊形和他們的矢量和作為一個例子。

兩個凸多邊形。 第一個多邊形的邊用紅色标記， 第二個用藍色。

上述多邊形的矢量和。 其邊的顔色與原多邊形的一緻。

用上述的結果， 我們十分容易的就能構造出一個算法來計算矢量和。 第一個向量可以是在給定方向上邊界向量的和（如 y 軸負方向）。 切線構造後， 在計算角度時候更新， 下一個點就很明确了。 我們需要做的隻是同時旋轉兩條線到新的位置來确定新的角度。 

算法的正确性來自主要的結論； 他是線性時間複雜度的， 因為每一步隻有一個所要求的向量和集合中的向量被确定， 并且他們隻有 m + n 個， 是以總運作時間是 m + n 。

六、最薄截面

1.最薄橫截帶

考慮下述裝置放置問題：一個“消費群體群”的集合是以個體呈現為平面上凸多邊形的一個家庭 F 給出的。 我們的目标是找到一個“裝置”， 一條平面上的直線， 使得線到消費者的最大距離最小。 

最後一點需要澄清。 直線與任何一個多邊形的距離都是指多邊形上一點到線的正交距離的最小值。 是以，每個多邊形到線的距離是唯一的。 

現在， 給定家庭中各個呈多邊形的成員和平面上的一條直線， 每個多邊形都有一個到線的距離。 是以， 對于整個家庭存在一個最大的線-多邊形距離。 這個距離同時依賴于線與各個家庭成員多邊形。 

這個問題的目标是： 給定一個特定的家庭成員多邊形集， 找到使得這個最大距離最小的線。 這個問題同樣存在着其他版本， 常見的有找一條線使得距離和最小， 或是使得多邊形帶權距離和最小。 

這裡的提出的結論是Robert和Toussaint在1990年發表的。 

主問題等價于找到一個寬最小的帶（一個平面上由兩條平行線為邊界的區域）和所有的家庭成員多邊形相交。是以， 帶的中心（與帶的邊界線平行等距的線）就是所求的使得最大距離最小的線。 

為了讨論這個問題我們做如下定義： 

平面上的一條直線 l ， 其方程為 ax + by + c = 0 （且 b >

0 或 a = -1）将平面分為兩個區域：上半平面 Hu(l) 中的點 p = (px,py)

滿足 apx + apy + c >= 0 ， 且下半平面 Hl(l)

中的點 p = (px,py) 滿足 apx + apy + c <=

0 。 

通過上面的定義， 如果線是鉛直的， 上半平面為 x 軸的負方向。 

進一步地， 一個帶可以定義為一條線的上半平面和另一條（平行）線的下半平面的交集。 

給定一個凸多邊形 P ， 一個方向角 theta ， 下切線 tl(P, theta)

是一條與 x 軸正半軸夾角為 theta 的線， 他與 P相交并且 P 在 tl(P, theta)

的上半平面。 交點（可能不止一個）稱為下頂點。 

同樣的， 定義上切線和上頂點。

給定一個家庭的多邊形集合和一個固定的方向角， 就确定了一個下頂點集和上頂點集。 

最後， 考慮下面的結論： 

給定家庭 F 的多邊形集， 和一個方向角 theta ， 一個帶 S （由 Hu(l1)

和 Hl(l2) 大于0的交集得到）是 F （在此方向上）最小寬度帶， 當且僅當 F 中存在兩個多邊形 P 和 Q 有

• P 和 Hu(l1) 的交在 l1 上。
• Q 和 Hl(l2) 的交在 l2 上。

其主要的結論是： 一個家庭 F 的凸多邊形集的最小寬度帶（一個給定方向 theta 上）由 l1 和 l2 确定當

l1=tl(CH(UP(F, theta)), theta)

且

l2=tu(CH(LP(F, theta)), theta)

成立。 

一個家庭的凸多邊形集， 以及給定角度上的最小帶寬。 下頂點和上頂點的凸包， 上述的結論如圖所示。 注意到兩個多邊形和帶的交都隻在一個頂點上出現。

是以， 隻要确定了家庭多邊形集的下頂點和上頂點的序列， 就能通過計算凸包得到給定方向上最小寬度帶。就如Robert和Toussaint解釋的， 幸運的是這些凸包不需要每次都完全重新計算： 他們需要更新即可。 實際上， 考慮兩個接近的方向：許多（或者是全部）多邊形對于這兩個方向擁有相同的上頂點和下頂點。 這個結果同樣暗示這隻有有限的方向上（當下頂點或上頂點變化時）需要檢測。

這裡的焦點在于旋轉卡殼模型， 而非關系到算法的細節。 本文打算利用旋轉卡殼來計算多邊形的上頂點和下頂點。下面是算法的主要實作過程。 給定一個凸多邊形 P ：

1. 找到擁有最小和最大 y 坐标的頂點。 标記為 p 和 q 并且通過他們構造水準切線。
2. 逆時針将切線旋轉過 theta 角直到其中一條與其中一個多邊形的邊平行。
3. 如果頂點在 p 後被擊出（按照逆時針方向）， 那麼 p 就是對于角度0（包括）到角度 theta（不包括） 之間的下頂點。 如果頂點是在 q 後被擊出， 那麼 q 就是同樣角度範圍内的上頂點。 這兩個情況當邊平行的時候也可能同時發生。
4. 更新目前點為新擊出的頂點， 并更新目前角度。
5. 重複執行步驟2到步驟4， 同時跟新角度區間， 知道新的角度大等于180度（在哪一點先回到了最初的位置， 但此時次序颠倒）。

線與其中一個多邊形的一條邊平行的方向稱之為 臨界方向 。 他們隻在上頂點和下頂點處發生變化。 對于一個臨界方向， 因為線穿過兩個頂點， 當逆時針旋轉時下頂點或是上頂點之一被定義為多邊形與線的一個交點。 

一旦臨界方向（按照順序給出）得到， 一個帶就能在第一個方向上進行計算。 然後， 在第二個臨界方向上， 至少一個上頂點或是下頂點被更新。 是以， 凸包此時需要更新， 而非重新計算一次。 一旦完成上述步驟， 新的帶就構造成功了， 并且他的寬度（邊界間的正交距離）被算出。 對所有臨界方向重複這個操作。 注意到如果任何點處如果産生了一個寬度為0的帶f， 這個過程就能夠因為找到一條穿過所有家庭多邊形的線而終止了。