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

黃清華

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

黃清華

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

逐點(diǎn)插入；凸殼；Delaunay三角剖分；Voronoi圖

0 引言

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

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

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

1 Delaunay三角剖分算法的概述

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

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

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

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

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

2 Delaunay三角剖分的生成

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

2.1 初始設(shè)置

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

2.2 建立凸殼

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

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

圖1 初始凸殼CH（3）

圖2 凸殼CH（16）

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

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

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

(1)找正切點(diǎn)算法：

Then pi在右側(cè)

Else pi在左側(cè)

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

2.3 Delaunay 三角剖分生成[6]

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

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

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

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

3 Voronoi剖分的生成

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

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

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

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

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

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

步驟5 逆時(shí)針連接外接圓圓心，可得Voronoi圖。遍歷所有點(diǎn)后，可得整體Voronoi圖。

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

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

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

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

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

圖7 Voronoi圖

采用逐點(diǎn)插入算法生成Delaunay三角剖分間接生成Voronoi圖。在生成Voronoi圖時(shí)，通過遍歷三角形的邊頂點(diǎn)快速識(shí)別相關(guān)的三角形組，進(jìn)而生成Voronoi圖。結(jié)果顯示，算法實(shí)現(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 ]. 工程圖學(xué)學(xué)報(bào), 2004, 25(2): 125 - 132.

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

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

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

[6] [6]李水鄉(xiāng)，陳斌，趙亮.快速Delaunay逐點(diǎn)插入網(wǎng)格生成算法[J].北京大學(xué)學(xué)報(bào)（自然科學(xué)版），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-），女，復(fù)旦大學(xué)，碩士研究生，研究方向：計(jì)算電磁學(xué)，上海，200433