基于VS平臺的D—TIN生長算法優化

黃煌

【摘 要】本文對傳統不規則三角網生長算法實現的研究，并對其進行優化，利用了Visual Studio 2012平臺強大的可視化用戶界面及其編程語言的靈活性及簡單易懂特點，基于各行業對于DEM的需要，從而開發出一種構網速度快，運行效率高的一種三角網構建算法。

【關鍵詞】不規則三角網；Delaunay三角網；VS環境；算法優化

0 引言

地球表面高低起伏，呈現為一種連續變化的曲面，這種曲面無法用平面地圖來確切表示，于是我們就利用數字高程模型來表達，這種方法已經被廣泛使用。數字高程模型即DEM（Digital Elevation Model），是以數字形式按一定結構組織在一起，表示實際地形特征空間分布的模型，也是地形形狀大小和起伏的數字描述。

由于地理信息系統的普及，DEM作為數字地形模擬的重要成果已經成為國家空間數據基礎設施（NSDI）的基本內容之一，并被納入數字化空間框架（DGDF）進行規?；a，已經成為獨立的標準基礎產品[1]。DEM有三種主要的表示模型：規則格網模型，等高線模型和不規則三角網。格網（即GRID）DEM在地形平坦的地方，存在大量的數據冗余，在不改變格網大小情況下，難以表達復雜地形的突變現象，在某些計算，如通視問題，過分強調網格的軸方向。不規則三角網（簡稱TIN，即Triangulated Irregular Network）是另外一種表示數字高程模型的的方法（Peuker等，1978），它既減少了規則格網帶來的數據冗余，同時在計算（如坡度）效率方面又優于純粹基于等高線的方法。不規則三角網能隨地形起伏變化的復雜性而改變采樣點的密度和決定采樣點的位置，因而它能夠避免地形起伏平坦時的數據冗余，又能按地形特征點如山脊，山谷線，地形變化線等表示數字高程特征。

基于三角形的表面建?？蛇m合所有的數據結構，且三角形在形狀和大小方面有很大靈活性，能很容易地融合斷裂線，生成線或其他任何數據，因此基于三角形的方法在地形表面建模中得到了越來越多的注意，已經成為表面建模的主要方法之一。C#語言簡潔易學并且開發效率高，易于移植，對于學習GIS的學生來說無疑是接受很容易而且較快的一門計算機編程和開發語言，也是大多數學生最熟悉和了解的語言。正是基于對生成不規則三角網算法的研究和滿足學GIS的學生對C#語言熟悉的情況下，本文就主要介紹用三角網生長算法生成不規則三角網及其在Visual Studio 2012環境下的實現。

1 TIN的算法種類及各算法特點

在介紹構成TIN各種算法之前我們要來了解認識一下一個重要法則——Delaunay三角網法則。通常構建三角網并不考慮地性線（山脊線，山谷線）的骨架作用，但是，由于用等高線數據構建三角網時，由于地形的復雜多樣，有的地區存在因地形突變而形成的斷裂線等特殊地貌。另外一些地區存在大面積水域等內部不需要構網的區域，因此，在精度要求較高的TIN中，必須考慮以上問題。因此此時應顧及地性線，斷裂線，水域線等特殊情況，也就是應構建約束—Delaunay三角網。約束法是基于約束圖計算約束D—三角剖分[2，4]（簡稱CDT，即Constrained Delaunay Triangulation）構造算法，這種Delaunay三角網滿足這樣的法則：Delaunay三角網為相互鄰接且互不重疊的三角形的集合，每一個三角形的外接圓內不包含其他點。Delaunay三角網由對應Voronoi多邊形的點連接而成。Delaunay三角形有三個相鄰點連接而成，這三個相鄰頂點對應的Voronoi多邊形有一個公共的頂點，此頂點是Delaunay三角形外接圓的圓心。

1.1 三角網生成算法的分類

根據構建三角網的步驟，可將三角網生成算法分為三類：（1）分而治之算法（由Shmaos和Hoey提出），其基本思路是使問題簡化，把點集劃分到足夠小，使其易于生成三角網，然后把子集中的三角網合并生成最終的三角網，用局部優化（LOP，即Local Optimization Procedure）算法保證其成為Delaunay三角網[3]，它的優點是時間效率高，但需要大量遞歸運算，因此占用內存空間較多，如果計算機沒有足夠的內存，這一方法就無法使用；（2）數據點漸次插入算法（由Lawson提出），其思路很簡單，先在包含所有數據點的一個多邊形中建立初始三角網，然后將余下的點逐一插入，用LOP算法保證其成為Delaunay三角網[3]。此算法雖然容易實現，但效率極低；（3）三角網生長算法，在這三種算法中，三角網生長算法在20世紀80年代以后的文獻中已很少見，較多的是前兩種算法[3]，三角網生長算法目前較少人研究，筆者在這里討論的就是這一算法，該算法是由Michael J.McCullagh，Charles G.Ross提出的，本文對原有的三角網生長算法作了進一步優化。

1.2 三角網生長算法的優化

傳統的三角網生長算法需要對新生成的兩條邊都進行擴展，這樣就導致已經擴展一次的邊再次擴展，加大了運算量。本文將在傳統三角網生長算法的基礎上加以改進，主要是在邊的數據結構中加入了使用次數這一屬性，這樣就沒有必要對每個新生成的三角形的兩條邊都進行擴展，從而有效的減少了擴展邊的條數，提高了三角網生成速度。詳細算法如下：

（1）在離散數據點集V 中任取一點A，以點A為基點尋找與它最近的一點B。連接AB，就得到了三角形的一條基邊，把該邊作為擴展基邊，轉（2）。

（2）在擴展基邊（是有向的）的右邊點集中去找與該邊兩端點連成直線組成的夾角為最大的P點，就組成了第一個三角形，將所有新生成的邊與三角形信息用相應的鏈表進行存儲起來，邊每使用一次，其數據結構中的使用次數就加1，轉（3）。

（3）在邊鏈表中取出頭位置的邊，以該邊為擴展基邊向外進行擴展。如果該邊的使用次數為2或是右邊沒有點，該邊不進行擴展；否則，轉（2）進行擴展，同時存儲新生成的邊和三角形。轉（4）。

（4）對邊鏈表中下一位置的邊進行擴展，實現過程同步驟（3），轉（5）。

（5）重復步驟（4），直至邊鏈表中的所有邊都進行了擴展，就結束構網。

為了對算法的穩定性及可行性進行檢驗，筆者用C#語言實現了上述算法，并用一些實驗數據點驗證了上述算法。應用以上算法原理，基于Visual Studio 編譯環境，高效地實現了大量量數據的Delaunay 三角網構建，實驗表明，此算法的執行效率較高，對計算機硬件配置的要求較低。

2 總結

實現上述算法具有很強的現實意義，為DEM的生成在許多領域中打下基礎。在土木工程中，如工程項目的填挖方計算，線路勘測設計，水利建設工程等的應用；TIN在GIS中得到了普遍使用，特別是在三維可視化方面受到格外關注，基于DEM的水文分析與GIS結合，DEM庫，矢量庫，影像庫的三維一體化，DEM與數字地球等的應用。還有在攝影測量與遙感方面，氣候分析和環境研究中的應用以及在地質和采礦工程，林業，地形學方面都有很強的應用。

本文對不規則三角網生長算法實現的研究，將傳統的三角網生長算法進行了改進，使三角網構建速度大大提高，相信這一研究會有一定的價值和現實意義。

【參考文獻】

[1]李志林，朱慶.數字高程模型[M].武漢大學出版社，2001.

[2]劉錦中，馬輝.基于等高線的DEM生成算法研究和實現[J].現代測繪，2004：27（3）.

[3]武嘵波，王世新，肖春生.Delaunay三角網的生成算法研究[J].測繪學報，1999：28（1）.

[4]劉學軍，龔健雅.約束數據域的Delaunay 三角剖分與修改算法[J].測繪學報，2001：30（1）.

[責任編輯：楊玉潔]