計算幾何第三周：三角剖分

目標：將多邊形剖分成三角形

1、畫廊問題

問題描述：在畫廊（如下圖的多邊形）中，如何設置哨兵可以監控整個畫廊？

直觀解：如果多邊形是凸多邊形或星形多邊形，那麼只須在中間的核設置一個即可。如果多邊形不規則，那麼最多n個點，即n多邊形的每個頂點都設置一個哨兵，就可以將整個多邊形覆蓋。因此問題的解的上界為n.

然而在數學上有證明指出畫廊問題是NP-Hard問題，這裡不做多的贅述。

實際上，對於不規則多邊形而言，最對只須n/3個點即可覆蓋多邊形（如下圖）。

2、Fisks Proof

• 幾個概念

扇形：一個有核點的星形多邊形。每個扇形可以由一個點覆蓋整個扇形。

內對角線：多邊形頂點之間的內部連線

切線：某個點相切。任意一個邊或切線都不是對角線

對角線的集合是連續的如果任意兩條對角線不相交。

• 三角剖分問題

多邊形P的最大的連續對角線的集合稱為P的三角剖分。

著色：任意一條邊和內對角線連接的兩個點顏色互異。

Fisks的證明指出：對於進行三角剖分後的多邊形，只需3種顏色即可對它完成著色

證明：構造三角剖分圖的對偶圖。首先對第一個點所在的那個三角形使用三種顏色進行著色，然後從這個點移至下一個點時，我們知道這兩個三角形是存在一條公共邊，必有第三個頂點之間是不相連的，因此它們可以是同一種顏色。遍歷這棵樹，即可完成著色。

因為每個三角形的點顏色不一，對於一種顏色的點而言，它可以覆蓋它所在的三角形，而多邊形又是被剖分成一個個三角形，因此只要在同一種顏色的點上設置監控即可覆蓋整個多邊形，因此至多需要n/3個監控就可以覆蓋整個多邊形。

對於這n/3還可以有進一步的優化：

由鴿巢原理知，對於三種顏色的點總共有n個，那麼必存在一種顏色的點數是小於等於n/3的。我們只需要選取其中最小規模的那個顏色集合即可。

3、正交多邊形

正交多邊形至多需要n/4個點即可覆蓋。

對於正交多邊形，採用的是凸四邊形剖分，如下：

可以根據每個凸四邊形中都有兩兩的對角線，進行四色染色，因此至多需要n/4個點。

4、三角剖分（Triangulation）

本課程只考慮簡單多邊形（即相鄰的邊才有交點的多邊形）以及中間帶洞的簡單多邊形的三角剖分。

如下圖所示不是簡單多邊形

• 一些概念

耳朵：多邊形的一個點，它與它相鄰的兩個點構成的三角形完全包含在多邊形內，這個三角形稱為該多邊形的耳朵(ear)

嘴巴：如果多邊形上一點與它相鄰的兩個點構成的三角形完全在多邊形外，稱為嘴巴(mouth)

• 三角剖分存在性

構造三角剖分的方法：不斷地切去多邊形的一個耳朵，直至它只剩下一個三角形，那麼就完成了該多邊形的三角剖分。

雙耳定理：任意一個簡單多邊形一定有兩個耳朵。（這個定理保證了我們在每次給多邊形切去一個耳朵時一定還會有新的耳朵用於切分）

• 三角剖分演算法

定義多邊形的大小比較：（洞的數目，頂點數目）

初始化：首先找到一個凸點J（Lowest-then-Leftmost原則），然後找到與它相鄰的兩個點I,K並把I,K連接起來。

遞歸基：最終變成一個三角形（無洞）

遞歸假設：每次都將多邊形分割成更小的簡單多邊形

遞歸：如果△IJK是一個耳朵，那麼IK是一條內對角線，可切。如果IK不是內對角線，意味著中間有空洞。假設M是離線IK最遠的那個點。

無論是哪種情況，沿著JM切開，我們得到的多邊形總比原多邊形要小。

• 三角剖分的性質

三角剖分不唯一

對於一個規模為n的簡單多邊形，它們的內對角線的數目為n-3條，構成三角剖分的三角形數目為n-2個。

對偶圖：多邊形中如果不帶洞的，那麼它的三角剖分圖的對偶圖是一棵樹；如果原來帶有洞，那麼就必然有環路。

5、三角剖分：Monotone Polygon

這裡只考慮不帶洞的簡單多邊形

• 幾個概念

單調多邊形鏈：對於某個特定的方向，上面的頂點可以投影在該軸上有一定的次序。即這條單調鏈可以被視作是一個函數圖像。

單調多邊形：它可以分解為互補的兩條鏈，並且這兩條鏈沿著同一方向單調。方便起見，我們將方向取作縱向，並將兩條鏈稱為左側鏈和右側鏈，這兩條鏈在最低點和最高點重合，從而構成多邊形。

多邊形的單調性測試：判斷一個多邊形是否在某個方向上具有單調性。

• 剖分演算法

整個演算法分成兩步：①對一個簡單多邊形分解成若干個單調多邊形；②對每個單調多邊形進行三角剖分。

下面對這兩步進行分別的解釋。

• 對單調多邊形的三角剖分：掃描線演算法（自頂而下）

初始化：頂點從高到低排序（假定了方向是縱向），因為已經是分成了兩條有序鏈，那麼只需要歸併即可。（這裡不考慮各種特殊情況）

事件點：每個頂點

數據結構：棧

每次處理的頂點：當前掃描線觸及的頂點c，棧中存放的頂點t，棧中的次頂點s

演算法進行時的每個步驟都滿足的一組不變性，：

①、在棧中所存放的點在任何時候都是屬於左或者右的同一側。

②、這些頂點總是按照高度變化

③、在棧中存放的點任何三個定義的內角都是凹的

④、掃描點c要麼和棧頂t相連要麼和棧底botton相連。

演算法進行時的可能性：

①、掃描點c與棧內所有點處於同側，且它與t點和s點形成的角是凹角，這種情況下就是把c點壓入棧中。

②、點c與棧中所有點同側，但是c與t和s形成的角是凸角。此時把c和次棧頂相連，那麼可以切除一個三角形。然後彈出棧頂s，持續判斷此時的棧頂和次棧頂相連的角的情況，直到c與棧頂和次棧頂相連的角是凹角或者棧內的點數小於2。這個操作完成後將c點push進棧內。

③、點c與棧中所有點異側。此時點c可以與每個棧中的點有一條內對角線，都可以切三角形。那麼這時就不停的將c與棧頂次棧頂的點構成的三角形切除同時將棧頂的點pop出來，持續這個過程直到棧中只剩下一個元素。然後將棧底pop出來，並把之前碰到的第一個棧頂元素t push進去，最後將點c壓入棧中。

• 一個實例

• 演算法分析

正確性：我們每次切除的連線都是內對角線，都不會與之前的內對角線相交

複雜性：多邊形的每一個頂點最多會參與兩對的push-pop操作，線性時間。因此整個演算法是線性時間。

6、Monotone Decomposition

問題描述：如何將簡單多邊形分解成若干個單調多邊形？消除掉多邊形內部的凹點。

• 兩個概念

鐘乳石點StalacTite和石筍StalagMite

• 分解原理：一個多邊形之所以不是單調的，是因為存在這兩種凹點。那麼剖分的話就是將這些點消除掉。

• 演算法：消除StalagMite（另一個類似）

演算法描述：先把所有頂點按照高度排序，一旦發現有StalagMite，那麼就將它之前準備好的某個頂點相連，從而把StalagMite消除。我們的目標就是要如何去維護更新這麼一些能消除凹點的頂點，這些頂點又稱作helper。當碰到StalagMite時，可以與helper連接，並且這條線是內對角線。因為對於一個StalagMite而言，一定會存在一個空的倒梯形如圖所示，那麼在StalagMite往上在梯形之內就會存在一個helper與之相連。因此，使用掃描線演算法，當掃描線自上而下掃描時，我們是要預先存著可能會成為helper的點，然後在碰到StalagMite時從中找到與它相匹配的helper。

對於這個helper存在三種可能。

①、支撐空梯形的左邊界的上端點

②、支撐空梯形的右邊界的上端點

③、自己本身就是一個StalagTite

我們將這三種情況稱之為掃描線的狀態結構State Structure，記錄所有當前活躍的梯形。

下面討論如何對helper進行動態更新

①、Start Vertex

若碰到頂點v，它與周圍構成一個局部的凹角，而且它相鄰的兩個點都比它低，此時會出現一個退化的梯形（即三角形）。那麼這個梯形也要加到狀態結構中。當前要指定一個helper v。

②、End Vertex

與Start Vertex對稱，我們要做的就是找到這個退化的梯形並把它從結構中剔除。

③、Left Adjacent

將原先的梯形T轉換為一個新的梯形T，新的梯形T的helper置為v

④、Right Ajacent

與第三種情況對稱

⑤、StalagMite

將StalagMite點與helper相連。此時這個大梯形會被分裂成左邊的梯形和右邊的梯形，那麼就將狀態結構中原來的大梯形替換成新的兩個小梯形。v會變成這時兩個梯形的helper。

⑥、StalacTite

與第5種情況對稱，相反的是兩個小梯形縫合成一個大梯形。那麼是將狀態結構中的兩個小梯形置換成大梯形，大梯形的helper是v。

• 下面舉一個例子：

• 演算法複雜度：O(nlogn)

7、Terahedralization

多面體剖分：三維多面體剖分成單純行——四面體

三維多面體的四面體剖分數目不是確定的。

有些多面體如果只能用頂點進行劃分的話甚至沒有四面體剖分。

有些多面體不能被我們之前畫廊問題所說的任意一個頂點都放上監控覆蓋——Seidels Polygon

推薦閱讀：