一、目錄
一些歷史：
1978年， M.I. Shamos's Ph.D. 的論文"Computational Geometry"標(biāo)志著計(jì)算機(jī)科學(xué)的這一領(lǐng)域的誕生。 當(dāng)時(shí)他發(fā)表成果的是一個(gè)尋找凸多邊形直徑的一個(gè)非常簡(jiǎn)單的算法， 即根據(jù)多邊形的一對(duì)點(diǎn)距離的最大值來(lái)確定。
后來(lái)直徑演化為由一對(duì)對(duì)踵點(diǎn)對(duì)來(lái)確定。
Shamos提出了一個(gè)簡(jiǎn)單的 O(n) 時(shí)間的算法來(lái)確定一個(gè)凸 n 角形的對(duì)踵點(diǎn)對(duì)。
因?yàn)樗麄冏疃嘀挥?3n/2 對(duì)， 直徑可以在 O(n) 時(shí)間內(nèi)算出。
如同Toussaint后來(lái)提出的， Shamos的算法就像繞著多邊形旋轉(zhuǎn)一對(duì)卡殼。 因此就有了術(shù)語(yǔ)“旋轉(zhuǎn)卡殼”。 1983年， Toussaint發(fā)表了一篇論文， 其中用同樣的技術(shù)來(lái)解決許多問(wèn)題。 從此， 基于此模型的新算法就確立了， 解決了許多問(wèn)題。
他們包括：
- 計(jì)算距離
- 凸多邊形直徑
- 凸多邊形寬
- 凸多邊形間最大距離
- 凸多邊形間最小距離
- 外接矩形
- 三角剖分
- 凸多邊形屬性
- 最薄截面
二、計(jì)算距離
1.凸多邊形直徑
我們將一個(gè)多邊形上任意兩點(diǎn)間的距離的最大值定義為多邊形的直徑。 確定這個(gè)直徑的點(diǎn)對(duì)數(shù)可能多于一對(duì)。 事實(shí)上， 對(duì)于擁有 n 個(gè)頂點(diǎn)的多邊形，
就可能有 n 對(duì)“直徑點(diǎn)對(duì)”存在。
一個(gè)多邊形直徑的簡(jiǎn)單例子如左圖所示。 直徑點(diǎn)對(duì)在圖中顯示為被平行線穿過(guò)的黑點(diǎn) （紅色的一對(duì)平行線）. 直徑用淺藍(lán)色高亮顯示。
顯然， 確定一個(gè)凸多邊形 P 直徑的點(diǎn)對(duì)不可能在多邊形 P 內(nèi)部。
故搜索應(yīng)該在邊界上進(jìn)行。 事實(shí)上， 由于直徑是由多邊形的平行切線的最遠(yuǎn)距離決定的， 所以我們只需要查詢對(duì)踵點(diǎn)。 Shamos (1978) 提供了一個(gè) O(n) 時(shí)間復(fù)雜度計(jì)算n點(diǎn)凸包對(duì)踵點(diǎn)對(duì)的算法。直徑通過(guò)遍歷頂點(diǎn)列表，
得到最大距離即可。 如下是1985年發(fā)表于 Preparata 和 Shamos 文章中的 Shamos 算法的偽代碼。
輸入是一個(gè)多邊形 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) 作為一個(gè)對(duì)踵點(diǎn)對(duì)輸出， Area(p,q,r) 表示三角形 pqr 的有向面積。
雖然直觀上看這個(gè)過(guò)程與常規(guī)旋轉(zhuǎn)卡殼算法不同， 但他們?cè)诒举|(zhì)上是相同的， 并且避免了所有角度的計(jì)算。
如下是一個(gè)更直觀的算法：
- 計(jì)算多邊形 y 方向上的端點(diǎn)。 我們稱之為 ymin 和 ymax 。
- 通過(guò) ymin 和 ymax 構(gòu)造兩條水平切線。 由于他們已經(jīng)是一對(duì)對(duì)踵點(diǎn)， 計(jì)算他們之間的距離并維護(hù)為一個(gè)當(dāng)前最大值。
- 同時(shí)旋轉(zhuǎn)兩條線直到其中一條與多邊形的一條邊重合。
- 一個(gè)新的對(duì)踵點(diǎn)對(duì)此時(shí)產(chǎn)生。 計(jì)算新的距離， 并和當(dāng)前最大值比較， 大于當(dāng)前最大值則更新。
- 重復(fù)步驟3和步驟4的過(guò)程直到再次產(chǎn)生對(duì)踵點(diǎn)對(duì) (ymin,ymax) 。
- 輸出確定最大直徑的對(duì)踵點(diǎn)對(duì)。
至此， 上述的過(guò)程（偽代碼中的）顯得十分有用， 我們可以從對(duì)踵點(diǎn)對(duì)中得到其他的信息， 如多邊形的寬度 。
2. 凸多邊形的寬度
凸多邊形的寬度定義為平行切線間的最小距離。 這個(gè)定義從寬度這個(gè)詞中已經(jīng)略有體現(xiàn)。 雖然凸多邊形的切線有不同的方向， 并且每個(gè)方向上的寬度（通常）是不同的。 但幸運(yùn)的是， 不是每個(gè)方向上都必須被檢測(cè)。
我們假設(shè)存在一個(gè)線段 [a,b]， 以及兩條通過(guò) a 和 b 的平行線。 通過(guò)繞著這兩個(gè)點(diǎn)旋轉(zhuǎn)這兩條線， 使他們之間的距離遞增或遞減。 特別的， 總存在一個(gè) 特定旋轉(zhuǎn)方向 使得兩條線之間的距離通過(guò)旋轉(zhuǎn)變小。
這個(gè)簡(jiǎn)單的結(jié)論可以被應(yīng)用于寬度的問(wèn)題中： 不是所有的方向都需要考慮。 假設(shè)給定一個(gè)多邊形， 同時(shí)還有兩條平行切線。 如果他們都未與邊重合， 那么我們總能通過(guò)旋轉(zhuǎn)來(lái)減小他們之間的距離。 因此， 兩條平行切線只有在其中至少一條與邊重合的情況下才可能確定多邊形的寬度。
這就意味著“對(duì)踵點(diǎn) 點(diǎn)-邊”以及“邊-邊”對(duì)需要在計(jì)算寬度過(guò)程中被考慮。
一個(gè)凸多邊形寬度的示意圖。 直徑對(duì)如圖由平行切線（紅線）穿過(guò)的黑點(diǎn)所示。 直徑如高亮的淡藍(lán)色線所示。
一個(gè)與計(jì)算直徑問(wèn)題非常相似的算法可以通過(guò)遍歷多邊形對(duì)踵點(diǎn)對(duì)列表得到， 確定頂點(diǎn)-邊以及邊-邊對(duì)來(lái)計(jì)算寬度。 選擇過(guò)程如下:
- 計(jì)算多邊形 y 方向上的端點(diǎn)。 我們稱之為 ymin 和 ymax。
- 通過(guò) ymin 和 ymax 構(gòu)造兩條水平切線。如果一條（或者兩條）線與邊重合， 那么一個(gè)“對(duì)踵點(diǎn) 點(diǎn)-邊”對(duì)或者“邊-邊”對(duì)已經(jīng)確立了。 此時(shí)， 計(jì)算兩線間的距離， 并且存為當(dāng)前最小距離。
- 同時(shí)旋轉(zhuǎn)兩條線直到其中一條與多邊形的一條邊重合。
- 一個(gè)新的“對(duì)踵點(diǎn) 點(diǎn)-邊”對(duì)（或者當(dāng)兩條線都與邊重合，“邊-邊”對(duì)）此時(shí)產(chǎn)生。 計(jì)算新的距離， 并和當(dāng)前最小值比較， 小于當(dāng)前最小值則更新。
- 重復(fù)步驟3和步驟4（卡殼）的過(guò)程直到再次達(dá)到最初平行邊的位置。
- 將獲得的最小值的對(duì)作為確定寬度的對(duì)輸出。
更為直觀的算法再次因?yàn)樾枰M(jìn)角度的計(jì)算而體現(xiàn)出其不足。 然而， 就如在凸多邊形間最大距離問(wèn)題中一樣， 有時(shí)候更為簡(jiǎn)單、直觀的旋轉(zhuǎn)卡殼算法必須被引入計(jì)算。
3.凸多邊形間最大距離
給定兩個(gè)凸多邊形 P 和 Q， 目標(biāo)是需要找到點(diǎn)對(duì) (p,q) （p 屬于 P 且 q 屬于 Q） 使得他們之間的距離最大。
很直觀地，這些點(diǎn)不可能屬于他們各自多邊形的內(nèi)部。 這個(gè)條件事實(shí)上與直徑問(wèn)題非常相似：
兩凸多邊形 P 和 Q 間最大距離由多邊形間的對(duì)踵點(diǎn)對(duì)確定。
雖然說(shuō)法一樣， 但是這個(gè)定義與給定凸多邊形的對(duì)踵點(diǎn)對(duì)的不同。
與凸多邊形間的對(duì)踵點(diǎn)對(duì)本質(zhì)上的區(qū)別在于切線是有向且反向的。 下圖展示了一個(gè)例子：
上述結(jié)論暗示不單純只是頂點(diǎn)對(duì)需要檢測(cè)， 而僅僅是特定的頂點(diǎn)對(duì)需要被考慮到。 事實(shí)上他們只檢測(cè)一個(gè)基于旋轉(zhuǎn)卡殼模式的算法確立的平行切線。
考慮如下的算法， 算法的輸入是兩個(gè)分別有 m 和 n 個(gè)順時(shí)針給定頂點(diǎn)的凸多邊形 P 和 Q。
- 計(jì)算 P 上 y 坐標(biāo)值最小的頂點(diǎn)（稱為 yminP ） 和 Q 上 y 坐標(biāo)值最大的頂點(diǎn)（稱為 ymaxQ）。
- 為多邊形在 yminP 和 ymaxQ 處構(gòu)造兩條切線 LP 和 LQ 使得他們對(duì)應(yīng)的多邊形位于他們的右側(cè)。 此時(shí) LP和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個(gè)對(duì)踵點(diǎn)對(duì)。
- 計(jì)算距離(yminP,ymaxQ) 并且將其維護(hù)為當(dāng)前最大值。
- 順時(shí)針同時(shí)旋轉(zhuǎn)平行線直到其中一個(gè)與其所在的多邊形的邊重合。
- 一個(gè)新的對(duì)踵點(diǎn)對(duì)產(chǎn)生了。 計(jì)算新距離， 與當(dāng)前最大值比較， 如果大于當(dāng)前最大值則更新。 如果兩條線同時(shí)與邊發(fā)生重合， 此時(shí)總共三個(gè)對(duì)踵點(diǎn)對(duì)（先前頂點(diǎn)和新頂點(diǎn)的組合）需要考慮在內(nèi)。
- 重復(fù)執(zhí)行步驟4和步驟5， 直到新的點(diǎn)對(duì)為(yminP,ymaxQ)。
- 輸出最大距離。
旋轉(zhuǎn)卡殼模式確保了所有的對(duì)踵點(diǎn)對(duì)都被考慮到。 此外， 整個(gè)算法擁有線性的時(shí)間復(fù)雜度， 因?yàn)椋ǔ顺跏蓟?執(zhí)行步數(shù)與頂點(diǎn)數(shù)相同。
類似的算法可以被用于凸多邊形間最小距離問(wèn)題中。
4.凸多邊形間最小距離
給定兩個(gè)非連接（比如不相交）的凸多邊形 P 和 Q， 目標(biāo)是找到擁有最小距離的點(diǎn)對(duì) (p,q) （p 屬于 P 且 q 屬于Q）。
事實(shí)上， 多邊形非連接十分重要， 因?yàn)槲覀兯f(shuō)的多邊形包含其內(nèi)部。 如果多邊形相交， 那么最小距離就變得沒(méi)有意義了。 然而， 這個(gè)問(wèn)題的另一個(gè)版本， 凸多邊形頂點(diǎn)對(duì)間最小距離對(duì)于相交和非相交的情況都有解存在。
回到我們的主問(wèn)題： 直觀的， 確定最小距離的點(diǎn)不可能包含在多邊形的內(nèi)部。 與最大距離問(wèn)題相似， 我們有如下結(jié)論：
兩個(gè)凸多邊形 P 和 Q 之間的最小距離由多邊形間的對(duì)踵點(diǎn)對(duì)確立。 存在凸多邊形間的三種多邊形間的對(duì)踵點(diǎn)對(duì)， 因此就有三種可能存在的最小距離模式：
- “頂點(diǎn)-頂點(diǎn)”的情況
- “頂點(diǎn)-邊”的情況
- “邊-邊”的情況
換句話說(shuō)， 確定最小距離的點(diǎn)對(duì)不一定必須是頂點(diǎn)。 下面的三個(gè)圖例表明了以上結(jié)論：
  
給定結(jié)果， 一個(gè)基于旋轉(zhuǎn)卡殼的算法自然而然的產(chǎn)生了:
考慮如下的算法， 算法的輸入是兩個(gè)分別有 m 和 n 個(gè)順時(shí)針給定頂點(diǎn)的凸多邊形 P 和 Q。
- 計(jì)算 P 上 y 坐標(biāo)值最小的頂點(diǎn)（稱為 yminP ） 和 Q 上 y 坐標(biāo)值最大的頂點(diǎn)（稱為 ymaxQ）。
- 為多邊形在 yminP 和 ymaxQ 處構(gòu)造兩條切線 LP 和 LQ 使得他們對(duì)應(yīng)的多邊形位于他們的右側(cè)。 此時(shí) LP和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個(gè)對(duì)踵點(diǎn)對(duì)。
- 計(jì)算距離(yminP,ymaxQ) 并且將其維護(hù)為當(dāng)前最小值。
- 順時(shí)針同時(shí)旋轉(zhuǎn)平行線直到其中一個(gè)與其所在的多邊形的邊重合。
- 如果只有一條線與邊重合， 那么只需要計(jì)算“頂點(diǎn)-邊”對(duì)踵點(diǎn)對(duì)和“頂點(diǎn)-頂點(diǎn)”對(duì)踵點(diǎn)對(duì)距離。 都將他們與當(dāng)前最小值比較， 如果小于當(dāng)前最小值則進(jìn)行替換更新。 如果兩條切線都與邊重合， 那么情況就更加復(fù)雜了。 如果邊“交疊”， 也就是可以構(gòu)造一條與兩條邊都相交的公垂線（但不是在頂點(diǎn)處相交）， 那么就計(jì)算“邊-邊”距離。 否則計(jì)算三個(gè)新的“頂點(diǎn)-頂點(diǎn)”對(duì)踵點(diǎn)對(duì)距離。 所有的這些距離都與當(dāng)前最小值進(jìn)行比較， 若小于當(dāng)前最小值則更新替換。
- 重復(fù)執(zhí)行步驟4和步驟5， 直到新的點(diǎn)對(duì)為(yminP,ymaxQ)。
- 輸出最大距離。
旋轉(zhuǎn)卡殼模式保證了所有的對(duì)踵點(diǎn)對(duì)（和所有可能的子情況）都被考慮到。 此外， 整個(gè)算法擁有現(xiàn)行的時(shí)間復(fù)雜度， 因?yàn)椋ǔ顺跏蓟?只有與頂點(diǎn)數(shù)同數(shù)量級(jí)的操作步數(shù)需要執(zhí)行。
最小距離和最大距離的問(wèn)題表明了旋轉(zhuǎn)卡殼模型可以用在不同的條件下（與先前的直徑和寬度問(wèn)題比較）。 這個(gè)模型可以應(yīng)用于兩個(gè)多邊形的問(wèn)題中。
“最小盒子”問(wèn)題（最小面積外接矩形）通過(guò)同一多邊形上兩個(gè)正交切線集合展示了另一種條件下旋轉(zhuǎn)卡殼的應(yīng)用。
三、外接矩形
1.凸多邊形最小面積外接矩形
給定一個(gè)凸多邊形 P ， 面積最小的能裝下 P （就外圍而言）的矩形是怎樣的呢？ 從技術(shù)上說(shuō)， 給定一個(gè)方向， 能計(jì)算出 P 的端點(diǎn)并且構(gòu)由此造出外接矩形。 但是我們需要測(cè)試每個(gè)情形來(lái)獲得每個(gè)矩形來(lái)計(jì)算最小面積嗎？ 謝天謝地， 我們不必那么干。
對(duì)于多邊形 P 的一個(gè)外接矩形存在一條邊與原多邊形的邊共線。
上述結(jié)論有力地限制了矩形的可能范圍。 我們不僅不必去檢測(cè)所有可能的方向， 而且只需要檢測(cè)與多邊形邊數(shù)相等數(shù)量的矩形。
 圖示上述結(jié)論： 四條切線（紅色）， 其中一條與多邊形一條邊重合， 確定了外接矩形（藍(lán)色）。
一個(gè)簡(jiǎn)單的算法是依次將每條邊作為與矩形重合的邊進(jìn)行計(jì)算。 但是這種構(gòu)造矩形的方法涉及到計(jì)算多邊形每條邊端點(diǎn)， 一個(gè)花費(fèi) O(n) 時(shí)間（因?yàn)橛?nbsp;n 條邊）的計(jì)算。 整個(gè)算法將有二次時(shí)間復(fù)雜度。
一個(gè)更高效的算法已經(jīng)發(fā)現(xiàn)。 利用旋轉(zhuǎn)卡殼， 我們可以在常數(shù)時(shí)間內(nèi)實(shí)時(shí)更新， 而不是重新計(jì)算端點(diǎn)。
實(shí)際上， 考慮一個(gè)凸多邊形， 擁有兩對(duì)和 x 和 y 方向上四個(gè)端點(diǎn)相切的切線。 四條線已經(jīng)確定了一個(gè)多邊形的外接矩形。 但是除非多邊形有一條水平的或是垂直的邊， 這個(gè)矩形的面積就不能算入最小面積中。
然而， 可以通過(guò)旋轉(zhuǎn)線直到條件滿足。 這個(gè)過(guò)程是下屬算法的核心。 假設(shè)按照順時(shí)針順序輸入一個(gè)凸多邊形的n 個(gè)頂點(diǎn)。
- 計(jì)算全部四個(gè)多邊形的端點(diǎn)， 稱之為 xminP， xmaxP， yminP， ymaxP。
- 通過(guò)四個(gè)點(diǎn)構(gòu)造 P 的四條切線。 他們確定了兩個(gè)“卡殼”集合。
- 如果一條（或兩條）線與一條邊重合， 那么計(jì)算由四條線決定的矩形的面積， 并且保存為當(dāng)前最小值。 否則將當(dāng)前最小值定義為無(wú)窮大。
- 順時(shí)針旋轉(zhuǎn)線直到其中一條和多邊形的一條邊重合。
- 計(jì)算新矩形的面積， 并且和當(dāng)前最小值比較。 如果小于當(dāng)前最小值則更新， 并保存確定最小值的矩形信息。
- 重復(fù)步驟4和步驟5， 直到線旋轉(zhuǎn)過(guò)的角度大于90度。
- 輸出外接矩形的最小面積。
因?yàn)閮蓪?duì)的“卡殼”確定了一個(gè)外接矩形， 這個(gè)算法考慮到了所有可能算出最小面積的矩形。 進(jìn)一步， 除了初始值外， 算法的主循環(huán)只需要執(zhí)行頂點(diǎn)總數(shù)多次。 因此算法是線性時(shí)間復(fù)雜度的。
一個(gè)相似但是鮮為人知的問(wèn)題是最小周長(zhǎng)外接矩形問(wèn)題。 有趣的是這兩個(gè)問(wèn)題是完全不同的問(wèn)題， 因?yàn)榇嬖冢ūM管極少）最小面積外接矩形和最小周長(zhǎng)外接矩形多邊形不重合的多邊形。
2.凸多邊形最小周長(zhǎng)外接矩形
這個(gè)問(wèn)題和最小面積外接矩形相似。 我們的目標(biāo)是找到一個(gè)最小盒子（就周長(zhǎng)而言）外接多邊形 P 。
有趣的是通常情況下最小面積的和最小周長(zhǎng)的外接矩形是重合的。 有人不禁想問(wèn)這是不是總成立的。 下面的例子回答了這個(gè)問(wèn)題： 多邊形（灰色的）及其最小面積外接矩形（左邊的）和最小周長(zhǎng)外接矩形（右邊的）。
現(xiàn)在， 給定一個(gè)方向， 我們可以算出 P 的端點(diǎn)， 以此來(lái)確定一個(gè)外接矩形。 但是， 就如同面積問(wèn)題中一樣， 由于有下面的結(jié)論， 我們不必檢測(cè)每個(gè)狀態(tài)來(lái)獲得擁有最小周長(zhǎng)的矩形：
凸多邊形 P 的最小周長(zhǎng)外接矩形存在一條邊和多邊形的一條邊重合。
這個(gè)結(jié)論通過(guò)枚舉多邊形的一條重合邊有力地限制了矩形的可能范圍。
圖示上述結(jié)論： 四條切線（紅色）， 其中一條與多邊形邊重合， 確定了外接矩形（藍(lán)色）。
因?yàn)榕c其面積問(wèn)題相當(dāng)， 這個(gè)問(wèn)題可以通過(guò)一個(gè)基于旋轉(zhuǎn)卡殼的相似的算法來(lái)解決。
下屬算法的輸入是順時(shí)針順序給定的一個(gè)凸多邊形的 n 個(gè)頂點(diǎn)。
- 計(jì)算全部四個(gè)多邊形的端點(diǎn)， 稱之為 xminP， xmaxP， yminP， ymaxP。
- 通過(guò)四個(gè)點(diǎn)構(gòu)造 P 的四條切線。 他們確定了兩個(gè)“卡殼”集合。
- 如果一條（或兩條）線與一條邊重合， 那么計(jì)算由四條線決定的矩形的面積， 并且保存為當(dāng)前最小值。 否則將當(dāng)前最小值定義為無(wú)窮大。
- 順時(shí)針旋轉(zhuǎn)線直到其中一條和多邊形的一條邊重合。
- 計(jì)算新矩形的周長(zhǎng)， 并且和當(dāng)前最小值比較。 如果小于當(dāng)前最小值則更新， 并保存確定最小值的矩形信息。
- 重復(fù)步驟4和步驟5， 直到線旋轉(zhuǎn)過(guò)的角度大于90度。
- 輸出外接矩形的最小周長(zhǎng)。
因?yàn)閮蓪?duì)的“卡殼”確定了一個(gè)外接矩形， 這個(gè)算法考慮到了所有可能算出最小周長(zhǎng)的矩形。 進(jìn)一步， 除了初始值外， 算法的主循環(huán)只需要執(zhí)行頂點(diǎn)總數(shù)多次。 因此算法是線性時(shí)間復(fù)雜度的。
問(wèn)題處理同樣包含三角形。 有兩個(gè)特例， 具體參見(jiàn)洋蔥三角剖分和螺旋三角剖分。
四、三角剖分
1.洋蔥三角剖分
給定一個(gè)平面上的點(diǎn)集， 目標(biāo)是構(gòu)造一個(gè)點(diǎn)集的三角剖分。
從Lennes 1911年二次時(shí)間復(fù)雜度的源算法到Chazelle 1991線性時(shí)間復(fù)雜度的算法， 前人已經(jīng)做了許多關(guān)于提高三角剖分算法效率的研究。
這里的焦點(diǎn)是關(guān)于一種特殊的三角剖分， 一種基于對(duì)點(diǎn)集進(jìn)行“剝洋蔥皮”操作。
考慮平面上一個(gè)有 n 個(gè)點(diǎn)的集合 S 。 計(jì)算 S 的凸包， 并且設(shè) S' 為在凸包內(nèi)的點(diǎn)集。 然后計(jì)算 S' 的凸包并且反復(fù)執(zhí)行這個(gè)操作直到?jīng)]有點(diǎn)剩下。 最后剩下了一個(gè)像鳥(niǎo)巢一樣層層覆蓋的凸包序列， 稱為洋蔥皮集合 S 。 感謝Chazelle的算法， 這個(gè)結(jié)構(gòu)能夠在 O(n log n) 時(shí)間操作內(nèi)實(shí)現(xiàn)。
 一個(gè)點(diǎn)集的洋蔥皮。 注意除了凸多邊形外，
最里面的結(jié)構(gòu)可能是一條線段或者是一個(gè)單一點(diǎn)。 這個(gè)圖給出了點(diǎn)的層次信息， 比如點(diǎn)間哪個(gè)相對(duì)更“深”。
兩個(gè)嵌套的凸包間的區(qū)域稱為一個(gè)環(huán)面。 Toussaint在1986年發(fā)表了一個(gè)利用旋轉(zhuǎn)卡殼計(jì)算環(huán)面三角剖分的簡(jiǎn)單算法。 利用這個(gè)方法， 一旦構(gòu)造出洋蔥皮， 就能在現(xiàn)行時(shí)間內(nèi)構(gòu)造出三角剖分。 進(jìn)一步， 這個(gè)三角剖分有兩個(gè)特點(diǎn)： 他的子圖仍然是洋蔥皮， 并且他是一個(gè)哈密爾頓圖， 即三角剖分圖的頂點(diǎn)可以是鏈狀的。
一個(gè)環(huán)面的三角剖分算法是非常簡(jiǎn)單的。 算法輸入一個(gè)被凸包 P 包裹的凸包 Q， 他們的頂點(diǎn)都是順時(shí)針序的。
- 將凸包的邊作為三角剖分的邊插入。
- 計(jì)算 P 和 Q 的 x 坐標(biāo)最小的點(diǎn)， 分別稱為 xmin(P) 和 xmin(Q) 。
- 在 xmin(P) 和 xmin(Q) 處構(gòu)造兩條鉛垂切線， 稱之為 LP 和 LQ 。
- 將 (xmin(P), xmin(Q)) 作為三角剖分的一條邊插入。
- 當(dāng)前 LP 和 LQ 對(duì)應(yīng)的 p 和 q 點(diǎn)分別是 xmin(P) 和 xmin(Q)。
- 將線順時(shí)針旋轉(zhuǎn)直到其中一個(gè)與一條邊重合。 一個(gè)新的頂點(diǎn)由此被一條線“擊”出。
- 如果他屬于 P （稱為 p'）， 插入 (p', q) 到三角剖分中。 更新當(dāng)前的點(diǎn)為 p' 和 p' 。
- 如果他屬于 Q （稱為 q'）， 插入 (p, q') 到三角剖分中。 更新當(dāng)前的點(diǎn)為 p 和 q' 。
- 對(duì)于平行邊的情況， 兩條切線都和邊重合， 并且兩個(gè)新的頂點(diǎn)被“擊”出（稱他們?yōu)?nbsp;p' 和 q'）。 然后插入 (p', q') ， 以及 (p, q') 和 (p', q) 到三角剖分中。 更新當(dāng)前的點(diǎn)為 p' 和 q' 。
- 重復(fù)執(zhí)行上述步驟直到達(dá)到開(kāi)始的最小點(diǎn)。
一個(gè)換面的三角剖分如下所示：
上述的算法擁有線性時(shí)間復(fù)雜度。 當(dāng)對(duì)于一個(gè)點(diǎn)集進(jìn)行三角剖分的時(shí)候， 一個(gè)凸包在整個(gè)過(guò)程中遍歷（最多）兩次， 最里面和最外部的凸包都只執(zhí)行遍歷一次。 因此對(duì)于一個(gè) n 個(gè)點(diǎn)的三角剖分的總運(yùn)行時(shí)間是 O(n) 。
另一個(gè)有效且與三角剖分有關(guān)的問(wèn)題是基于點(diǎn)集的凸螺旋線的螺旋三角剖分。
2.螺旋三角剖分
點(diǎn)集的螺旋三角剖分是基于集合螺旋凸包的三角剖分圖。
凸螺旋線可以通過(guò)如下方法構(gòu)造：
- 從一個(gè)特定的端點(diǎn)開(kāi)始（比如給定方向上的最小點(diǎn)）， 這里取有最小 x 坐標(biāo)的點(diǎn)。
- 通過(guò)那個(gè)點(diǎn)構(gòu)造一條鉛垂線。
- 按照一個(gè)給定的方向旋轉(zhuǎn)線（總保持順時(shí)針或者是逆時(shí)針?lè)较颍?直到線“擊” 出另一個(gè)頂點(diǎn)。
- 將兩個(gè)點(diǎn)用一條線段連接。
- 重復(fù)步驟3和步驟4， 但是總忽略已經(jīng)擊出的點(diǎn)。
大體上， 這個(gè)過(guò)程類似于計(jì)算凸包的卷包裹算法， 但是不同在于其循環(huán)永遠(yuǎn)不會(huì)停止。 對(duì)于一個(gè)凸包上有 h 個(gè)點(diǎn)的點(diǎn)集， 存在 2h 個(gè)凸螺旋線： 對(duì)于每個(gè)起點(diǎn)有順時(shí)針和逆時(shí)針螺旋線兩種。
一個(gè)點(diǎn)集（左邊）， 及其順時(shí)針凸螺旋線， 以最小的 x 坐標(biāo)點(diǎn)作為初始點(diǎn)。
有趣的是， 一個(gè)點(diǎn)集的凸螺旋線和洋蔥皮可以在線性時(shí)間內(nèi)相互轉(zhuǎn)換。 進(jìn)一步的， 類似于洋蔥三角剖分， 我們可以定義一個(gè)點(diǎn)集的子圖為凸螺旋線的螺旋三角剖分。
構(gòu)造螺旋三角剖分的算法， 雖然是基于環(huán)面三角剖分的， 但是卻更為復(fù)雜， 因?yàn)槁菪€必須被分割為合適的凸包鏈。 假設(shè)輸入是一個(gè)點(diǎn)集的順時(shí)針凸螺旋線 C ， 且有 C = { p1 , ... , pn } 。
- 將凸螺旋線的邊作為三角剖分的邊插入。
- 從 p1 開(kāi)始， 尋找點(diǎn)集凸螺旋線上的最后一個(gè)點(diǎn) ph 。
- 延長(zhǎng)凸螺旋線上的最后一條邊 [p(n-1),pn] 直到其與凸螺旋線相交。 標(biāo)記交點(diǎn)為 q' 。
- 構(gòu)造與 C 切于點(diǎn) q' 的切線。 逆時(shí)針旋轉(zhuǎn)那條線直到他與 C 相交于一點(diǎn) q 并且平行于 [p(n-1),pn] 。
- 將 [p(n-1),q] 插入三角剖分中。
- 此操作后將凸螺旋鏈分割稱了兩個(gè)部分： 鏈外的部分和鏈內(nèi)的多邊形區(qū)域。 設(shè) Co = { p1 , ... , q } 且 Ci = { ph , ... , q , ... , pn } 。 這個(gè)構(gòu)造過(guò)程如下圖所示：
左上角： 構(gòu)造過(guò)程。 右上角： 螺旋外和內(nèi)部的多邊形區(qū)域。 底部： 外部和內(nèi)部的凸鏈 Co 和Ci 。
- 外部螺旋區(qū)域可以如環(huán)面一樣進(jìn)行三角剖分。 Co 和 Ci 此時(shí)可以被看成一個(gè)嵌套凸包。
- 內(nèi)部的多邊形區(qū)域可以很容易的在 pn 處星型劃分形成三角剖分。
- 這兩個(gè)三角剖分的組合構(gòu)成了整個(gè)螺旋三角剖分的結(jié)構(gòu)。
一個(gè)螺旋凸包的例子和其三角剖分如下所示：
上述的算法是線性時(shí)間復(fù)雜度的， 算法的時(shí)間依賴于環(huán)面剖分的運(yùn)行時(shí)間。
3.四邊形剖分
雖然三角剖分是一個(gè)更常用的結(jié)構(gòu)， 但最近四邊形剖分在某些特定條件下顯得更適用， 比如 scattered data interpolation 以及 finite element method 等。
一個(gè)四邊形剖分實(shí)際上是一個(gè)點(diǎn)集的四邊形分割。 一些與三角剖分本質(zhì)上的區(qū)別（除了特別明顯的）應(yīng)該引起注意：
首先， 不是所有的點(diǎn)集都存在四邊形剖分。 事實(shí)上， 只有偶數(shù)點(diǎn)集才有。 對(duì)于奇數(shù)點(diǎn)集， 有時(shí)需要附加點(diǎn)（稱為Steiner點(diǎn)）到原集合中， 從而構(gòu)造一個(gè)四邊形剖分。
同時(shí)， 人們經(jīng)常期望四邊形剖分構(gòu)造擁有一些“好的”性質(zhì)， 比如凸的。 這個(gè)與三角剖分是不同的。
有許多簡(jiǎn)單的四邊形剖分算法。 比如， 首先考慮點(diǎn)集的三角剖分， 然后加入一個(gè)Steiner點(diǎn)到每個(gè)三角形內(nèi)部， 以及每條邊的中間。 連接這些新點(diǎn)構(gòu)成了四邊形剖分（這是DeBerg提出的）。
Bose 和 Toussaint 在1997年提出從一個(gè)點(diǎn)集的螺旋三角剖分開(kāi)始， 來(lái)構(gòu)造一個(gè)o四邊形剖分。
如果點(diǎn)集是偶數(shù)的， 那么每隔一個(gè)的對(duì)角線（在螺旋三角剖分算法中加入的）移除， 構(gòu)造了一個(gè)四邊形剖分。 如果是奇數(shù)個(gè)點(diǎn)， 那么從最后一條對(duì)角線開(kāi)始每個(gè)隔一條對(duì)角線（比如最后一個(gè)， 倒數(shù)第三個(gè)等）進(jìn)行移除， 在被移除的第一條對(duì)角線附近加入一個(gè)Steiner點(diǎn)。 下圖展示第一種情況（偶數(shù)個(gè)點(diǎn)的點(diǎn)集）。 螺旋三角剖分（左邊）， 和最終的四邊形剖分（右邊）。
因?yàn)閷?duì)角線的移除過(guò)程（和必要的更新）花費(fèi) O(n) 的時(shí)間， 這個(gè)四邊形剖分算法與螺旋三角剖分有相同的時(shí)間復(fù)雜度。 這個(gè)算法的優(yōu)點(diǎn)在于便于理解與實(shí)現(xiàn)（一旦凸螺旋線建立）， 并且事實(shí)上其產(chǎn)生了一個(gè)比許多競(jìng)爭(zhēng)者“更好的”四邊形剖分算法。
下一個(gè)問(wèn)題集是關(guān)于凸多邊形， 特別的， 關(guān)于凸包上的操作， 比如合并凸包。
五、凸多邊形屬性
1.合并凸包
考慮如下問(wèn)題： 給定兩個(gè)凸多邊形， 包含他們并的最小凸多邊形是怎樣的？ 答案即合并凸包后得到的凸多邊形。
合并凸包可以通過(guò)一個(gè)低效的方式實(shí)現(xiàn)： 給定兩個(gè)多邊形的所有頂點(diǎn)， 計(jì)算這些點(diǎn)對(duì)應(yīng)的凸包。 更高效的方法是存在的， 他依賴于多邊形間的 橋 的查找。 下圖描述了這個(gè)概念：
兩個(gè)不相交的凸多邊形。 合并后的凸包包含兩個(gè)多邊形中的凸包鏈（途中藍(lán)色粗實(shí)線）， 通過(guò)多邊形間的橋進(jìn)行連接（途中藍(lán)色虛線）
給定兩個(gè)不相交的多邊形， 在多邊形間存在兩條橋。 多邊形相交時(shí)， 擁有和頂點(diǎn)數(shù)同樣數(shù)量的橋， 如下圖所示：
兩個(gè)相交的凸多邊形。 合并凸包只包含多邊形間的橋（圖中虛線所示）。 存在連接八個(gè)頂點(diǎn)的八個(gè)橋。
合并操作的核心是分治方法。 他同樣用于多邊形中。 一個(gè)獲取凸包的十分簡(jiǎn)單的方法是將點(diǎn)集分為兩部分， 分別計(jì)算兩個(gè)較小點(diǎn)集的凸包， 并且將他們合并。 每個(gè)集合再次被分割， 直到元素的個(gè)數(shù)足夠?。ū热缯f(shuō)三個(gè)或者更少） 因此凸包就能被很容易獲得了。
Toussaint 提出利用旋轉(zhuǎn)卡殼來(lái)尋找兩個(gè)凸多邊形間的橋。 這個(gè)方法的主要優(yōu)點(diǎn)在于其利用回溯， 并且多邊形可以交疊（其他的算法要求多邊形不相交）。 下述結(jié)論是他的算法的主要過(guò)程：
給定凸多邊形 P = { p(1) , ... , p(m) } 和 Q = { q(1) , ... , q(n) }，一個(gè)點(diǎn)對(duì) (p(i), q(j)) 形成 P 和 Q 之間的橋當(dāng)且僅當(dāng)：
- (p(i), q(j)) 形成一個(gè)并踵點(diǎn)對(duì)。
- p(i-1), p(i+1), q(j-1), q(j+1) 都位于由 (p(i), q(j)) 組成的線的同一側(cè)。
假設(shè)多邊形以標(biāo)準(zhǔn)形式給出并且頂點(diǎn)是以順時(shí)針序排列， 算法如下：
- 分別計(jì)算 P 和 Q 擁有最大 y 坐標(biāo)的頂點(diǎn)。 如果存在不止一個(gè)這樣的點(diǎn)， 取 x 坐標(biāo)最大的。
- 構(gòu)造這些點(diǎn)的遂平切線， 以多邊形處于其右側(cè)為正方向（因此他們指向 x 軸正方向）。
- 同時(shí)順時(shí)針旋轉(zhuǎn)兩條切線直到其中一條與邊相交。 得到一個(gè)新的并踵點(diǎn)對(duì) (p(i), q(j)) 。 對(duì)于平行邊的情況， 得到三個(gè)并踵點(diǎn)對(duì)。
- 對(duì)于所有有效的并踵點(diǎn)對(duì) (p(i), q(j))： 判定 p(i-1), p(i+1), q(j-1), q(j+1) 是否都位于連接點(diǎn) (p(i), q(j)) 形成的線的同一側(cè)。 如果是， 這個(gè)并踵點(diǎn)對(duì)就形成了一個(gè)橋，
并標(biāo)記他。
- 重復(fù)執(zhí)行步驟3和步驟4直到切線回到他們?cè)瓉?lái)的位置。
- 所有可能的橋此時(shí)都已經(jīng)確定了。 通過(guò)連續(xù)連接橋間對(duì)應(yīng)的凸包鏈來(lái)構(gòu)造合并凸包。
上述的結(jié)論確定了算法的正確性。 運(yùn)行時(shí)間受步驟1，5，6約束。 他們都為 O(N) 運(yùn)行時(shí)間（N 是頂點(diǎn)總數(shù)）。 因此算法擁有現(xiàn)行的時(shí)間復(fù)雜度。
一個(gè)凸多邊形間的橋?qū)嶋H上確定了另一個(gè)有用的概念：多邊形間公切線。 同時(shí)， 橋也是計(jì)算凸多邊形交的算法核心。
2.找共切線
公切線是同時(shí)與多邊形相切的簡(jiǎn)單直線， 并且兩個(gè)多邊形都位于線的同一側(cè)。 換句話說(shuō)， 一條公切線是一條與兩個(gè)多邊形都相切的線。 一個(gè)例子如下圖所示：
兩個(gè)不相交的凸多邊形和一條他們的公切線
事實(shí)上， 公切線可以通過(guò)多邊形間的一些確定橋的點(diǎn)對(duì)來(lái)確立。 因此， 給定兩個(gè)不相交的多邊形， 就存在兩個(gè)多邊形間兩條公切線， 并且當(dāng)多邊形相交時(shí)， 還有可能存在與頂點(diǎn)數(shù)一樣多的公切線。
用來(lái)計(jì)算兩多邊形間橋的算法（如歸并算法）同樣可以用來(lái)確定公切線。
另一個(gè)“版本”的兩多邊形的公切線是關(guān)鍵切線。 那種情況下多邊形分立于線的兩側(cè)。
橋可以用來(lái)計(jì)算多邊形的交。
3.凸多邊形交
給定兩個(gè)多邊形， 我們第一個(gè)需要討論的問(wèn)題應(yīng)該是：“他們相交嗎？”。 Chazelle 和 Dobkin 1980年在他們的一篇叫做“Detection is easier than computation”的論文中發(fā)表了一個(gè)對(duì)數(shù)時(shí)間級(jí)的算法（論文的名字很貼切）。 對(duì)于多邊形的交， 許多算法能計(jì)算出交集。 有趣的是一個(gè)結(jié)論（由Guibas提出）證明了多邊形交點(diǎn)和和他們之間的橋是一一對(duì)應(yīng)關(guān)系。
兩個(gè)多邊形（淺紅色和藍(lán)色）和他們的交集（淺紫色）。 交點(diǎn)以紅色標(biāo)記。 每個(gè)交點(diǎn)與一個(gè)多邊形之間的橋（標(biāo)記為紅色點(diǎn)劃線）有關(guān)。
Toussaint在1985年的文獻(xiàn)中利用Guibas的結(jié)論， 加上他先前的關(guān)于 查找橋的算法來(lái)計(jì)算交點(diǎn)集。 他的算法利用橋來(lái)計(jì)算交點(diǎn)集。 一旦他們被找到， 與合并凸包的操作類似， 凸鏈以及交點(diǎn)集形成了多邊形的交集。
算法的細(xì)節(jié)， 特別是從橋到交點(diǎn)的計(jì)算可以在Toussaint的論文中找到：
G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123.
1985.
下一個(gè)問(wèn)題設(shè)計(jì)尋找兩個(gè)凸多邊形的 臨界切線。
4.臨界切線
兩個(gè)凸多邊形間的臨界切線（一般被叫做CS線）是使得兩個(gè)多邊形分居線不同側(cè)的切線。 換句話說(shuō)， 他們分隔了多邊形。
CS線可以應(yīng)用于motion planning， visibility 和 range fitting。
下圖是關(guān)于兩個(gè)多邊形和他們的兩條臨界切線。
這里要注意的一點(diǎn)是假設(shè)數(shù)據(jù)是以標(biāo)準(zhǔn)形式給出的， CS線只會(huì)在兩個(gè)頂點(diǎn)處與兩個(gè)多邊形相交。 因此， 一條CS線由多邊形間頂點(diǎn)對(duì)確定。
如下的結(jié)論描述了這個(gè)點(diǎn)對(duì)：
給定兩個(gè)凸多邊形 P， Q， 兩個(gè)頂點(diǎn) p(i), q(j)
（分別屬于 P 和 Q） 確定一條CS線當(dāng)且僅當(dāng)：
- p(i), q(j) 構(gòu)成多邊形間對(duì)踵點(diǎn)對(duì)。
- p(i-1),p(i+1) 位于線 (p(i), q(j))
一側(cè)，同時(shí)q(j-1),q(j+1) 位于另一次。
利用這個(gè)結(jié)論， CS線可以很容易地確定。 只有多邊形間的對(duì)踵點(diǎn)對(duì)才需要進(jìn)行測(cè)試。 因此， Toussaint建議使用旋轉(zhuǎn)卡殼。 假設(shè)多邊形是以標(biāo)準(zhǔn)形式給出并且是順時(shí)針序排列頂點(diǎn)， 考慮如下過(guò)程：
- 計(jì)算 P 上 y 坐標(biāo)值最小的頂點(diǎn)（稱為 yminP ） 和 Q 上 y 坐標(biāo)值最大的頂點(diǎn)（稱為 ymaxQ）。
- 為多邊形在 yminP 和 ymaxQ 處構(gòu)造兩條切線 LP 和 LQ 使得他們對(duì)應(yīng)的多邊形位于他們的右側(cè)。
此時(shí) LP 和 LQ擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個(gè)對(duì)踵點(diǎn)對(duì)。
- 令 p(i)= yminP， q(j)= ymaxQ。
(p(i), q(j)) 構(gòu)成了多邊形間的一個(gè)對(duì)踵點(diǎn)對(duì)。 檢測(cè)是否有 p(i-1),p(i+1)
在線 (p(i),q(j)) 的一側(cè)， 并且 q(j-1),q(j+1)
在另一側(cè)。 如果成立， (p(i), q(j)) 確定了一條CS線。
- 旋轉(zhuǎn)這兩條線， 直到其中一條和其對(duì)應(yīng)的多邊形的邊重合。
- 一個(gè)新的對(duì)踵點(diǎn)對(duì)確定了。 如果兩條線都與邊重合， 總共三對(duì)對(duì)踵點(diǎn)對(duì)（原先的頂點(diǎn)和新的頂點(diǎn)的組合）需要考慮。 對(duì)于所有的對(duì)踵點(diǎn)對(duì)， 執(zhí)行上面的測(cè)試。
- 重復(fù)執(zhí)行步驟4和步驟5， 直到新的點(diǎn)對(duì)為(yminP,ymaxQ)。
- 輸出CS線。
這個(gè)算法基本通過(guò)繞著多邊形旋轉(zhuǎn)切線， 順序查找所有多邊形間的對(duì)踵點(diǎn)對(duì)。 每次一對(duì)對(duì)踵點(diǎn)確定后， 執(zhí)行所有必要的測(cè)試。 在上述過(guò)程執(zhí)行完后， 所有的臨界切線都被找到了。
算法的運(yùn)行時(shí)間由步驟1和步驟6決定， 他們都花費(fèi) O(n) 的時(shí)間（所有的檢測(cè)都花費(fèi)常數(shù)時(shí)間。 因?yàn)橛?nbsp; O(n) 的對(duì)踵點(diǎn)對(duì)， 總的花費(fèi)為 O(n)）。
關(guān)于凸多邊形的學(xué)習(xí)， 最后的操作是 凸多邊形矢量和。
5.凸多邊形矢量和
給定平面上兩個(gè)凸多邊形 P 和 Q ， P 和 Q 的矢量和， 記為 P + Q 定義如下：
P + Q = { p + q } 所有的分別屬于 P 和 Q 的 p 和 q 。
多邊形矢量和在 motion planning 中也稱為 Minkowski 總數(shù)。
考慮上述的定義， 許多問(wèn)題可以通過(guò)詢問(wèn)集合 P + Q 的組成， 他擁有的性質(zhì)等等。 下屬結(jié)果幫助我們描述多邊形矢量和。
- P + Q 是一個(gè)凸多邊形。
- 頂點(diǎn)集 P + Q 是頂點(diǎn)集 P 和 Q 的和。
- 頂點(diǎn)集 P + Q 是 P 和 Q 間的并踵點(diǎn)對(duì)集。
- 給定分別有 m 和 n 個(gè)頂點(diǎn)的 P 和 Q ， P + Q 有不多于 m + n 個(gè)頂點(diǎn)。
最后， 下屬結(jié)論不僅僅描述了這個(gè)問(wèn)題， 同時(shí)也提供了一個(gè)一個(gè)個(gè)頂點(diǎn)的增量式計(jì)算矢量和的計(jì)算方法。
給定 P + Q 集合的第 k 個(gè)向量 z(k)， 滿足 z(k)
= p(i) + q(j)。 構(gòu)造在 p(i)
和 q(j) 處構(gòu)造兩條平行切線， 使得多邊形同時(shí)位于各自線的右側(cè)。 兩條線分別在 p(i) 和 q(j)
處確定了角 theta(i) 和 phi(j) （如下圖所示）
因此下一個(gè)向量 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)
下述的多邊形和他們的矢量和作為一個(gè)例子。
兩個(gè)凸多邊形。 第一個(gè)多邊形的邊用紅色標(biāo)記， 第二個(gè)用藍(lán)色。
上述多邊形的矢量和。 其邊的顏色與原多邊形的一致。
用上述的結(jié)果， 我們十分容易的就能構(gòu)造出一個(gè)算法來(lái)計(jì)算矢量和。 第一個(gè)向量可以是在給定方向上邊界向量的和（如 y 軸負(fù)方向）。 切線構(gòu)造后， 在計(jì)算角度時(shí)候更新， 下一個(gè)點(diǎn)就很明確了。 我們需要做的只是同時(shí)旋轉(zhuǎn)兩條線到新的位置來(lái)確定新的角度。
算法的正確性來(lái)自主要的結(jié)論； 他是線性時(shí)間復(fù)雜度的， 因?yàn)槊恳徊街挥幸粋€(gè)所要求的向量和集合中的向量被確定， 并且他們只有 m + n 個(gè)， 因此總運(yùn)行時(shí)間是 m + n 。
六、最薄截面
1.最薄橫截帶
考慮下述設(shè)備放置問(wèn)題：一個(gè)“消費(fèi)群體群”的集合是以個(gè)體呈現(xiàn)為平面上凸多邊形的一個(gè)家庭 F 給出的。 我們的目標(biāo)是找到一個(gè)“設(shè)備”， 一條平面上的直線， 使得線到消費(fèi)者的最大距離最小。
最后一點(diǎn)需要澄清。 直線與任何一個(gè)多邊形的距離都是指多邊形上一點(diǎn)到線的正交距離的最小值。 因此，每個(gè)多邊形到線的距離是唯一的。
現(xiàn)在， 給定家庭中各個(gè)呈多邊形的成員和平面上的一條直線， 每個(gè)多邊形都有一個(gè)到線的距離。 因此， 對(duì)于整個(gè)家庭存在一個(gè)最大的線-多邊形距離。 這個(gè)距離同時(shí)依賴于線與各個(gè)家庭成員多邊形。
這個(gè)問(wèn)題的目標(biāo)是： 給定一個(gè)特定的家庭成員多邊形集， 找到使得這個(gè)最大距離最小的線。 這個(gè)問(wèn)題同樣存在著其他版本， 常見(jiàn)的有找一條線使得距離和最小， 或是使得多邊形帶權(quán)距離和最小。
這里的提出的結(jié)論是Robert和Toussaint在1990年發(fā)表的。
主問(wèn)題等價(jià)于找到一個(gè)寬最小的帶（一個(gè)平面上由兩條平行線為邊界的區(qū)域）和所有的家庭成員多邊形相交。因此， 帶的中心（與帶的邊界線平行等距的線）就是所求的使得最大距離最小的線。
為了討論這個(gè)問(wèn)題我們做如下定義：
平面上的一條直線 l ， 其方程為 ax + by + c = 0 （且 b >
0 或 a = -1）將平面分為兩個(gè)區(qū)域：上半平面 Hu( l) 中的點(diǎn) p = ( px, py)
滿足 apx + apy + c >= 0 ， 且下半平面 Hl( l)
中的點(diǎn) p = ( px, py) 滿足 apx + apy + c <=
0 。
通過(guò)上面的定義， 如果線是鉛直的， 上半平面為 x 軸的負(fù)方向。
進(jìn)一步地， 一個(gè)帶可以定義為一條線的上半平面和另一條（平行）線的下半平面的交集。
給定一個(gè)凸多邊形 P ， 一個(gè)方向角 theta ， 下切線 tl( P, theta)
是一條與 x 軸正半軸夾角為 theta 的線， 他與 P相交并且 P 在 tl( P, theta)
的上半平面。 交點(diǎn)（可能不止一個(gè)）稱為下頂點(diǎn)。
同樣的， 定義上切線和上頂點(diǎn)。
給定一個(gè)家庭的多邊形集合和一個(gè)固定的方向角， 就確定了一個(gè)下頂點(diǎn)集和上頂點(diǎn)集。
最后， 考慮下面的結(jié)論：
給定家庭 F 的多邊形集， 和一個(gè)方向角 theta ， 一個(gè)帶 S （由 Hu( l1)
和 Hl( l2) 大于0的交集得到）是 F （在此方向上）最小寬度帶， 當(dāng)且僅當(dāng) F 中存在兩個(gè)多邊形 P 和 Q 有
- P 和 Hu(l1) 的交在 l1 上。
- Q 和 Hl(l2) 的交在 l2 上。
其主要的結(jié)論是： 一個(gè)家庭 F 的凸多邊形集的最小寬度帶（一個(gè)給定方向 theta 上）由 l1 和 l2 確定當(dāng)
l1= tl( CH( UP( F, theta)), theta)
且
l2= tu( CH( LP( F, theta)), theta)
成立。
一個(gè)家庭的凸多邊形集， 以及給定角度上的最小帶寬。 下頂點(diǎn)和上頂點(diǎn)的凸包， 上述的結(jié)論如圖所示。 注意到兩個(gè)多邊形和帶的交都只在一個(gè)頂點(diǎn)上出現(xiàn)。
因此， 只要確定了家庭多邊形集的下頂點(diǎn)和上頂點(diǎn)的序列， 就能通過(guò)計(jì)算凸包得到給定方向上最小寬度帶。就如Robert和Toussaint解釋的， 幸運(yùn)的是這些凸包不需要每次都完全重新計(jì)算： 他們需要更新即可。 實(shí)際上， 考慮兩個(gè)接近的方向：許多（或者是全部）多邊形對(duì)于這兩個(gè)方向擁有相同的上頂點(diǎn)和下頂點(diǎn)。 這個(gè)結(jié)果同樣暗示這只有有限的方向上（當(dāng)下頂點(diǎn)或上頂點(diǎn)變化時(shí)）需要檢測(cè)。
這里的焦點(diǎn)在于旋轉(zhuǎn)卡殼模型， 而非關(guān)系到算法的細(xì)節(jié)。 本文打算利用旋轉(zhuǎn)卡殼來(lái)計(jì)算多邊形的上頂點(diǎn)和下頂點(diǎn)。下面是算法的主要實(shí)現(xiàn)過(guò)程。 給定一個(gè)凸多邊形 P ：
- 找到擁有最小和最大 y 坐標(biāo)的頂點(diǎn)。 標(biāo)記為 p 和 q 并且通過(guò)他們構(gòu)造水平切線。
- 逆時(shí)針將切線旋轉(zhuǎn)過(guò) theta 角直到其中一條與其中一個(gè)多邊形的邊平行。
- 如果頂點(diǎn)在 p 后被擊出（按照逆時(shí)針?lè)较颍?那么 p 就是對(duì)于角度0（包括）到角度 theta（不包括） 之間的下頂點(diǎn)。 如果頂點(diǎn)是在 q 后被擊出，
那么 q 就是同樣角度范圍內(nèi)的上頂點(diǎn)。 這兩個(gè)情況當(dāng)邊平行的時(shí)候也可能同時(shí)發(fā)生。
- 更新當(dāng)前點(diǎn)為新?lián)舫龅捻旤c(diǎn)， 并更新當(dāng)前角度。
- 重復(fù)執(zhí)行步驟2到步驟4， 同時(shí)跟新角度區(qū)間， 知道新的角度大等于180度（在哪一點(diǎn)先回到了最初的位置， 但此時(shí)次序顛倒）。
線與其中一個(gè)多邊形的一條邊平行的方向稱之為 臨界方向 。 他們只在上頂點(diǎn)和下頂點(diǎn)處發(fā)生變化。 對(duì)于一個(gè)臨界方向， 因?yàn)榫€穿過(guò)兩個(gè)頂點(diǎn)， 當(dāng)逆時(shí)針旋轉(zhuǎn)時(shí)下頂點(diǎn)或是上頂點(diǎn)之一被定義為多邊形與線的一個(gè)交點(diǎn)。
一旦臨界方向（按照順序給出）得到， 一個(gè)帶就能在第一個(gè)方向上進(jìn)行計(jì)算。 然后， 在第二個(gè)臨界方向上， 至少一個(gè)上頂點(diǎn)或是下頂點(diǎn)被更新。 因此， 凸包此時(shí)需要更新， 而非重新計(jì)算一次。 一旦完成上述步驟， 新的帶就構(gòu)造成功了， 并且他的寬度（邊界間的正交距離）被算出。 對(duì)所有臨界方向重復(fù)這個(gè)操作。 注意到如果任何點(diǎn)處如果產(chǎn)生了一個(gè)寬度為0的帶f， 這個(gè)過(guò)程就能夠因?yàn)檎业揭粭l穿過(guò)所有家庭多邊形的線而終止了。
對(duì)于完整的算法描述， 正確性討論和運(yùn)行時(shí)間分析， 見(jiàn)作者的論文：
J.-M. Robert, G.T. Toussaint. Computational geometry and facility location. Proc. Internatioanl Conf. on Operations Research and Management Science, Manila, The Philippines, Dec. 11-15, 1990. pp B-1 to B-19.
源自：http://cgm.cs./~orm/rotcal.frame.html
|
