不規(guī)則三角網(wǎng)的算法設(shè)計(jì)與實(shí)現(xiàn)

/1

引言地球表面高低起伏，呈現(xiàn)一種連續(xù)變化的曲面，這種曲面無法用平面地圖來確切表示。于是我們就利用一種全新的數(shù)字地球表面的方法——數(shù)字高程模型的方法，這種方法已經(jīng)被普遍廣泛采用.數(shù)字高程模型即DEM（DｉgitalEｌevaｔioｎＭｏdel）,是以數(shù)字形式按一定結(jié)構(gòu)組織在一起，表示實(shí)際地形特征空間分布的模型,也是地形形狀大小和起伏的數(shù)字描述.由于地理信息系統(tǒng)的普及,DEM作為數(shù)字地形模擬的重要成果已經(jīng)成為國(guó)家空間數(shù)據(jù)基礎(chǔ)設(shè)施(NＳDI)的基本內(nèi)容之一，并被納入數(shù)字化空間框架（ＤGDF)進(jìn)行規(guī)?；a(chǎn),已經(jīng)成為獨(dú)立的標(biāo)準(zhǔn)基礎(chǔ)產(chǎn)品[５]。DEM有三種主要的表示模型：規(guī)則格網(wǎng)模型，等高線模型和不規(guī)則三角網(wǎng)。格網(wǎng)（即GRID）ＤEＭ在地形平坦的地方，存在大量的數(shù)據(jù)冗余，在不改變格網(wǎng)大小情況下，難以表達(dá)復(fù)雜地形的突變現(xiàn)象，在某些計(jì)算，如通視問題，過分強(qiáng)調(diào)網(wǎng)格的軸方向。不規(guī)則三角網(wǎng)（簡(jiǎn)稱TIN,即TrianｇulatｅdIrｒegularNetwoｒｋ）是另外一種表示數(shù)字高程模型的的方法（Ｐeｕkeｒ等，1978)，它既減少了規(guī)則格網(wǎng)帶來的數(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ù)，因此基于三角形的方法在地形表面建模中得到了越來越多的注意,已經(jīng)成為表面建模的主要方法之一。VB語言簡(jiǎn)潔易學(xué)，對(duì)于學(xué)習(xí)GIS的學(xué)生來說無疑是接受很容易而且較快的一門計(jì)算機(jī)編程和開發(fā)語言，也是大多數(shù)學(xué)生最熟悉和了解的語言.正是基于對(duì)生成不規(guī)則三角網(wǎng)算法的研究和滿足學(xué)GIS的學(xué)生對(duì)VB語言的喜愛和熟悉的情況下,本文就主要介紹用三角網(wǎng)生長(zhǎng)算法生成不規(guī)則三角網(wǎng)及其在ＶB6.0環(huán)境下的實(shí)現(xiàn)。2

ＴIN的算法種類及各算法特點(diǎn)在介紹構(gòu)成TＩN各種算法之前我們要來了解認(rèn)識(shí)一下一個(gè)重要法則——Delaｕnａy三角網(wǎng)法則。通常構(gòu)建三角網(wǎng)并不考慮地性線（山脊線，山谷線)的骨架作用,但是，由于用等高線數(shù)據(jù)構(gòu)建三角網(wǎng)時(shí),由于地形的復(fù)雜多樣，有的地區(qū)存在因地形突變而形成的斷裂線等特殊地貌。另外一些地區(qū)存在大面積水域等內(nèi)部不需要構(gòu)網(wǎng)的區(qū)域，因此,在精度要求較高的TIN中,必須考慮以上問題.因此此時(shí)應(yīng)顧及地性線，斷裂線，水域線等特殊情況,也就是應(yīng)構(gòu)建約束-Ｄelaunaｙ三角網(wǎng)。約束法是基于約束圖計(jì)算約束D-三角剖分［1，9］（簡(jiǎn)稱CDT，即ConｓtraiｎedDｅlaunayＴrianｇulatioｎ）構(gòu)造算法[8],這種Delaｕｎaｙ三角網(wǎng)滿足這樣的法則:Ｄeｌaunay三角網(wǎng)為相互鄰接且互不重疊的三角形的集合，每一個(gè)三角形的外接圓內(nèi)不包含其他點(diǎn)。Dｅlaunａy三角網(wǎng)由對(duì)應(yīng)Voronoi多邊形的點(diǎn)連接而成。Delaunaｙ三角形有三個(gè)相鄰點(diǎn)連接而成,這三個(gè)相鄰頂點(diǎn)對(duì)應(yīng)的Ｖoｒonoi多邊形有一個(gè)公共的頂點(diǎn),此頂點(diǎn)是Dｅlａunay三角形外接圓的圓心(如圖1）.根據(jù)構(gòu)建三角網(wǎng)的步驟，可將三角網(wǎng)生成算法分為三類:(1)分而治之算法(由Ｓhｍaoｓ和Hoｅy提出）,其基本思路是使問題簡(jiǎn)化，把點(diǎn)集劃分到足夠小,使其易于生成三角網(wǎng)，然后把子集中的三角網(wǎng)合并生成最終的三角網(wǎng),用局部?jī)?yōu)化(LOP，即LocalＯptiｍizaｔiｏnPｒoceｄure)算法保證其成為Ｄｅlaunay三角網(wǎng)[3］，它的優(yōu)點(diǎn)是時(shí)間效率高,但需要大量遞歸運(yùn)算，因此占用內(nèi)存空間較多，如果計(jì)算機(jī)沒有足夠的內(nèi)存,這一方法就無法使用［2］；（2）數(shù)據(jù)點(diǎn)漸次插入算法（由Laｗｓon提出），其思路很簡(jiǎn)單，先在包含所有數(shù)據(jù)點(diǎn)的一個(gè)多邊形中建立初始三角網(wǎng),然后將余下的點(diǎn)逐一插入，用LOP算法保證其成為Dｅｌauｎａy三角網(wǎng)［3］.此算法雖然容易實(shí)現(xiàn),但效率極低；（3）三角網(wǎng)生長(zhǎng)算法,在這三種算法中，三角網(wǎng)生長(zhǎng)算法在80年代以后的文獻(xiàn)中已很少見,較多的是前兩種算法［3］，三角網(wǎng)生長(zhǎng)算法目前較少人研究,筆者在這里討論的就是這一算法，該算法是由MichaelJ.MｃCullagｈ，CharｌeｓG．Roｓs提出的，本文對(duì)原有的三角網(wǎng)生長(zhǎng)算法作了進(jìn)一步優(yōu)化。2。１

三角網(wǎng)生長(zhǎng)算法步驟：(過程如圖2)(1）

在所采集的離散點(diǎn)中任意找一點(diǎn)，然后查找距此點(diǎn)最近的點(diǎn),連接后作為初始基線.（2）

在初始基線右側(cè)運(yùn)用Delａunaｙ法則搜尋第三點(diǎn),具體的做法是：在初始基線右側(cè)的離散點(diǎn)中查找距此基線距離最短的點(diǎn)，做為第三點(diǎn)。（3）

生成Ｄelaunａy三角形,再以三角形的兩條新邊（從基線起始點(diǎn)到第三點(diǎn)以及第三點(diǎn)到基線終止點(diǎn)）作為新的基線。(４）

重復(fù)步驟(2)，(3）直至所有的基線處理完畢。也有人稱此算法為“炸彈法”。

圖１dｅｌauｎay三角形與Voroｎoi多邊形偶圖

圖2三角網(wǎng)生長(zhǎng)算法過程2．1

在ＶB環(huán)境中的數(shù)據(jù)結(jié)構(gòu)為了對(duì)離散數(shù)據(jù)進(jìn)行有效管理，作者在構(gòu)建TIN時(shí)采用的數(shù)據(jù)結(jié)構(gòu)為點(diǎn)結(jié)構(gòu),邊（或線）結(jié)構(gòu),三角形(或面)結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)定義如下(圖3是對(duì)應(yīng)于圖4的不規(guī)則三角網(wǎng)的表示方法［６］）:(1）類模塊a.三角形數(shù)據(jù)結(jié)構(gòu)Ｔｒiａngle(Trianｇlｅ．ｃlｓ)Puｂlicpnt1AsNｅwPOINT

‘三頂點(diǎn)Pubｌｉcｐnｔ2AsＮｅwPOＩNTＰuｂｌicpｎｔ３AsNｅｗPOＩNTＰｕｂliｃNＯAｓLong

‘三角形編號(hào)ＰubliｃtrｉNO1,triNO2,ｔriNO3AsLong

‘三角形的相鄰三角形號(hào)PublicEｄgeNＯ1，EｄgeNO2,EdgeNO３AsLoｎg

‘三角形的三條邊號(hào)b.點(diǎn)的數(shù)據(jù)結(jié)構(gòu)Pｏint（Poiｎｔ。cls）ＰuｂliｃxＡsＤoublePubliｃyAsＤoubｌePublｉczAsＤouｂlePｕblｉcpntNＯAsLoｎｇ

‘頂點(diǎn)編號(hào)c.邊的數(shù)據(jù)結(jié)構(gòu)Edgｅ(Ｅdge．cls）PｕbliceＳＡsＰoint

‘邊的起點(diǎn)PubｌiceＥＡsPoiｎｔ

‘邊的終點(diǎn)PublｉｃLTriＮOAｓＬoｎｇ

‘邊的左三角形編號(hào)PｕｂlicRTriNOAｓLong

‘邊的左三角形編號(hào)

（2）模塊a．

三角形數(shù)組和點(diǎn)數(shù)組，三角形記數(shù)和點(diǎn)記數(shù)Ｍodulｅｌ（Moduｌel。baｓ）PｕｂliｃtriＡrrayAsNewCollectiｏn

‘三角形集合PｕblicpntAｒrayAsＮｅwCｏllｅｃtion

‘點(diǎn)的集合PublicedgeAｒrayＡｓNewColｌectiｏn

‘邊的集合PuｂlｉcnCounｔAｓLonｇ

‘點(diǎn)個(gè)數(shù)ＰubliｃeCoｕｎtAｓLoｎg

‘邊個(gè)數(shù)PubliｃtriCoｕnｔAsLｏng

‘三角形個(gè)數(shù)ｂ.

存放窗體函數(shù)中的調(diào)用函數(shù)maｔhＣal（ｍathCal。bas）ＦunctionTwｏPntDistance(ByValp1AｓPＯIＮＴ，ByValｐ2AsPＯＩＮＴ）AsDoubｌe

‘計(jì)算兩點(diǎn)之間的距離FｕncｔiｏnMinDisｔａｎcePnt（ByVaｌpAsＰOINT)AsPOＩＮＴ‘找與已知點(diǎn)最短距離的點(diǎn)FuncｔionMaｘAnglePｎt（ByValeasEdge)AsPOＩＮT‘找距與已知的基線兩端點(diǎn)組成夾角最大的點(diǎn)

圖3

TＩN的數(shù)據(jù)結(jié)構(gòu)

圖４

ＴＩN的平面圖形3

VB環(huán)境中此算法思想以及實(shí)現(xiàn)過程本文選用的方法是一種改進(jìn)的生長(zhǎng)算法,本算法和原始的生長(zhǎng)算法比較，具有速度快等優(yōu)點(diǎn)，主要是在Edge邊數(shù)據(jù)結(jié)構(gòu)中加入了邊的使用次數(shù),這樣就沒有必要對(duì)每個(gè)新生成的三角形的兩條新邊都向外擴(kuò)展生長(zhǎng)，有效地減少了擴(kuò)展的邊個(gè)數(shù)，從而提高了構(gòu)網(wǎng)速度，本算法的詳細(xì)如下。(１)在離散數(shù)據(jù)點(diǎn)集V中任取一點(diǎn)Ａ,以點(diǎn)A為基點(diǎn)尋找與它最近的一點(diǎn)Ｂ。連接ＡＢ，就得到了三角形的一條基邊,把該邊作為擴(kuò)展基邊,轉(zhuǎn)(2)。（2)在擴(kuò)展基邊（是有向的)的右邊點(diǎn)集中去找與該邊兩端點(diǎn)連成直線組成的夾角為最大的P點(diǎn),就組成了第一個(gè)三角形，將所有新生成的邊與三角形信息用相應(yīng)的鏈表進(jìn)行存儲(chǔ)起來,邊每使用一次，其數(shù)據(jù)結(jié)構(gòu)中的UseTimeｓ就加1,轉(zhuǎn)(3)。（３)在邊鏈表中取出頭位置的邊，以該邊為擴(kuò)展基邊向外進(jìn)行擴(kuò)展。如果該邊的使用次數(shù)為2或是右邊沒有點(diǎn)，該邊不進(jìn)行擴(kuò)展；否則,轉(zhuǎn)（2)進(jìn)行擴(kuò)展,同時(shí)存儲(chǔ)新生成的邊和三角形。轉(zhuǎn)（４)。(4)對(duì)邊鏈表中下一位置的邊進(jìn)行擴(kuò)展，實(shí)現(xiàn)過程同步驟（3），轉(zhuǎn)（5)。(5）重復(fù)步驟（4），直至邊鏈表中的所有邊都進(jìn)行了擴(kuò)展,就結(jié)束構(gòu)網(wǎng)。

為了對(duì)算法的穩(wěn)定性及可行性進(jìn)行檢驗(yàn),筆者在ＶB中實(shí)現(xiàn)了上述算法，并用一些實(shí)驗(yàn)數(shù)據(jù)點(diǎn)驗(yàn)證了上述算法，圖5是原始的數(shù)據(jù)點(diǎn)，圖6是用該算法實(shí)現(xiàn)TIN。應(yīng)用以上算法原理,基于ＶisualBaｓic6．0編譯環(huán)境及數(shù)據(jù)庫相結(jié)合,高效地實(shí)現(xiàn)了海量數(shù)據(jù)的Delauｎay三角網(wǎng)構(gòu)建，實(shí)驗(yàn)表明,此算法的執(zhí)行效率較高,對(duì)計(jì)算機(jī)硬件配置的要求較低.

圖5

原始數(shù)據(jù)點(diǎn)

圖６

原始數(shù)據(jù)點(diǎn)生成TＩＮ

4

數(shù)據(jù)的存儲(chǔ)-數(shù)據(jù)庫管理由于我們構(gòu)網(wǎng)所使用的點(diǎn)是我們事先所采樣測(cè)量得到的點(diǎn)，且對(duì)于一個(gè)實(shí)際的項(xiàng)目應(yīng)用來說,數(shù)據(jù)容量大,而如果是直接人為在窗體的坐標(biāo)軸中輸入數(shù)據(jù)的話,很難找準(zhǔn)所給的采樣點(diǎn)位置，因此就要將數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫中，進(jìn)行統(tǒng)一存儲(chǔ)管理。本文中,作者是將數(shù)據(jù)庫與VＢ連接起來，那么在VB中程序運(yùn)行時(shí)可直接調(diào)用數(shù)據(jù)庫中的數(shù)據(jù)。在現(xiàn)實(shí)的工程項(xiàng)目中，修路時(shí)要將某處的山地挖為平地,旅游園林公園等單位要在某些平坦的地方填方建造山林，采礦單位在地下挖方開采就形成了低洼或山體的峽谷等，形成了地形的復(fù)雜多變，那么就要在變化的區(qū)域進(jìn)行點(diǎn)的重新測(cè)量采樣,在構(gòu)網(wǎng)時(shí)，有的地方要增加點(diǎn),有的地方要?jiǎng)h除點(diǎn),有時(shí)我們還需要查詢和編輯修改某個(gè)點(diǎn)的說明信息.那么這些都要依靠數(shù)據(jù)庫的管理。當(dāng)然,也可以將數(shù)據(jù)存儲(chǔ)在文本文件中進(jìn)行讀取,關(guān)于從文件中讀取數(shù)據(jù)，相信大家在平時(shí)的學(xué)習(xí)中都有所接觸，這里不再贅述。本文空間數(shù)據(jù)的操作包括圖形的顯示，放大,縮小,漫游,編輯,拓?fù)浣?查詢和分析.

5

改進(jìn)和提高數(shù)據(jù)放在數(shù)據(jù)庫(內(nèi)存）里，再從內(nèi)存中讀取數(shù)據(jù),這比直接從硬盤上讀取數(shù)據(jù)快的多，但是,若數(shù)據(jù)量很大，Ｗindows就要頻繁地在內(nèi)存和硬盤之間交換數(shù)據(jù),反而影響速度,這種方法對(duì)硬件的依賴很大，并未從根本上解決問題［4，7］。為了提高構(gòu)網(wǎng)速度,要采用格網(wǎng)索引,即在尋找第三點(diǎn)時(shí)，減少搜尋時(shí)間。同時(shí)對(duì)于生成的三角網(wǎng)的顯示和縮放具有優(yōu)勢(shì)。在這里的改進(jìn)方式有文件格網(wǎng)索引和數(shù)據(jù)庫格網(wǎng)索引.對(duì)格網(wǎng)索引有興趣的話可參閱[4,7]。６.結(jié)束語實(shí)現(xiàn)上述算法具有很強(qiáng)的現(xiàn)實(shí)意義。TIN的直接應(yīng)用價(jià)值就是生成DEM，為DEM的生成在許多領(lǐng)域中打下基礎(chǔ)。在土木工程中,如工程項(xiàng)目的填挖方計(jì)算,線路勘測(cè)設(shè)計(jì),水利建設(shè)工程等的應(yīng)用;TＩN在ＧＩS中得到了普遍使用，特別是在三維可視化方面受到格外關(guān)注，基于DEＭ的水文分析與GIS結(jié)合，DEM庫，矢量庫,影像庫的三維一體