在AutoCAD環境下不規則三角網構建及等高線生成

代 莉，陳春華，聶 焱

（湖北省測繪工程院，湖北武漢 430071）

在AutoCAD環境下不規則三角網構建及等高線生成

代 莉，陳春華，聶 焱

（湖北省測繪工程院，湖北武漢 430071）

對不規則三角網的生成進行了分析，在AutoCAD環境下使用三角形生成算法，將離散點構建成不規則三角網，并在此三角網的基礎上生成相應的等高線。

數字高程模型；不規則三角網；Delaunay三角網；等高線

地球表面高低起伏，呈現為一種連續變化的曲面，這種曲面無法用平面地圖來確切表示。于是我們就利用一種全新的數字地球表面的方法--數字高程模型（DigitalElevationModel，縮寫DEM）表示，這種方法已經被普遍廣泛采用。DEM是一定范圍內規則格網點的平面坐標（X，Y）及其高程（Z）的數據集，它主要是描述區域地貌形態的空間分布，是通過等高線或相似立體模型進行數據采集（包括采樣和量測），然后進行數據內插而形成的。DEM 是對地貌形態的虛擬表示，可派生出等高線、坡度圖等信息，也可與DOM或其他專題數據疊加，用于與地形相關的分析應用，同時它本身還是制作DOM的基礎數據。

1 不規則三角網生成的算法

在地理信息系統中，DEM最主要的三種表示模型是：規則格網模型，等高線模型和不規則三角網模型。目前常用的算法是通過等高線和高程點建立不規則的三角網 (Triangular Irregular Network,簡稱TIN),然后在TIN基礎上通過線性和雙線性內插建DEM。

不規則的三角網是由Peuker和他的同事于1978年設計的一個系統，它是根據區域的有限個點集將區域劃分為相等的三角面網絡，數字高程由連續的三角面組成，所有三角面相互鄰接，互不相交，互不重疊，三角面的形狀和大小取決于不規則分布的測點的密度和位置，能夠避免地形平坦時的數據冗余，又能按地形特征點如山脊、山谷線、地形變化線等表示數字高程特征。TIN常用來擬合連續分布現象的覆蓋表面。

Delaunay三角網，具有空外接圓，以及最小角最大的特性，可最大限度的保證網中三角形滿足近似等邊形狀，在地形擬合方面表現最為出色，且 Delaunay三角網結構良好，數據結構簡單，數據冗余度小，存儲效率高，可適應各種分布密度的數據，因此常被用于TIN的生成。

根據構建三角網的步驟，可將三角網生成算法分為三類：①分而治之算法（由Shmaos和Hoey提出），其基本思路是使問題簡化，把點集劃分到足夠小，使其易于生成三角網，然后把子集中的三角網合并生成最終的三角網，用局部優化（LOP，即LocalOptimization Procedure）算法保證其成為Delaunay三角網，它的優點是時間效率高，但需要大量遞歸運算，因此占用內存空間較多；②數據點漸次插入算法（由 Lawson提出），其思路很簡單，先在包含所有數據點的一個多邊形中建立初始三角網，然后將余下的點逐一插入，用LOP算法保證其成為Delaunay三角網。此算法雖然容易實現，但效率極低；③三角網生長算法，在這三種算法中，三角網生長算法在80年代以后的文獻中已很少見，該算法是由M ichael J.M cCullagh,CharlesG.Ross提出的。

下面以圖1中的離散點為例（該離散點均取自高程點），討論三角形生長算法在AutoCAD中的實現。

圖1 離散點分布圖

1.1 數據結構設計

在不規則三角網生成的過程中，最重要的兩個表就是三角形表和三角形的邊表。三角形表是用來存放所有生成的三角形，存放的格式為：（點1的坐標，點2的坐標，點3的坐標，指針），點1、點2、點3為三角形的3個頂點，坐標格式為（X，Y，Z），且方向為逆時針。指針則是指向三角形三條邊的鄰接三角形，初始值為（-1，-1，-1）。三角形的邊表存放已生成的三角形的三條邊，存放格為（第一個點坐標，第二個點坐標），和三角形存放順序一樣，也是按逆時針。

1.2 初始三角形生成

首先要選擇初始三角形的起始點。以離散點的坐標（X,Y）為參照，取X+Y值最小的那個點作為三角形的起始點。該起始點在圖1的左下角。如圖2所示點 A，就是遍歷所有的點后，用比較算法得到的初始三角形的起始點。

圖2 初始三角形起始點

然后尋找離點A最近的那個點B，就構成初始三角形的起始邊（如圖3所示）。

圖3 初始三角形的起始邊

根據Delaunay三角網的空外接圓性質，尋找第三個點。以AB邊對角為參照對象，尋找最大的∠ACB，如圖4所示就得到初始三角形ABC。

圖4 初始三角形ABC

數據結構中要求所有的三角形按逆時針的方向存儲。那么就要判斷點C在AB邊的位置，如果在AB邊的右邊的話，就交換B、C兩點。那么初始三角形修改如圖5所示。

圖5 修改后的初始三角形

以初始三角形為例，三角形的存儲格式為（點 A坐標，點B坐標，點C坐標，（-1，-1，-1））。邊表的存儲格式為（（點A，點B），（點B，點C），（點C，點A））。

1.3 擴展三角形

以圖5中的初始三角形為例。先從AB邊擴展，首先要選擇在AB邊右邊的點。用公式：(ym-ya)*(xb-xa)-(yb-ya)*(xm-xa)來判斷點的位置，（xa，ya）為點 A的坐標，（xb，yb）為點B的坐標，（xm，ym）為擴展點M的坐標。若值大于 0，點在直線的左邊；若值等于 0，點在直線上；若小于0，點在直線右邊。再根據Delaunay三角網的空外接圓性質，確定擴展三角形的第三個點M。同時還要判斷擴展三角形的邊AM,MB是否存在于邊表。

在這里，邊表的作用就是判斷是否存在重復的三角形。以邊 AB為例，由于方向性的問題，在相鄰三角形中的同一條邊存儲格式分別為(A，B)和(B，A)，也就是說不會有第三個三角形會有AB或BA這條邊；否則就會出現三角形重復或者三角形相交的問題。

滿足以上條件，就可以確定擴展三角形的點 M。將該擴展三角形添加到三角形表中，同時也將三角形的三條邊添加到邊表中，還要修改對應三角形的指針。若沒有符合條件的點M，則直接處理下一條邊。

BC邊的擴展同AB邊一樣。

兩邊均處理完后，再從三角形表中取出下一個三角形，按上述方法擴展，直至所有三角形擴展完畢。

如圖6所示，即為圖1的離散點得到的三角網。

2 等高線生成

三角形表中存放了不規則三角網中所有的三角形，以及指向相鄰三角形的指針。根據三角形 3個頂點的Z值，就可以判斷某一高程值的等高線是否穿過該三角形。若等高線經過該三角形，就要判斷等高線經過的是三角形的哪兩條邊并計算交點的坐標，交點坐標可以根據插值公式得到。根據指針，就可以繼續判斷相鄰的下一個三角形，直至遍歷三角網中所有的三角形。最后將所有交點按順序連接起來就可以得到該高程值的等高線。

要生成全圖的等高線，就需要高程范圍，這個可以直接遍歷全圖的高程點得到。

如圖7所示，為在圖6的不規則三角網的基礎上生成的5m等高距的等高線。

圖6 不規則三角網

圖7 等高線

3結語

本算法在AutoCAD中已經實現并調試完成。利用三角形生長算法實現Delaunay三角網構建并不是最優的算法，存在計算的時間復雜性不能徹底解決的問題，也就是說離散點越多，生成Delaunay三角網花費的時間也就越多。且算法中選取的離散點為實際測圖中的高程點，若要得到更貼合地面形態的 TIN，就要求測圖中的高程點為特征點。若要提高運算速度又要更好地貼合地面形態，需要在今后的工作中進一步探索和研究。

[1] 南勝.基于不規則三角網(TIN)數模建構的優化算法[J].浙江測繪,2007(1):5-7

[2] 王建雄.CAD環境下基于不規則三角網的DEM算法及實現[J].云南農業大學學報,2005,20(4):573-576

[3] 蔣瑜,杜斌,盧軍,等.基于Delaunay三角網的等值線繪制算法[J].計算機應用研究,2010,27(1):101-103

[4] 馬智民,羅斌.Delaunay三角網構建DEM整體優化算法[J].長安大學學報:自然科學版,2008,28(3):44-48

[5] 任振娜,李斌兵,周浩,等.應用等高線構Delaunay三角網算法的研究與實現[J].工程圖學學報,2006(6):54-58

[6] 張巧鳳,張錦.基于MapX二次開發生成Delaunay三角網[J].測繪工程，2005,14(1):59-62

[7] 芮一康,王結臣.Delaunay三角形構網的分治掃描線算法[J].測繪學報,2007,3：358-362

Construction of TIN and Generation of Contour Lineon AutoCAD

by DAILi

The generation of TIN was being analysed.According to algorithm of triangle generation,construct the TIN while based on discrete point in Auto CAD,and generated contour line of arbitrary height the same.

DigitalElevation Model，Triangular Irregular Network，Delaunay triang ularnet work，contour line （Page:40）

P208

B

1672-4623(2011)02-0040-03

2010-10-08

項目來源：精密工程與工業測量國家測繪局重點實驗室2009年開放基金資助項目（PF2009-D,PF2009-23)

代莉，工程師，研究方向為測繪工程。