李小秋 ，許民獻 ，尹志永

（1．桂林市測繪研究院，廣西 桂林541002；2．河北省第三測繪院，河北 石家莊 050031；3．河北省基礎(chǔ)地理信息中心，河北石家莊050031）

Delaunay三角網(wǎng)關(guān)鍵技術(shù)探討

李小秋 ，許民獻 ，尹志永

（1．桂林市測繪研究院，廣西 桂林541002；2．河北省第三測繪院，河北 石家莊 050031；3．河北省基礎(chǔ)地理信息中心，河北石家莊050031）

123

利用計算機技術(shù)，基于實際測量數(shù)據(jù)，利用逐點插入法，在不建立格網(wǎng)索引的情況下，提出一種高效的Delaunay三角網(wǎng)構(gòu)建方法，與建立格網(wǎng)索引法搜索點所在的三角形相比，具有較高的執(zhí)行效率。

Delaunay；不規(guī)則三角網(wǎng)；TIN；數(shù)據(jù)結(jié)構(gòu)

由于Delaunay三角網(wǎng)具有最大的最小角及空外接圓兩大重要性質(zhì)，使剖分所得每個三角形最大限度地接近正三角形，因此它在所有的構(gòu)網(wǎng)原則中是最優(yōu)的，這使得它作為一種基本手段在地學(xué)分析、地理信息系統(tǒng)、虛擬現(xiàn)實以及道路設(shè)計等領(lǐng)域有著廣泛的應(yīng)用。

經(jīng)過20多年的研究，國內(nèi)外已經(jīng)出現(xiàn)了不少成熟的Delaunay三角網(wǎng)生成算法，Lewis和Robinson提出了分治算法，Lawson提出了逐點插入法，Green和Sibson提出了三角網(wǎng)生長法；國內(nèi)許多學(xué)者也在此基礎(chǔ)上作了大量的研究，提出了卓有成效的改進算法。

三角網(wǎng)生長法由于算法復(fù)雜、時間效率差，在80年代中期以后的文獻中已很少見，研究較多的是分治算法和逐點插入法。

分治算法構(gòu)網(wǎng)速度快，其缺點是程序遞歸執(zhí)行需要占用大量內(nèi)存空間，數(shù)據(jù)預(yù)處理以及優(yōu)化工作量大，對計算機硬件要求高；逐點插入法原理簡單，占用內(nèi)存資源少，編程容易實現(xiàn)，傳統(tǒng)算法時間復(fù)雜度差，主要制約因素在于點在三角網(wǎng)中的查找和判斷以及三角網(wǎng)的局部優(yōu)化。文獻［1］提出通過對原始數(shù)據(jù)預(yù)處理并進行格網(wǎng)化管理，從理論和實踐均證明這是一種有效的提高逐點插入法構(gòu)網(wǎng)速度的方法，已被廣泛采用；但由于此方法需要對原始數(shù)據(jù)進行排序和對構(gòu)網(wǎng)過程中的三角形進行格網(wǎng)管理，工作量較大，數(shù)據(jù)結(jié)構(gòu)復(fù)雜，增加了編程的難度。筆者通過對逐點插入法深入剖析，提出了一種實用的方法，實踐證明，其效率要優(yōu)于格網(wǎng)化逐點插入法。

1 數(shù)據(jù)結(jié)構(gòu)

三角網(wǎng)的數(shù)據(jù)存儲方式比較復(fù)雜，它不僅要存儲每個點的平面坐標(biāo)及高程，還要存儲邊與點、邊與三角形、點與三角形、以及三角形與三角形之間的拓撲關(guān)系；簡潔而緊湊的數(shù)據(jù)結(jié)構(gòu)不僅能優(yōu)化內(nèi)存使用，還能提高數(shù)據(jù)檢索速度，它是提高構(gòu)網(wǎng)效率的關(guān)鍵因素之一。以下是用C＋＋語言定義的三角網(wǎng)數(shù)據(jù)拓撲數(shù)據(jù)結(jié)構(gòu)。

可以看出，以上數(shù)據(jù)結(jié)構(gòu)除了點的三維坐標(biāo)外，其余數(shù)據(jù)成員都是整型數(shù)，計算機對整型數(shù)的運算速度要大大快于對浮點數(shù)的運算速度；另外，在獲得數(shù)據(jù)點的總數(shù)后要盡量一次性分配足夠的內(nèi)存空間，避免在程序運行過程中動態(tài)分配內(nèi)存，造成內(nèi)存使用碎片，降低構(gòu)網(wǎng)速度。

2 數(shù)值運算

逐點插入算法是Lawson在1977年提出的，其基本思想是：對于一已經(jīng)存在的三角形網(wǎng)絡(luò)，當(dāng)在其中插入一點時，將該點與包含它的三角形的三個頂點相連，從而與周圍的三角形形成共用同一條對角線的四邊形，然后逐個對四邊形中的2個三角形進行空外接圓檢測，如果不滿足空外接圓準(zhǔn)則，則用另一條對角線替換現(xiàn)有對角線；連續(xù)執(zhí)行這一步驟，直到全部滿足空外接圓準(zhǔn)則為止［2］；基本過程如下：

1）遍歷所有數(shù)據(jù)點，生成一矩形包容盒包含所有數(shù)據(jù)點，將此矩形包容盒分割為2個三角形。

2）數(shù)據(jù)點的逐點插入：從點集中順次取出一點p，找到包含該點的三角形，P與包含三角形的頂點相連，形成3個新三角形，更新拓撲關(guān)系并將新生成的三角形加入優(yōu)化隊列中，如圖1所示。

3）優(yōu)化隊列中的三角形。

4）重復(fù)2）、3），直到所有點插入完畢。

圖1 在三角網(wǎng)中插入一點

可見，逐點插入法的時間主要耗費在定位三角形和三角網(wǎng)的優(yōu)化上，隨著點數(shù)的增加，三角形個數(shù)成倍增加，基于點在三角形中的查找判斷過程是一個很費時的過程。

2．1 定位三角形

向初始三角網(wǎng)中添加構(gòu)網(wǎng)點，就必須知道構(gòu)網(wǎng)點所在的三角形，然后才可對初始三角網(wǎng)進行局部重構(gòu)。如何快速找到構(gòu)網(wǎng)點所在的三角形是逐點插入算法的核心問題。判斷點是否在三角形內(nèi)可以通過點與三角形三邊的關(guān)系來判斷；點與直線的關(guān)系可以用簡化式（1）表示。

由上述關(guān)系可以知道點是否在三角形中；設(shè)構(gòu)網(wǎng)點P與三角形三邊的關(guān)系分別用d 1、d2、d3來表示，d1、d2、d3都是有向的并且按順時針排列，如果三者都大于0，則點在三角形內(nèi)部；如果兩個大于0，另一個等于0，則點在三角形的一條邊上；如果僅有一個大于0，另外兩個等于0，則點與三角形的某頂點重合；否則點在三角形的外部。

遍歷整個三角網(wǎng)，總可以找到點所在的三角形，當(dāng)三角形個數(shù)較大時，這是個很費時的操作，消耗大量的時間，隨著三角形個數(shù)的增多，構(gòu)網(wǎng)速度會越來越低。

文獻［1］通過對隨機無序的散點和三角形建立格網(wǎng)索引來確定搜索起點三角形，使搜索起點三角形與目標(biāo)三角形最近來減少搜索時間，這一方法與遍歷整個三角網(wǎng)相比其搜索時間大幅度降低，但由于需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，消耗了大量的內(nèi)存，使程序結(jié)構(gòu)也相對復(fù)雜。

實際測量數(shù)據(jù)并非隨機分布，而是局部基本有序的，筆者利用這一特性，將上一個插入三角形作為下一插入點的搜索起始三角形，不需要建立復(fù)雜的格網(wǎng)索引，只需要記錄上一個目標(biāo)三角形并作為下一插入點的搜索起始三角形，同樣可以達到相同甚至較高的構(gòu)網(wǎng)效率。

如圖2所示，搜索起始三角形S確定后，使用方向搜索技術(shù)［3］可以迅速而精確地定位到插入點P所在的目標(biāo)三角形T。

圖2 方向搜索

2．2 三角網(wǎng)的優(yōu)化

新點插入后，就可以根據(jù)優(yōu)化條件來判斷相鄰三角形是否需要優(yōu)化，優(yōu)化條件為：公共邊所對的2個內(nèi)角和大于180°，可以證明僅此條件即可滿足Delaunay三角網(wǎng)特征，如圖3所示。

圖3 三角網(wǎng)的優(yōu)化

設(shè)：α1＝∠N1N3N2，α2＝∠N1N4N2．

顯然，當(dāng)（α1＋α2）＞180°時，也就是當(dāng)滿足條件sin（α1＋α2）＜0時，點 N4在三角形 N1N2N3的外接圓內(nèi)，這時需要交換對角線。

本算法不需要對四點共圓和三點共線的情況進行特殊處理，并且其數(shù)值運算只有加、減和乘法，運算效率極高。

3 效率分析

圖4為使用本文方法建立的某測區(qū)數(shù)字高程模型的一部分，計算機硬件配置為：P4 2．8 GHz 256 M內(nèi)存。

圖4 某測區(qū)局部構(gòu)網(wǎng)樣例

表1和圖5為本文方法和格網(wǎng)索引法的效率分析，可以看出，點數(shù)和構(gòu)網(wǎng)時間二者基本都為線性關(guān)系，而構(gòu)網(wǎng)效率本文方法較高。

表1 構(gòu)網(wǎng)效率對照表

圖5 效率對比

4 結(jié)束語

一個良好的數(shù)據(jù)結(jié)構(gòu)和三角劃分準(zhǔn)則，必須由一個高效的算法和程序?qū)崿F(xiàn)；算法在具體應(yīng)用中發(fā)揮的作用由算法本身的性能和實現(xiàn)它的程序質(zhì)量共同決定；逐點插入算法在解決了它的瓶頸問題后，其構(gòu)網(wǎng)速度基本與分治算法接近。利用本文方法對實際測量數(shù)據(jù)構(gòu)造Delaunay三角網(wǎng)的速度達到每秒15萬個點，在效率上已經(jīng)完全能滿足工程設(shè)計的需要。

［1］蔣瑜，杜斌，盧軍，等．基于Delaunay三角網(wǎng)的等值線繪制算法［J］．計算機應(yīng)用研究，2010（1）：101－103．

［2］劉永和，王燕平，齊永安．一種快速生成平面Delaunay三角網(wǎng)的橫向擴張法［J］．地球信息科學(xué)，2008，10（1）：20－25．

［3］胡金星，馬照亭．基于格網(wǎng)劃分的海量數(shù)據(jù)Delaunay三角剖分 ［J］．測繪學(xué)報，2004，33（2）：163－167．

［4］劉學(xué)軍，符鋅砂．公路數(shù)字地面模型整體建立原理及方法 ［J］．中國公路學(xué)報，2000，20（3）：16－20．

［5］劉少華，程朋根．Delaunay三角網(wǎng)內(nèi)插特征點算法研究［J］．華東地質(zhì)學(xué)院學(xué)報，2002，25（3）：254－257．

［6］方勇，劉鵬，胡海彥．一種Delaunay三角網(wǎng)的快速生成算法［J］．測繪科學(xué)與工程，2006，26（3）：1－4．

［7］周曉云，劉慎權(quán)．實現(xiàn)約束Delaunay三角剖分的健壯算法［J］．計算機學(xué)報，1996，19（8）：615－624．

Discussion on key technology of the Delaunay triangulated network

LI Xiao－qiu1，XU Min－xian2，YIN Zhi－yong3
（1．Guilin Institute of Surveying and Mapping，Guilin 541002，China；2．Hebei the Third Bureau of Surveying and Mapping，Shijiazhuang 050031，China；3．Hebei Geomatics Center，Shijiazhuang 050031，China）

A new efficient Delaunay triangulated network construction method is introduced using incremental inserting method based on real survey data without setting up grid index．Comparing with grid index method to find the triangle with the searching points located，this method has much higher executing efficiency．

Delaunay；irregular triangle network；TIN；data structure

P208

A

1006－7949（2011）06－0061－03

2011－09－28

李小秋（1974－），男，工程師．

［責(zé)任編輯張德福］