寧化展,徐炳喜,田茂義,張 麗

(1.山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院,山東青島266510;2.中煤礦山建設(shè)集團(tuán)有限責(zé)任公司,合肥安徽230601;2.峽山生態(tài)經(jīng)濟(jì)發(fā)展區(qū)太保莊街道水利站,山東濰坊261325)

0 引 言

數(shù)字地形模型(Digital Terrain Model,DTM)是以離散分布的平面點(diǎn)來(lái)模擬連續(xù)分布的地形,是野外地表勘測(cè)成果的數(shù)字化展現(xiàn),廣泛的應(yīng)用于地理信息系統(tǒng)各領(lǐng)域中。

Delaunay三角網(wǎng)是DTM的主要實(shí)現(xiàn)形式,用一系列互不交叉、重疊的連接在一起的三角形網(wǎng)來(lái)表示地形。Delaunay三角網(wǎng)具有很好的特性:構(gòu)建結(jié)果的唯一性;每個(gè)三角形的外接圓不包含其它點(diǎn),即所有樣本點(diǎn)都是與其最近的兩個(gè)點(diǎn)連接組成一個(gè)三角形;利用野外勘查測(cè)量數(shù)據(jù)作為網(wǎng)格節(jié)點(diǎn),不改變?cè)紨?shù)據(jù)精度,很好的展示關(guān)鍵地形特征[1]。

1 主要模塊的生成

帶有邊界條件的基本三角網(wǎng)的生成模塊[2]

1)生成凸殼模型:建立一個(gè)包含所有數(shù)據(jù)點(diǎn)的初始凸多邊形;

2)生成初始的三角網(wǎng):利用生成的凸殼;

3)局部?jī)?yōu)化:對(duì)生成的三角網(wǎng)利用LOP算法優(yōu)化;

4)最終Delaunay三角網(wǎng)的生成:利用邊界條件剔除多余的三角形。

2 模塊的算法思路

2.1 凸殼的構(gòu)造

一般的凸殼構(gòu)造方法只是找到了最少點(diǎn)的多邊形,特殊情況如:多點(diǎn)恰巧在凸殼的一條邊上一般的算法只是找出了這條邊的兩端的兩個(gè)點(diǎn)而中間的點(diǎn)卻沒(méi)找出來(lái)。這對(duì)于地質(zhì)體的建模是不利的。

為此本文設(shè)計(jì)了一種“夾角與距離最小”的查找凸殼算法[3],下面以圖1為例說(shuō)明凸殼的產(chǎn)生過(guò)程(涉及到的坐標(biāo)以平面二維坐標(biāo)系為例)。

圖1 離散點(diǎn)集

第1步:首先定義一個(gè)泛型數(shù)組用來(lái)存放邊界點(diǎn)在初始離散點(diǎn)集數(shù)組中的索引值;

第2步:在存放離散點(diǎn)集的數(shù)組中找出Y值最小的點(diǎn)(p8)的位置索引值,將此索引值存入定義的泛型數(shù)組,求出p8與離散點(diǎn)集中其它點(diǎn)組成的所有向量與x軸的夾角,以?shī)A角最小和距p8的距離最小為條件篩選出下一個(gè)點(diǎn)(p10)的位置索引值并添加到定義的泛型數(shù)組;

第3步:求出第2步里找出的點(diǎn)p10(泛型數(shù)組里的最后一個(gè)點(diǎn))與離散點(diǎn)集數(shù)組里其它點(diǎn)(p8、p10除外)組成的所有向量與向量p8p10(即是:泛型數(shù)組里倒數(shù)第二個(gè)點(diǎn)與倒數(shù)第一個(gè)點(diǎn)構(gòu)成的向量)的夾角,以?shī)A角最小和距點(diǎn)p10(泛型數(shù)組里最后一個(gè)點(diǎn))的距離最小為條件篩選出下一個(gè)點(diǎn)(p12),根據(jù)在離散點(diǎn)集數(shù)組里的位置索引值并添加到定義的泛型數(shù)組;

第4步:重復(fù)循環(huán)第3步,直到篩選出的索引值為第二步找出的Y值最小點(diǎn)的索引值時(shí)退出循環(huán)。

2.2 三角網(wǎng)的構(gòu)造及優(yōu)化

根據(jù)前一部分生成的凸殼多邊形利用逐點(diǎn)插入法[4]生成三角網(wǎng),如圖2所示。

1)在初始多邊形中建立一個(gè)最大三角形,其構(gòu)造方法為,找出離散數(shù)據(jù)的x,y最大、最小值,形成一個(gè)矩形,做出該矩形的外接圓,然后做出該外接圓的等邊三角形;然后迭代以下步驟,直至所有點(diǎn)被處理;

2)插入一個(gè)數(shù)據(jù)點(diǎn)P,在三角網(wǎng)中找出包含P的三角形t,把P與t的三個(gè)頂點(diǎn)相連,生成三個(gè)新的三角形;

3)利用Lop算法優(yōu)化三角網(wǎng)。

圖2 逐點(diǎn)插入法示意圖

局部?jī)?yōu)化算法[5](Local Optimization Procedure,Lop)是為了生成Delaunay三角網(wǎng)。算法的基本含義:對(duì)由兩個(gè)公共邊組成的四邊形進(jìn)行判斷,如果其中一個(gè)三角形的外接圓包含第四個(gè)頂點(diǎn),則這個(gè)四邊形的對(duì)角線(xiàn)互換,如圖3所示。

2.3 三角形的剔除

目前有些文獻(xiàn)提出了處理凹形區(qū)域的算法,但仍先假設(shè)制圖區(qū)域?yàn)橥剐蔚?待聯(lián)網(wǎng)結(jié)束后去掉那些三角形三點(diǎn)都為邊界點(diǎn)的三角形。通過(guò)研究發(fā)現(xiàn),此算法是具有局限性的,它可能去掉那些合法的三角形(圖4中的三角形ABC)。為此設(shè)計(jì)了一種新的算法用以處理這種會(huì)剔除合理三角形的情況。(圖5中的三角形ABC不會(huì)被剔除,三角形BCD會(huì)被剔除)

圖3 Lop算法示意圖

圖4 三角形剔除示意圖

算法描述如下:

1)判斷三角形的三個(gè)頂點(diǎn)是否位于邊界上。

2)如果均位于邊界上,求出其內(nèi)切圓的圓心,判斷該圓心是否位于邊界內(nèi)[6],如果圓心位于邊界內(nèi),三角形保留,否則剔除。

圖5 三角形剔除示意圖二

3 程序的實(shí)現(xiàn)

此算法已經(jīng)用java語(yǔ)言實(shí)現(xiàn),經(jīng)多次測(cè)試(測(cè)試方法:把要測(cè)試的離散點(diǎn)以及邊界點(diǎn)坐標(biāo)＜x,y,z＞放到或從存放數(shù)據(jù)的txt、excel文檔中讀到定義好的數(shù)組里,然后調(diào)用定義好的方法即可。注意:數(shù)組里先存放邊界點(diǎn)的坐標(biāo)后面存放其它的離散點(diǎn)坐標(biāo)),此算法是有效的。下圖為用特殊(邊界上的點(diǎn)有多點(diǎn)在一條邊上的)的一些點(diǎn)測(cè)試,生成的凸殼邊界(圖6),無(wú)邊界條件的Delaunay三角網(wǎng)(見(jiàn)圖7),有邊界條件生成的Delaunay三角網(wǎng)(見(jiàn)圖8)。

4 結(jié) 論

在Delaunay三角網(wǎng)生成算法的基礎(chǔ)上,研究了帶有邊界約束條件的Delaunay三角網(wǎng)的構(gòu)建,并對(duì)查找“凸殼”的算法進(jìn)行了改進(jìn),改進(jìn)后的算法對(duì)凸殼的查找更簡(jiǎn)單更全面。目前對(duì)于大區(qū)域內(nèi)帶有小區(qū)域漏洞的Delaunay三角網(wǎng)構(gòu)建還不能實(shí)現(xiàn),將在后續(xù)的學(xué)習(xí)研究中實(shí)現(xiàn)這類(lèi)Delaunay三角網(wǎng)的構(gòu)建。

[1] 劉永和,王潤(rùn)懷,齊永安.一種非凸包邊界約束不規(guī)則三角網(wǎng)生成算法[J].測(cè)繪科學(xué),2008,33(3):79-81.

[2] 吳燕來(lái),朱 莉.Delaunay三角網(wǎng)生成算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)與信息技術(shù),2007,31(4):21-22.

[3] 陳 濤,李光耀.平面離散點(diǎn)集的邊界搜索算法[J].計(jì)算機(jī)仿真,2004,21(3):21-23.

[4] 徐道柱,劉海硯.大量約束邊界條件下Delaunay三角網(wǎng)的快速生成[J].測(cè)繪工程,2007,16(3):6-10.

[5] 袁 翰,李偉波,陳婷婷.對(duì)構(gòu)建Delaunay三角網(wǎng)中凸殼算法的研究與改進(jìn)[J].計(jì)算機(jī)工程,2007,33(7):70-72.

[6] 孫家廣.計(jì)算機(jī)圖形學(xué)[M].北京:清華大學(xué)出版社,1995.