帶有邊界條件的Delaunay三角網(wǎng)生成算法的研究與實現(xiàn)

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

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

0 引 言

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

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

1 主要模塊的生成

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

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

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

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

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

2 模塊的算法思路

2.1 凸殼的構(gòu)造

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

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

圖1 離散點集

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

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

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

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

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

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

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

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

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

圖2 逐點插入法示意圖

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

2.3 三角形的剔除

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

圖3 Lop算法示意圖

圖4 三角形剔除示意圖

算法描述如下:

1)判斷三角形的三個頂點是否位于邊界上。

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

圖5 三角形剔除示意圖二

3 程序的實現(xiàn)

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

4 結(jié) 論

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

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

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

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

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

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

[6] 孫家廣.計算機圖形學[M].北京:清華大學出版社,1995.