一種基于逐點插入Delaunay三角剖分生成Voronoi圖的算法

黃清華

一種基于逐點插入Delaunay三角剖分生成Voronoi圖的算法

黃清華

采用改進的逐點插入算法生成Voronoi圖。該算法在逐點插入的過程中生成凸殼，進而生成Delaunay三角剖分。在生成Voronoi圖的實現(xiàn)過程中，通過遍歷三角形的邊頂點快速識別相關(guān)的三角形組，進而生成Voronoi圖。試驗結(jié)果表明，該算法能實現(xiàn)，成功生成Voronoi圖。

逐點插入；凸殼；Delaunay三角剖分；Voronoi圖

0 引言

Voronoi圖與convex hull 和delaunay三角形并稱為計算幾何的三大支柱，早在1850年Dirichlet及1908年Voronoi在其論文中都討論過Voronoi圖的概念[1]。Voronoi又稱泰森多邊形或者Dirichlet圖。Voronoi圖在求解點集或者其他幾何對象與距離有關(guān)的問題時起著重要作用。從上世紀90年代以來，voronoi圖的應(yīng)用領(lǐng)域在不斷擴展，這些領(lǐng)域從幾何重構(gòu)到計算機圖形學、圖像處理，從路徑規(guī)劃到粒子微觀狀態(tài)分布，幾乎涵蓋了自然科學領(lǐng)域的大部分學科[2]，足以看出voronoi圖的優(yōu)越性與重要性。所以voronoi的算法實現(xiàn)就顯得舉足輕重。

最基本的voronoi圖是以平面點集P為基礎(chǔ)的，點集中的點有序的組成多個凸多邊形，這些凸多邊形組成了voronoi區(qū)域。其重要的一個性質(zhì)就是點集中的每個點pi對應(yīng)這樣一個區(qū)域Vi，區(qū)域Vi內(nèi)的任何點距離pi點比點集內(nèi)的其他點近，這也決定了voronoi圖的獨特性。

Voronoi圖的對偶圖為Delaunay三角剖分。Delaunay三角剖分的生成算法較多且成熟，我們可以通過先生成Delaunay三角剖，在再生成其對偶圖來生成Voronoi圖。目前 Delaunay三角剖分的生成算法主要有：三角網(wǎng)生長法、分治算法和逐點插入法，其中屬逐點插入法應(yīng)用最廣泛，被研究最多。該方法實現(xiàn)簡單，易于推廣到高維。本文先通過逐點插入法生成Delaunay三角網(wǎng)，再生成Delaunay三角網(wǎng)的對偶圖來得到Voronoi圖。

1 Delaunay三角剖分算法的概述

Delaunay三角剖分對于數(shù)值分析是一項極為重要的與處理技術(shù)。Delaunay三角剖分有兩個重要的性質(zhì)：（1）最大化最小角，即最接近于規(guī)則化；（2）唯一性，即構(gòu)成三角網(wǎng)的點集內(nèi)任意四點不共圓。這兩個性質(zhì)既定義了Delaunay，也確定了應(yīng)用之時其優(yōu)越性。Miles 證明了Delaunay三角網(wǎng)是“好的”三角網(wǎng)；Lingas進一步論證了“在一般情況下，Delaunay三角網(wǎng)是最優(yōu)的。”以上定義及性質(zhì)是建立Delaunay三角網(wǎng)的算法依據(jù)。

Delaunay三角剖分的經(jīng)典剖分算法可概括為下面兩類[3]：

1）增量算法：原理是從一個基本三角形開始，每次增加一個點，重新生成三角網(wǎng)并保證得到的當前三角形是局部優(yōu)化的三角形。

2）局部變換法：原理為先構(gòu)造非優(yōu)化的三角網(wǎng)，然后對兩個共邊三角形形成的凸四邊形迭代換邊優(yōu)化。

迄今為止Delaunay剖分的生成算法，主要有分治算法、逐步插入法、三角網(wǎng)生長法等。比較三種算法：分治算法高效，但實現(xiàn)算法復雜；三角網(wǎng)生長算法效率較低；逐點插入法實現(xiàn)簡單,但它的時間復雜度差。時間復雜度缺陷可通過提高硬件水平來彌補。所以綜合考量，本文用逐點插入法來生成Delaunay剖分。逐點插入法的代表算法為Lawson算法，由Lawson于1977年提出。逐點插入法的基本步驟為：（1）生成點集坐標數(shù)據(jù)；（2）生成包圍點集的邊界即凸殼；（3）綜合邊界和內(nèi)部點集生成三角網(wǎng)。

2 Delaunay三角剖分的生成

Voronoi剖分的關(guān)鍵在于生成Delaunay網(wǎng)格。Delaunay剖分的關(guān)鍵技術(shù)為：快速創(chuàng)建包含點集的凸殼；插入新點后快速生成新的Delaunay網(wǎng)。逐點插入法是在點集內(nèi)點大于等于3的情況下每插入一點就生成新的Delaunay，也意味著要生成新的凸殼。

2.1 初始設(shè)置

凸殼頂點鏈表：ConvexHull List；凸殼頂點數(shù)組：Vertex Array；剖分后三角形鏈表：Del-Tri List；三角形頂點鏈表：Tri-Points List 。

2.2 建立凸殼

凸殼建立有許多經(jīng)典算法，如分治法、卷包裹法、格雷厄姆掃描法和增量法等[4-5]。卷包裹法和格雷厄姆掃描法等需要對點集進行排序，而增連法則不需要預(yù)先排序。本文來用增量遞推算法，不需要排序。凸殼CH（S）具體建立步驟如下：

步驟1 初始化凸殼頂點鏈表ConvexHull List。插入的點數(shù)目為3時，取這三點p1，p2，p3圍成的三角形為初始凸殼CH(3)（{ p1，p2，p3}）3點放入鏈表。如圖1所示：

圖1 初始凸殼CH（3）

圖2 凸殼CH（16）

圖3 凸殼CH（17）（P17CH（16））

圖4 凸殼CH（18）（P18CH（17））

可以直觀觀察上述兩種情況。圖2為插入16點時生成的凸殼；圖3為插入第17點時生成的凸殼，對應(yīng)第一種情況；圖4為插入第18點時生成的凸殼，對應(yīng)第二種情況。

(1)找正切點算法：

Then pi在右側(cè)

Else pi在左側(cè)

步驟3鏈表ConvexHull List即為凸殼點集內(nèi)的點。

2.3 Delaunay 三角剖分生成[6]

Delaunay三角剖分生成步驟如下：

步驟1 復制鏈表ConvexHull內(nèi)數(shù)據(jù)入數(shù)組Vertex，對凸殼構(gòu)建三角網(wǎng)。從第一點開始依次取點構(gòu)成構(gòu)成三角形，在構(gòu)成三角形之前判斷該三角形外接圓中是否包含其他凸殼頂點。包含則重新選點構(gòu)網(wǎng)，不包含則將三角形加入到鏈表Del_Tri List。

步驟2 逐點加入修改三角網(wǎng)。插入新點加入三角形頂點鏈表Tri_Points，定位插入點影響的所有三角形，即點在其外接圓內(nèi)的三角形。刪除受影響三角形的三邊，鏈表Del_Tri內(nèi)表尾三角形前移插入受影響三角形處。并在受影響區(qū)域重新構(gòu)網(wǎng)。新生成的三角形加入Del_Tri List。

步驟3 重復步驟2，可得要求數(shù)目點集的Delaunay三角網(wǎng)。鏈表Tri_Points內(nèi)為三角剖頂點，三角形鏈表Del_TriList即為所求Delaunay三角剖分。

3 Voronoi剖分的生成

Voronoi圖與Delaunay三角剖分互為對偶圖，本文中用已生成的Delaunay三角剖分生成Voronoi剖分的關(guān)鍵技術(shù)在于快速遍歷每個點的目標三角形的邊。在生成Delaunay三角剖分的過程中生成的凸殼頂點為半封閉邊界點，不參與Vonoroi剖分的生成。

鏈表設(shè)置：Voronoi點鏈表：Vor_Points List；三角形邊鏈表：Tri_Edge List；邊終點數(shù)組：End_Points Array；

步驟1 在Delaunay三角剖分生成的過程中得到凸殼的頂點鏈表ConvexHull和三角形的頂點鏈表Tri_Points。從Tri_Points List中去除ConvexHull中的頂點，將剩余點有序加入新的鏈表Vor_Points List。

步驟2 在Delaunay三角剖分的基礎(chǔ)上，依次遍歷每個三角形的3條邊，加入鏈表Tri_Edge。在遍歷的過程中，如出現(xiàn)重復的邊則不再重復加入。

步驟3遍歷鏈表Vor_Points內(nèi)的點。對每一點遍歷該點相關(guān)的邊鏈表Tri_Edge，可得相關(guān)的邊的另一點，即終點End_Points，結(jié)合Tri_Points內(nèi)點的坐標,可以得到End_Points內(nèi)的點坐標。

步驟4 將End_Points內(nèi)點逆時針排序，則同時也對點相關(guān)的三角形進行了排序。計算上述有序三角形的外接圓圓心。

步驟5 逆時針連接外接圓圓心，可得Voronoi圖。遍歷所有點后，可得整體Voronoi圖。

4 實現(xiàn)結(jié)果與結(jié)論

為檢驗本算法，采用VS2005編譯環(huán)境、C#語言編程實現(xiàn)了增量算法生成凸殼、逐點插入Delaunay三角剖分，最后生成了Voronoi圖。計算機配置為Intel CPU 3.2GHz、4G內(nèi)存，在逐點插入的過程中生成的凸殼，如圖2至圖4所示。如圖5和6所示：

圖5 23點Delaunay三角網(wǎng)

圖6 24點Delaunay三角網(wǎng)

是逐點插入過程中生成Delaunay三角剖分。最后生成的Voronoi圖如圖7所示：

圖7 Voronoi圖

采用逐點插入算法生成Delaunay三角剖分間接生成Voronoi圖。在生成Voronoi圖時，通過遍歷三角形的邊頂點快速識別相關(guān)的三角形組，進而生成Voronoi圖。結(jié)果顯示，算法實現(xiàn)很好，成功生成Voronoi圖。

[1] AURENHAMMER F. Voronoi diagrams: A survey of a fundamental geometric data structure [ J ]. ACM Computing Surveys, 1991, 23(3) : 345 - 405.

[2] [2]劉金義,劉爽. Voronoi圖應(yīng)用綜述[ J ]. 工程圖學學報, 2004, 25(2): 125 - 132.

[3] [3]吳莉莉.Delaunay 三角剖分的幾種算法綜述[J].科技信息，2011,28:119-120

[4] [4]樊廣佺，王小牛，楊炳儒.平面點集凸殼的一種近似算法[J].計算機工程與應(yīng)用2007,43（12）：40-41.

[5] [5]周培德. 計算幾何:算法設(shè)計與分析[M ]. 3版. 北京:清華大學出版社, 2008.

[6] [6]李水鄉(xiāng)，陳斌，趙亮.快速Delaunay逐點插入網(wǎng)格生成算法[J].北京大學學報（自然科學版），2006,03:1-4

A Voronoi Generation Algorithm Based on Point Insertion Algorithm of Delaunay Triangulation

Huang Qinghua
(School of Communication and Engineering, Fudan University, Shanghai 200433, China)

An improved Voronoi generation algorithm based on point insertion algorithm of Delaunay triangulation is presented in this paper. The algorithm generates the convex hull in the process of inserting point by point and then generates Delaunay triangulation. In the process of generating the Voronoi diagram, the algorithm identifies related triangles rapidly by traversing the edge vertices. The experimental results show that the algorithm generates Voronoi diagram successfully.

Point Insertion; Convex Hull; Delaunay Triangulation; Voronoi Diagram

TP391. 41

A

1007-757X(2014)06-0043-03

2014.04.18)

黃清華（1989-），女，復旦大學，碩士研究生，研究方向：計算電磁學，上海，200433