PAGE24數(shù)字地面模型（DTM）中不規(guī)則三角網(wǎng)（TIN）的構(gòu)建研究摘要數(shù)字地面模型（DTM）作為一種地圖信息識(shí)別技術(shù)，在地理信息系統(tǒng)、地學(xué)、計(jì)算機(jī)圖形學(xué)及虛擬現(xiàn)實(shí)等領(lǐng)域有著廣泛的應(yīng)用。不規(guī)則三角網(wǎng)（TIN）是數(shù)字地面模型最廣泛的一種表現(xiàn)形式，國(guó)內(nèi)外已經(jīng)對(duì)其有了較深入的研究。由于TIN是通過(guò)從不規(guī)則分布的數(shù)據(jù)點(diǎn)生成的連續(xù)三角面來(lái)逼近地形表面，從表達(dá)地形信息的角度而言，TIN模型的優(yōu)點(diǎn)是它能以不同層次的分辨率來(lái)描述地形表面，即TIN的三角形隨點(diǎn)集密度變化而變化，當(dāng)點(diǎn)集密集時(shí)生成的三角形小而密，稀疏時(shí)生成的三角形大而疏，這與實(shí)際的地形特征恰好一致，因此由于其能夠較好地反映實(shí)際地形信息而被廣泛使用。所以眾多的專家學(xué)者對(duì)狄洛尼三角網(wǎng)的構(gòu)建進(jìn)行了大量的研究，在實(shí)現(xiàn)算法方面已提出了幾種較成熟的算法：分割合并算法、逐點(diǎn)插入算法和三角網(wǎng)生長(zhǎng)算法等。由于不規(guī)則三角網(wǎng)（TIN）是數(shù)字高程模型中最基本和最重要的一種模型，它能以不同層次的分辨率來(lái)描述地形表面，并可以靈活的處理特殊地形。所以，本文主要圍繞基與TIN的DEM的構(gòu)建，論述了基于TIN結(jié)構(gòu)的數(shù)字高程模型建模原理和方法。主要研究離散點(diǎn)的Delaunay三角網(wǎng)生成算法，并結(jié)合了有關(guān)的研究成果對(duì)三角網(wǎng)生長(zhǎng)算法進(jìn)行了改進(jìn)。并且通過(guò)快速建立索引的方法，提高構(gòu)網(wǎng)的效率，實(shí)現(xiàn)不規(guī)則三角網(wǎng)的建立。關(guān)鍵詞：不規(guī)則三角網(wǎng)(TIN)；三角網(wǎng)生長(zhǎng)算法；C++目錄177431緒論 1180541.1研究背景 150791.2研究現(xiàn)狀 1297501.3研究目的與意義 221991.4研究?jī)?nèi)容 3162982數(shù)字高程模型 4163162.1數(shù)字高程模型 425232.2數(shù)字高程模型的特點(diǎn) 4240442.3數(shù)學(xué)高程模型的表示方法 5220452.4三種表示模型 6116012.4.1等高線模型 6208742.4.2規(guī)則格網(wǎng)模型 7275962.4.3不規(guī)則三角網(wǎng)模型 7150892.5數(shù)字高程模型的應(yīng)用 970953無(wú)約束離散點(diǎn)的Delaunay三角網(wǎng)建立 11222623.1Delaunay三角網(wǎng) 11296803.1.1Voronoi圖 11149913.1.2Delaunay三角網(wǎng)性質(zhì) 12125423.2經(jīng)典Delaunay三角網(wǎng)生成算法 13179183.2.1三角網(wǎng)生長(zhǎng)法 14226663.2.2分治算法 14156013.2.3逐點(diǎn)插入法 15188263.3建立TIN模型的方法比較 1632014不規(guī)則三角網(wǎng)的構(gòu)建 1817394.1無(wú)約束三角網(wǎng)的構(gòu)建 1856504.2約束三角網(wǎng)的構(gòu)建 19222034.2.1帶約束條件的三角網(wǎng)法則 21200824.2.2顧及約束線段的三角網(wǎng)生成算法 21273044.3構(gòu)網(wǎng)算法的優(yōu)化 22150114.3.1建立網(wǎng)格索引 2243014.4不規(guī)則三角網(wǎng)構(gòu)建成果 24246234.4.1三角網(wǎng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 24204464.4.2程序流程 25115204.4.3生成三角網(wǎng)的成果 27327645總結(jié)與展望 29151185.1總結(jié) 29215555.2展望 298428參考文獻(xiàn) 318249附錄A 3220223附錄Ｂ 491緒論1.1研究背景1946年人類的第一臺(tái)數(shù)字計(jì)算機(jī)在賓夕法尼亞大學(xué)誕生，數(shù)字化的概念也隨之出現(xiàn)，1958年，在測(cè)繪領(lǐng)域出現(xiàn)了數(shù)字高程模型(DEM)的概念。目前，對(duì)地球表面地形的數(shù)字描述和模擬多采用數(shù)字高程模型，數(shù)據(jù)高程模型已成為空間“數(shù)字地球”和數(shù)據(jù)基礎(chǔ)設(shè)施不可或缺的一部分，各國(guó)學(xué)者對(duì)其也是在進(jìn)行不斷的深入探索和研究。20世紀(jì)70年代，ISPRS就將數(shù)字高程模型納入重點(diǎn)項(xiàng)目進(jìn)行深入研究[1]。這幾年，科技進(jìn)步的速度非?？?，特別是以電子信息技術(shù)為代表的信息科學(xué)發(fā)展尤為迅猛。測(cè)繪領(lǐng)域?qū)τ贒EM的數(shù)據(jù)獲取、存儲(chǔ)和處理速度等各個(gè)方面都取得了巨大的成績(jī)和成果。如何進(jìn)行數(shù)據(jù)地形的模擬已成為研究地球科學(xué)的最為重要分支。事實(shí)上，隨時(shí)地理信息系統(tǒng)（GIS）的廣泛普及和應(yīng)用，DEM在中、法、英等國(guó)業(yè)已成為數(shù)據(jù)地形模擬中最大的亮點(diǎn)和成就，并同時(shí)成為國(guó)家基礎(chǔ)地理信息系統(tǒng)（NSDI）中不可或缺的一部分，并包含在用于大規(guī)模生產(chǎn)的智能空間數(shù)據(jù)架構(gòu)（DGDF)中。不難看出，與以往提供的等高線地形圖相同，DEM的提供已經(jīng)成為測(cè)繪工程單位的基本日常任務(wù)和日常工作之一。全國(guó)范圍內(nèi)的DEM相當(dāng)于中小比例尺的基本地形圖，而其他大比例尺、高精度的DEM相當(dāng)于大比例尺的地形圖[2]。這種高精度的DEM無(wú)疑是由非常多的地區(qū)或技術(shù)專業(yè)單位提供。近年來(lái)不同精度的數(shù)字高程模型進(jìn)行投入使用和研究，DEM逐漸變成了一項(xiàng)重要的研究?jī)?nèi)容，在空間數(shù)據(jù)設(shè)施的建設(shè)和數(shù)字地球發(fā)展戰(zhàn)略的實(shí)施中具有非常關(guān)鍵的作用[17]。1.2研究現(xiàn)狀在地理信息系統(tǒng)的飛速發(fā)展過(guò)程中，數(shù)字高程模型基于高程數(shù)據(jù)信息對(duì)特定地貌面進(jìn)行數(shù)字模擬和表示，已廣泛應(yīng)用于氣候、水利工程、測(cè)繪工程單位、地質(zhì)環(huán)境等科研領(lǐng)域以及地質(zhì)工程、生態(tài)學(xué)等。工程項(xiàng)目行業(yè)也是地理學(xué)領(lǐng)域的重點(diǎn)分支之一。此外，DEM數(shù)據(jù)存儲(chǔ)及數(shù)據(jù)處理方法等方面也取得了重大進(jìn)展。數(shù)字高程模型是地球空間數(shù)據(jù)的核心要素，同時(shí)也是各種自然地理信息的傳遞。它在建立國(guó)家空間數(shù)據(jù)基礎(chǔ)設(shè)施和實(shí)施數(shù)字地球發(fā)展戰(zhàn)略方面發(fā)揮著關(guān)鍵作用?，F(xiàn)階段，中國(guó)、英國(guó)、法國(guó)、美國(guó)等多個(gè)國(guó)家已將數(shù)字高程模型作為國(guó)家空間數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)的關(guān)鍵要素之一，納入數(shù)字空間數(shù)據(jù)架構(gòu)。數(shù)字地形模型（DTM）是米勒教授明確提出的。它主要是使用采用點(diǎn)的方式來(lái)研究地球表面。其中數(shù)字高程模型是數(shù)字地形模型的重要組成部分[16]，也是測(cè)繪中用于指示地形的常用模型。典型的網(wǎng)格化方法有規(guī)則格網(wǎng)和不規(guī)則三角網(wǎng)兩種。由于利用不規(guī)則三角剖分的不同分辨率，可以很好地解決緩沖區(qū)溢出的問(wèn)題，因此不規(guī)則三角剖分一般用于離散變量點(diǎn)的網(wǎng)格管理。隨著數(shù)字高程模型的發(fā)展趨勢(shì)，針對(duì)不規(guī)則三角剖分產(chǎn)生了許多完美的生成算法。在不同的算法中，由于Delaunay三角剖分算法可以盡可能地避開(kāi)長(zhǎng)三角形，因此對(duì)Delaunay三角剖分算法的科學(xué)研究從20世紀(jì)70年代中后期到80年代中后期逐漸興起。隨著Delaunay三角剖分技術(shù)的應(yīng)用范圍逐漸擴(kuò)大，其實(shí)際應(yīng)用也得到了緩慢推進(jìn)，另外，這種技術(shù)對(duì)于網(wǎng)絡(luò)的高效率和盈余管理的要求也在不斷變化和提升，所以在實(shí)際應(yīng)用時(shí)就必須對(duì)Delaunay三角剖分的相關(guān)生成算法及相關(guān)理論進(jìn)行深入的研究和分析。但在對(duì)其進(jìn)行深入分析和研究時(shí)，主要是研究無(wú)約束Delaunay三角網(wǎng)生成和約束Delaunay三角網(wǎng)的生成等兩種關(guān)鍵類型。1.3研究目的與意義由于云計(jì)算技術(shù)和大數(shù)據(jù)技術(shù)的快速發(fā)展和普及，我國(guó)已將DEM作為數(shù)據(jù)地形模擬仿真的關(guān)鍵技術(shù)，并成為空間信息基礎(chǔ)設(shè)施建設(shè)（NSDI）的基礎(chǔ)內(nèi)容，同時(shí)納入智能室內(nèi)空間的發(fā)展，已成為一種獨(dú)立的標(biāo)準(zhǔn)化基礎(chǔ)商品。通常情況下，DEM有規(guī)則格網(wǎng)模型、等高線模型以及不規(guī)則三角剖分模型等三個(gè)關(guān)鍵表示模型。另外，格網(wǎng)DEM（GRIDDEM）在地形平坦的地區(qū)，有很多緩沖區(qū)溢出，如果不改變網(wǎng)格大小，在諸如通視、過(guò)分強(qiáng)調(diào)網(wǎng)格的軸方向等計(jì)算方面根本無(wú)法表達(dá)復(fù)雜地形的基因突變狀態(tài)。不規(guī)則三角網(wǎng)（TriangulatedIrregularNetwork，簡(jiǎn)稱TIN）是表示DEM模型的另一種方式。它不僅減少了規(guī)則格網(wǎng)產(chǎn)生的緩沖區(qū)溢出，而且優(yōu)于估計(jì)的高效率（如斜率），效果也比單獨(dú)基于繪制好等高線的方法要好的多。不規(guī)則三角網(wǎng)可以根據(jù)地形波動(dòng)的多樣性改變采樣點(diǎn)的相對(duì)密度和決定采樣點(diǎn)的位置[4]。如此，它可以很好的防止在地形起伏平整時(shí)緩沖區(qū)溢出，并且可以充分利用峽谷線、山地、地形過(guò)渡線等地形特征點(diǎn)，繼而如實(shí)表示數(shù)字高程的基本特征。不規(guī)則三角網(wǎng)是數(shù)字高程模型最常見(jiàn)最常用的一種表達(dá)方式，世界上很多國(guó)都對(duì)其進(jìn)行了更加深入和詳盡的分析和研究。該領(lǐng)域的很多著名專家、學(xué)者、教授對(duì)Delaunay三角剖分的構(gòu)造進(jìn)行了大量的科學(xué)研究，并在完成優(yōu)化算法的層面明確提出了三角網(wǎng)生長(zhǎng)法、分治法和逐點(diǎn)插入法等幾類較為完善的優(yōu)化技術(shù)和算法。其中分治算法主要采用遞歸思想進(jìn)行設(shè)計(jì)，應(yīng)用也很多廣泛，但當(dāng)數(shù)據(jù)量非常大時(shí)，對(duì)計(jì)算機(jī)的硬件及軟件資源要求較高。當(dāng)數(shù)據(jù)量較大時(shí)，傳統(tǒng)的逐點(diǎn)插入方式算法復(fù)雜度較弱，建網(wǎng)速度較慢。三角測(cè)量增長(zhǎng)和發(fā)展方法涉及尋找最接近整體目標(biāo)點(diǎn)的點(diǎn)，數(shù)據(jù)量大時(shí)，效率也低。隨著應(yīng)用理論和算法的不斷應(yīng)用及完善，在實(shí)際中經(jīng)常會(huì)對(duì)對(duì)大面積區(qū)域進(jìn)行有效處理，或者針對(duì)復(fù)雜地形實(shí)現(xiàn)數(shù)字化路面物理模型并完成建模。越來(lái)越多的行業(yè)必須更高效、更強(qiáng)大、更有效、更具可擴(kuò)展性的數(shù)字地面模型系統(tǒng)1.4研究?jī)?nèi)容（1）掌握MicrosoftVisualStudio.NetC#或C++語(yǔ)言和AutoCAD等軟件開(kāi)發(fā)方法；（2）根據(jù)不規(guī)則三角網(wǎng)模型構(gòu)建的理論、方法和應(yīng)用領(lǐng)域，構(gòu)造相應(yīng)的TIN模型；（3）對(duì)構(gòu)造的三角網(wǎng)數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行研究和分析，進(jìn)而優(yōu)化數(shù)據(jù)結(jié)構(gòu)和算法，能快速高效構(gòu)建三角網(wǎng)。2數(shù)字高程模型2.1數(shù)字高程模型數(shù)字地形模型主要是通過(guò)一些采樣點(diǎn)來(lái)有效描述地球表面的地形特點(diǎn)，其本質(zhì)特征就是對(duì)地面的形狀信息的空間分布采用有序序列進(jìn)行描述和表達(dá)，其表示形式為：Kp在式2-1中，Kp表示在第p號(hào)地面點(diǎn)上，針對(duì)第k類地面特性信息的特征值，函數(shù)的參數(shù)中，（uｐ，vｐ）表示P點(diǎn)處的坐標(biāo)值，n為所研究的地面點(diǎn)的個(gè)數(shù)，m表示共有多少種信息的類型。當(dāng)k=1時(shí)，則f1為地面高程的映射關(guān)系，（uｐ，vｐ）為數(shù)據(jù)的兩個(gè)坐標(biāo)，這個(gè)公式所表達(dá)的是數(shù)字高程模型[16]，是最關(guān)鍵的部分?jǐn)?shù)字地面模型[6]。用數(shù)字高程模型來(lái)表示地形特征，是地理空間數(shù)據(jù)的基本內(nèi)容，它包含了地面的各種物理上的信息，對(duì)于構(gòu)建空間數(shù)據(jù)發(fā)揮著不可或缺的作用，它也是某個(gè)區(qū)域三維空間向量有限序列的表達(dá)：Vi式2-2中，Xi，Yi表示某個(gè)地面點(diǎn)的坐標(biāo)值，而Zi則表示當(dāng)前地面點(diǎn)的相應(yīng)高程值。另外，當(dāng)以規(guī)則格網(wǎng)排序每個(gè)平面向量的位置時(shí)，為了簡(jiǎn)化表示就可以忽略它們的平面坐標(biāo)，這時(shí)，數(shù)字高程模型就退化成了一維空間向量編碼序列，其可表示為：{Zi2.2數(shù)字高程模型的特點(diǎn)數(shù)字高程模型與地圖有著很多的區(qū)別，其主要表現(xiàn)為：（1）多方面多角度顯示地形制作完成地形圖之后，不能隨意更改其比例尺。如果你想換一張不同的地圖，你必須用人為因素來(lái)實(shí)際操作管理方法。地形信息可以通過(guò)計(jì)算機(jī)進(jìn)行管理，生成的地圖可以具有各種比例精度。（2）可以保證精度不受損壞隨著時(shí)間的推移，傳統(tǒng)的地圖會(huì)發(fā)生變化。另外，常規(guī)地圖的人因管理方法是通過(guò)不同的方式制作地圖，會(huì)失去原有的精度。數(shù)字高程模型采用數(shù)字化存儲(chǔ)，確保精度不易改變。（3）實(shí)時(shí)和自動(dòng)化技術(shù)的實(shí)現(xiàn)非常容易常規(guī)地圖形成后，如需添加或修改相關(guān)信息，仍然需要從前到后進(jìn)行同樣的工作，即費(fèi)時(shí)又費(fèi)力，其更新周期較長(zhǎng)，不能馬上升級(jí)地圖。數(shù)字高程模型用數(shù)字方法表示，必須增加或改變的自然地理信息存儲(chǔ)在計(jì)算機(jī)中，經(jīng)過(guò)中后期管理方法，可以創(chuàng)建各種實(shí)時(shí)地圖。2.3數(shù)學(xué)高程模型的表示方法一般情況下，地面形態(tài)的變化可能用很多方法進(jìn)行表達(dá)，其中最常用的數(shù)字高程模型在表示地表變化時(shí)，用數(shù)學(xué)和圖像兩種形式進(jìn)行表示。地形表達(dá)方式地形表達(dá)方式數(shù)學(xué)方式圖像方式全局局部點(diǎn)方式線方式其他方式（繪畫(huà)、影像等）傅立葉級(jí)數(shù)多項(xiàng)式函數(shù)規(guī)則的分塊函數(shù)不規(guī)則的分塊函數(shù)規(guī)則（密度一致、密度可變）不規(guī)則（三角網(wǎng)、臨近網(wǎng)）典型特征（山峰、洼坑、隘口、邊界等）滑面線等高線特征線（谷底線、山脊線、海岸線、坡度變化線等）圖2-1地形表達(dá)方法（1）數(shù)學(xué)方法用數(shù)學(xué)方法對(duì)數(shù)字高程實(shí)體模型進(jìn)行表示時(shí)通常采用整體擬合法和局部擬合法兩種方式。整體擬合利用代數(shù)公式和傅里葉級(jí)數(shù)進(jìn)行該區(qū)域所有高程的表示，然后將其轉(zhuǎn)換成高程坡度以表示高程實(shí)體模型；部分?jǐn)M合方法則是將該地形區(qū)域劃分為基本相同多個(gè)不規(guī)則區(qū)域，然后進(jìn)內(nèi)部搜索，最終根據(jù)有限點(diǎn)生成對(duì)應(yīng)的高程坡度[7]。（2）圖像方法圖像表示方法可以用于對(duì)數(shù)據(jù)高程模型進(jìn)行有效說(shuō)明，其分為點(diǎn)、線等方式。在線方法表示時(shí)，最經(jīng)典和常用的方法則是等高線的方法，當(dāng)然諸如山線、海域、峽谷線等其他特征線也都是描述地面高程的非常重要信息。點(diǎn)方法則用于創(chuàng)建模型，可以通過(guò)多種方式收集離散變量點(diǎn)數(shù)據(jù)，可以按照不規(guī)則格子采集，也可以按照標(biāo)準(zhǔn)格子采集，也可以選擇采集。2.4三種表示模型在地理信息系統(tǒng)中，對(duì)于數(shù)據(jù)高程模型的表示，最為常用和經(jīng)典且關(guān)鍵的主要有三種模型，即等高線模型、規(guī)則格網(wǎng)模型和不規(guī)則格網(wǎng)模型[16]，對(duì)于地表形態(tài)均可以采用這三模型分別模擬。它們分別具有各自優(yōu)缺點(diǎn)，但模型之間可以相互轉(zhuǎn)換。2.4.1等高線模型傳統(tǒng)的等高線圖是基于手工制作的。布魯因斯于最早制作了人類歷史上第一張描述深海變遷的等高線圖；P.Buache發(fā)表了第一個(gè)等高線圖，其模擬第一個(gè)等高線圖時(shí)，化費(fèi)了大量的時(shí)間用于計(jì)算，且工作復(fù)雜很高；20世紀(jì)40年代，計(jì)算機(jī)的發(fā)明人馮諾依曼經(jīng)過(guò)長(zhǎng)期研究，提出采用數(shù)據(jù)自動(dòng)內(nèi)插的方式來(lái)實(shí)現(xiàn)模擬，大大節(jié)省的計(jì)算量及時(shí)間，同時(shí)開(kāi)啟了運(yùn)用計(jì)算機(jī)實(shí)現(xiàn)繪制等值線圖的新時(shí)代，也使這種方式得到了飛速的發(fā)展和應(yīng)用。其中對(duì)于等值線的函數(shù)表達(dá)式為：f(x,y)=D（2-4）式2-4函數(shù)中，D為一個(gè)常數(shù)，主要表示屬性信息。當(dāng)其表示的是高程信息時(shí)被稱作等高線。等高線是高程相等的點(diǎn)所連接而成的閉合弧線[16]。等高線模型主要存儲(chǔ)的為等高線和相應(yīng)高程的集合信息[8]。等高線主要以兩種方式進(jìn)行存儲(chǔ)：第一是存儲(chǔ)標(biāo)準(zhǔn)為等值點(diǎn)處的坐標(biāo)，在此種情況下，每個(gè)輪廓都是一個(gè)圓弧或者一個(gè)簡(jiǎn)單的不規(guī)則圖形。因此，一般情況下，均采用二維單向鏈表的方法對(duì)相關(guān)內(nèi)容及數(shù)據(jù)進(jìn)行存儲(chǔ)。這種存儲(chǔ)方式相比之下十分的簡(jiǎn)便，但是也有一定的弊端。如果相應(yīng)的等高線長(zhǎng)度過(guò)大則需要一個(gè)大空間的鏈表來(lái)進(jìn)行相關(guān)信息的存儲(chǔ)，導(dǎo)致處理比較困難。另外除了高程之外的其他信息存儲(chǔ)需要插值完成[16]。第二種方式則是根據(jù)等高線、等高線間的拓?fù)浣Y(jié)構(gòu)進(jìn)行存儲(chǔ)，這種以拓?fù)潢P(guān)系為依據(jù)的存儲(chǔ)方式可以很好的使用圖的結(jié)構(gòu)。連接點(diǎn)是兩個(gè)相鄰等高線之間的區(qū)域，圖的邊則對(duì)應(yīng)等高線。該方法可以十分直接的反映等高線是否為圖形，同時(shí)能夠清晰的表明其拓?fù)浣Y(jié)構(gòu)。在GIS中，等高線模型可以精準(zhǔn)的表示和反映地質(zhì)的高程、傾角、坡度等構(gòu)造特征，所以等高線轉(zhuǎn)換已經(jīng)成為輔助設(shè)計(jì)圖和數(shù)據(jù)可視化的關(guān)鍵內(nèi)容。當(dāng)然，等高線模型可以有效的表示連續(xù)坡度，但不適合數(shù)學(xué)分析過(guò)程，數(shù)據(jù)高程模型轉(zhuǎn)化為智能海流等高線圖時(shí)，與航空攝影測(cè)量精確測(cè)量得到的模型相比較而言，效果不盡人意，所以，在實(shí)際應(yīng)用時(shí)，往往需要轉(zhuǎn)化為格網(wǎng)模型來(lái)進(jìn)行表示。2.4.2規(guī)則格網(wǎng)模型由于通過(guò)數(shù)據(jù)航拍，精確測(cè)量整個(gè)區(qū)域的數(shù)據(jù)信息一般都是不規(guī)則分布，且數(shù)據(jù)信息的差異性很大，如果仍然使用等值線制作，則要預(yù)先進(jìn)行網(wǎng)格管理數(shù)據(jù)信息的整合和獲取，然后對(duì)等點(diǎn)進(jìn)行搜索跟蹤并制作。規(guī)則格網(wǎng)和不規(guī)則格網(wǎng)是兩種經(jīng)常采用的兩種方法。[16]。格網(wǎng)模型通常有三角形、正方形、六邊形等。另外，對(duì)于格網(wǎng)高程值的表述主要是有兩種不同的描述。一種是將格網(wǎng)中的各點(diǎn)高程值進(jìn)行存儲(chǔ)，但是這種方式所得到的高程模型不連續(xù)；另外一種就是將網(wǎng)格點(diǎn)內(nèi)的平均值來(lái)進(jìn)行存儲(chǔ)，這種方式各點(diǎn)的高程值需要內(nèi)插得到[16]。規(guī)則網(wǎng)格模型算法設(shè)計(jì)簡(jiǎn)單，排序標(biāo)準(zhǔn)，不僅測(cè)量地形中每個(gè)點(diǎn)的高程非常實(shí)用，而且測(cè)量輪廓、山坡陰影、坡度和傾角也很方便，但它仍然存在以下不足：（1）在實(shí)際應(yīng)用中，規(guī)則格網(wǎng)模型很難得到十分準(zhǔn)確的地形信息。這樣會(huì)導(dǎo)致在不同的地形中造成不同的問(wèn)題，平坦處容易導(dǎo)致信息重復(fù)，而復(fù)雜地區(qū)會(huì)獲得較低分辨率當(dāng)[16]，但實(shí)際應(yīng)用時(shí)，人們希望針對(duì)復(fù)雜區(qū)域數(shù)據(jù)信息點(diǎn)的密度應(yīng)當(dāng)比較大，而針對(duì)平坦區(qū)域的密度可以比較??；（2）如果離散變量級(jí)別很大，求解起來(lái)比較困難，所以往往需要先將其數(shù)據(jù)信息進(jìn)行人為減少，然后再進(jìn)行存儲(chǔ)；（3）在描述地形時(shí)，如果格網(wǎng)尺寸固定不變，在地形非常復(fù)雜的地區(qū)，數(shù)據(jù)高程模型的精度會(huì)受到影響。2.4.3不規(guī)則三角網(wǎng)模型由于不規(guī)則三角剖分的不同分辨率可以很好地解決緩沖區(qū)溢出的問(wèn)題，當(dāng)三角剖分的分辨率固定不變時(shí)，可以用較小的室內(nèi)空間來(lái)描述地形復(fù)雜的區(qū)域，所以不規(guī)則三角網(wǎng)一般用于離散變量點(diǎn)的網(wǎng)格管理。1978年，Peuker等學(xué)者針對(duì)地形的表示，設(shè)計(jì)了不規(guī)則三角網(wǎng)模型進(jìn)行相關(guān)信息表示，這種方法是利用不同的離散點(diǎn)進(jìn)行生成，得到的三角面互不重疊，如圖。使用這種方法得到的三角網(wǎng)其形狀則需要離散點(diǎn)的情況來(lái)決定。在平坦地區(qū)則需要大量的地形點(diǎn)才能勾畫(huà)出相應(yīng)的三角網(wǎng)[16]，這樣就產(chǎn)生較多數(shù)量的三角形；同理，如果針對(duì)地形比較復(fù)雜的地方，則需較少的離散點(diǎn)，這樣產(chǎn)生的三角形數(shù)量勢(shì)必較少。如此，TIN就可以充分的描述地形信息，尤其是較為復(fù)雜的地形和地貌。圖2-4不規(guī)則三角網(wǎng)在實(shí)際創(chuàng)建TIN的時(shí)候，通常使用無(wú)約束和約束的數(shù)據(jù)予來(lái)進(jìn)行創(chuàng)建。無(wú)約束數(shù)據(jù)域是指三角網(wǎng)數(shù)據(jù)域中的數(shù)據(jù)之間不相關(guān)，沒(méi)有聯(lián)系，均為離散分布。約束數(shù)據(jù)域則是指所取得的數(shù)據(jù)中一部分的某種類型之間具有約束關(guān)聯(lián)和某種制約，通常指的是道路、峽線等特征來(lái)表示。另外需要有內(nèi)部約束和外部約束。邊界約束基本上可以包含所有的數(shù)據(jù)[16]；當(dāng)然，如果數(shù)據(jù)的一部分具有約束關(guān)系，則屬于內(nèi)部約束[9]。如果三角網(wǎng)由不受約束的數(shù)據(jù)域組成，則稱為不受約束的三角網(wǎng)。如果三角網(wǎng)由受約束的數(shù)據(jù)域組成，則稱為約束三角網(wǎng)。約束三角網(wǎng)的一大特點(diǎn)是能夠保持原始數(shù)據(jù)中的約束條件，能夠很好地反映地形幾何和結(jié)構(gòu)的特點(diǎn)，它是一種在實(shí)踐中經(jīng)常使用的建模方法。由于不規(guī)則三角網(wǎng)中的三角形是可變的，所以設(shè)計(jì)起來(lái)需要考慮節(jié)點(diǎn)和端點(diǎn)的各種坐標(biāo)，還需要考慮連接和幾何拓?fù)鋯?wèn)題，比較負(fù)責(zé)。在使用TIN時(shí)，需要進(jìn)行點(diǎn)線面[16]算法設(shè)計(jì)及模型的形成。為了更全面、準(zhǔn)確地識(shí)別每個(gè)數(shù)據(jù)信息點(diǎn)的信息內(nèi)容，必須對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化和存儲(chǔ)。其存儲(chǔ)方法的關(guān)鍵是：（1）三角形的存儲(chǔ)順序，一般要包括三角形的幾個(gè)重要參數(shù)，如節(jié)點(diǎn)、邊、三角形等，還有三個(gè)頂點(diǎn)坐標(biāo)的相關(guān)參數(shù)以及相鄰三個(gè)三角形的相關(guān)參數(shù)；（2）端點(diǎn)和相鄰點(diǎn)的存儲(chǔ)，包括每個(gè)節(jié)點(diǎn)的三個(gè)平面坐標(biāo)、點(diǎn)的序號(hào)和相關(guān)及相鄰點(diǎn)的參數(shù)存儲(chǔ)問(wèn)題。在應(yīng)用這種方法時(shí)，一般要求不規(guī)則三角網(wǎng)中的各個(gè)三角形之間：（1）不規(guī)則三角網(wǎng)是唯一存在的；（2）盡量讓三角形的幾何形狀看起來(lái)更符合實(shí)際且具有基本的數(shù)學(xué)特征，最好是每個(gè)三角形三邊相等，使其盡可能接近等邊三角形；（3）確保形成的三角形的直徑最小。TIN模型可以減少數(shù)據(jù)冗余，并且比等高線模型具有更高的測(cè)量效率。它可以根據(jù)地形地貌的變化來(lái)改變離散變量點(diǎn)的位置和分布，另外，它可以準(zhǔn)確地描述復(fù)雜的地形特征，同時(shí)，具有如下優(yōu)點(diǎn)和表達(dá)優(yōu)勢(shì)：（1）隨著地形的變化，三角網(wǎng)的外觀可以實(shí)時(shí)更新和變化，也就是說(shuō)，三角形端點(diǎn)在存儲(chǔ)時(shí)，進(jìn)行了充分的考慮，包括了點(diǎn)的所有數(shù)據(jù)信息；（2）通過(guò)三角形的邊可以方便判斷和識(shí)別斷裂線相關(guān)信息內(nèi)容，并可加入到三角網(wǎng)信息中去，以便更為準(zhǔn)確表示地形特征；（3）有不規(guī)則三角網(wǎng)，等高線是由規(guī)則格網(wǎng)生成的，所以布線時(shí)可能會(huì)出現(xiàn)鞍點(diǎn)問(wèn)題，這個(gè)問(wèn)題需要進(jìn)行特殊的考慮和處理；（4）基于三角面的地形參數(shù)不但測(cè)量簡(jiǎn)單，而且表示直觀，便于使用，更重要的是它能更準(zhǔn)確地表征地形結(jié)構(gòu)類型和內(nèi)部關(guān)鍵點(diǎn)的相關(guān)信息，為算法設(shè)計(jì)及模型建立提供了可靠的支撐。2.5數(shù)字高程模型的應(yīng)用數(shù)字高程模型是對(duì)地形表面的數(shù)字化表達(dá)，具有非常好的應(yīng)用前景和市場(chǎng)，具體應(yīng)用在以上幾個(gè)方面。（1）科學(xué)研究方面針對(duì)地表形態(tài)的科學(xué)研究，其關(guān)鍵信息特征和基礎(chǔ)資料主要來(lái)自于地形表面的描述、特征提取和分析。在實(shí)際科學(xué)研究中，數(shù)字高程模型可以用于氣候問(wèn)題、水源、自然動(dòng)植物傳播、地質(zhì)環(huán)境和水文水利模型的創(chuàng)建、大數(shù)據(jù)技術(shù)、地形地貌分析、土地資源利用和土地資源覆蓋變化檢測(cè)行業(yè)。（2）工業(yè)設(shè)計(jì)方面數(shù)字高程模型可以充分的適用于工業(yè)方面，并且獲得了很多的應(yīng)用，創(chuàng)造了很高的經(jīng)濟(jì)效益。最早使用數(shù)字高程模型的行業(yè)是建筑行業(yè)。1957年，羅伯特提出基于數(shù)字高程數(shù)據(jù)信息設(shè)計(jì)公路、開(kāi)挖填方路基計(jì)算、路線勘察設(shè)計(jì)方案和水利工程項(xiàng)目。此外，數(shù)字高程模型可以快速生成等高線地形、工作區(qū)總體規(guī)劃、壩線選擇和壩軸線谷地?cái)嗝鎴D的制作。（3）商業(yè)方面在商業(yè)方面，數(shù)字高程模型應(yīng)用一般是以用戶為核心，其經(jīng)濟(jì)效益主要取決于相應(yīng)產(chǎn)品和副產(chǎn)品的生產(chǎn)和銷售：1）直接提供相關(guān)高程信息。2)提供相應(yīng)的定制產(chǎn)品和專業(yè)限制的數(shù)字高程產(chǎn)品10]。（4）其它方面另外，它還可以用于自然資源水平垂直分布特征，以完成防波堤的最佳設(shè)計(jì)，通過(guò)計(jì)算和模擬以確定可能的洪水淹沒(méi)區(qū)；分析山區(qū)日照狀況及其數(shù)據(jù)信息的三維可視化?？梢詰?yīng)用于航空[16]、自然環(huán)境、應(yīng)用地形匹配指導(dǎo)技術(shù)，以實(shí)現(xiàn)巡航導(dǎo)彈的導(dǎo)航、陸基雷達(dá)的選址?；鹋谒较嗷ツ芤?jiàn)度的探測(cè)和統(tǒng)籌。3無(wú)約束離散點(diǎn)的Delaunay三角網(wǎng)建立不規(guī)則三角網(wǎng)可以很好的描述地形和高程信息，并且可以避免緩沖區(qū)溢出，因此成為一種關(guān)鍵的建模方法。作為一種標(biāo)準(zhǔn)的三角剖分算法，Delaunay三角剖分算法可以盡可能地避開(kāi)細(xì)長(zhǎng)的三角形。此外，它可以保證構(gòu)建的三角網(wǎng)的唯一性，促使許多專家學(xué)者將重點(diǎn)放在將Delaunay三角網(wǎng)算法轉(zhuǎn)化為Delaunay三角網(wǎng)算法的科學(xué)研究。3.1Delaunay三角網(wǎng)3.1.1Voronoi圖Voronoi圖，又叫做泰森多邊形，由連續(xù)的多邊形組成，這些多邊形之間相鄰點(diǎn)之間由其垂直平分線連接而成[18]。1908年，俄國(guó)學(xué)者G.Voronoi從數(shù)學(xué)上定義了每個(gè)觀點(diǎn)所能代表的空間范圍，并用Voronoi圖在二維平面上表示了它的幾何意義：假設(shè)P={p1，p2，...，pn.}(n≥3)是平面上的一個(gè)離散點(diǎn)集，其中任意兩點(diǎn)都不共位，而且任意四點(diǎn)不共圓d（p，q）=（則任意點(diǎn)pi的Voronoi圖定義為Vp（如圖3-1所示）：Vp={pd泰勒多邊形為點(diǎn)線面之間進(jìn)行生成，所以需要嚴(yán)格遵循[18]：多邊形內(nèi)通常都有一個(gè)生成元；多邊形內(nèi)的點(diǎn)到生成元的距離最短；邊界上的點(diǎn)到各此邊界點(diǎn)之間的距離相同；泰勒多邊形的特性為空間分析和模型提供了一個(gè)很好的方法，生成泰勒多邊形主要使用矢量法和柵格法[16]。相鄰Voronoi多邊形是指具有公共邊的Voronoi多邊形，而Delaunay三角網(wǎng)是全部的Voronoi多邊形的生長(zhǎng)中心相互連接形成的三角網(wǎng)，它是由互不相同且相互不疊加、相互毗鄰的三角形拼合而成，和Voronoi圖是相互對(duì)偶的[16]。在形成的Delaunay三角網(wǎng)中，所有三角形的外接圓都不含有點(diǎn)集中的其他點(diǎn)，圖3-2表示Delaunay三角網(wǎng)和Voronoi圖的相互關(guān)系，關(guān)系圖中實(shí)線表示Voronoi圖，虛線表示Delaunay三角網(wǎng)。圖3-2Delaunay三角網(wǎng)和Voronoi圖3.1.2Delaunay三角網(wǎng)性質(zhì)Delaunay三角剖分具有非常關(guān)鍵的特性，即唯一性、空外接圓特性、最大最小內(nèi)角性以及局部性等[16]，如下：（1）唯一性隨機(jī)點(diǎn)集的Delaunay三角剖分是唯一存在的，即對(duì)于隨機(jī)點(diǎn)集，無(wú)論以哪一點(diǎn)作為起點(diǎn)和終點(diǎn)，最后的Delaunay三角剖分都是唯一存在的，如圖3-3所示。圖3-3三角剖分圖（2）空外接圓性Delaunay三角網(wǎng)中每個(gè)三角形的外接圓不包括點(diǎn)集中的所有其他點(diǎn)，這是Delaunay三角網(wǎng)的創(chuàng)建的基本原理，如圖3-4所示。圖3-4空外接圓（3）最大最小內(nèi)角性對(duì)于不規(guī)則三角網(wǎng)，根據(jù)兩個(gè)相鄰的三角形形成的凸四邊形，最小內(nèi)部這兩個(gè)相鄰三角形的角度必須大于替換直線后的角度。局部最優(yōu)法在背景下于1977年由Lawson提出，Lawson提出的局部最優(yōu)法的根據(jù)是通過(guò)替換凸四邊形的對(duì)角線，進(jìn)而得到三角網(wǎng)。如圖所示。圖3-5LOP優(yōu)化（4）局部性在生成三角網(wǎng)的過(guò)程中，若對(duì)點(diǎn)進(jìn)行插入或刪除等操作，Delaunay三角剖分也隨之發(fā)生區(qū)域性的變化，即點(diǎn)的插入或刪除等操作只會(huì)對(duì)部分區(qū)域有損害[16]。3.2經(jīng)典Delaunay三角網(wǎng)生成算法現(xiàn)今，以生成Delaunay三角網(wǎng)的過(guò)程不同為依據(jù)，生成三角網(wǎng)的算法主要包括有三角網(wǎng)生長(zhǎng)法、分治法及其逐點(diǎn)插入法等。而分治法和逐點(diǎn)插入法以及兩種融合算法為當(dāng)前普遍使用的算法[16]。3.2.1三角網(wǎng)生長(zhǎng)法三角網(wǎng)成長(zhǎng)法主要是先進(jìn)行隨機(jī)選取一個(gè)初始點(diǎn)，之后找到最近點(diǎn)，連接作為初始基準(zhǔn)線[16]，從該直線找到最近的點(diǎn)從而獲得一個(gè)初始三角形，之后利用三條邊再按照之前的方法找取最近點(diǎn)構(gòu)成三角形，之后再進(jìn)行不停重復(fù)，直到解析完所有的離散點(diǎn)。三角網(wǎng)生長(zhǎng)法比較簡(jiǎn)單，網(wǎng)絡(luò)建設(shè)的高效率較弱，現(xiàn)在已經(jīng)很少使用了。如今改進(jìn)的三角網(wǎng)生長(zhǎng)方法都在尋找第三點(diǎn)。圖3-6三角網(wǎng)生長(zhǎng)算法步驟3.2.2分治算法分治算法是不斷的對(duì)數(shù)據(jù)進(jìn)行對(duì)等分割，最終獲得的子三角網(wǎng)中點(diǎn)數(shù)不大于4之后進(jìn)行合并獲得三角網(wǎng)的一種算法。該算法采用遞歸來(lái)實(shí)現(xiàn)，其概念相對(duì)簡(jiǎn)單，運(yùn)算速度快，所使用的時(shí)間基本上與離散點(diǎn)的數(shù)量成正比。但是在數(shù)據(jù)大時(shí)需要計(jì)算機(jī)有足夠的內(nèi)存。[19]。圖3-7分割合并算法圖解3.2.3逐點(diǎn)插入法Lawson在1977年提出建立一個(gè)大的邊界多邊形或者三角形來(lái)容納所有數(shù)據(jù)，之后進(jìn)行逐點(diǎn)插入，利用局部?jī)?yōu)化進(jìn)行獲得三角網(wǎng)，這種算法叫做逐點(diǎn)插入法。這種算法對(duì)空間沒(méi)有要求，容易實(shí)現(xiàn)，但是時(shí)間效率比較低。[20]。其步驟如下：建立一個(gè)大的多邊形，可以將所有的點(diǎn)包含在內(nèi)；從離散點(diǎn)中選取一點(diǎn)，進(jìn)行初始三角網(wǎng)的插入，并與三角形頂點(diǎn)相連，構(gòu)成三個(gè)新的小三角形[16]；（3）LOP優(yōu)化；（4）重復(fù)（2）、（3），直至插入完所有離散點(diǎn)。 圖3-8包含P的三角形和該三角形的初始三角剖分1．把包含P的三角形的三個(gè)鄰接三角形T1、T2、T31．把包含P的三角形的三個(gè)鄰接三角形T1、T2、T3放入堆棧中2．從堆棧中彈出三角形T33．檢查P點(diǎn)是否在T3外接圓中，如果在則交換對(duì)角線，反之彈出下一個(gè)三角形4．如果交換對(duì)角線，則把原來(lái)與T3相鄰的三角形T7、T8壓入堆棧5．重復(fù)2~4，直到堆棧為空，則P點(diǎn)的插入過(guò)程結(jié)束圖3-9逐點(diǎn)插入法圖解3.3建立TIN模型的方法比較上述三種建立TIN模型的方法及的比較見(jiàn)表3-1。表3-1建立TIN模型的方法及比較建模方法方法描述比較分治算法排序數(shù)據(jù)，分成兩個(gè)子集后分別建立三角網(wǎng)并合并。算法比較復(fù)雜并且對(duì)計(jì)算機(jī)的要求也比較高，較難實(shí)現(xiàn)。三角網(wǎng)生長(zhǎng)算法先進(jìn)行隨機(jī)選取一個(gè)初始點(diǎn)，之后找到最近點(diǎn)，連接作為初始基準(zhǔn)]，從該直線找到最近的點(diǎn)從而獲得一個(gè)初始三角形，之后利用三條邊再按照之前的方法找取最近點(diǎn)構(gòu)成三角形，之后再進(jìn)行不停重復(fù)，直到解析完所有的離散點(diǎn)。該算法的大部分時(shí)間花費(fèi)在搜索符合要求的給定基線的鄰域點(diǎn)的過(guò)程中，效率低，但通過(guò)建立網(wǎng)格索引能解決這一問(wèn)題。逐點(diǎn)插入算法建立一個(gè)大的邊界多邊形或者三角形來(lái)容納所有數(shù)據(jù)，之后進(jìn)行逐點(diǎn)插入，利用局部?jī)?yōu)化進(jìn)行獲得三角網(wǎng)該算法實(shí)現(xiàn)較簡(jiǎn)單，占用內(nèi)存較小，但它的時(shí)間復(fù)雜度差，效率較低，所以大多數(shù)學(xué)者會(huì)研究如何改進(jìn)算法的效率。4不規(guī)則三角網(wǎng)的構(gòu)建TIN是矢量結(jié)構(gòu)又有柵格的空間鋪蓋特征，能很好地描述和維護(hù)空間關(guān)系。T即三角化，是離散數(shù)據(jù)的三角剖分過(guò)程，也是建立TIN的過(guò)程，可以利用三角形的平面方程唯一確定其中的任一點(diǎn)高程。I為不規(guī)則性，指的是在構(gòu)建不規(guī)則三角網(wǎng)中采樣點(diǎn)的分布形式不規(guī)則。TIN具有可變分辨率，比格網(wǎng)DEM能更好地反映地形起伏。N即網(wǎng)，表示不可以交叉和重疊的三角形分布態(tài)勢(shì)[21]。用來(lái)描述TIN的基本元素為點(diǎn)、線、和面和拓?fù)潢P(guān)系。本文使用三角網(wǎng)生長(zhǎng)算法來(lái)建立TIN。這種算法可以根據(jù)生長(zhǎng)過(guò)程的不同分為收縮生長(zhǎng)算法和擴(kuò)張生長(zhǎng)算法。前者是先進(jìn)行邊界確定再進(jìn)行收縮獲得三角網(wǎng)，而后者則是通過(guò)小三角形向外擴(kuò)招以致覆蓋全區(qū)域。4.1無(wú)約束三角網(wǎng)的構(gòu)建在三角網(wǎng)生長(zhǎng)算法過(guò)程中要注意以下兩點(diǎn)：一是建立一初始基線，并利用其將數(shù)據(jù)域劃分為兩部分，二是在初始基線所構(gòu)成的三角形的另一頂點(diǎn)的異側(cè)，應(yīng)用Delaunay法則搜索第三點(diǎn)（圖4-1）。例如，初始三角形ABC的初始基線為AB，其第三個(gè)頂點(diǎn)為C。在點(diǎn)C相較初始基線AB的另一側(cè)尋一復(fù)合Delaunay法則的點(diǎn)D，形成三角形ABD。可通過(guò)以下方法對(duì)其進(jìn)行判斷：設(shè)直線兩端點(diǎn)的坐標(biāo)為A，B，另兩點(diǎn)分別為C，D，可通過(guò)下式判斷點(diǎn)C、D在AB的同異側(cè)關(guān)系：(4-1)在式4-1中代入C、D坐標(biāo)，則有：若F與F符號(hào)相異，則C、D分別位于AB的兩側(cè)；若F=0或F=0，則C或D與AB共線。圖4-1在三角形另一側(cè)搜尋第三點(diǎn)為避免三角形的交叉與重復(fù)，在經(jīng)過(guò)上面所敘述的判斷方法進(jìn)行異側(cè)點(diǎn)判斷的同時(shí)，還需要進(jìn)一步的判定。在一個(gè)三角網(wǎng)中最多兩個(gè)三角形擁有一個(gè)公共邊，所以在進(jìn)行擴(kuò)展時(shí)需要進(jìn)行確認(rèn)是否該邊還需擴(kuò)展即[22]。在設(shè)計(jì)中，為每條邊設(shè)置了左右三角形，通過(guò)判斷其左右三角形值來(lái)確定該邊是否還能構(gòu)成新三角形。4.2約束三角網(wǎng)的構(gòu)建有不相交的地形特征線或是特殊的邊界線等被選作預(yù)先定義的限制條件作用生成TIN，則要考慮帶約束條件的Delaunay三角網(wǎng)（CDT）。最簡(jiǎn)單的處理方式是于1990年由Boissonnat提出的“加密算法”，這種算法是對(duì)約束線段山的點(diǎn)進(jìn)行加密，從而將其變?yōu)槠胀〝?shù)據(jù)，之后再按相應(yīng)的方式進(jìn)行剖分。這種方法比較簡(jiǎn)單，但是在一定程度上改變了原始數(shù)據(jù)并加大了數(shù)據(jù)量[23]。至今為止結(jié)構(gòu)約束的Delaunay三角剖分算法大概可以分為5類（表4-1所示）。

表4-1約束Delaunay三角剖分算法算法名稱提出年份/年主要人物算法簡(jiǎn)介約束圖法1986Lee和Lin先計(jì)算出約束數(shù)據(jù)的可見(jiàn)性圖，之后在基礎(chǔ)上進(jìn)行優(yōu)化形成CDT。分割合并算法1981Lee和Schachte它的優(yōu)點(diǎn)是執(zhí)行效率高，缺點(diǎn)是分割過(guò)程中由于有約束線段而增加了執(zhí)行困難。加密算法1990Boissonnat首先把約束數(shù)據(jù)變?yōu)榉羌s束數(shù)據(jù)。第二步是將加密后的點(diǎn)進(jìn)行剖分。它雖然思路清晰，但是增加了計(jì)算量。Shell三角化算法1993Piegl和Richard該算法的實(shí)質(zhì)則是三角網(wǎng)生長(zhǎng)算法在非約束數(shù)據(jù)域的推廣。兩步法目前Bernal、Sloan和Floriani根據(jù)數(shù)據(jù)建立非約束三角網(wǎng)，然后第二步則是想辦法把約束關(guān)系或者約束線段嵌套進(jìn)去。4.2.1帶約束條件的三角網(wǎng)法則CDT能夠滿足Delaunay法則，但是如同等角特性這樣的局部特性也會(huì)發(fā)生變化。所以當(dāng)需要考慮約束條件時(shí)，我們需要重新定義Delaunay法則和Lawson

LOP交換法。任意兩互相可視的點(diǎn)連接而成的則是可視圖，可視圖中除在斷裂線的斷點(diǎn)處以外的連接線，其他連接線與任何斷裂線都不會(huì)相交（圖4-2）。由此，兩種法則的新定義如下：約束Delaunay法則：三角形外接圓內(nèi)沒(méi)有任何其他點(diǎn)且三角形的三個(gè)頂點(diǎn)能夠互相通視，這樣的三角形就是約束Delaunay三角形。約束Delaunay

Lawson

LOP交換：在滿足帶約束條件的Delaunay法則的情況下，選取相鄰兩個(gè)三角形構(gòu)成的凸四邊形中的最佳對(duì)角線23]。圖4-29個(gè)點(diǎn)與兩條約束線段的通視圖4.2.2顧及約束線段的三角網(wǎng)生成算法線段約束不但可以生成Delaunay三角形，還可以做靜態(tài)三角網(wǎng)的生長(zhǎng)算法[23]。一般采用基于動(dòng)態(tài)的方法生成三角網(wǎng)，CDT的建立分為以下兩步：（1）包括約束線段上所有數(shù)據(jù)信息點(diǎn)，建立CDT；（2）按照約束線段，通過(guò)對(duì)角線交換法LOP調(diào)整每條線段影響到的所有三角形。如果存在一些地形特征信息可以作為約束條件，在構(gòu)建Delanuay三角網(wǎng)時(shí)，通過(guò)預(yù)先的約束線段，構(gòu)建出有約束標(biāo)準(zhǔn)的Delanuay三角網(wǎng)。如圖4-3所示，加入約束條件的步驟如下：1）將約束線段插入三角網(wǎng)中；2）找出與約束線段有相交部分的三角形，這兩個(gè)三角形有公共邊則刪除這，最后能夠形成一個(gè)受約束條件影響的多變形；3）將約束線段的起始結(jié)點(diǎn)與影響多邊形的其他頂點(diǎn)相連；4）通過(guò)約束Delaunay優(yōu)化法則更新多邊形內(nèi)的三角網(wǎng)，讓約束邊成為三角形的一條邊；5）重復(fù)上面步驟，直到約束線段都加入到三角網(wǎng)中[23]。（a）插入線段ab，搜索其影響多邊形（b）連接節(jié)點(diǎn)a與影響多邊形的所有頂點(diǎn)（c）對(duì)三角形進(jìn)行優(yōu)化（d）帶約束線段ab的三角形圖4-3約束線段ab插入到已有Delaunay三角網(wǎng)的過(guò)程4.3構(gòu)網(wǎng)算法的優(yōu)化4.3.1建立網(wǎng)格索引網(wǎng)格索引是根據(jù)離散數(shù)據(jù)信息的點(diǎn)集，邊和三角形根據(jù)構(gòu)網(wǎng)時(shí)即時(shí)轉(zhuǎn)換成網(wǎng)絡(luò)而建立的。它是一種基于塊的網(wǎng)格數(shù)據(jù)庫(kù)索引方法，這種方法不需要塊的組合，從而可以優(yōu)化算法，減少時(shí)間，進(jìn)一步提高了建網(wǎng)率。優(yōu)化算法在初始三角網(wǎng)的構(gòu)建時(shí)就進(jìn)行分開(kāi)從而減少尋找點(diǎn)的時(shí)間，從而縮小檢索目標(biāo)點(diǎn)的范圍，提高網(wǎng)絡(luò)建設(shè)效率。首先，遍歷所有點(diǎn)集，并從中得知點(diǎn)集數(shù)目和x、y坐標(biāo)的閾值。之后按照塊的平均進(jìn)行選取閾值，最好為20-100以內(nèi)，根據(jù)公式（4-2），可以獲得相應(yīng)的數(shù)目，從而放入對(duì)應(yīng)塊的離散點(diǎn)，用二維數(shù)組對(duì)所有點(diǎn)塊集進(jìn)行管理[24]。(4-2)其中total_v代表數(shù)據(jù)域的點(diǎn)總數(shù)，average_v為域值，row，col，row_width，col_width分別為數(shù)據(jù)域的行列個(gè)數(shù)及行列寬。構(gòu)建初始三角形時(shí)，將實(shí)時(shí)生成的邊和三角形與點(diǎn)集一樣，即分塊管理。以邊的中心為標(biāo)準(zhǔn)，將邊的相關(guān)信息存儲(chǔ)為二維數(shù)組。三角形則按照重心點(diǎn)，將三角形存儲(chǔ)在三角形塊的二維數(shù)組中，包括三角形序號(hào)及三角形數(shù)，完成后應(yīng)與點(diǎn)集塊數(shù)相同從而建立數(shù)據(jù)庫(kù)索引。當(dāng)使用最大角度法進(jìn)行網(wǎng)絡(luò)建立時(shí)，在搜索過(guò)程中進(jìn)行設(shè)置所在塊與基線右點(diǎn)進(jìn)行集中進(jìn)行尋找第三個(gè)點(diǎn)。如果無(wú)法找到，則進(jìn)行水平和垂直方向上的檢索，直到找到。這比在所有點(diǎn)中找到滿足條件的第三個(gè)點(diǎn)要快得多，數(shù)據(jù)量越多，其速度越顯著[24]。具體實(shí)現(xiàn)如圖（4-4）和圖（4-5）所示：xmax,ymax·1·8·14·12·7·6·2·10·16·3·11·13·5·4·15·9X(N) xmin,ymin Y圖4-4原始數(shù)據(jù)的格網(wǎng)劃分圖4-5原始采樣點(diǎn)掃描后建立的數(shù)據(jù)鏈表4.4不規(guī)則三角網(wǎng)構(gòu)建成果數(shù)據(jù)結(jié)構(gòu)很大程度上決定了算法的執(zhí)行效率，所以為了更好的進(jìn)行數(shù)據(jù)的開(kāi)發(fā)和信息的管理，需要設(shè)計(jì)一個(gè)好的數(shù)據(jù)結(jié)構(gòu)方式。4.4.1三角網(wǎng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1）點(diǎn)數(shù)據(jù)結(jié)構(gòu)：structPoint { doublex;//X坐標(biāo)doubley;//Y坐標(biāo)doublez;//Z坐標(biāo)WCHARPN[30];//點(diǎn)號(hào) }2）邊數(shù)據(jù)結(jié)構(gòu)： structLine { intstart,end;//起點(diǎn)和終點(diǎn) inttimes;//邊使用次數(shù) } 3）三角形數(shù)據(jù)結(jié)構(gòu)： structTri { intp1,p2,p3;//三角形的頂點(diǎn)點(diǎn)號(hào) intno;//三角形編號(hào) }4.4.2程序流程通過(guò)對(duì)三角網(wǎng)生長(zhǎng)算法中各的具體步驟的分析和對(duì)比，總結(jié)出具體的程序?qū)崿F(xiàn)的步驟：（1）讀取坐標(biāo)文件；（2）采用快速排序法，根據(jù)x坐標(biāo)排序(當(dāng)x值相同時(shí)，則按y值從小到大排序）從小到大排序，刪除重復(fù)的數(shù)據(jù)點(diǎn)，完成遍歷，記錄4個(gè)子集max_x、min_x、max_y和min_y；（3）從一個(gè)點(diǎn)開(kāi)始，搜索與起始點(diǎn)距離最近的點(diǎn)；（4）根據(jù)前兩點(diǎn)，根據(jù)角度最大原則找到第三個(gè)點(diǎn)，將點(diǎn)、線和三角形添加到相應(yīng)的數(shù)據(jù)表結(jié)構(gòu)中；（5）根據(jù)生成好的第一個(gè)三角形，向外擴(kuò)展，通過(guò)每條邊最多能用兩次來(lái)解決三角形重復(fù)和交叉的問(wèn)題，搜索第三點(diǎn)，合格的加入到三角形表中；（6）重復(fù)第五步，知道所有的離散點(diǎn)都加入到三角形表中；（7）在CAD中建立圖形數(shù)據(jù)庫(kù)，添加符號(hào)表和實(shí)體，實(shí)現(xiàn)三角網(wǎng)的顯示。圖4-6程序流程圖4.4.3生成三角網(wǎng)的成果圖4-7無(wú)約束三角網(wǎng)成果圖4-8加入地性線圖4-9約束三角網(wǎng)成果圖4-10三角網(wǎng)渲染成果圖

5總結(jié)與展望5.1總結(jié)隨著數(shù)字高程模型的發(fā)展趨勢(shì)，其關(guān)鍵技術(shù)便是不規(guī)則三角網(wǎng)，將科學(xué)研究的Delaunay三角網(wǎng)生成算法具有重要的使用價(jià)值。作為一種標(biāo)準(zhǔn)的三角剖分算法，Delaunay三角剖分簡(jiǎn)單來(lái)說(shuō)就是盡可能的避免細(xì)長(zhǎng)三角形的產(chǎn)生，同時(shí)也可以保證三角剖分的唯一性。隨著Delaunay三角網(wǎng)逐漸應(yīng)用于各個(gè)領(lǐng)域，對(duì)網(wǎng)絡(luò)建設(shè)的高效率和盈余管理的要求不斷提高，因此有必要深入分析算法轉(zhuǎn)化為Delaunay三角剖分，以及如何改進(jìn)Delaunay三角形的構(gòu)造。網(wǎng)絡(luò)的高效率及其降低的復(fù)雜性已成為當(dāng)今科研網(wǎng)絡(luò)的一個(gè)熱點(diǎn)。通過(guò)不規(guī)則三角網(wǎng)的建立與研究，主要完成的工作有：（1）總結(jié)了不規(guī)則三角網(wǎng)的研究現(xiàn)狀，通過(guò)敘述不規(guī)則三角網(wǎng)的建立的理論基礎(chǔ)以及方法，實(shí)現(xiàn)利用三角網(wǎng)生長(zhǎng)算法建立TIN。（2）基于AutoCAD2008的應(yīng)用模塊，生成并繪制不規(guī)則三角網(wǎng)TIN。5.2展望本次畢業(yè)設(shè)計(jì)主要對(duì)平面域Delaunay三角網(wǎng)的生成算法進(jìn)行了些許研究，但是還相對(duì)簡(jiǎn)單