帶有邊界條件的Delaunay三角網生成算法的研究與實現

2010-04-26 06:36:16寧化展徐炳喜田茂義

全球定位系統 2010年4期

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

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

0 引言

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

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

1 主要模塊的生成

帶有邊界條件的基本三角網的生成模塊[2]

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

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

3)局部優化:對生成的三角網利用LOP算法優化;

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

2 模塊的算法思路

2.1 凸殼的構造

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

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

圖1 離散點集

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

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

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

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

2.2 三角網的構造及優化

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

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

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

3)利用Lop算法優化三角網。

圖2 逐點插入法示意圖

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

2.3 三角形的剔除

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

圖3 Lop算法示意圖

圖4 三角形剔除示意圖

算法描述如下:

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

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

圖5 三角形剔除示意圖二

3 程序的實現

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