黃煌

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

【關鍵詞】不規(guī)則三角網(wǎng)；Delaunay三角網(wǎng)；VS環(huán)境；算法優(yōu)化

0 引言

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

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

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

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

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

1.1 三角網(wǎng)生成算法的分類

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

1.2 三角網(wǎng)生長算法的優(yōu)化

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

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

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

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

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

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

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

2 總結

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

本文對不規(guī)則三角網(wǎng)生長算法實現(xiàn)的研究，將傳統(tǒng)的三角網(wǎng)生長算法進行了改進，使三角網(wǎng)構建速度大大提高，相信這一研究會有一定的價值和現(xiàn)實意義。

【參考文獻】

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

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

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

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

[責任編輯：楊玉潔]