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

李小秋 ，許民獻(xiàn) ，尹志永

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

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

李小秋 ，許民獻(xiàn) ，尹志永

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

123

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

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

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

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

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

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

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

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

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

2 數(shù)值運(yùn)算

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

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

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

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

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

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

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

2．1 定位三角形

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

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

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

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

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

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

圖2 方向搜索

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

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

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

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

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

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

3 效率分析

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

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

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

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

圖5 效率對(duì)比

4 結(jié)束語

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

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

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

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

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

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

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

［7］周曉云，劉慎權(quán)．實(shí)現(xiàn)約束Delaunay三角剖分的健壯算法［J］．計(jì)算機(jī)學(xué)報(bào)，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é)任編輯張德福］