基于合成算法的Delaunay三角網(wǎng)生成改進(jìn)算法

潘麗麗,孫玉秋

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北荊州434023)

不規(guī)則三角網(wǎng)能夠精確的表示復(fù)雜的地形。Delaunay三角網(wǎng)因其在所有可能的三角網(wǎng)中表現(xiàn)最為出色而被用于不規(guī)則三角網(wǎng)的生成。被人們廣泛采用的Delaunay三角網(wǎng)生成算法有分治法與逐點(diǎn)插入法,這2種算法各有優(yōu)劣,隨之出現(xiàn)了綜合2種算法的合成算法。合成算法雖然提高了執(zhí)行效率,但并沒(méi)有很好的解決其中的一些 “瓶頸”問(wèn)題。因此,如何改進(jìn)現(xiàn)有算法從而提高算法的執(zhí)行效率成為必須要解決的另一個(gè)問(wèn)題。為此,筆者基于合成算法對(duì)子模塊中的關(guān)鍵步驟進(jìn)行改進(jìn),提高算法的性能,簡(jiǎn)化算法的實(shí)現(xiàn)。

1 基本概念及性質(zhì)

Voronoi圖 (以下簡(jiǎn)稱V圖),又叫泰森多邊形或Dirichlet圖,它是由一組連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形。N個(gè)在平面上有區(qū)別的點(diǎn),按照最鄰近原則劃分平面;每個(gè)點(diǎn)與它的最近鄰區(qū)域相關(guān)聯(lián)。Delaunay三角網(wǎng)是由與相鄰Voronoi多邊形共享一條邊的相關(guān)點(diǎn)連接而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關(guān)的Voronoi多邊形的一個(gè)頂點(diǎn)。Voronoi三角網(wǎng)是Delaunay圖的偶圖。

性質(zhì)1(空外接圓性質(zhì)) 在由點(diǎn)集V生成的Delaunay三角網(wǎng)中,每個(gè)三角網(wǎng)的外接圓均不包含該點(diǎn)集的其他任意點(diǎn)。

性質(zhì)2(最大最小角度性質(zhì)) 在由點(diǎn)集V生成的Delaunay三角網(wǎng)中,所有三角形中的最小角度是最大的,即在生成的三角形網(wǎng)格中,各三角形的最小內(nèi)角和為最大。

性質(zhì)3(唯一性) 不論從區(qū)域何處開(kāi)始構(gòu)網(wǎng),最終都將得到一致的結(jié)果。

2 合成算法

合成算法[1,2]的基本思想是將逐點(diǎn)插入法植入到分治算法中,即以分治算法為主體,當(dāng)遞歸分割數(shù)據(jù)集的過(guò)程進(jìn)行到子集中的數(shù)據(jù)量小于一個(gè)預(yù)定值時(shí),用逐點(diǎn)插入法在子集中生成三角網(wǎng),以達(dá)到互相取長(zhǎng)補(bǔ)短,以體現(xiàn)它們的綜合優(yōu)勢(shì),從而達(dá)到較好的時(shí)空性能的效果,合成算法包含3個(gè)模塊:逐點(diǎn)插入法模塊、尋找上下切線模塊以及合并模塊。

1)逐點(diǎn)插入模塊 ①找出凸殼;②建立初始三角網(wǎng);③插入點(diǎn);④優(yōu)化。

2)尋找上下切線模塊 這個(gè)模塊找出連接左右2個(gè)子三角網(wǎng)的凸殼HL和H R的上切線和下切線。

3)合并模塊 子三角網(wǎng)TL和TR的合并由一個(gè)循環(huán)完成。

3 改進(jìn)算法

改進(jìn)的合成算法主要分為逐點(diǎn)插入模塊和合并模塊,筆者在插入點(diǎn)的定位問(wèn)題上以及凸殼生成問(wèn)題上,改進(jìn)了傳統(tǒng)的算法,以提高算法的整體執(zhí)行效率。

1)凸殼的生成與初始化三角網(wǎng) 原合成算法采用Larkin的凸殼生成算法[3]生成凸殼,這需要判斷點(diǎn)的位置等操作,在點(diǎn)的數(shù)量大的時(shí)候,執(zhí)行效率不高。凸殼的生成算法中較為經(jīng)典的是格雷厄姆法[4]。

構(gòu)建凸殼的算法需要滿足的2個(gè)條件:實(shí)現(xiàn)簡(jiǎn)單,無(wú)需大量預(yù)處理工作;不影響下一步的點(diǎn)插入步驟。因此,筆者在格雷厄姆方法的基礎(chǔ)上改進(jìn)以更好的解決凸殼快速生成問(wèn)題。

①首先對(duì)點(diǎn)集預(yù)處理,對(duì)其進(jìn)行排序,用點(diǎn)(max(X),max(Y))、(min(X),min(Y))、(max(X),min(Y))和(min(X),max(Y))4個(gè)點(diǎn)所圍矩形來(lái)構(gòu)成凸殼,這樣就生成了一個(gè)包含所有點(diǎn)的簡(jiǎn)單凸殼(如圖1所示)。②連接含有max(X)、max(Y)、min(X)和min(Y)4個(gè)值的點(diǎn)并對(duì)所構(gòu)成的多邊形初始三角網(wǎng)(如圖2所示)。③在三角網(wǎng)生成后要將這4個(gè)點(diǎn)刪除,同時(shí)刪除含有這4個(gè)點(diǎn)的三角形。圖3為三角網(wǎng)生成后刪除4個(gè)頂點(diǎn)前的三角網(wǎng)圖;圖4為刪除頂點(diǎn)后的三角網(wǎng)圖。

圖1 凸殼

圖2 初始三角形

圖3 刪除矩形頂點(diǎn)前三角網(wǎng)

圖4 刪除矩形頂點(diǎn)后三角網(wǎng)

2)點(diǎn)的快速定位 逐點(diǎn)插入的過(guò)程就是對(duì)點(diǎn)的定位循環(huán)過(guò)程,也就是查找點(diǎn)所在三角形的過(guò)程。因此,改進(jìn)點(diǎn)的定位過(guò)程可以提高算法的效率。判斷點(diǎn)是否在三角形內(nèi),一般的做法是掃描整個(gè)或局部三角網(wǎng),利用點(diǎn)在多邊形中原理判斷計(jì)算。當(dāng)三角形數(shù)目較多時(shí)是一個(gè)費(fèi)時(shí)的過(guò)程。因此,點(diǎn)的定位算法為逐點(diǎn)插入過(guò)程的關(guān)鍵步驟。判斷點(diǎn)是否在多邊形內(nèi),常用的有射線法、轉(zhuǎn)角法[5]以及適用于三角網(wǎng)的快速方向定位法[6]。對(duì)于點(diǎn)的定位方法需要遵循2個(gè)原則:實(shí)現(xiàn)簡(jiǎn)單和避免復(fù)雜運(yùn)算。因此,筆者利用點(diǎn)在三角形內(nèi)的特點(diǎn)來(lái)解決。

首先求出三角形頂點(diǎn)X、Y坐標(biāo)的最大及最小值,并構(gòu)成矩形,判斷點(diǎn)是否在矩形中,若不在矩形中,則不在三角形中。若在矩形中,則作下面的判斷。連接點(diǎn)A與P,B與P,C與P,得出3向量:

為了判斷點(diǎn)與三角形的位置關(guān)系,定義:

圖5 點(diǎn)在邊上

圖6 點(diǎn)在三角形外

圖7 點(diǎn)在三角形內(nèi)

4 結(jié) 語(yǔ)

在對(duì)Delaunay三角網(wǎng)生成算法進(jìn)行深入研究的基礎(chǔ)上,提出了一種基于合成算法的改進(jìn)的Delaunay三角網(wǎng)生成算法,算法改進(jìn)了原合成算法在凸殼生成過(guò)程以及的快速定位的不足,更好的發(fā)揮了分治算法與逐點(diǎn)插入算法合并后的優(yōu)勢(shì),充分發(fā)揮了其兼顧時(shí)間、空間的特性,較原合成算法在速度和效率上所有提高。

[1]武曉波,王世新,肖春生.Delaunay三角網(wǎng)的生成算法研究 [J].測(cè)繪學(xué)報(bào),1999,28(1):28-35.

[2]武曉波,王世新,肖春生.一種生成Delaunay三角網(wǎng)的合成算法[J].遙感學(xué)報(bào),2000,4(1):32-35.

[3]Larkin B J.An ANSIC Program to Determine Expected Li near Time the Vertices of the Convex Hull ofa Set ofPlanar Points[J].Computers&Geosciences,1991,17(3):431-443.

[4]周培德.算法設(shè)計(jì)與分析[M].第2版.北京:清華大學(xué)出版社,2004:209-210.

[5]吳立新,史文中.地理信息系統(tǒng)原理與算法 [M].北京:科學(xué)出版社,2001:65-70.

[6]蒲浩,宋占峰,詹振炎.快速構(gòu)建三角網(wǎng)數(shù)字地形模型方法的研究 [J].中國(guó)鐵道科學(xué),2001,22(6):100-106.