點線矛盾檢查中出現(xiàn)平三角形的處理方法研究

葉燕萍，董小軍，葉駿

（1.浙江華東測繪有限公司，浙江杭州，310030；2.華東勘測設(shè)計研究院有限公司，浙江杭州，310014；3.浙江省隧道工程公司，浙江杭州，310013）

0 引言

點線矛盾也稱為“高曲矛盾”，指高程注記點與周圍等高線高程之間的相互矛盾［1］。造成點線矛盾的原因有多種，如人為因素、儀器穩(wěn)定性、地貌特殊性、影像質(zhì)量等［2］。點線矛盾的檢查方法主要有目視檢查法、鄰近等高線法、等高線構(gòu)TIN檢測法［1］。人工檢查是很費時費力的工作。因此，研究利用程序?qū)崿F(xiàn)自動檢查是非常有意義的。

等高線構(gòu)TIN檢測法檢查精度高、檢查結(jié)果可靠且運行速度快，是目前最常采用的方法。等高線構(gòu)TIN檢測法中，TIN的質(zhì)量是一個非常重要的影響因素。從等高線生成TIN的方法有三種［3］：（1）將等高線離散化直接生成TIN方法；（2）將等高線作為特征線的方法；（3）自動增加特征點及優(yōu)化TIN的方法。第一種方法不考慮等高線之間的約束關(guān)系，其模擬的地形會造成失真，使TIN中三角形的邊穿越等高線，并且形成平三角形。第二種方法可以避免三角形的邊穿越等高線的情況，但是也會形成平三角形。第三種方法通過增加特征點及優(yōu)化TIN，可以消除TIN中平三角形現(xiàn)象。以該種方法為理論依據(jù)進行實驗。

實驗數(shù)據(jù)為Geodatabase格式的1∶2000 DLG，采用ArcGIS Engine組件構(gòu)TIN。在研究其他學者對平三角形區(qū)域處理方法的基礎(chǔ)上，提出了根據(jù)平三角形區(qū)域存在的非平三角形個數(shù)討論平三角形區(qū)域的修復的算法，并用實驗驗證了等高線彎曲度比較大的地方及特殊地形（山頂或洼地、圖幅邊緣處、鞍部）平三角形區(qū)域處理方法的有效性。

1 TIN的建立

對數(shù)據(jù)進行過濾，僅留下等高線層，以等高線為約束邊，采用ArcGIS Engine組件技術(shù)構(gòu)TIN。利用各種約束條件構(gòu)建的不規(guī)則三角網(wǎng)，由點、邊、三角形構(gòu)成。而組成三角形的邊有三種類型：普通邊（Regular edge）、硬邊（Hard edge）、軟邊（Soft edge）。在構(gòu)建三角網(wǎng)時，地理要素的約束條件為“Hard”類型。

2 平三角形區(qū)域地性線樹的建立

2.1 產(chǎn)生平三角形的區(qū)域

平三角形是指三個頂點的高程值都相同的三角形。出現(xiàn)平三角形的原因是因為該區(qū)域缺少地形特征線信息，從地形地貌上來說，出現(xiàn)平三角形的區(qū)域也是地性線樹存在的區(qū)域［4］。

平三角形存在的區(qū)域主要有［5］：（1）等高線彎曲度較大的地方：在一條等高線彎曲度較大的地方，同一個三角形的三個頂點可能來自于同一條等高線，從而形成平三角形；（2）山頂或洼地：山頂或洼地的閉合等高線內(nèi)部，因為缺少相鄰等高線，而在構(gòu)TIN時不允許三角形穿越等高線，所以形成平三角形；（3）鞍部：有兩個或兩個以上的山頂或洼地形成鞍部區(qū)域，兩條等值等高線參與構(gòu)網(wǎng)，從而形成了平三角形；（4）圖幅邊緣處：靠近圖幅邊的單條等高線，由于缺少包含的等高線，無法實現(xiàn)相鄰等高線的構(gòu)網(wǎng)，從而形成平三角形。其中（1）有且僅有一個非平三角形；（3）有兩個或兩個以上的非平三角形；（2）、（4）沒有非平三角形。

2.2 平三角形區(qū)域的搜索

平三角形的坡度為0，因此，采用坡度為0的條件可以查找出平三角形區(qū)域［6］。同時還需要把與平三角形區(qū)域相鄰的非平三角形也搜索出來，加入平三角形區(qū)域。如圖3，多邊形ABCDEFGHIJ為平三角形區(qū)域，△PAJ為非平三角形，將它們合成一個整體考慮。點P稱為高低點（高低點只會出現(xiàn)在含有非平三角形的平三角形區(qū)域內(nèi)），平三角形區(qū)域的其他三角形頂點稱為平點。若該平三角形區(qū)域沒有非平三角形，則需要知道相鄰等高線的高程值以便地性線樹的建立。查找相鄰等高線高程值的方法為：搜索與平三角形區(qū)域相鄰的非平三角形，以該三角形非公共邊上的那個頂點高程作為平三角形區(qū)域相鄰等高線的高程值。

2.3 地性線樹的建立方法

見圖3，平三角形區(qū)域中當前三角形只有一個相鄰三角形的稱為一類三角形，如△PAJ；當前三角形有兩個相鄰三角形的稱為二類三角形，如△JAB；當前三角形有三個相鄰三角形的稱為三類三角形，如△JBG。一類三角形主要出現(xiàn)在地性線樹的端點，三類三角形出現(xiàn)在地性線的分支，其余的情況都是二類三角形。

圖1 各類三角形的中軸線連接Fig.1 Connection of axes of various types of triangles

對平三角形區(qū)域建立地性線樹時需考查每個平三角形與相鄰三角形的關(guān)系，從而建立各類三角形的中軸線連線。一類三角形連接的是唯一公共邊的中點與其相對的頂點，二類三角形連接的是兩條公共邊的中點，三類三角形連接的是三角形的重心和三條公共邊的中點，見圖1。地性線是相互連接在一起的樹狀分支結(jié)構(gòu)，可以用二叉樹來描述，見圖2，A作為根結(jié)點，G、I、K、F為葉子結(jié)點，地性線樹上的其他結(jié)點作為非葉子結(jié)點。

圖2 地性線樹的二叉樹結(jié)構(gòu)Fig.2 Binary tree structure of terrain structure line

地性線樹的數(shù)據(jù)結(jié)構(gòu)定義如下：

根據(jù)平三角形區(qū)域存在非平三角形的個數(shù)分三種情況討論地性線樹的建立，即（1）存在一個非平三角形，如等高線彎曲度較大處；（2）存在兩個或兩個以上的非平三角形，如鞍部；（3）沒有非平三角形，如山頂、洼地、圖幅邊緣處。

2.3.1 等高線彎曲度較大處平三角形區(qū)域地性線樹的提取

圖3 等高線彎曲度較大處地性線樹的提取Fig.3 Extraction of terrain structure line in the contour with large curvatures

等高線彎曲度較大處是平三角形可能存在的區(qū)域。該區(qū)域中存在一個非平三角形。以下是該區(qū)域平三角形處理的算法思想。

步驟1：先把高低點所在的非平三角形作為當前三角形，將高低點作為地性線樹的根結(jié)點，根結(jié)點作為當前結(jié)點；

步驟2：然后將高低點所對邊的中點作為左子結(jié)點，左子結(jié)點作為當前結(jié)點；

步驟3：根據(jù)當前結(jié)點所在的邊搜索位于該邊左邊的三角形，并將該三角形作為當前三角形，搜索當前三角形另外兩邊相鄰三角形的個數(shù)：

（1）若另外兩邊都有相鄰三角形，則追蹤當前三角形的重心，如果當前結(jié)點的左右子結(jié)點都為空，則將重心結(jié)點作為其左子結(jié)點；如果當前結(jié)點的左子結(jié)點不為空，則將重心結(jié)點作為其右子結(jié)點。然后把重心結(jié)點作為當前結(jié)點，取其中一條邊的中點作為當前結(jié)點的左子結(jié)點，將左子結(jié)點的相關(guān)信息進行入棧操作；取另外一條邊的中點作為當前結(jié)點的右子結(jié)點，右子結(jié)點作為當前結(jié)點，執(zhí)行步驟3進行遞歸操作。

（2）若另外兩邊只有一條邊有相鄰三角形，則追蹤到有相鄰三角形邊的中點，將該中點作為當前結(jié)點的左子結(jié)點，并把左子結(jié)點作為當前結(jié)點，執(zhí)行步驟3進行遞歸操作。

（3）若另外兩邊都沒有相鄰三角形，則追蹤到當前結(jié)點所在邊相對的三角形頂點，說明已經(jīng)追蹤到地性線樹的另一端，該頂點作為葉子結(jié)點；然后將棧頂信息出棧，根據(jù)出棧信息，繼續(xù)追蹤地性樹的另一個分支。

2.3.2 鞍部平三角形域地性線樹的提取

鞍部也是平三角形存在的區(qū)域，該區(qū)域存在兩個或兩個以上非平三角形，見圖4。

圖4 鞍部地性線樹的提取Fig.4 Extraction of terrain structure line in the saddles

在鞍部有兩條或兩條以上的等高線參加構(gòu)網(wǎng)。對于有兩個山頭的鞍部，可能形成兩種形態(tài)的平三角形區(qū)域，兩者都是對鞍部真實地形的扭曲：第一種將鞍部削平成“低平原”，如圖4（a）所示；第二種將鞍部填高成“高平原”，如圖4（b）所示。兩者的處理方法相同，都是利用提取地性線信息來恢復真實地形［3］。如圖4所示，一個典型的鞍部構(gòu)網(wǎng)形成的平三角形區(qū)域，其中APB為平三角形區(qū)域的中軸線，即地性線樹的主線，P為中軸線的中間點，A、B兩點的高程值相同，因此，需要給P點指定一個高程值。P點的高程值取鞍部父等高線和子等高線高程值的平均值，即高低點高程和平三角形區(qū)域高程的平均值。

2.3.3 山頂或洼地、圖幅邊緣處平三角形區(qū)域地性線樹的提取

在山頂、洼地、圖幅邊緣處的平三角形區(qū)域中沒有非平三角形。在山頂或洼地，如果沒有地形特征點參與構(gòu)TIN，則山頂或洼地處等高線在內(nèi)部構(gòu)網(wǎng)時會形成平三角形區(qū)域。出現(xiàn)山頂被削平，洼地被填高的不合理情況。同樣，先得到中軸線APB，如圖5所示，然后為中軸線上的各個結(jié)點賦高程值。此處不存在所謂的“高低點”，因此無法直接進行高程值的分配。為了恢復原來的地形，首先要獲得相鄰等高線高程值H1，將H1與平三角形區(qū)域的高程值H2進行比較，若H1-H2＞0，則該地為洼地，地性線樹主線的中間點P高程值為H2-△H/2（△H為等高距）；若H1-H2＜0，則該地為山頂，地性線樹主線的中間點P高程值為H2+△H/2，然后以中間點P為界，對地性線樹主線中間點兩端的分支根據(jù)長度大小分別進行線性內(nèi)插［5］。

圖5 鞍部平三角形區(qū)域存在的兩種形態(tài)Fig.5 Two forms exist in flat triangular area of the saddle

圖幅邊緣處的等高線由于缺少相鄰等高線，而在構(gòu)TIN過程中三角形不可能穿越等高線，因此在等高線內(nèi)部形成了平三角形區(qū)域。在這種情況下追蹤地性線樹的各葉子結(jié)點時，需要判斷各葉子結(jié)點所在三角形邊的情況，（1）若該三角形存在一條硬邊，則葉子結(jié)點追蹤到另一條非硬邊的中點；（2）若該三角形存在兩條硬邊，則葉子結(jié)點追蹤到兩硬邊之間的頂點；（3）若該三角形不存在硬邊，則需要先追蹤到該三角形的重心，然后再追蹤到另外兩條邊的中點。追蹤完地性線樹后，得到地性線樹的主線，這里不存在“高低點”，因此需要獲得相鄰等高線的高程值H1，把H1與平三角形區(qū)域的高程值H2進行比較：若H1-H2＞0，葉子結(jié)點為（1）、（3）兩種情況，則葉子結(jié)點高程值為H2-△H/2（△H為等高距）；若H1-H2＜0，葉子結(jié)點為（1）、（3）兩種情況，則葉子結(jié)點高程值為H2+△H/2。根據(jù)根結(jié)點與葉子結(jié)點的高程值，對地性線樹主線上各結(jié)點以長度大小進行線性內(nèi)插，由主及次，逐層計算，直到所有的結(jié)點都有高程為止。葉子結(jié)點為（2）的情況，該結(jié)點高程值為H2，這里計算各結(jié)點高程值參考山頂或洼地中的采用的方法。

圖6 山頂或洼地地性線樹的提取Fig.6 Extraction of terrain structure line on the top of moun?tains or in the low-lying lands

2.3.4 追蹤算法說明

在地性線樹的追蹤過程中，每追蹤到一個結(jié)點，需要計算該結(jié)點到根結(jié)點的路徑長度LenR，所取的值是該結(jié)點父結(jié)點的LenR值加上該結(jié)點到父結(jié)點的長度值。在所有的結(jié)點中，除了父結(jié)點和葉子結(jié)點有高程值之外，其余的結(jié)點賦高程初始值為-999，表示該結(jié)點沒有實際高程值。

在本算法中采用了棧的數(shù)據(jù)結(jié)構(gòu)，目的是為了在遇到地性線樹分支過程中，保存分支結(jié)點的信息，以便在追蹤完一個分支之后返回原來的結(jié)點繼續(xù)追蹤其分支。以圖2為例，分支結(jié)點入棧出棧操作如圖8所示。

圖7 圖幅邊緣處地性線樹的提取Fig.7 Extraction of terrain structure line on the edge of maps

圖8 分支結(jié)點入棧出棧圖Fig.8 Branch nodes in and out of the stack diagram

2.3.5 地性線點高程計算

已知特征點的平面坐標，若要參加構(gòu)TIN還需要內(nèi)插出其高程值，地性線樹的建立正是用來解決平三角形區(qū)域的高程分配問題［4］。提取出地性線樹之后，從地性線樹的根結(jié)點到各個葉子結(jié)點之間都存在一條路徑LenRi（i=0…M，M為路徑條數(shù)，即葉子結(jié)點的個數(shù)）。在所有的路徑中，取LenR值最大的分支作為地性線樹的主線，主線兩端的根結(jié)點與葉子結(jié)點高程值是已知的，按長度大小對主線進行線性內(nèi)插得到各個結(jié)點的高程。主線上所有的結(jié)點高程賦值完畢后，取出次長分支，根據(jù)分支根結(jié)點與葉子結(jié)點的高程值，對次長分支上的各結(jié)點以長度大小進行線性內(nèi)插。

如圖2為例，取地性線樹的主線A-B-C-E-H-JK，已知根結(jié)點A和葉子結(jié)點K的高程值，根據(jù)長度為權(quán)進行高程分配，見公式（1）。

其中，ZJ、ZA、ZK分別為J、A、K結(jié)點的高程值，LenRJ、LenRK分別為J、K結(jié)點到根結(jié)點A的長度。依次類推，分別計算出主線上其余結(jié)點的高程值。取出次長分支B-D-F，已知分支根結(jié)點B和葉子結(jié)點F的高程值，根據(jù)長度為權(quán)計算出該分支的所有結(jié)點高程值。采用這種由主到次、逐層內(nèi)插的方法直到地性線樹上所有結(jié)點都有高程值為止。

將帶有（X、Y、Z）值的地性線樹結(jié)點信息放到平三角形區(qū)域中，以esriTinHardLine方式重新構(gòu)網(wǎng)，得到一個合理的TIN。圖9為消除平三角形前后的情況對比圖。

圖9 消除平三角形前后的效果對比圖Fig.9 Comparison before and after the elimination of flat triangle

3 點線矛盾的檢查

點線矛盾檢查中，根據(jù)每個高程注記點（X、Y）坐標，內(nèi)插出其在TIN表面的高程，將內(nèi)插出的高程值與高程注記點的屬性高程值進行比較，若兩者之差不在閾值內(nèi)，則可能存在點線矛盾，將該高程注記點的相關(guān)信息記錄到檢查結(jié)果數(shù)據(jù)庫中。

4 結(jié)語

經(jīng)過實驗驗證，提取平三角形區(qū)域的地形特征線信息，并將該特征點信息加入平三角形區(qū)域重新構(gòu)TIN，消除了在等高線彎曲度比較大的地方、鞍部、山頂或洼地、圖幅邊緣處的平三角形。在研究前人的基礎(chǔ)上，對平三角形修復算法進行補充，提出根據(jù)平三角形區(qū)域存在非平三角形個數(shù)的方法對不同區(qū)域存在的平三角形進行修復。將平三角形修復方法引入點線矛盾質(zhì)量檢查，采用平三角形修復后的TIN進行點線矛盾質(zhì)量檢查，明顯提高了點線矛盾質(zhì)量檢查的準確性。當然，這種方法只有在保證等高線質(zhì)量的前提下才能使用，若等高線出現(xiàn)打折、相交、自相交等現(xiàn)象，該方法不適用?！?/p>

[1]何艷飛.1∶5萬DLG質(zhì)量檢查系統(tǒng)及其關(guān)鍵問題的研究[D].成都:西南交通大學,2008.

[2]徐建達.航測地貌數(shù)據(jù)的質(zhì)量控制[D].鄭州:中國人民解放軍信息工程大學,2002.

[3]李志林,朱慶.數(shù)字高程模型[M].武漢:武漢大學出版社,2003:6-52.

[4]陳仁喜,龍毅.顧及三角形處理的TIN建立算法[J].武漢大學學報,2003,28(5):619-622.

[5]吳永軍,王燕午.基于ArcGIS Engine平三角形處理[C].中國地理信息產(chǎn)業(yè)發(fā)展論壇暨2008中國GIS協(xié)會年會論文集.

[6]于娟,張麗萍,張永忠.基于ArcGIS空間處理模型的TIN平坦三角形處理[J].地理與地理信息科學,2009(2)：113

[7]邸元.基于等高線建立DTM中平坦區(qū)域的一種處理方法[J].計算機輔助設(shè)計與圖形學學報,2000,12(8):566-570.