voronoi

Voronoi圖是計算幾何中的一個基本概念，由下面的問題引出它：

問題：給定平面中N個點，對於每個點Pi，平面中距離Pi點比距離其它點更近的點的區域是什麼？即區域內的任意一點(x,y)，距Pi比距離平面中的其它點都近。

首先從最簡單的情況入手，對於平面中兩個點A、B，距離A點比距離B點近的點的區域是由A、B的垂直平分線確定的包含A的那半個平面。如圖1所示，V(A)為A點的最近區域。

如果點集由N個點組成，距離Pi比距離其它點更近的點的區域是包含Pi的那N-1個半平面的交集。這N-1個半平面是由Pi點與其它點的垂直平分線確定的。

V(i)是由一些垂直平分線段構成的多邊形。用上述方法做出每個點的區域，就形成的點Voronoi圖。它將整個平面分成N個區域，每個區域中包含一個點，這個區域就是這個點的區域，其中的線段或射線稱為Voronoi邊，它一定是兩個點的連線的中垂線的一段，這兩個點稱為該Voronoi邊的相關點，Voronoi邊之間的交點稱為Voronoi頂點，Voronoi邊的相關點也是Voronoi頂點的相關點。此外，如果點(x,y)∈V(i)，則Pi是點(x,y)的最近點。

對於給定的初始點集P，有多種三角網剖分方式，其中Delaunay三角網具有以下特徵：

1、Delaunay三角網通常是唯一的；（不唯一的情況如：P只含四個點，該四點共圓）

2、三角網的外邊界構成了點集P的凸多邊形“外殼”；

3、沒有任何點在三角形的外接圓內部，反之，如果一個三角網滿足此條件，那麼它就是Delaunay三角網。

4、如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay三角網的排列得到的數值最大，從這個意義上講，Delaunay三角網是“最接近於規則化的“的三角網。

Delaunay三角形網的特徵又可以表達為以下特性：

1、在Delaunay三角形網中任一三角形的外接圓範圍內不會有其它點存在並與其通視，即空圓特性；

2、在構網時，總是選擇最鄰近的點形成三角形並且不與約束線段相交；

3、形成的三角形網總是具有最優的形狀特徵，任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那麼兩個三角形6個內角中最小的角度不會變大；

4、不論從區域何處開始構網，最終都將得到一致的結果，即構網具有唯一性。

任何一個Delaunay三角形的外接圓的內部不能包含其他任何點[Delaunay 1934]。Lawson[1972]提出了最大化最小角原則，每兩個相鄰的三角形構成凸四邊形的對角線，在相互交換后，六個內角的最小角不再增大。Lawson[1977提出了一個局部優化過程（LOP, local Optimization Procedure）方法。

基於散點建立數字地面模型，常採用在d維的歐幾里得空間Ed中構造Delaunay三角形網的通用演演算法—逐點插入演演算法，具體演演算法過程如下：

1、遍歷所有散點，求出點集的包容盒，得到作為點集凸殼的初始三角形並放入三角形鏈表。

2、將點集中的散點依次插入，在三角形鏈表中找出其外接圓包含插入點的三角形（稱為該點的影響三角形），刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鏈表中的插入。

3、根據優化準則對局部新形成的三角形進行優化（如互換對角線等）。將形成的三角形放入Delaunay三角形鏈表。

4、循環執行上述第2步，直到所有散點插入完畢。

上述基於散點的構網演演算法理論嚴密、唯一性好，網格滿足空圓特性，較為理想。由其逐點插入的構網過程可知，在完成構網后，增加新點時，無需對所有的點進行重新構網，只需對新點的影響三角形範圍進行局部聯網，且局部聯網的方法簡單易行。同樣，點的刪除、移動也可快速動態地進行。但在實際應用當中，這種構網演演算法不易引入地面的地性線和特徵線，當點集較大時構網速度也較慢，如果點集範圍是非凸區域或者存在內環，則會產生非法三角形。

為了克服基於散點構網演演算法的上述缺點，特別是為了提高演演算法效率，可以對網格中三角形的空圓特性稍加放鬆，亦即採用基於邊的構網方法，其演演算法簡述如下：

1、根據已有的地性線和特徵線，形成控制邊鏈表。

2、以控制邊鏈表中一線段為基邊，從點集中找出同該基邊兩端點距離和最小的點，以該點為頂點，以該基邊為邊，向外擴展一個三角形（僅滿足空橢圓特性）並放入三角形鏈表。

3、按照上述第2步，對控制邊鏈表所有的線段進行循環，分別向外擴展。

4、依次將新形成的三角形的邊作為基邊，形成新的控制邊鏈表，按照上述第2步，對控制邊鏈表所有的線段進行循環，再次向外擴展，直到所有三角形不能再向外擴展為止。