Triangulation

Triangulation

平面上散布許多點。只以這些點作為三角形頂點,用線段連接產生三角形,三角形數量越多越好。所有線段形成一個「三角剖分」,通常有許多種。

因為三角形數量越多越好,所以三角剖分的外圍一定是凸包。

三角形的建構順序、建構地點都相當自由,也因此各種凸包演算法都可以順便求得三角剖分。

三角剖分的三角形個數、邊數

計算凸包的三角剖分,再用剩下的點遞迴分割所在的三角形,最後處理共線的點。

令h是凸包點數,令k是其餘點數。凸包的三角剖分得到h-2個三角形;剩下的點,逐次用於三角剖分,每次都多出兩個三角形。由此可知,無論三角剖分長相如何,一個三角剖分固定有(h-2)+2k個三角形,是O(N)。

同理可知,無論三角剖分長相如何,一個三角剖分固定有(2h-3)+3k條邊,亦是O(N)。

這也呼應了平面圖歐拉公式v-e+f=2。

三角剖分的數量

計算不同的三角剖分有多少種,目前除了窮舉法以外沒有更好的演算法,也無人知道這是P問題抑或是NP-complete問題。

Flip Graph

一個三角剖分,翻轉一條邊,可以得到另一個三角剖分。注意到並不是每一條邊都能翻轉的。

二維平面上,給定一個點集合,把所有三角剖分依照翻轉關係連接成一張無向圖,稱作Flip Graph,是連通的。

Flip Graph有著許多謎團,例如點到點最短路徑(兩個三角剖分之間的最少翻轉次數)、直徑、連接性,目前都沒有演算法。

演算法(Graham's Scan)

仿照「Convex Hull: Graham's Scan」,掃除凸包頂點的過程即可進行三角剖分。一如既往,共線的點不好處理。時間複雜度O(NlogN),主要取決於排序的時間。

演算法(Incremental Method)

仿照「Convex Hull: Incremental Algorithm」,如果當前輸入點在三角形內部,則直接連線至三角形頂點;如果當前輸入點在所有三角形外部,則連線至凸包的切點與凹點。要小心當前輸入點在三角形上的情況。時間複雜度O(N²)。

如果預先按照XY座標排序所有點(平移的掃描線),就能保證當前輸入點都在所有三角形外部。

當前輸入點與凹點的連線,不超過三角剖分的邊數O(N);當前輸入點與切點的連線,等同Andrew's Monotone Chain,時間複雜度是O(NlogN)。分開分析,總時間複雜度O(NlogN)。

演算法(Divide and Conquer)

仿照「Convex Hull: Divide and Conquer」,尋找外公切線的過程即可合併左右兩個三角剖分。時間複雜度O(NlogN)。

Minimum Weight Triangulation

線段長度總和最小。時間複雜度目前不明。

判斷一個三角剖分是不是線段長度總和最小的三角剖分,則是NP-hard問題。

用途是節省印刷墨水。

Maxmin Angle Triangulation

最小的角盡量大。已有演算法。

即是「Delaunay Triangulation」。

Minmax Angle Triangulation

最大的角盡量小。已有演算法。

《An O(n² log n) time algorithm for the minmax angle triangulation》

Compatible Triangulation

兩個三角剖分,點數相同,每一點相互對應,每一個三角形的三個頂點也相互對應。

用途是動畫製作,讓物體外觀平滑變形。

《Morphing Planar Graph Drawings with a Polynomial Number of Steps》

Tetrahedralization

Tetrahedralization

「四面體剖分」。三角剖分推廣到三維空間。

四面體剖分的Flip Graph目前完全不知道長什麼樣。

有些形狀不存在四面體剖分,例如Schönhardt Polyhedron:三角柱扭轉凹陷。

Polygon Triangulation

Polygon Triangulation

簡單多邊形,沿對角線切割,成為許多三角形。對角線、多邊形互不交錯。通常有許多種。

N個頂點,N-2個三角形,N-3條對角線。

「耳ear」是凸點與鄰點組成的三角形,而且未與其他邊相交。「嘴mouth」是凹點與鄰點組成的三角形。剩下的點沒有取名。

耳適合當作剖分對象。但是簡單多邊形一定有耳嗎?

三角形的相鄰關係,恰是一棵樹。超過一點的樹,至少有兩葉。

葉必是耳。超過三點的多邊形,至少有兩耳,且兩耳不重疊。

也就是說,簡單多邊形無論長相,必有耳。甚至可以不斷刵耳,直到剩下三角形,得到三角剖分!

演算法(Enumeration)

窮舉所有點,判斷是否為耳(的凸點)?若為耳,則刵之。

判斷一個點是否為耳(的凸點)有兩種方式:一、窮舉多邊形所有點。皆在三角形外,便是耳。二、窮舉多邊形所有邊。皆在三角形外,便是耳。大家習慣使用第一種方式。

多邊形的資料結構是circular linked list,以便快速刵耳。

未知點最初共N點。刵1次,至多添2點;刵N-3次,至多添2N-6點。未知點至多3N-6點。判斷一個點是否為耳需時O(N),總時間複雜度為O((3N-6) ⋅ N) = O(N²)。

ICPC 4426

演算法(Divide and Conquer)

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

一、找到一耳。O(N)。二、刵N-3次。O(N²)。

此法不太健康,參考看看就好。

Art Gallery Problem

一個簡單多邊形,至少要放幾個360度鏡頭,才能看到整個內部、顧及所有地方?

NP-complete問題,難以快速求得答案,但是可以快速估計答案的上限是ceil(n/3)個:三角剖分的點著色數為三,挑一個顏色放滿鏡頭,就能顧及每個三角形。

Minimum Weight Polygon Triangulation

一、所有三角形周長總和最小:Dynamic Programming,時間複雜度為O(N²)。此問題與Matrix Chain Multiplication關係密切,時間複雜度可以加速至O(NlogN)。

二、所有對角線長度總和最小:我沒有研究。

UVa 1331

Minmax Angle Polygon Triangulation

最大的角盡量小:我沒有研究。

ICPC 3132 4458

Polygon Partition

Polygon Trapezoidalization

簡單多邊形,每個頂點發射水平線(垂直線),切割成許多梯形、三角形。梯形剖分只有唯一一種。

梯形剖分的用途是建立區域相鄰關係,形成有向無環圖!掃描線的順序就是拓樸順序,方便設計高速演算法。有洞多邊形亦然。

ICPC 2479

Acute Triangulation / Non-obtuse Triangulation

簡單多邊形,切成許多個三角形,角度皆小於90°、小於等於90°。

雖然名稱是Triangulation,但是三角形頂點不必是多邊形頂點。名稱取得不好。

《Linear-size Nonobtuse Triangulation of Polygons》

Polygon Convex Partition

簡單多邊形,切成許多個凸多邊形。

演算法是Hertel-Mehlhorn Algorithm。我沒有研究。