苑林爽 姜軍華

【摘 要】基于三角網(wǎng)生成算法的不規(guī)則三角網(wǎng)，利用VB可視化用戶界面結(jié)合數(shù)據(jù)庫(kù)實(shí)現(xiàn)離散點(diǎn)構(gòu)建三角網(wǎng)和其數(shù)據(jù)生成。本文對(duì)不規(guī)則三角網(wǎng)生長(zhǎng)算法實(shí)現(xiàn)的研究，利用了VB強(qiáng)大的可視化用戶界面及其編程語(yǔ)言的靈活性及簡(jiǎn)單易懂特點(diǎn)，基于各行業(yè)對(duì)于DEM的需要，開發(fā)出一種利用VB6.0語(yǔ)言生成基于生長(zhǎng)算法的不規(guī)則三角網(wǎng)，結(jié)合數(shù)據(jù)庫(kù)強(qiáng)大的數(shù)據(jù)存取、編輯、查詢功能，共同實(shí)現(xiàn)離散點(diǎn)構(gòu)建三角網(wǎng)和其數(shù)據(jù)生成。

【關(guān)鍵詞】TIN模型 VB 數(shù)據(jù)生成

1 在VB環(huán)境中構(gòu)建三角網(wǎng)

首先，我們要提取出需要處理的離散點(diǎn)集。本文介紹的數(shù)據(jù)都是存儲(chǔ)在Access數(shù)據(jù)庫(kù)中的數(shù)據(jù)。這樣就要先解決VB與數(shù)據(jù)庫(kù)連接的問題，需要?jiǎng)?chuàng)建控件，打開專有格式的文件（Access數(shù)據(jù)庫(kù)文件格式為.mdb），然后打開數(shù)據(jù)庫(kù)中的點(diǎn)表（xyz），從數(shù)據(jù)庫(kù)的記錄集的第一條向下讀取直至讀出所有數(shù)據(jù)。但是我們?cè)诔绦蛏峡床怀鰜?。這時(shí)我們?nèi)绻胍纯袋c(diǎn)的離散狀態(tài)可以把這些點(diǎn)展現(xiàn)在程序中，使我們能夠直觀的看到。點(diǎn)數(shù)據(jù)讀出后就可以根據(jù)具體的算法進(jìn)行三角網(wǎng)的生成了。

本文選用的方法是生長(zhǎng)算法，算法的詳細(xì)步驟如下。

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

k1 = 1

dmin = Sqr（（x（2） - x（1）） * （x（2） - x（1）） + （y（2） - y（1）） * （y（2） - y（1）））

k2 = 2

For r = 3 To dh

d = Sqr（（x（r） - x（1）） * （x（r） - x（1）） + （y（r） - y（1）） * （y（r） - y（1）））

If d < dmin Then

dmin = d

k2 = r

End If

Next r

Picture1.Line （x（1）， y（1））-（x（k2）， y（k2））， RGB（0， 0， 255）

（2）在擴(kuò)展基邊（是有向的）的右邊點(diǎn)集中去找與該邊兩端點(diǎn)連成直線組成的夾角為最大的點(diǎn) ，連接 ， 就組成了第一個(gè)三角形。代碼如下：

k3 = 0

cosa = 1

For r = 2 To dh

If IsLeft（k1， k2， r） Then

a = fcos（k1， k2， r）

If a < cosa Then

cosa = a

k3 = r

End If

End If

Next r

If k3 > 0 Then

Picture1.Line （x（k1）， y（k1））-（x（k3）， y（k3））， RGB（0， 0， 255）

Picture1.Line （x（k2）， y（k2））-（x（k3）， y（k3））， RGB（0， 0， 255）

（3）然后以 為第一條邊向外進(jìn)行擴(kuò)展。如果該邊的右邊沒有點(diǎn)，該邊不進(jìn)行擴(kuò)展；否則，轉(zhuǎn)（2）進(jìn)行擴(kuò)展，同時(shí)存儲(chǔ)新生成的邊和三角形。代碼如下：

k3 = 0

cosa = 1

For r = 2 To dh

If IsLeft（k2， k1， r） Then

a = fcos（k2， k1， r）

If a < cosa Then

cosa = a

k3 = r

End If

End If

Next r

If k3 > 0 Then

Picture1.Line （x（k1）， y（k1））-（x（k3）， y（k3））， RGB（0， 0， 255）

Picture1.Line （x（k2）， y（k2））-（x（k3）， y（k3））， RGB（0， 0， 255）

（4）然后對(duì)下一位置的邊進(jìn)行擴(kuò)展，實(shí)現(xiàn)過程同步驟（3）。

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

為了對(duì)算法的穩(wěn)定性及可行性進(jìn)行檢驗(yàn)，本人在VB中實(shí)現(xiàn)了上述算法，并用一些實(shí)驗(yàn)數(shù)據(jù)點(diǎn)驗(yàn)證了上述算法，應(yīng)用以上算法原理，基于Visual Basic6.0編譯環(huán)境及數(shù)據(jù)庫(kù)相結(jié)合，高效地實(shí)現(xiàn)了海量數(shù)據(jù)Delaunay三角網(wǎng)構(gòu)建。實(shí)驗(yàn)表明，此算法的執(zhí)行效率較高，對(duì)計(jì)算機(jī)硬件配置的要求較低。

2 數(shù)據(jù)的存儲(chǔ)

由于我們構(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ù)庫(kù)中，進(jìn)行統(tǒng)一存儲(chǔ)管理。本文中，是將數(shù)據(jù)庫(kù)與VB連接起來，在VB中程序運(yùn)行時(shí)可直接調(diào)用數(shù)據(jù)庫(kù)中的數(shù)據(jù)。在現(xiàn)實(shí)的工程項(xiàng)目中，修路時(shí)要將某處的山地挖為平地，建設(shè)單位要在某些平坦的地方挖填方建造營(yíng)地場(chǎng)地等，形成了地形的復(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ù)庫(kù)的管理。本文在VB中實(shí)現(xiàn)生成三角網(wǎng)的數(shù)據(jù)頁(yè)是直接存儲(chǔ)到數(shù)據(jù)庫(kù)中的。與上面打開要讀取數(shù)據(jù)的數(shù)據(jù)的一樣，我們存儲(chǔ)數(shù)據(jù)也要先打開數(shù)據(jù)要存儲(chǔ)到的數(shù)據(jù)庫(kù)。

然后就可以把生成的三角網(wǎng)的數(shù)據(jù)如三角形個(gè)點(diǎn)數(shù)組p1（），p2（），p3（）和與其臨近的三角型號(hào)數(shù)組t1（），t2（），t3（）寫如數(shù)據(jù)庫(kù)中。

程序設(shè)計(jì)完成后，針對(duì)本程序的具體操作步驟如下：

（1）運(yùn)行程序，見下圖5.1。

圖5.1 開始界面

（2）點(diǎn)擊打開數(shù)據(jù)庫(kù)，出現(xiàn)下拉菜單，然后選取所用數(shù)據(jù)庫(kù)，提取離散點(diǎn)集。見下圖5.2。

圖5.2 打開下拉菜單

（3）點(diǎn)擊菜單中展點(diǎn)，把離散數(shù)據(jù)點(diǎn)展現(xiàn)在程序窗體畫板上，見圖5.3.

圖5.3 展點(diǎn)界面

（4）點(diǎn)擊生成三角網(wǎng)，程序運(yùn)行得到有離散數(shù)據(jù)連網(wǎng)而成的三角網(wǎng)，見圖5.4。

圖5.4 生成的三角網(wǎng)

（5）選擇菜單中保存數(shù)據(jù)，出現(xiàn)下拉菜單，選擇保存數(shù)據(jù)的數(shù)據(jù)庫(kù)文件，對(duì)三角網(wǎng)生成的數(shù)據(jù)進(jìn)行保存。見下圖5.5。

圖5.5 保存下拉菜單

（6）完成以上操作后，點(diǎn)擊推出，推出程序。

3 結(jié)語(yǔ)

實(shí)現(xiàn)上述算法具有很強(qiáng)的現(xiàn)實(shí)意義。TIN的直接應(yīng)用價(jià)值就是生成DEM，為DEM的生成在許多領(lǐng)域中打下基礎(chǔ)。在水利水電工程中，如工程項(xiàng)目的填挖方計(jì)算、線路勘測(cè)設(shè)計(jì)等的應(yīng)用。本文對(duì)不規(guī)則三角網(wǎng)生長(zhǎng)算法實(shí)現(xiàn)的研究，利用了VB6.0強(qiáng)大的可視化用戶界面及其編程語(yǔ)言的靈活性及簡(jiǎn)單易懂特點(diǎn)，基于各行業(yè)對(duì)于DEM的需要，開發(fā)出一種利用VB語(yǔ)言生成基于生長(zhǎng)算法的不規(guī)則三角網(wǎng)，結(jié)合數(shù)據(jù)庫(kù)強(qiáng)大的數(shù)據(jù)存取、編輯、查詢功能，實(shí)現(xiàn)離散點(diǎn)的管理和三角網(wǎng)的構(gòu)成。

參考文獻(xiàn)：

[1]周秋生.建立數(shù)字地面模型的算法研究[J].測(cè)繪工程，2001（1）.

[2]賴?guó)櫛?，李永?基于不規(guī)則網(wǎng)的DTM若干問題的探討[J].重慶交通學(xué)院學(xué)報(bào)，2003.