一般而言,沃羅諾伊圖(Voronoi Diagram)與德勞內三角分割(Delaunay Triangulation)有著密不可分的關係,前者代表著勢力均衡,後者代表著一組特徵點不重複的獨立三角區域,它們不單只是結構迷人,也深具影響力。

掃描Voronoi邊界

我在先前專欄文章〈深入Worley噪聲〉談過Voronoi圖案,由於是勢力均衡的結果,最自然的處理方式是半平面交集法(Half-plane Intersection),而在程式實作上,必須處理線的交點、多邊形交集等問題,也就認識幾何問題在程式上如何處理。雖然這是個不錯的主題,然而就建立Voronoi圖形的效率而言,稱不上快速(時間複雜度O(N²logN),如果有興趣看看實作,可以參考〈勢力的交集〉,是以九宮格方式處理雖可以略為改進,點的分布卻也會因而受限。

實務上求Voronoi,一般會推薦使用Fortune演算。而這是Steven Fortune在1986年的論文〈A Sweepline Algorithm for Voronoi Diagrams〉中發表的演算法(時間複雜度O(NlogN)),基本原理是透過一條掃描線橫掃每個點,掃描線經過的點會成為拋物線的焦點,而掃描線與焦點之間的中點,會作為拋物線的頂點,在掃描過程中,如果將這些拋物線的交點連接起來,將會是Voronoi細胞的邊界。

若要純粹就拋物線的原理來理解為何這能構成Voronoi圖,會是什麼狀況?其實,這就是焦點至拋物線上任一點的距離,必然等於拋物線上該點至掃描線的距離,既然如此,若兩條拋物線相交在一點,那麼,交點與各自焦點的距離必然相等,也就是說,兩條拋物線不斷變化下交點構成的直線,就是兩個點間的中垂線。

只不過從拋物線來理解其構成Voronoi圖形的原理,過程還是有點複雜,因此,最簡單的理解方式是,每個點會各自往上建立圓錐體,然後有個與圓錐邊相同斜度的無限大平面,掃描過這些圓錐,圓錐體與平面交集出來的形狀,就是拋物線,而這些拋物線的交接構成的線,正好就是俯視這些圓錐時,圓錐交界處構成的直線,而俯視這些圓錐時,你也能發現自然構成的Voronoi圖形。

也就是說,雖然演算法是基於掃描線來計算,然而,說穿了,這樣的圖形,還是圓錐彼此之間勢力均衡下的產物。

想實際看看圓錐與平面掃描的動畫,我們可以參考〈Fortune's Algorithm - Animation〉,若想有個程式實作可供參考,我們可以來看看〈Fortune's Algorithm in C++〉

Delaunay三角分割

如果給你一張Voronoi圖,每個相鄰的細胞彼此之間,我們以直線連接細胞核,將會得到一組三角形,而對於每個三角形,若找出其各自的外接圓,很神奇地,每個圓中不會包含任何的點。

進一步地,任兩個鄰接三角形外接圓的兩個交點,正好就是細胞核的位置,兩個圓心的相連線,正好是Voronoi細胞的邊。這不難理解,因為兩個細胞核連接成兩圓的中垂線,圓心的相連線會平分中垂線,細胞核與圓心的相連線間自然是等距。

也就是說,若將這個過程反過來,一開始有堆隨機散布的點,如果有辦法將這些點連接成一組三角形,每個三角形的外接圓不包含其他點,那麼,找出相鄰三角形的外接圓,將它們的圓心連接起來,就可以構成Voronoi圖形。

將隨機點畫分為外接圓中不會包含其他點的三角形,基本上,這是數學家Boris Delaunay在1934提出的一種三角分割,為了紀念他在這個領域的貢獻,這樣的三角分割,因此被大家稱為Delaunay三角分割(Delaunay triangulation)。

為何Voronoi與Delaunay三角分割的關係如此密切?其實是因為Georgy Voronoy基於Delaunay三角分割,建立了Voronoi圖形,而他是Boris Delaunay非正式的博士顧問。

Delaunay三角分割後的三角形,外接圓並不會包含其他的點,這也代表了,三角形中也不會有其他點,三角形中的資訊並不會重複,因此Delaunay三角分割在臉部辨識、地理資料分析等領域,都有著重要的應用。

Bowyer-Watson演算

在演算法方面,如果我們想求得Delaunay三角分割,大多數人推薦的演算法是Bowyer-Watson演算,不過,乍看維基百科該條目中的虛擬碼有點嚇人。

其實,我們可以先看看只有三個點的情況會是如何。因為這樣沒什麼好說明的,只能連成一個三角形,由於沒有其他點,也就沒有外接圓中還有點存在的可能性。

接著若在三角形中增加一個點,增加的點在三角形內,顯然就是在其外接圓內,這個三角形不合格了,此時,如果我們拆掉這個三角形,然後增加的點與原三角形各邊的兩端點連接,可以形成新的一組三角形,而這樣就構成了新的Delaunay三角分割,但現在問題來了!若增加的點不在三角形內,但是在其外接圓內呢?

該三角形當然也是不合格,只不過拆掉它後,你「不能」單純地連接每個邊成為新的三角形,因為新三角形會有邊交叉,問題是:我們怎麼知道哪個邊不能連成三角形?此時,我們可以判斷新三角形的外接圓,是否包含了被拆掉三角形的頂點,若是,就是不合格的三角形,而這一邊就不能用來連為新三角形。

接下來的問題就是,如果有一堆隨機的點,一開始要選哪三個點作為初始三角形,你並不能任意選取,因為:選出來的第一個三角形,可能極為瘦長,附近可能有個更合適的點。

Bowyer-Watson演算的方法是,構造一個可涵蓋全部點的超級三角形,然後一次加入一個點,進行三角分割,直到全部的點都加入為止。對於以上的過程若要進一步了解,我們可以參考〈Delaunay三角分割〉中的圖解,接著再對照維基百科Bowyer–Watson演算條目的虛擬碼,這樣應該就不難理解了。

在實際化為程式實作時,其實,更重要的是,如何快速判斷出三角形之間的鄰接關係,在U-Net這個Repository,有個delaunay2D.py,其中使用了字典結構,鍵是三角形頂點索引,值是個Tuple,其中記錄各頂點面對的三角形,可用來快速判斷鄰接關係,是個不錯的實作方式。

深具影響力的幾何結構

對我來說,Voronoi與Delaunay,是非常迷人的結構,研究它們不單只是認識各自的特性,還連帶著對相關的幾何特性有更多的理解,而且它們也不單只是結構迷人,也深具影響力,甚至有《沃羅諾伊圖形與德勞內三角分割》專書,在探討相關原理與各種應用。

有些程式庫就內建或基於Delaunay或Voronoi建構了API或應用,像是OpenCV、Facenet,甚至於p5.js,官網上也列出Voronoi的擴充程式庫,我們可以直接使用。

然而,如果我們試著自行實作構造Delaunay或Voronoi,也可以從中習得不少的演算技巧,對於其變化,也就能更加地得心應手!

專欄作者

熱門新聞

Advertisement