李功權

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

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

李功權

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

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

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

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

1 轉換算法

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

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

圖1 第1類可刪除的高程點

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

圖2 第2類可刪除的高程點

圖3 模板形狀

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

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

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

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

2 新算法測試及評估

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

圖4 選點前后模型比較

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

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

3 結 語

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

[1]周啟鳴, 劉學軍. 數(shù)字地形分析[M]. 北京: 科學出版社, 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轉換為TIN的選點算法[J]. 計算機工程, 2003,29(11):62-63.

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

[5]劉學軍, 符鋅砂, 趙建三. 三角網(wǎng)數(shù)字地面模型快速構建算法研究[J]. 中國公路學報, 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