數(shù)字地面模型中不規(guī)則三角網(wǎng)的構(gòu)建案例分析目錄TOC\o"1-3"\h\u12933數(shù)字地面模型中不規(guī)則三角網(wǎng)的構(gòu)建案例分析 1169591.1無約束三角網(wǎng)的構(gòu)建 133001.2約束三角網(wǎng)的構(gòu)建 286201.2.1帶約束條件的三角網(wǎng)法則 378371.2.2顧及約束線段的三角網(wǎng)生成算法 4270381.3構(gòu)網(wǎng)算法的優(yōu)化 5102531.3.1建立網(wǎng)格索引 580891.4不規(guī)則三角網(wǎng)構(gòu)建成果 7114841.4.1三角網(wǎng)數(shù)據(jù)結(jié)構(gòu)設計 7174231.4.2程序流程 8126601.4.3生成三角網(wǎng)的成果 10TIN是矢量結(jié)構(gòu)又有柵格的空間鋪蓋特征，能很好地描述和維護空間關(guān)系。T即三角化，是離散數(shù)據(jù)的三角剖分過程，也是建立TIN的過程，可以利用三角形的平面方程唯一確定其中的任一點高程。I為不規(guī)則性，指的是在構(gòu)建不規(guī)則三角網(wǎng)中采樣點的分布形式不規(guī)則。TIN具有可變分辨率，比格網(wǎng)DEM能更好地反映地形起伏。N即網(wǎng)，表示不可以交叉和重疊的三角形分布態(tài)勢[21]。用來描述TIN的基本元素為點、線、和面和拓撲關(guān)系。本文使用三角網(wǎng)生長算法來建立TIN。這種算法可以根據(jù)生長過程的不同分為收縮生長算法和擴張生長算法。前者是先進行邊界確定再進行收縮獲得三角網(wǎng)，而后者則是通過小三角形向外擴招以致覆蓋全區(qū)域。1.1無約束三角網(wǎng)的構(gòu)建在三角網(wǎng)生長算法過程中要注意以下兩點：一是建立一初始基線，并利用其將數(shù)據(jù)域劃分為兩部分，二是在初始基線所構(gòu)成的三角形的另一頂點的異側(cè)，應用Delaunay法則搜索第三點（圖4-1）。例如，初始三角形ABC的初始基線為AB，其第三個頂點為C。在點C相較初始基線AB的另一側(cè)尋一復合Delaunay法則的點D，形成三角形ABD。可通過以下方法對其進行判斷：設直線兩端點的坐標為A，B，另兩點分別為C，D，可通過下式判斷點C、D在AB的同異側(cè)關(guān)系：(4-1)在式4-1中代入C、D坐標，則有：若F與F符號相異，則C、D分別位于AB的兩側(cè)；若F=0或F=0，則C或D與AB共線。圖4-1在三角形另一側(cè)搜尋第三點為避免三角形的交叉與重復，在經(jīng)過上面所敘述的判斷方法進行異側(cè)點判斷的同時，還需要進一步的判定。在一個三角網(wǎng)中最多兩個三角形擁有一個公共邊，所以在進行擴展時需要進行確認是否該邊還需擴展即[22]。在設計中，為每條邊設置了左右三角形，通過判斷其左右三角形值來確定該邊是否還能構(gòu)成新三角形。1.2約束三角網(wǎng)的構(gòu)建有不相交的地形特征線或是特殊的邊界線等被選作預先定義的限制條件作用生成TIN，則要考慮帶約束條件的Delaunay三角網(wǎng)（CDT）。最簡單的處理方式是于1990年由Boissonnat提出的“加密算法”，這種算法是對約束線段山的點進行加密，從而將其變?yōu)槠胀〝?shù)據(jù)，之后再按相應的方式進行剖分。這種方法比較簡單，但是在一定程度上改變了原始數(shù)據(jù)并加大了數(shù)據(jù)量[23]。至今為止結(jié)構(gòu)約束的Delaunay三角剖分算法大概可以分為5類（表4-1所示）。

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

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

Lawson

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