Voronoi圖是一組連續多邊形組成，多邊形的邊界是由連線的垂直平分線組成。M 個在工平面上有區則的點。按照最近鄰原則劃分平面，每一個點與它最近鄰的區域關聯，與每個點相關聯的區城(成多邊用是唯一的，它由這些點的空網分布所決定。
基本介紹
- 中文名：voronoi圖
- 外文名：Voronoi diagram
- 所屬領域：計算幾何
- 提出者：喬奇·沃若諾依(Georgy Voronoi)
- 其它名稱：Voronoi劃分，Voronoi鋪砌
幾何定義,構造方法,套用,
幾何定義
Voronoi圖，又叫泰森多邊形或Dirichlet圖，它是由一組由連線兩鄰點直線的垂直平分線組成的連續多邊形組成。N個在平面上有區別的點，按照最鄰近原則劃分平面；每個點與它的最近鄰區域相關聯。Delaunay三角形是由與相鄰Voronoi多邊形共享一條邊的相關點連線而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關的Voronoi多邊形的一個頂點。
對於點集
里的種子點
，它的Voronoi區域
定義為：
構造方法
Voronoi圖是Delaunay三角剖分的對偶圖，生成它的方法有很多，比較有名的有分治算法，掃描線算法，增量法等。但利用Delaunay三角剖分生成Voronoi圖的算法是最快的。
但最快的方法則是構造Delaunay三角剖分，再連線相鄰三角形的外接圓圓心，即可以到Voronoi圖。
Delaunay三角剖分算法：
對於給定的初始點集P，有多種三角網剖分方式，其中Delaunay三角網具有以下特徵：
1、Delaunay三角網是唯一的；
2、三角網的外邊界構成了點集P的凸多邊形“外殼”；
3、沒有任何點在三角形的外接圓內部，反之，如果一個三角網滿足此條件，那么它就是Delaunay三角網。
4、如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay三角網的排列得到的數值最大，從這個意義上講，Delaunay三角網是“最接近於規則化的“的三角網。
Delaunay三角形網的特徵又可以表達為以下特性：
1、在Delaunay三角形網中任一三角形的外接圓範圍內不會有其它點存在並與其通視，即空圓特性；
2、在構網時，總是選擇最鄰近的點形成三角形並且不與約束線段相交；
3、形成的三角形網總是具有最優的形狀特徵，任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那么兩個三角形6個內角中最小的角度不會變大；
4、不論從區域何處開始構網，最終都將得到一致的結果，即構網具有唯一性。
Delaunay三角形產生的基本準則：任何一個Delaunay三角形的外接圓的內部不能包含其他任何點[Delaunay 1934]。Lawson[1972]提出了最大化最小角原則，每兩個相鄰的三角形構成凸四邊形的對角線，在相互交換後，六個內角的最小角不再增大。Lawson[1977提出了一個局部最佳化過程（LOP, local Optimization Procedure）方法。
基於散點建立數字地面模型，常採用在d維的歐幾里得空間Ed中構造Delaunay三角形網的通用算法—逐點插入算法，Delaunay三角剖分算法過程如下：
1、遍歷所有散點，求出點集的包容盒，得到作為點集凸殼的初始三角形並放入三角形鍊表。
2、將點集中的散點依次插入，在三角形鍊表中找出其外接圓包含插入點的三角形（稱為該點的影響三角形），刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連線起來，從而完成一個點在Delaunay三角形鍊表中的插入。
3、根據最佳化準則對局部新形成的三角形進行最佳化（如互換對角線等）。將形成的三角形放入Delaunay三角形鍊表。
4、循環執行上述第2步，直到所有散點插入完畢。
上述基於散點的構網算法理論嚴密、唯一性好，格線滿足空圓特性，較為理想。由其逐點插入的構網過程可知，在完成構網後，增加新點時，無需對所有的點進行重新構網，只需對新點的影響三角形範圍進行局部聯網，且局部聯網的方法簡單易行。同樣，點的刪除、移動也可快速動態地進行。但在實際套用當中，這種構網算法不易引入地面的地性線和特徵線，當點集較大時構網速度也較慢，如果點集範圍是非凸區域或者存在內環，則會產生非法三角形。
為了克服基於散點構網算法的上述缺點，特別是為了提高算法效率，可以對格線中三角形的空圓特性稍加放鬆，亦即採用基於邊的構網方法，其算法簡述如下：
1、根據已有的地性線和特徵線，形成控制邊鍊表。
2、以控制邊鍊表中一線段為基邊，從點集中找出同該基邊兩端點距離和最小的點，以該點為頂點，以該基邊為邊，向外擴展一個三角形（僅滿足空橢圓特性）並放入三角形鍊表。
3、按照上述第2步，對控制邊鍊表所有的線段進行循環，分別向外擴展。
4、依次將新形成的三角形的邊作為基邊，形成新的控制邊鍊表，按照上述第2步，對控制邊鍊表所有的線段進行循環，再次向外擴展，直到所有三角形不能再向外擴展為止。
套用
Voronoi圖的套用非常廣泛。在計算幾何中，重心Voronoi圖(CVT)方法被用來最佳化格線，可以使種子點變得更加均勻。在網路通訊中，利用加權Voronoi圖設計中繼站的位置可以提高利用率，降低成本。
