基于VS平臺(tái)的D—TIN生長(zhǎng)算法優(yōu)化

黃煌

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

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

0 引言

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

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

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

1 TIN的算法種類及各算法特點(diǎn)

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

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

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

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

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

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

（2）在擴(kuò)展基邊（是有向的）的右邊點(diǎn)集中去找與該邊兩端點(diǎn)連成直線組成的夾角為最大的P點(diǎn)，就組成了第一個(gè)三角形，將所有新生成的邊與三角形信息用相應(yīng)的鏈表進(jìn)行存儲(chǔ)起來(lái)，邊每使用一次，其數(shù)據(jù)結(jié)構(gòu)中的使用次數(shù)就加1，轉(zhuǎn)（3）。

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

（4）對(duì)邊鏈表中下一位置的邊進(jìn)行擴(kuò)展，實(shí)現(xiàn)過(guò)程同步驟（3），轉(zhuǎn)（5）。

（5）重復(fù)步驟（4），直至邊鏈表中的所有邊都進(jìn)行了擴(kuò)展，就結(jié)束構(gòu)網(wǎng)。

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

2 總結(jié)

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

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

【參考文獻(xiàn)】

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

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

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

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

[責(zé)任編輯：楊玉潔]