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)。

演算法(divide-and-conquer method)

仿照「convex hull: divide-and-conquer method」,尋找外公切線的過程即可合併左右兩個三角剖分。時間複雜度O(NlogN)。

minimum weight triangulation

線段長度總和最小。NP-hard。是否為NP-complete仍是懸案。

用途是節省印刷墨水。

maxmin angle triangulation

最小的角盡量大。時間複雜度O(NlogN)。

即是「Delaunay triangulation」。

minmax angle triangulation

最大的角盡量小。時間複雜度O(N²logN)。

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

tetrahedralization

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

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

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

polygon triangulation

polygon triangulation

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

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

「耳ear」是凸點與兩鄰點組成的三角形,並且不碰其他點、不碰其他邊。「嘴mouth」是凹點與兩鄰點組成的三角形。

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

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

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

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

演算法(incremental method)

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

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

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

ICPC 4426

演算法(divide-and-conquer method)

一、找到一耳。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

PSLG triangulation

PSLG triangulation

平面直線圖,切成許多個三角形。

時間複雜度O(NlogN)。

compatible triangulation

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

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

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

polygon partition

polygon trapezoidalization

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

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

ICPC 2479

polygon convex partition

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

演算法是Hertel–Mehlhorn algorithm。我沒有研究。

acute triangulation / non-obtuse triangulation

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

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

《Linear-size Nonobtuse Triangulation of Polygons》