基于等高線建立的TIN模型中平三角形區域的消除方法

王超　逄超

摘要：本文分析了基于平三角形搜索消除平三角形的算法中存在的問題，通過對現有1：1萬基礎地理信息數據特點的研究和對已有算法的改進，得到一種新的、基于等高線的TIN模型中平三角形處理算法，并闡述了其原理和思路。通過對在不同情況下的等高線反演DEM進行實驗，證明了該方法對于消除平三角形、提高1：1萬比例尺DEM精度具有良好的效果。

1.引言

DEM（數字高程模型）是一種能夠通過格網及其屬性表現地形起伏的數據存儲方式，也是基礎地理信息數據的一個重要組成部分。DEM通常采用空間數據插值方法進行大批量生產，而空間數據插值算法主要包括兩類：一類為基于等高線及高程點的約束形地形內插方法；另一類是完全根據地面離散的高程點進行地形內插的方法（通常為克里金內插法）。在內插效率方面，克里金內插算法具有較為突出的表現，但是對于1：1萬比例尺基礎地理信息數據而言，其內插精度無法完全滿足要求，后期需要大量人工修改。因此，在實際生產中通常采用第一類方法?；诘雀呔€及高程點的地形內插算法最核心的步驟便是構建不規則三角網，不規則三角網（TIN）是由連續的三角面組成，三角面的形狀和大小取決于不規則分布的測點的密度和位置，既能夠避免地形平坦時的數據冗余，又能按地形特征點表示數字高程特征，因而成為DEM的主要組織形式之一。

在利用等高線數據構建不規則三角網TIN的過程中，TIN模型的構網的方式通常采用基于邊約束條件的Delau-nay三角剖分。由于等高線數據缺少地形特征點和特征線信息，因而在等高線彎曲較大的地區或山頂等區域常會出現平三角形（三角形三個頂點的高程值相等），從而無法保證所生成的DEM有較高的質量。因此，就需要對TIN中的平三角形進行有效處理。

2.TIN模型中平三角形的消除

平三角形出現的情況主要有四種：第一種是在一條等高線較為曲折的地方，這是最為常見的一種情況；第二種是在山頂或谷底地區閉合等高線的內部，由于其內部沒有任何其他地形特征點或線，因此會在其內部完全生成平三角形區域；第三種是在具有兩個或多個山頭地區或周圍有相同高程值等高線的谷底所形成的鞍部地區；第四種是在圖幅邊界地區，由于單條等高線與圖幅之間的封閉地區缺少任何其他特征點，所以即使等高線在此處并不曲折，也會形成平三角區域。除在第三種情況中平三角形會出現在不同等高線之間，在其余三種情況下，平三角均會出現在同一等高線上。

之前曾有學者提出先將平三角形區域作為一個整體提取出來（如圖1所示），之后取非平三角形△ABC的幾何中心點，記為T，T點的高程由△ABC的平面方程確定，將點T與兩個原始TIN三角形的四個頂點A、B、C、D相連并刪除公共邊BC，重構三角形網，形成四個新三角形，△ABT、△BDT、△DCT、△CAT；然后再計算△CDT的幾何中心，依照上述方法計算插入點的平面位置和高程。

該方法是由最外邊的三角形逐漸向內依次處理平三角形的過程，其優點是不用構造地性線樹，因而從數據結構和處理過程的角度上講，該算法非常簡單高效。然而，這種方法存在一個嚴重的問題：當從外向內直接插入特征點時，相鄰特征點的高程差將會逐漸減小，當平三角形區域中的三角形較多的時候，插入的特征點的高程差將趨近于0，這將導致區域末端的平三角形無法被全部處理，這里將這一現象稱為插入點高程的退化現象。顯然，這種算法對于地形特征點的高程計算并不合理，因此，需要對其進行改進。

2.1數據預處理

數據的預處理是實現本算法的一項重要的前提性工作，對于保證算法所處理數據的質量起著重要的作用。數據預處理包括以下三項內容：

對等高線數據進行簡單的數據錯誤排查，找到高程突變點（遠高于或低于周圍鄰近地形點高程值）和高程超出陸地最高或最低高程范圍（-392m～8845m）的點，對其進行刪除。

使用Douglas抽稀算法利用適當的距離閾值對等高線進行處理，除去不必要的冗余點和重復點。

在原始的TIN三角網中找到各個由平三角形相鄰構成的平坦區域，并找到各區域中的平三角形的相鄰關系以及入口平三角形。

2.2數據結構

在進行地形線樹的構建過程中，應將每個地形特征點視為樹的節點，對于每個節點有如下數據結構：

public class Node

{publie double x；

public double y；

public double z：

public node leftnode；//左子節點

public node rightnode；//右子節點

public int deep；//節點深度

public double distance；//該節點距上一節點的距離}

對于每個由TIN構成的不規則三角形，根據邊與等高線的位置關系可分為軟邊（softedge）與硬邊（hardedge）：軟邊為不與等高線重合的邊，硬邊為構成等高線一部分的邊。故，不規則三角形邊的數據結構中需加入枚舉類型EdgeType，其值為soft和hard。

2.3算法的基本思想

首先，找到與人口三角形相鄰的非平三角形的幾何中心（重心），其坐標值為該三角形三點平面坐標的算術平均值，這樣可以保證所插入的特征點落在該三角形內，以防止后來出現某些較為狹長的平三角形無法得到有效消除的可能情況；然后，將所找到的點作為二叉樹的根節點Node進行存儲，其平面坐標x，Y均已確定，z值可根據該三角形所代表的平面方程予以確定，其deep為0，distance為0，左右子節點leftnode和rightnode暫時為空，待稍候步驟中進行確定；之后，再找到入口三角形的軟邊中點，并計算其x，Y分量的坐標值（軟邊兩端點坐標值平均值），將該節點作為二叉樹的第二個節點存儲，同時將其作為上一個節點的左子節點（由此可知第一個節點的右子節點必為空），該節點的deep較上一節點的deep加1，變為1，計算該節點到上一節點的水平距離作為該節點的distance的值，其z坐標暫時不確定，平面坐標值已算出，左右節點待下一步確定；之后，將新找到的節點同與入口平三角形相鄰的平三角形構成四邊形，繼續計算其重心坐標并建立節點，此時可能會找到兩個平三角形與其相鄰，這樣就會出現二叉樹的分支，將首先找到的一個分支定為左分支，隨后找到的定為由分支，依照上述方法繼續確定各節點的相關信息，直到將平三角形區域中所有的三角形遍歷完畢。當搜索到底部的三角形時，由于這樣的三角形不再有相鄰的平三角形。所以，此處節點的左右子節點均為空。此時形成的二叉樹，其各個節點的信息只有高程值z尚未確定。

在確定了內插特征點二叉樹的存儲結構以及其平面位置相關信息后，再來確定各特征點的高程值。首先搜索到deep值最大的節點，再根據節點之間的相關關系，從葉節點向根節點回溯，計算回溯路徑的長度（各節點的distance之和），并以此來確定樹的主干；當該步回溯結束后，將根節點的高程和葉節點的高程之差，按照各節點之間的距離（dis-tance）為其按照距離加權分配高程差，就得到了各節點的高程值z。

2.4特殊地形的處理

對于鞍部平三角形區域，由于其擁有兩個甚至多個入口平三角形，因此對其處理的方式應予以調整，應對其各個入口三角形依次遍歷，以便從各個入口向內依次處理。此時應該注意的是，由于鞍部的中心沒有其他高程信息，導致在從外部處理到中心時，無法同一般情況那樣進行回溯處理，將其幾何中心的點的高程值定為外部等高線高程與平三角形高程的均值，即二分等高距處的高程。在處理到中心平三角形后，可以對每一條路徑分別利用回溯的方法對內插特征點的高程進行確定。

對于山頂地區的平三角形區域，由于其是由閉合等高線所形成的，既沒有入口三角形也沒有中心的額外高程信息，所以其處理方法應繼續予以調整。本文仿照艾廷華所提出的面狀區域中心確定方法，按照平三角形周圍面積最均衡的原則，找到中心平三角形，將其重心作為此類型的平三角區域的重心，并作為內插特征點樹的根節點，從此點開始，向周圍處理，直到遇到等高線上的點，然后進行回溯處理，確定各點高程。

對于入口邊處于圖幅邊緣的平三角形區域，其處理方式為：將邊緣處的平三角形找到，計算其重心位置（三點坐標平均值），找到與該平三角形相鄰的非平三角形（以硬邊相鄰），設非平三角形的高低點（不在硬邊上的頂點）為zr，平三角形高程為zq，則所找到的重心的高程為Zp=Zq-2/Zr-Zq然后以該點為根節點，按照上述插點回溯算法確定各內插特征點的相關信息。

3.實驗與結論

為了驗證算法對于TIN的模擬精度的影響效果，進行如下實驗：首先，利用已有的高程控制點的平面坐標在原始TIN模型中通過內插計算得到的理論高程；然后再利用相同的方法在利用本文所提出的算法重構后的TIN模型中計算得到另一組理論高程；將兩組理論高程與控制點的實際高程進行對比，可以發現該算法對于TIN模型的模擬精度有大幅度提高，其高程誤差在1/2等高距以內。該算法對于平三角形區域的處理有較好效果，與其他地形特征點內插方法相比，其在運行效率及精度指標上均具有較大優勢，能夠很好地滿足1：1萬比例尺DEM數據的生產要求。