代 莉，陳春華，聶 焱

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

在AutoCAD環(huán)境下不規(guī)則三角網(wǎng)構(gòu)建及等高線生成

代 莉，陳春華，聶 焱

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

對不規(guī)則三角網(wǎng)的生成進行了分析，在AutoCAD環(huán)境下使用三角形生成算法，將離散點構(gòu)建成不規(guī)則三角網(wǎng)，并在此三角網(wǎng)的基礎(chǔ)上生成相應(yīng)的等高線。

數(shù)字高程模型；不規(guī)則三角網(wǎng)；Delaunay三角網(wǎng)；等高線

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

1 不規(guī)則三角網(wǎng)生成的算法

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

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

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

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

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

圖1 離散點分布圖

1.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

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

1.2 初始三角形生成

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

圖2 初始三角形起始點

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

圖3 初始三角形的起始邊

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

圖4 初始三角形ABC

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

圖5 修改后的初始三角形

以初始三角形為例，三角形的存儲格式為（點 A坐標(biāo)，點B坐標(biāo)，點C坐標(biāo)，（-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的坐標(biāo)，（xb，yb）為點B的坐標(biāo)，（xm，ym）為擴展點M的坐標(biāo)。若值大于 0，點在直線的左邊；若值等于 0，點在直線上；若小于0，點在直線右邊。再根據(jù)Delaunay三角網(wǎng)的空外接圓性質(zhì)，確定擴展三角形的第三個點M。同時還要判斷擴展三角形的邊AM,MB是否存在于邊表。

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

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

BC邊的擴展同AB邊一樣。

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

如圖6所示，即為圖1的離散點得到的三角網(wǎng)。

2 等高線生成

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

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

如圖7所示，為在圖6的不規(guī)則三角網(wǎng)的基礎(chǔ)上生成的5m等高距的等高線。

圖6 不規(guī)則三角網(wǎng)

圖7 等高線

3結(jié)語

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

[1] 南勝.基于不規(guī)則三角網(wǎng)(TIN)數(shù)模建構(gòu)的優(yōu)化算法[J].浙江測繪,2007(1):5-7

[2] 王建雄.CAD環(huán)境下基于不規(guī)則三角網(wǎng)的DEM算法及實現(xiàn)[J].云南農(nóng)業(yè)大學(xué)學(xué)報,2005,20(4):573-576

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

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

[5] 任振娜,李斌兵,周浩,等.應(yīng)用等高線構(gòu)Delaunay三角網(wǎng)算法的研究與實現(xiàn)[J].工程圖學(xué)學(xué)報,2006(6):54-58

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

[7] 芮一康,王結(jié)臣.Delaunay三角形構(gòu)網(wǎng)的分治掃描線算法[J].測繪學(xué)報,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

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

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