Voronoi與Delaunay

一般而言，沃羅諾伊圖（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，也可以從中習得不少的演算技巧，對於其變化，也就能更加地得心應手！