1、基于約束Delaunay三角剖分進(jìn)行數(shù)模建摘要分析了各種三角網(wǎng)生成算法，選定逐點(diǎn)插入算法進(jìn)行三角構(gòu)網(wǎng)，并對(duì)該算法進(jìn)行了優(yōu)化處理。在數(shù)據(jù)點(diǎn)集不變的情況下，提出了交換對(duì)角線的算法以進(jìn)行數(shù)字地面模型的建構(gòu)，使得數(shù)模成果真實(shí)地反映了地面情況。關(guān)鍵詞數(shù)字地面模型Delaunay三角網(wǎng)約束邊嵌入算法1前言數(shù)字地面模型（Digital Terrain Modal，簡(jiǎn)稱(chēng)DTM）是地表勘測(cè)成果的數(shù)字化表現(xiàn)形式，它廣泛應(yīng)用于公路勘測(cè)設(shè)計(jì)一體化、地理信息系統(tǒng)等領(lǐng)域中。其主要實(shí)現(xiàn)形式是不規(guī)則三角網(wǎng)（Triangulation Irregular Net，簡(jiǎn)稱(chēng)TIN）。Delaunay三角網(wǎng)1具有空外接圓，以及最小角最

2、大的性質(zhì)，可最大限度的保證網(wǎng)中三角形滿足近似等邊（角）性，避免了過(guò)于狹長(zhǎng)和尖銳的三角形的出現(xiàn)，是公認(rèn)的最優(yōu)三角網(wǎng)。鑒于此，對(duì)二維域內(nèi)點(diǎn)集進(jìn)行Delaunay三角剖分是當(dāng)今流行的TIN構(gòu)網(wǎng)技術(shù)。本文主要介紹了用逐點(diǎn)插入算法來(lái)生成Delaunay三角網(wǎng)，并討論了如何在不改變點(diǎn)集的情況下實(shí)現(xiàn)約束邊的嵌入，這符合數(shù)據(jù)采集及數(shù)模生成的規(guī)則，可以方便地處理地表上的陡坎線、斷裂線等，真實(shí)地反映地表情況。2建立無(wú)約束三角網(wǎng)關(guān)于Delaunay三角網(wǎng)的生成算法，已經(jīng)有了二十多年的研究，現(xiàn)在已趨于成熟，其主流算法有三種：分割歸并法，逐點(diǎn)插入法，三角網(wǎng)生長(zhǎng)法。其中三角網(wǎng)生長(zhǎng)法已不常見(jiàn)，分割歸并法和逐點(diǎn)插入法各有優(yōu)缺

3、點(diǎn)，分治算法由于遞歸執(zhí)行，因而需要較大的內(nèi)存空間，消耗系統(tǒng)資源，但時(shí)間復(fù)雜度要好。逐點(diǎn)插入法實(shí)現(xiàn)簡(jiǎn)單，占用內(nèi)存較小，其時(shí)間復(fù)雜度差一些，但可以從數(shù)據(jù)的組織和管理上采用新方法，使之在時(shí)間和空間上達(dá)到最佳，并且逐點(diǎn)插入是一種動(dòng)態(tài)剖分方法，有利于以后對(duì)DTM的維護(hù)和更新，是一種較好的構(gòu)建DTM的剖分方法。綜合分析各算法，本文采用逐點(diǎn)插入法進(jìn)行構(gòu)網(wǎng)，分析了該算法中制約運(yùn)行速度的因素，在數(shù)三角網(wǎng)拓?fù)潢P(guān)系、三角形的查找、LOP算法（Local Optimization Procedure）等方面進(jìn)行了優(yōu)化處理，使之有了較高的執(zhí)行效率。2.1數(shù)據(jù)結(jié)構(gòu)在采用逐點(diǎn)插入進(jìn)行Delaunay三角剖分的過(guò)程中，存在大

4、量的查詢(xún)操作，利用數(shù)據(jù)結(jié)構(gòu)提供三角形之間的拓?fù)湫畔?，能夠有效地提高算法效率。邊結(jié)構(gòu)應(yīng)包含點(diǎn)與三角形的信息，三角形結(jié)構(gòu)應(yīng)包含點(diǎn)與邊的信息，再考慮到構(gòu)網(wǎng)過(guò)程中動(dòng)態(tài)的數(shù)據(jù)更新，算法中采用了雙向鏈表結(jié)構(gòu)，以方便于剖分過(guò)程中新舊邊（三角形）的添加、刪除工作。三角形拓?fù)潢P(guān)系如圖1。2.2算法原理逐點(diǎn)插入法是Lawson在1977年提出的，該算法思路簡(jiǎn)單，易于編程實(shí)現(xiàn)?；驹頌椋簩?duì)于已有的三角網(wǎng)絡(luò)，向其中插入一點(diǎn)，該點(diǎn)與包含它的三角形三個(gè)頂點(diǎn)相連，形成三個(gè)新的三角形，然后逐個(gè)對(duì)它們進(jìn)行空外接圓檢測(cè)，通過(guò)交換對(duì)角線的方法來(lái)保證所形成的三角網(wǎng)為Delaunay三角網(wǎng)。2.3算法基本步驟逐點(diǎn)插入算法主要執(zhí)行步驟

5、如圖2所示。在按圖4(a)進(jìn)行剖分時(shí)，添加了三條新邊及三個(gè)新三角形NT，刪除了舊三角形T。同樣，在圖4(b)的情況中，記錄點(diǎn)所在的邊E，根據(jù)拓?fù)潢P(guān)系，找出該邊的左右相鄰三角形T1，T2，添加四條新邊和四個(gè)新三角形NT，刪除T1，T2以及邊E。構(gòu)網(wǎng)的關(guān)鍵是對(duì)新剖分出的三角形用LOP算法進(jìn)行優(yōu)化，其基本過(guò)程為：新三角形與周?chē)娜切螛?gòu)成共用同一條對(duì)角線的四邊形，逐個(gè)對(duì)四邊形中的兩個(gè)三角形進(jìn)行空外接圓檢測(cè)，如果滿足空外接圓準(zhǔn)則，則略過(guò)。如果不滿足，則用另一對(duì)角線替換現(xiàn)有對(duì)角線，在交換對(duì)角線后，又會(huì)產(chǎn)生相應(yīng)的新四邊形，繼續(xù)進(jìn)行空外接圓檢測(cè)。這種方法可連續(xù)進(jìn)行,直到全部滿足空外接準(zhǔn)則為止。這個(gè)過(guò)程是隨著

6、數(shù)據(jù)點(diǎn)P的逐次插入，與三角剖分同時(shí)進(jìn)行的，可以通過(guò)遞歸調(diào)用優(yōu)化程序來(lái)實(shí)現(xiàn)。2.4算法分析通過(guò)以上的分析來(lái)看，逐點(diǎn)插入進(jìn)行Delaunay三角剖分算法的效率取決于尋找包含新加入點(diǎn)的三角形及LOP優(yōu)化過(guò)程，即構(gòu)網(wǎng)過(guò)程中的第(3)、(4)步。下面介紹一些優(yōu)化方法，以提高算法的速度?？焖俨樵?xún)包含新加入點(diǎn)的三角形是算法效率的關(guān)鍵，通常做法是遍歷各個(gè)三角形，利用點(diǎn)在多邊形中原理進(jìn)行判斷，則算法復(fù)雜度最壞為O(n2),n為點(diǎn)數(shù)。本文采取三角形面積法來(lái)判斷點(diǎn)與三角形的關(guān)系，同時(shí)結(jié)合三角形之間的拓?fù)潢P(guān)系，可方便的找到包含新點(diǎn)的三角形。該方法簡(jiǎn)單易行，其基本原理是通過(guò)多邊形面積公式來(lái)計(jì)算三角形面積，然后根據(jù)面積結(jié)

7、果判斷點(diǎn)是否在三角形內(nèi)。該面積結(jié)果有正有負(fù)，這與三角形三個(gè)頂點(diǎn)的排列順序有關(guān)。如圖5，約定三角形的頂點(diǎn)按照順時(shí)針?lè)较蚺帕?，已知P1，P2 ，P3的坐標(biāo)分別為(x1，y1)、(x2，y21)、(x3，y3)，分別計(jì)算數(shù)據(jù)點(diǎn)P與三角形三個(gè)頂點(diǎn)所形成的新三角形PP1P2 ，PP2P3，PP3P1的面積S1，S2，S3，此時(shí)點(diǎn)P在三角形T內(nèi)，三個(gè)面積同為負(fù)值：S10，S20，S30而P點(diǎn)在三角形T外。計(jì)算三角形PP1P2 ，PP2P3，PP3P1的面積S1，S2，S3,可知:S10，S20這說(shuō)明若點(diǎn)在三角形外，則至少有一個(gè)面積是大于零的。通過(guò)這種大于零的面積可以指明三角形的查找方向，如S30，則點(diǎn)P必

8、在對(duì)應(yīng)邊P3P1的另一側(cè)，然后根據(jù)拓?fù)潢P(guān)系，找到邊P3P1的相鄰三角形，繼續(xù)用三角形面積法判斷，直至它們同時(shí)小于零為止，這樣便找到了目標(biāo)三角形。以此方法編制點(diǎn)與三角形的關(guān)系函數(shù)PointinTriangle（P，T），找到目標(biāo)三角形，若與三角形某頂點(diǎn)重合，則記錄該點(diǎn)，函數(shù)返回0；點(diǎn)在三角形內(nèi)，記錄該三角形，函數(shù)返回1；點(diǎn)在三角形的某個(gè)邊上，記錄該邊，返回2。對(duì)三角形都進(jìn)行空外接圓檢測(cè)，常見(jiàn)做法是計(jì)算其中一個(gè)三角形的外接圓圓心及半徑，然后利用第四頂點(diǎn)到圓心的距離來(lái)判斷是否滿足空外接圓法則。這個(gè)過(guò)程要多次執(zhí)行開(kāi)方、平方等運(yùn)算，執(zhí)行效率較低，在程序中占用大量CPU時(shí)間。本文采用了簡(jiǎn)單直觀的方法來(lái)判斷

9、，如圖6，求出E兩側(cè)相對(duì)應(yīng)的兩對(duì)頂角P1、P4的弧度值：(1)P1P4，P4在圓周外，對(duì)角線不需交換。建立測(cè)試是否交換對(duì)角線的函數(shù)SwapTest（E）,若需交換則返回TRUE，不需交換返回FALSE。已知上述函數(shù)，交換對(duì)角線進(jìn)行LOP優(yōu)化。程序中采用了雙向鏈表結(jié)構(gòu)，且結(jié)構(gòu)中建立了良好的拓?fù)潢P(guān)系，在優(yōu)化過(guò)程中，可以方便地進(jìn)行三角形的動(dòng)態(tài)添加及刪除。3嵌入約束邊重新構(gòu)網(wǎng)按前所述，無(wú)約束的Delaunay三角剖分業(yè)已完成，現(xiàn)在進(jìn)行約束邊的嵌入。對(duì)于約束邊，其兩端點(diǎn)必定在剖分結(jié)果中?？紤]到已知離散數(shù)據(jù)點(diǎn)是確定的，不可改變的，在這樣不能添加附加點(diǎn)的情況下，只有通過(guò)交換對(duì)角線的方法來(lái)實(shí)現(xiàn)約束邊的嵌入。這

10、里規(guī)定幾個(gè)術(shù)語(yǔ)，待嵌入約束邊的一端點(diǎn)稱(chēng)為起始點(diǎn)，另一端點(diǎn)稱(chēng)為目標(biāo)點(diǎn)。待嵌入約束邊所經(jīng)過(guò)的三角形構(gòu)成的多邊形區(qū)域稱(chēng)為影響域2，如圖7。影響域內(nèi)與約束邊相交的邊稱(chēng)為影響域的對(duì)角線。我們的目標(biāo)即是從起始點(diǎn)出發(fā)，按照一定的規(guī)則逐步交換域內(nèi)對(duì)角線，最終使起始點(diǎn)與目標(biāo)點(diǎn)相連，即得到了所需的約束邊。3.1對(duì)角線交換算法基本思想程序中使用了四邊形對(duì)角線交換算法，其基本思想是：從約束線起點(diǎn)出發(fā)，在影響域內(nèi)，對(duì)所遇到的對(duì)角線進(jìn)行可交換性判斷，若可交換，則交換，不可交換就判斷下一條，達(dá)到最后一條對(duì)角線后，第一輪交換結(jié)束。然后從頭再來(lái)，開(kāi)始下一輪，直到將約束邊嵌入為止。如圖8。對(duì)角線交換之后，會(huì)產(chǎn)生新的對(duì)角線。對(duì)新對(duì)

11、角線的處理，是隨交換同時(shí)進(jìn)行的動(dòng)態(tài)添加過(guò)程。這在算法步驟中，有詳細(xì)的闡述。3.2對(duì)角線交換算法步驟已知Delaunay三角剖分完畢，構(gòu)網(wǎng)成果中包含三角形間的拓?fù)潢P(guān)系。約束邊起點(diǎn)OP，目標(biāo)點(diǎn)TP，約束邊標(biāo)記為CE，對(duì)角線交換步驟如圖9。根據(jù)以上過(guò)程編制約束構(gòu)網(wǎng)函數(shù)OnConstraintNet()。4程序的實(shí)現(xiàn)在實(shí)際工作中，用VC在微機(jī)上編程實(shí)現(xiàn)上述算法，三角構(gòu)網(wǎng)核心算法實(shí)現(xiàn)如下：void OnConstructTriNet()Trianglet0=headt;/三角形鏈表表頭Pointp0=headp;/點(diǎn)鏈表表頭while (p0)intn=PointinTriangle (p0,t0);i

12、f (n=0)/重點(diǎn)/提示“重點(diǎn)”，是否刪除，繼續(xù)下一點(diǎn)elseif(n=1) /點(diǎn)在三角形內(nèi)，需優(yōu)化/生成三條新邊、三個(gè)新三角形，刪除舊三角形，建立新的拓?fù)潢P(guān)系/記錄三個(gè)新四邊形的對(duì)角線e1，e2，e3OptimizeEdge(e1);OptimizeEdge(e2);OptimizeEdge(e3);/調(diào)用優(yōu)化函數(shù)else/點(diǎn)在邊上/生成四條新邊、四個(gè)新三角形，刪除舊邊、舊三角形，建立新的拓?fù)潢P(guān)系/記錄四個(gè)新四邊形的對(duì)角線e1，e2，e3，e4OptimizeEdge(e1);OptimizeEdge(e2);OptimizeEdge(e3); OptimizeEdge(e4);/調(diào)用優(yōu)化函數(shù)p0=p0next;/讀取下一點(diǎn)OnConstraintNet();/約束構(gòu)網(wǎng)/刪除不必要的三角形/刪除不必要的邊/數(shù)模成果保存5結(jié)論 本文討論了Delaunay三角網(wǎng)的生成算法，以及在Delaunay三角剖分中強(qiáng)行嵌入約束邊的多對(duì)角線交換算法，探討了一個(gè)從構(gòu)網(wǎng)到約束的DTM構(gòu)建全過(guò)程。在分析逐