葉燕萍，董小軍，葉駿

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

0 引言

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

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

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

1 TIN的建立

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

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

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

平三角形是指三個(gè)頂點(diǎn)的高程值都相同的三角形。出現(xiàn)平三角形的原因是因?yàn)樵搮^(qū)域缺少地形特征線信息，從地形地貌上來(lái)說(shuō)，出現(xiàn)平三角形的區(qū)域也是地性線樹(shù)存在的區(qū)域［4］。

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

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

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

2.3 地性線樹(shù)的建立方法

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

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

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

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

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

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

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

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

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

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

步驟2：然后將高低點(diǎn)所對(duì)邊的中點(diǎn)作為左子結(jié)點(diǎn)，左子結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)；

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

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

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

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

2.3.2 鞍部平三角形域地性線樹(shù)的提取

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

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

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

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

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

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

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

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

2.3.4 追蹤算法說(shuō)明

在地性線樹(shù)的追蹤過(guò)程中，每追蹤到一個(gè)結(jié)點(diǎn)，需要計(jì)算該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度LenR，所取的值是該結(jié)點(diǎn)父結(jié)點(diǎn)的LenR值加上該結(jié)點(diǎn)到父結(jié)點(diǎn)的長(zhǎng)度值。在所有的結(jié)點(diǎn)中，除了父結(jié)點(diǎn)和葉子結(jié)點(diǎn)有高程值之外，其余的結(jié)點(diǎn)賦高程初始值為-999，表示該結(jié)點(diǎn)沒(méi)有實(shí)際高程值。

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

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

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

2.3.5 地性線點(diǎn)高程計(jì)算

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

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

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

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

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

3 點(diǎn)線矛盾的檢查

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

4 結(jié)語(yǔ)

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

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

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

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

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

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

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

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