李功權(quán)

(長江大學(xué)地球科學(xué)學(xué)院，湖北 荊州 434023)

規(guī)則格網(wǎng)模型轉(zhuǎn)換為三角網(wǎng)模型的新方法

李功權(quán)

(長江大學(xué)地球科學(xué)學(xué)院，湖北 荊州 434023)

在保留重要點(diǎn)法的基礎(chǔ)上，根據(jù)GRID與TIN模型的特性，設(shè)計(jì)了一個(gè)新的模板——“方孔錢”模板，此模板考慮了縱、橫、對角3個(gè)方向上的情況，還兼顧了以節(jié)點(diǎn)為圓心，2倍網(wǎng)格步長度為半徑的圓作為搜索方向。通過對一個(gè)在縱向上分布為3個(gè)山脊和2個(gè)山谷，且山脊與山谷之間有的坡度陡峭，有的坡度平緩的網(wǎng)格數(shù)據(jù)模型的測試說明，該算法不但很好地保留了關(guān)鍵網(wǎng)格點(diǎn)(頂點(diǎn)、凹點(diǎn))，最大限度地消除了冗余高程點(diǎn)，消除率達(dá)50%以上；而且保證了轉(zhuǎn)換前后模型的精度。

GRID; TIN; 三維可視化; 模板; 數(shù)字高程模型

在DEM中，格網(wǎng)模型(GRID)和不規(guī)則三角網(wǎng)(TIN)有著各自的優(yōu)缺點(diǎn)，適用于不同的場合和應(yīng)用目的[1]。但由于數(shù)據(jù)的來源格式不一定符合當(dāng)前的應(yīng)用和要求，這就有可能需要將GRID模型轉(zhuǎn)換為TIN模型。目前GRID向TIN的轉(zhuǎn)換主要有2種算法：①保留重要點(diǎn)法(VIP, Very Important Point)；②啟發(fā)丟棄法(DH, Drop Heuristic)。VIP方法在保留關(guān)鍵網(wǎng)格點(diǎn)方面(頂點(diǎn)、凹點(diǎn))最好，但沒有很好的考慮在重構(gòu)TIN模型時(shí)邊選取的一些規(guī)則，沒有最大限度的消除冗余點(diǎn)；DH方法在每次丟棄數(shù)據(jù)點(diǎn)時(shí)確保信息丟失最少，但要求計(jì)算量大[2]。這2種算法都沒有實(shí)現(xiàn)效率與精度的最佳融合。易法令等[3]、朱理等[4]分別根據(jù)Delaunay三角形的特點(diǎn)和高程點(diǎn)的法向量來作為選點(diǎn)條件，研究了GRID向TIN的轉(zhuǎn)換算法，在消除冗余點(diǎn)方面取得了較好的效果，但精度評價(jià)只是和ArcInfo提供的算法進(jìn)行了對比。下面，筆者以最大限度的消除冗余點(diǎn)、保證轉(zhuǎn)換精度為目標(biāo)，設(shè)計(jì)了一種新的模板——“方孔錢”模板，很好的實(shí)現(xiàn)了效率與精度的兼容。

1 轉(zhuǎn)換算法

1)轉(zhuǎn)換算法選點(diǎn)一般原則 當(dāng)空間某一點(diǎn)的高程數(shù)據(jù)能由已知點(diǎn)的高程數(shù)據(jù)推導(dǎo)時(shí)，該高程數(shù)據(jù)是冗余的,可刪除。為了增加重構(gòu)三角網(wǎng)時(shí)TIN模型的穩(wěn)定性和規(guī)則性，在篩選時(shí)遵循了Delaunay三角網(wǎng)重構(gòu)時(shí)的選取方法，也用到了Delaunay三角網(wǎng)的一些特性[5～7]。因此在判斷某一點(diǎn)的高程數(shù)據(jù)為冗余后，還應(yīng)判斷刪除該點(diǎn)后在重構(gòu)TIN模型時(shí)還能否滿足Delaunay三角網(wǎng)的特性。

2)模板說明 通過對TIN模型的構(gòu)網(wǎng)方法與Delaunay三角網(wǎng)的特性研究論證出了2類可刪除高程數(shù)據(jù)的情況。具體說明如下：

圖1 第1類可刪除的高程點(diǎn)

①第1類可刪除的情況。當(dāng)A22=(A12+A32)/2；A22=(A21+A23)/2；A22=(A11+A33)/2并且A22=(A13+A31)/2，A22可刪除。如圖1示，當(dāng)A22點(diǎn)高程數(shù)據(jù)被刪除后，可構(gòu)成的TIN模型如圖1(b)，(c)。根據(jù)Delaunay三角網(wǎng)的特性三角形的外接圓內(nèi)不存在其他點(diǎn)[3～7]，圖1(b),(c)是滿足Delaunay三角網(wǎng)要求的。在圖1(b)中A22的高程數(shù)據(jù)能由A21，A23推導(dǎo)，在圖1(c)中A22的高程數(shù)據(jù)能由A12,A32推導(dǎo)，因此A22的高程數(shù)據(jù)可刪除。要求A22=(A11+A33)/2和A22=(A13+A31)/2是考慮到精度的需求。

圖2 第2類可刪除的高程點(diǎn)

圖3 模板形狀

②第2類可刪除的情況。當(dāng)A22=(A12+A32)/2并且在模版的圓框內(nèi)不存在兩點(diǎn)過線段A12A32時(shí)；或者當(dāng)A22=(A21+A23)/2并且在模版的圓框內(nèi)不存在兩點(diǎn)過線段A21A23時(shí)，A22可刪除。如圖2所示，高程點(diǎn)5的值能由高程點(diǎn)3、4的值導(dǎo)出。當(dāng)刪除點(diǎn)5的高程數(shù)據(jù)后，在形成Delaunay三角網(wǎng)時(shí)可出現(xiàn)12或34兩條線段來實(shí)現(xiàn)三角化，如果是12線段來實(shí)現(xiàn)三角化則點(diǎn)3在點(diǎn)1、2、4所形成的外接圓內(nèi)顯然是不滿足Delaunay三角網(wǎng)的特性的，也就是說在這種條件下刪除5號點(diǎn)后在生成TIN模型只會選擇34。而高程點(diǎn)5的值能有34導(dǎo)出。即要求12線段的長度超過34線段的長度時(shí)5號點(diǎn)才能刪除。在模板中即要求圓框內(nèi)不存在過線段3，4的線段。

根據(jù)GRID與TIN模型的特性，依據(jù)上述分析，可以歸納為模板形狀如圖3所示，其中A11…A33是高程數(shù)據(jù)在GRID中的保存形式，外圓是以線段A21A23的長度為半徑，以點(diǎn)A22為圓心繪制。

3)精度保證 為了保證轉(zhuǎn)換過程中模型的精度，在進(jìn)行第2類情況的判斷時(shí)，應(yīng)先判斷A22是否為“重要點(diǎn)”，所謂重要點(diǎn)是指在第一類情況中刪除了高程點(diǎn)的情況下，那些保留下來的、能推導(dǎo)出已刪除點(diǎn)高程數(shù)據(jù)的點(diǎn)。如果是重要點(diǎn)則即使?jié)M足條件也不應(yīng)刪除，不是則可按照上面的判斷條件進(jìn)行高程點(diǎn)的刪除。

4)算法的靈活性 該模板不僅實(shí)現(xiàn)了效率與精度的最佳融合，并且還可根據(jù)不同的要求對刪除條件進(jìn)行調(diào)整以達(dá)到特定的要求。如精度要求相當(dāng)高時(shí)，可將模板中的外圓去掉。效率要求相當(dāng)高時(shí)，可在高程的比較中采用設(shè)置閥值的方法，還可適當(dāng)?shù)恼{(diào)整模板的外圓大小，以達(dá)到最大限度的消除冗余點(diǎn)，提高建TIN模型時(shí)的速度。

2 新算法測試及評估

為了檢查新算法的效果，特挑選了一個(gè)具有典型特征的網(wǎng)格數(shù)據(jù)(見圖4(a))，該數(shù)據(jù)模型在縱向上分布為3個(gè)山脊和2個(gè)山谷，且山脊與山谷之間有的坡度陡峭，有的坡度平緩。為了方便對比，在VC6.0下調(diào)用OpenGL提供的三維圖形軟件開發(fā)包(glu32.lib、opengl32.lib、glaux.lib)；將轉(zhuǎn)換后的數(shù)據(jù)和Z軸上的屬性值按Delaunay三角網(wǎng)規(guī)則構(gòu)建TIN模型，實(shí)現(xiàn)了格網(wǎng)模型和TIN模型的三維可視化(圖4(b))。這樣，不僅有助于分析原始網(wǎng)格模型的典型地形特征，而且還有利于算法之間、模型之間的相互比較和評價(jià)。

圖4 選點(diǎn)前后模型比較

筆者選擇了保留重要點(diǎn)法中最經(jīng)典的3×3模板算法與該算法進(jìn)行了比較，如表1所示?？梢钥闯觯S著GRID模型的網(wǎng)格數(shù)目的增加，該算法去掉冗余點(diǎn)的數(shù)目越來越多，基本都超過了50%，但3×3模板算法冗余點(diǎn)的消除變化不大。該算法與3×3模板算法對比可以看出，該算法冗余點(diǎn)消除的百分比多達(dá)10%以上。在精度比較過程中，選擇了表1中的第3組數(shù)據(jù)進(jìn)行轉(zhuǎn)換前后的比較(圖5)，從圖5分析得到，該算法不但在保留關(guān)鍵網(wǎng)格點(diǎn)方面(頂點(diǎn)、凹點(diǎn))相當(dāng)好，而且在坡度平緩區(qū)域中大大消除了冗余點(diǎn)。

表1 新算法與3×3模板比較

3 結(jié) 語

隨著DEM模型在社會生活中的廣泛應(yīng)用，GRID和TIN模型的相互轉(zhuǎn)化也會得到進(jìn)一步的深入研究。筆者根據(jù)GRID模型和TIN模型的特點(diǎn)，以保留重要點(diǎn)法為基礎(chǔ)，提出基于“方孔錢”模板的GRID向TIN的轉(zhuǎn)換算法。通過在三維可視化的環(huán)境下的測試表明，該算法不但很好地保留了關(guān)鍵網(wǎng)格點(diǎn)(頂點(diǎn)、凹點(diǎn))，而且最大限度地消除了冗余高程點(diǎn)，冗余高程點(diǎn)的消除率達(dá)50%以上，而且保證了轉(zhuǎn)換前后模型的精度?？梢?，該算法有較高的實(shí)用價(jià)值。

[1]周啟鳴, 劉學(xué)軍. 數(shù)字地形分析[M]. 北京: 科學(xué)出版社, 2006：57-62.

[2]JAY Lee. Compparison of existing methods for building triangular irregular netwoek models of terrain from grid digital elevation models[J]. International Journal Geographical Information Systems，1991, 5(3): 267-285.

[3]易法令, 韓德志, 謝云. GRID轉(zhuǎn)換為TIN的選點(diǎn)算法[J]. 計(jì)算機(jī)工程, 2003,29(11):62-63.

[4]朱理, 胡超. 一種有效的規(guī)則網(wǎng)格到不規(guī)則三角網(wǎng)的轉(zhuǎn)換算法[J]. 計(jì)算技術(shù)與自動化, 2006,25(2):67-70.

[5]劉學(xué)軍, 符鋅砂, 趙建三. 三角網(wǎng)數(shù)字地面模型快速構(gòu)建算法研究[J]. 中國公路學(xué)報(bào), 2000, 13(2): 31-36.

[6]Tsung-Pao Fang and Les A. Piegl. Delaunay Triangulation Using a Uniform Grid[J]. IEEE Computer Graphics &Applications，1993,13(3):36-47.

[7]Lewis B A, Robinson J S. Triangulation of Planar Regions with Applications [J]. The Computer Journal, 1978, 21(4): 324-332.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.04.022

TP311

A

1673-1409(2011)04-0068-03