VB環(huán)境下不規(guī)則三角網(wǎng)的算法設計與實現(xiàn)

1、VB環(huán)境下不規(guī)則三角網(wǎng)的算法設計與實現(xiàn)基金項目: 湖北省高等學校優(yōu)秀中青年團隊計劃項目資助(T200602); 江西省數(shù)字國土重點實驗室開發(fā)研究基金資助(DLLJ200501); 長江大學發(fā)展基金資助(2004Z0115)江劍霞1，劉少華1,2，（1北京建筑工程學院，北京 100044 ；2江西省數(shù)字國土重點實驗室 江西 撫州 344000；）摘要：本文對不規(guī)則三角網(wǎng)生長算法實現(xiàn)的研究，利用了VB強大的可視化用戶界面及其編程語言的靈活性及簡單易懂特點，基于各行業(yè)對于DEM的需要，從而開發(fā)出一種利用VB6.0語言生成基于生長算法的不規(guī)則三角網(wǎng)，結(jié)合數(shù)據(jù)庫強大的數(shù)據(jù)庫存取，編輯，查詢功能，共同實現(xiàn)

2、離散點的管理和三角網(wǎng)的構(gòu)成。關(guān)鍵詞：不規(guī)則三角網(wǎng)；Delaunay三角網(wǎng)；VB環(huán)境；算法Algorithm designing and realizing of TIN In VBJIANG Jian-xia1, LIU Shao-hua1,2(1BeiJing Institute of Civil Engineering And Architecture, BeiJing, 100044; 2 Digital Land Key Lab of JiangXi Province, Fuzhou 344000)Abstract: the paper discuss the algorithm of

3、 the TIN which takes advantage of VBs powerfully visible interface of user and flexibility and knowing easily of compiling procedure. On the basis of demanding for DEM for all professions, the author uses the VB language to develop a kind of TIN based on the growth-algorithm, in combination with the

4、 powerful function of the data bases data accessed, edited and inquired about, achieving the management of the dispersed points and the construction of TIN Key words :TIN, Delaunay, VB, algorithm1 引言地球表面高低起伏，呈現(xiàn)一種連續(xù)變化的曲面，這種曲面無法用平面地圖來確切表示。于是我們就利用一種全新的數(shù)字地球表面的方法數(shù)字高程模型的方法，這種方法已經(jīng)被普遍廣泛采用。數(shù)字高程模型即DEM（Digital

5、 Elevation Model），是以數(shù)字形式按一定結(jié)構(gòu)組織在一起，表示實際地形特征空間分布的模型，也是地形形狀大小和起伏的數(shù)字描述。由于地理信息系統(tǒng)的普及，DEM作為數(shù)字地形模擬的重要成果已經(jīng)成為國家空間數(shù)據(jù)基礎(chǔ)設施（NSDI）的基本內(nèi)容之一，并被納入數(shù)字化空間框架（DGDF）進行規(guī)?；a(chǎn)，已經(jīng)成為獨立的標準基礎(chǔ)產(chǎn)品5。DEM有三種主要的表示模型：規(guī)則格網(wǎng)模型，等高線模型和不規(guī)則三角網(wǎng)。格網(wǎng)（即GRID）DEM在地形平坦的地方，存在大量的數(shù)據(jù)冗余，在不改變格網(wǎng)大小情況下，難以表達復雜地形的突變現(xiàn)象，在某些計算，如通視問題，過分強調(diào)網(wǎng)格的軸方向。不規(guī)則三角網(wǎng)（簡稱TIN，即Triangul

6、ated Irregular Network）是另外一種表示數(shù)字高程模型的的方法（Peuker等，1978），它既減少了規(guī)則格網(wǎng)帶來的數(shù)據(jù)冗余，同時在計算（如坡度）效率方面又優(yōu)于純粹基于等高線的方法。不規(guī)則三角網(wǎng)能隨地形起伏變化的復雜性而改變采樣點的密度和決定采樣點的位置，因而它能夠避免地形起伏平坦時的數(shù)據(jù)冗余，又能按地形特征點如山脊，山谷線，地形變化線等表示數(shù)字高程特征?；谌切蔚谋砻娼？蛇m合所有的數(shù)據(jù)結(jié)構(gòu)，且三角形在形狀和大小方面有很大靈活性，能很容易地融合斷裂線，生成線或其他任何數(shù)據(jù)，因此基于三角形的方法在地形表面建模中得到了越來越多的注意，已經(jīng)成為表面建模的主要方法之一。VB語言簡

7、潔易學，對于學習GIS的學生來說無疑是接受很容易而且較快的一門計算機編程和開發(fā)語言，也是大多數(shù)學生最熟悉和了解的語言。正是基于對生成不規(guī)則三角網(wǎng)算法的研究和滿足學GIS的學生對VB語言的喜愛和熟悉的情況下，本文就主要介紹用三角網(wǎng)生長算法生成不規(guī)則三角網(wǎng)及其在VB6.0環(huán)境下的實現(xiàn)。2 TIN的算法種類及各算法特點在介紹構(gòu)成TIN各種算法之前我們要來了解認識一下一個重要法則Delaunay三角網(wǎng)法則。通常構(gòu)建三角網(wǎng)并不考慮地性線（山脊線，山谷線）的骨架作用，但是，由于用等高線數(shù)據(jù)構(gòu)建三角網(wǎng)時，由于地形的復雜多樣，有的地區(qū)存在因地形突變而形成的斷裂線等特殊地貌。另外一些地區(qū)存在大面積水域等內(nèi)部不需

8、要構(gòu)網(wǎng)的區(qū)域，因此，在精度要求較高的TIN中，必須考慮以上問題。因此此時應顧及地性線，斷裂線，水域線等特殊情況，也就是應構(gòu)建約束Delaunay三角網(wǎng)。約束法是基于約束圖計算約束D三角剖分1,9（簡稱CDT，即Constrained Delaunay Triangulation）構(gòu)造算法8，這種Delaunay三角網(wǎng)滿足這樣的法則：Delaunay三角網(wǎng)為相互鄰接且互不重疊的三角形的集合，每一個三角形的外接圓內(nèi)不包含其他點。Delaunay三角網(wǎng)由對應Voronoi多邊形的點連接而成。Delaunay三角形有三個相鄰點連接而成，這三個相鄰頂點對應的Voronoi多邊形有一個公共的頂點，此頂點是

9、Delaunay三角形外接圓的圓心（如圖1）。根據(jù)構(gòu)建三角網(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)點是時間效率高，但需要大量遞歸運算，因此占用內(nèi)存空間較多，如果計算機沒有足夠的內(nèi)存，這一方法就無法使用2；（2）數(shù)據(jù)點漸次插入算法（由Lawson提出），其思路很簡單，先在包含所有數(shù)據(jù)點的一個多邊形中建立初始三角網(wǎng)，然后

10、將余下的點逐一插入，用LOP算法保證其成為Delaunay三角網(wǎng)3。此算法雖然容易實現(xiàn)，但效率極低；（3）三角網(wǎng)生長算法，在這三種算法中，三角網(wǎng)生長算法在80年代以后的文獻中已很少見，較多的是前兩種算法3，三角網(wǎng)生長算法目前較少人研究，筆者在這里討論的就是這一算法，該算法是由Michael J.McCullagh,Charles G.Ross提出的，本文對原有的三角網(wǎng)生長算法作了進一步優(yōu)化。2.1 三角網(wǎng)生長算法步驟：（過程如圖2）（1） 在所采集的離散點中任意找一點，然后查找距此點最近的點，連接后作為初始基線。（2） 在初始基線右側(cè)運用Delaunay法則搜尋第三點，具體的做法是：在初始基線

11、右側(cè)的離散點中查找距此基線距離最短的點，做為第三點。（3） 生成Delaunay三角形，再以三角形的兩條新邊（從基線起始點到第三點以及第三點到基線終止點）作為新的基線。（4） 重復步驟（2），（3）直至所有的基線處理完畢。也有人稱此算法為“炸彈法”。圖1 delaunay三角形與Voronoi多邊形偶圖 圖2 三角網(wǎng)生長算法過程2.2 在VB環(huán)境中的數(shù)據(jù)結(jié)構(gòu)為了對離散數(shù)據(jù)進行有效管理，作者在構(gòu)建TIN時采用的數(shù)據(jù)結(jié)構(gòu)為點結(jié)構(gòu)，邊（或線）結(jié)構(gòu)，三角形（或面）結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)定義如下（圖3是對應于圖4的不規(guī)則三角網(wǎng)的表示方法6）：(1)類模塊a.三角形數(shù)據(jù)結(jié)構(gòu)Triangle(Triangle.cl

12、s)Public pnt1 As New POINT 三頂點Public pnt2 As New POINTPublic pnt3 As New POINTPublic NO As Long 三角形編號Public triNO1, triNO2, triNO3 As Long 三角形的相鄰三角形號Public EdgeNO1, EdgeNO2, EdgeNO3As Long 三角形的三條邊號b.點的數(shù)據(jù)結(jié)構(gòu) Point(Point.cls)Public x As DoublePublic y As DoublePublic z As DoublePublic pntNO As Long 頂點編

13、號c.邊的數(shù)據(jù)結(jié)構(gòu)Edge(Edge.cls)Public eS As Point 邊的起點Public eE As Point 邊的終點Public LTriNO As Long 邊的左三角形編號Public RTriNO As Long 邊的左三角形編號 (2) 模塊a. 三角形數(shù)組和點數(shù)組，三角形記數(shù)和點記數(shù)Modulel(Modulel.bas)Public triArray As New Collection 三角形集合Public pntArray As New Collection 點的集合Public edgeArray As New Collection 邊的集合Public

14、 nCount As Long 點個數(shù)Public eCount As Long 邊個數(shù)Public triCount As Long 三角形個數(shù)b. 存放窗體函數(shù)中的調(diào)用函數(shù)mathCal(mathCal.bas)Function TwoPntDistance(ByVal p1 As POINT, ByVal p2 As POINT) As Double 計算兩點之間的距離Function MinDistancePnt(ByVal p As POINT) As POINT 找與已知點最短距離的點Function MaxAnglePnt(ByVal e as Edge) As POINT 找距

15、與已知的基線兩端點組成夾角最大的點 圖 3 TIN的數(shù)據(jù)結(jié)構(gòu) 圖 4 TIN的平面圖形 3 VB環(huán)境中此算法思想以及實現(xiàn)過程本文選用的方法是一種改進的生長算法,本算法和原始的生長算法比較,具有速度快等優(yōu)點,主要是在Edge邊數(shù)據(jù)結(jié)構(gòu)中加入了邊的使用次數(shù),這樣就沒有必要對每個新生成的三角形的兩條新邊都向外擴展生長,有效地減少了擴展的邊個數(shù),從而提高了構(gòu)網(wǎng)速度,本算法的詳細如下。(1) 在離散數(shù)據(jù)點集V 中任取一點A ,以點A為基點尋找與它最近的一點B。連接AB ,就得到了三角形的一條基邊,把該邊作為擴展基邊,轉(zhuǎn)(2) 。(2) 在擴展基邊(是有向的)的右邊點集中去找與該邊兩端點連成直線組成的夾角

16、為最大的P點,就組成了第一個三角形,將所有新生成的邊與三角形信息用相應的鏈表進行存儲起來,邊每使用一次,其數(shù)據(jù)結(jié)構(gòu)中的UseTimes就加1,轉(zhuǎn)(3) 。(3) 在邊鏈表中取出頭位置的邊,以該邊為擴展基邊向外進行擴展。如果該邊的使用次數(shù)為2或是右邊沒有點,該邊不進行擴展;否則,轉(zhuǎn)( 2)進行擴展,同時存儲新生成的邊和三角形。轉(zhuǎn)(4)。(4) 對邊鏈表中下一位置的邊進行擴展,實現(xiàn)過程同步驟(3) ,轉(zhuǎn)(5)。(5) 重復步驟( 4) ,直至邊鏈表中的所有邊都進行了擴展,就結(jié)束構(gòu)網(wǎng)。為了對算法的穩(wěn)定性及可行性進行檢驗，筆者在VB中實現(xiàn)了上述算法，并用一些實驗數(shù)據(jù)點驗證了上述算法，圖5是原始的數(shù)據(jù)點

17、，圖6是用該算法實現(xiàn)TIN。應用以上算法原理,基于Visual Basic 6.0 編譯環(huán)境及數(shù)據(jù)庫相結(jié)合,高效地實現(xiàn)了海量數(shù)據(jù)的Delaunay 三角網(wǎng)構(gòu)建,實驗表明,此算法的執(zhí)行效率較高,對計算機硬件配置的要求較低。 圖5 原始數(shù)據(jù)點 圖6 原始數(shù)據(jù)點生成TIN4 數(shù)據(jù)的存儲數(shù)據(jù)庫管理由于我們構(gòu)網(wǎng)所使用的點是我們事先所采樣測量得到的點，且對于一個實際的項目應用來說，數(shù)據(jù)容量大，而如果是直接人為在窗體的坐標軸中輸入數(shù)據(jù)的話，很難找準所給的采樣點位置，因此就要將數(shù)據(jù)存儲在數(shù)據(jù)庫中，進行統(tǒng)一存儲管理。本文中，作者是將數(shù)據(jù)庫與VB連接起來，那么在VB中程序運行時可直接調(diào)用數(shù)據(jù)庫中的數(shù)據(jù)。在現(xiàn)實的工

18、程項目中，修路時要將某處的山地挖為平地，旅游園林公園等單位要在某些平坦的地方填方建造山林，采礦單位在地下挖方開采就形成了低洼或山體的峽谷等，形成了地形的復雜多變，那么就要在變化的區(qū)域進行點的重新測量采樣，在構(gòu)網(wǎng)時，有的地方要增加點，有的地方要刪除點，有時我們還需要查詢和編輯修改某個點的說明信息。那么這些都要依靠數(shù)據(jù)庫的管理。當然，也可以將數(shù)據(jù)存儲在文本文件中進行讀取，關(guān)于從文件中讀取數(shù)據(jù)，相信大家在平時的學習中都有所接觸，這里不再贅述。本文空間數(shù)據(jù)的操作包括圖形的顯示，放大，縮小，漫游，編輯，拓撲建立，查詢和分析。5 改進和提高數(shù)據(jù)放在數(shù)據(jù)庫（內(nèi)存）里，再從內(nèi)存中讀取數(shù)據(jù)，這比直接從硬盤上讀取

19、數(shù)據(jù)快的多，但是，若數(shù)據(jù)量很大，Windows就要頻繁地在內(nèi)存和硬盤之間交換數(shù)據(jù)，反而影響速度，這種方法對硬件的依賴很大，并未從根本上解決問題4,7。為了提高構(gòu)網(wǎng)速度，要采用格網(wǎng)索引，即在尋找第三點時，減少搜尋時間。同時對于生成的三角網(wǎng)的顯示和縮放具有優(yōu)勢。在這里的改進方式有文件格網(wǎng)索引和數(shù)據(jù)庫格網(wǎng)索引。對格網(wǎng)索引有興趣的話可參閱4,7。6結(jié)束語實現(xiàn)上述算法具有很強的現(xiàn)實意義。TIN的直接應用價值就是生成DEM，為DEM的生成在許多領(lǐng)域中打下基礎(chǔ)。在土木工程中，如工程項目的填挖方計算，線路勘測設計，水利建設工程等的應用；TIN在GIS中得到了普遍使用，特別是在三維可視化方面受到格外關(guān)注，基于DEM的水文分析與GIS結(jié)合，DEM庫，矢量庫，影像庫的三維一體化，DEM與數(shù)字地球等的應用。還有在攝影測量與遙感方面，氣候分析和環(huán)境研究中的應用以及在地質(zhì)和采礦工程，林業(yè)，地形學方面都有很強的應用。本文對不規(guī)則三角網(wǎng)生長算法實現(xiàn)的研究，利用了VB6.0強大的可視化用戶界面及其