劉琴琴

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安710062）

平面域Delaunay三角網(wǎng)點定位算法研究綜述

劉琴琴

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安710062）

不規(guī)則三角網(wǎng)常用于地形的可視化，其生成算法一直是國內(nèi)研究熱點。Delaunay三角剖分算法是構(gòu)建不規(guī)則三角網(wǎng)的主要算法。討論了平面域離散點生成Delaunay三角網(wǎng)算法的研究現(xiàn)狀，其中逐點插入法中影響構(gòu)網(wǎng)效率的關(guān)鍵因素是任意插入點定位的速度。總結(jié)了目前國內(nèi)主流的點定位算法，對國內(nèi)該領(lǐng)域現(xiàn)有文獻研究存在的主要問題作了詳細(xì)分析，并展望了未來可能的研究走向，以期為國內(nèi)Delaunay三角網(wǎng)生成算法研究提供理論與方法上的指導(dǎo)意見。

Delaunay；不規(guī)則三角網(wǎng)；逐點插入法；點定位

在地理信息系統(tǒng)中，數(shù)字高程模型最基本和最重要的模型是不規(guī)則三角網(wǎng) （Triangulated Irregular Network，TIN）模型。不規(guī)則三角網(wǎng)是由不規(guī)則的離散點生成互不交叉、互不重疊又相互鄰接的連續(xù)三角形來擬合地形的[1-2]。由于Delaunay三角網(wǎng)[3]具有唯一性、空外接圓和最大的最小內(nèi)角等性質(zhì)，所以在一般情況下，Delaunay三角網(wǎng)被公認(rèn)為是所有構(gòu)網(wǎng)規(guī)則中最優(yōu)的[4]，因此被廣泛應(yīng)用。

Delaunay三角網(wǎng)生成算法經(jīng)過20多年的研究已取得了豐富的研究成果，按照構(gòu)網(wǎng)過程的不同，主要可分為三角網(wǎng)生長法[5]、分治算法[6]和逐點插入法[7]，采用后兩種以及兩種結(jié)合算法較多。

三角網(wǎng)生長法構(gòu)網(wǎng)步驟相對簡單，時間效率較差，平均時間復(fù)雜度為O（n2）[8]，現(xiàn)應(yīng)用很少。

分治算法構(gòu)建三角網(wǎng)思路簡單，運行速度較快，構(gòu)網(wǎng)費時與離散點數(shù)基本成正比[9]，其缺點是需占用大量的內(nèi)存來存儲空間，相對復(fù)雜。

逐點插入法構(gòu)網(wǎng)原理簡單，內(nèi)存占用少，容易實現(xiàn)，但時間復(fù)雜度差，運行速度慢，主要影響因素為點在三角形中的定位和三角網(wǎng)的優(yōu)化。近年來，一些學(xué)者致力于點定位算法的研究，并取得了一定的理論成果。文中依托CNKI中國知網(wǎng)，對Delaunay三角網(wǎng)生成算法的相關(guān)中文文獻進行檢索和整理，總結(jié)和討論了任意點定位的改進算法，同時對國內(nèi)該領(lǐng)域現(xiàn)有文獻的研究局限作了詳細(xì)分析，并展望其未來可能的研究走向。

1 逐點插入法

逐點插入法于1977年由Lason提出，后來Lee和 Schachlter、Bowyer、Watson、Sloan以及 Tsai等學(xué)者對其進行了改進，具體過程如下：

1）定義一個初始多邊形包含所有離散點，在初始多邊形中構(gòu)建初始三角網(wǎng)；

2）數(shù)據(jù)點的插入：從離散點中選取一點P，定位該點所在的三角形，連接點P與包含該點的三角形的3個頂點，形成新三角形；

3）優(yōu)化三角形[10]；

4）迭代2）、3）步驟，直至插入完所有離散點。

逐點插入法在建立初始三角網(wǎng)后，將點插入到初始三角網(wǎng)中時，需要查找包含該點的三角形，即點定位[11]。隨著點的插入，點數(shù)增加，三角形數(shù)量也成倍增加，查找該點所在的三角形的過程非常費時，執(zhí)行效率低，算法平均時間復(fù)雜度為O（n log n），在最壞情況下時間復(fù)雜度為O（n2）[8]。由此可見，定位點所在的三角形是影響逐點插入法構(gòu)網(wǎng)效率的一個關(guān)鍵步驟。

2 平面域Delaunay三角網(wǎng)點定位算法

為了提高逐點插入法構(gòu)建Delaunay三角網(wǎng)的效率，國內(nèi)很多學(xué)者已提出了相應(yīng)的點定位算法。

2.1 基于面積坐標(biāo)定位算法

定位點所在的三角形和判斷下一個三角形的算法比較多。根據(jù)有限元理論，劉學(xué)軍等人提出利用三角形面積坐標(biāo)和三角網(wǎng)的拓?fù)潢P(guān)系來定位[12-13]。假設(shè)三角形 3個頂點坐標(biāo)為 V1（x1，y1）、V2（x2，y2）、V3（x3，y3），面積為S，任意插入點P（xp，yp）與三角形構(gòu)成的矢量面積分別為S1、S2、S3，面積坐標(biāo)分別為L1、L2、L3，三角形頂點按逆時針排列，則：

若3個面積坐標(biāo)均大于0，則點P位于三角形內(nèi)；若至少有一個面積坐標(biāo)小于0，則點P位于三角形外；若有面積坐標(biāo)為0，則點P位于三角形的邊上（不考慮點P與三角形頂點重合的特殊情況）。通過該方法可很快定位出點所在的三角形，計算效率較高，缺點是搜索路徑不唯一，當(dāng)出現(xiàn)兩邊的面積坐標(biāo)S1、S3都為負(fù)值時，搜索路徑不唯一。

2.2 點線關(guān)系方向定位算法

為了解決搜索定位路徑唯一性問題，宋占峰等人提出了方向搜索法，基本思想為：從首三角形開始，利用點在直線邊側(cè)的檢測（CCW檢測），需要判斷插入點P和三角形的重心G是否相對于三角形的某一邊位于異側(cè)，若點P與重心G相對于三角形的3條邊都位于同側(cè)，則點P在三角形中，若點P與重心G相對于三角形的某一邊異側(cè)，則以該邊為公共邊的相鄰三角形就是下一個搜索三角形[14]。點與三角形某條邊的關(guān)系可用公式（3）判斷：若ccw（c，a，b）大于0，則點c在向量ab的左側(cè)；若ccw（c，a，b）小于0，則點c在向量ab的右側(cè)；若ccw（c，a，b）等于0時，則點c在向量ab上。

宋占峰等人[14]采用方向搜索法可快速定位點所在的三角形，缺點是該方法在特殊情況下也會出現(xiàn)搜索路徑不唯一，雖然不影響最后的效果，但明顯增加了運算量，效率較低。劉少華等人[15]提出點邊方向定位法，根據(jù)點和有向線段的正負(fù)性來判斷點是否在三角形中，計算效率較高，但搜索方向不唯一。李小秋等人[16]將上一個插入三角形作為下一插入點的搜索初始三角形，使用方向搜索法定位點所在的三角形，在實際測量數(shù)據(jù)構(gòu)建三角網(wǎng)的速度可達(dá)每秒15萬個點，在效率上能滿足工程設(shè)計需要；文獻[17]則將三角形頂點按順時針排列，將新生成的三角形作為初始三角形并采用方向搜索法定位，可保持較高的生成效率；Jian Hui-xi[18]也采用方向搜索法定位。

為了進一步解決搜索定位路徑不唯一問題，很多學(xué)者在此基礎(chǔ)上提出了改進算法，如徐道柱等人[19]在此基礎(chǔ)上增加了一個條件，在判斷點P和三角形的重心G是否相對于三角形的某一邊位于異側(cè)時，判斷重心G與點P的連線GP與三角形的邊是否相交，驗證表明算法的效率可提高4倍多；楊小運等人[20]提出“基于三角形方向搜索”的方法，通過判斷三角形與插入點與三角形頂點形成的三角形的方向是否相同來定位，只需簡單的數(shù)值比較運算可判斷三角形的方向，有效縮短了構(gòu)網(wǎng)過程中定位點的時間；蒲浩等人提出最速方向定位法[21]，將三角形重心G與點P連線GP作為方向線，若三角形不包含點P，則下個搜索三角形則為與方向線GP相交邊的相鄰三角形，如圖1所示，劉云等人[22]也用此方法來定位點所在的三角形。這些方法都不同程度的提高了點定位三角形的效率，解決了搜索路徑不唯一性。其中，最速方向定位法雖然路徑唯一，但不是最短路徑，沒有考慮方向線GP與三角形頂點、邊重合的情況，當(dāng)遇上特殊情況時會出現(xiàn)死循環(huán)（如圖2所示）。

圖1 最速方向定位法

圖2 點與線、三角形之間的關(guān)系

針對最速方向定位法中存在的不足，劉少華等人[15]還結(jié)合最速方向定位法，規(guī)定若方向線GP經(jīng)過三角形頂點時，則以這個頂點為中心逆時針?biāo)阉魅切?，判斷方向線GP與三角形邊的關(guān)系，若三角形的某一邊與方向線GP重合，則以這條邊的另一個頂點為中心逆時針?biāo)阉魅切?，重?fù)以上步驟，解決了方向線GP與三角形頂點、邊重合的情況，定位路徑唯一，保證了算法的穩(wěn)健性和高效性，但也不是最短路徑，也沒有利用點與三角形的拓?fù)潢P(guān)系，計算重心的次數(shù)也較多。針對上述算法中的不足，鄒永貴等人[23]充分考慮了點與三角形的拓?fù)潢P(guān)系，改進了算法，減少了重心計算次數(shù)，運算步驟也減少，搜索路徑唯一，通過驗證表明，在相同的離散點數(shù)據(jù)條件下，文獻[15]計算了7次重心、7次相交邊，而此算法只計算了2次重心、2次相交邊，耗時明顯小于文獻[15]，提高了定位效率和構(gòu)網(wǎng)速度。張詠等人結(jié)合三角形面積坐標(biāo)定位法、重心方向搜索法和點邊方向定位法[15]這三種方法，提出融和算法[24-25]，如圖 3所示，在相同的離散點條件下，融合算法比基于面積坐標(biāo)的定位算法搜索的三角形減少了，構(gòu)網(wǎng)效率提高了。融合算法不僅定位路徑惟一，還是最短路徑，構(gòu)網(wǎng)效率高，在健壯性和效率上達(dá)到了有效平衡，但由于沒有引入格網(wǎng)索引，整體定位效率不高。

圖3 融合算法

2.3 格網(wǎng)索引法

對離散點分塊管理是快速定位點所在三角形的一個重要方法，該方法通過縮小查找范圍而使點定位效率提高。定位點所在的三角形，先將離散數(shù)據(jù)點劃分成矩形網(wǎng)格，將離散點的編號依照點的坐標(biāo)存儲到對應(yīng)的網(wǎng)格中，通過計算三角形的重心坐標(biāo)即可判斷出所在的網(wǎng)格，然后通過網(wǎng)格中記錄的三角形進行判斷。徐旭等人采用網(wǎng)格分塊的方法對構(gòu)網(wǎng)離散點和已生成的三角網(wǎng)建立索引來提高點在三角網(wǎng)中的定位效率[26]，大大縮小了搜索范圍，提高了點定位速度。

很多研究學(xué)者也采用格網(wǎng)索引法來定位點所在的三角形。如蔣瑜等人[27]將離散點總體上看成隨機均勻分布，采用格網(wǎng)索引法來定位，但實際測量數(shù)據(jù)并非隨機分布，常常存在一些約束關(guān)系，不夠通用；趙巖等人[28]選擇適當(dāng)?shù)母窬W(wǎng)大小對三角網(wǎng)進行存儲從而減小點定位時遍歷次數(shù)；李小麗等人[29]將數(shù)據(jù)按線性四叉樹方式劃分成若干格網(wǎng)來構(gòu)建三角網(wǎng)；文獻[30-31]則采用自適應(yīng)格網(wǎng)劃分來構(gòu)建Delaunny三角網(wǎng)。也有學(xué)者提出結(jié)合格網(wǎng)索引法和點線關(guān)系方向定位法的算法，如姜志偉等人[32]提出基于格網(wǎng)索引和方向法搜索的三角網(wǎng)生成算法，該算法構(gòu)網(wǎng)效率比一般插入法高，構(gòu)網(wǎng)效率和點的個數(shù)幾乎成線性關(guān)系，可利用該算法快速找到約束線段的影響三角形；王濤等人[33]利用建立的格網(wǎng)索引確定已知頂點后，由頂點與定位點組成方向線，搜索判斷與方向線相交的邊所在的三角形是否包含定位點，算法搜索路徑惟一，但計算步驟較融和算法多。

3 存在的問題與研究趨勢

3.1 存在的問題

1）研究注重提出新算法，缺少算法的實用性分析。如算法能適應(yīng)多大的數(shù)據(jù)量、適用何種數(shù)據(jù)形式以及能處理的數(shù)據(jù)復(fù)雜度等等，同時，算法效率分析也很重要，目前很多算法提出卻實用性較少。

2）格網(wǎng)索引法可大大縮小搜索范圍，提高了點定位三角形的效率，但在對構(gòu)網(wǎng)過程中的三角形格網(wǎng)分塊時，若單個格網(wǎng)過大，則處理格網(wǎng)中的三角形需要大量的耗時，若單個格網(wǎng)過小，則格網(wǎng)數(shù)量會很大，許多格網(wǎng)會出現(xiàn)無點的情況，對三角網(wǎng)在格網(wǎng)中的存儲、內(nèi)存占用等都有影響。在大多數(shù)情況下，格網(wǎng)索引法可以使初始三角形與目標(biāo)三角形距離很近，但少數(shù)情況下，距離卻很遠(yuǎn)，從初始三角形定位點所在的三角形需查找的三角形的數(shù)目很多，耗費了大量的時間。

3）三維領(lǐng)域的應(yīng)用較少。文獻雖然提出了一些關(guān)于Delaunay三角網(wǎng)的地形三維可視化的方法，但是大部分都是基于二維空間的，但二維空間是無法直觀地表述地形形態(tài)的，在三維領(lǐng)域中的應(yīng)用研究較少。

3.2 研究趨勢

Delaunay三角網(wǎng)生成算法一直是國內(nèi)學(xué)者研究的熱點。目前，隨著Delaunay三角網(wǎng)的應(yīng)用需求以及領(lǐng)域逐漸擴大，特別是為了解決大規(guī)模三維地形可視化，對三角網(wǎng)的構(gòu)網(wǎng)效率和穩(wěn)定性要求更高，因此有必要對Delaunay三角剖分算法繼續(xù)深入的研究。文中總結(jié)了平面域Delaunay三角網(wǎng)任意點定位算法的原理和步驟，雖已突破以往算法，在數(shù)據(jù)結(jié)構(gòu)和構(gòu)網(wǎng)效率方面取得較好性能，但還有一定的改進空間。結(jié)合本文的研究，本人認(rèn)為今后該算法的研究方向主要有以下幾個方面：

1）算法的改進。Delaunay三角網(wǎng)算法常被用來處理海量數(shù)據(jù)，算法的效率特別重要。Delaunay三角網(wǎng)任意點定位算法各有優(yōu)缺點，將多種算法合理的結(jié)合起來，相互補充，綜合應(yīng)用，從而提高Delaunay三角網(wǎng)的構(gòu)網(wǎng)效率成為目前的研究熱點。在對構(gòu)網(wǎng)過程中的三角形格網(wǎng)分塊時，格網(wǎng)的大小很重要，過大、過小都會影響算法的效率，因此需要對比分析，看怎么樣劃分網(wǎng)格才能使構(gòu)網(wǎng)效率較高，這是我下一步需要做的工作。

2）研究提出了很多算法，各有其適用范圍和條件，當(dāng)面對一個具體的地形時，選用一種或多種適合的算法非常重要。因此，需要在對各種算法進行詳細(xì)分析之后選擇相應(yīng)的算法處理。

3）三維領(lǐng)域的應(yīng)用研究。文中論述的Delaunay三角網(wǎng)是基于二維空間的，算法已趨于成熟，但二維空間是無法直觀地表述地形形態(tài)的，隨著三維地形可視化的發(fā)展需要，還需進一步研究其在三維領(lǐng)域中的應(yīng)用。

4 結(jié)束語

隨著地理信息系統(tǒng)的發(fā)展，不規(guī)則三角網(wǎng)作為其關(guān)鍵技術(shù)，在三維地形可視化中已廣泛應(yīng)用，在Delaunay三角網(wǎng)生成算法上已取得眾多學(xué)術(shù)成果。文中討論了平面域離散點構(gòu)建Delaunay三角網(wǎng)算法的研究現(xiàn)狀，總結(jié)了當(dāng)前國內(nèi)主流的點定位算法，分別從基于面積坐標(biāo)定位算法、點線關(guān)系定位算法和格網(wǎng)索引法3個方面介紹了它們的原理和步驟，但一些關(guān)鍵問題還未能完全解決，今后還需繼續(xù)研究。隨著研究的深入，該領(lǐng)域的研究將會進一步得到改善，從而更好地發(fā)揮應(yīng)用價值。

[1]魏向輝，夏春林，魯慶偉.一種基于凸包的Delaunay三角網(wǎng)算法設(shè)計[J].測繪科學(xué)，2010（5）: 152-153．

[2]李志林，朱慶.數(shù)字高程模型[M].2版.武漢:武漢大學(xué)出版社，2003.

[3]李鳳霞，劉詠梅，王曉哲，等.一種基于映射法的散亂點云Delaunay三角剖分算法[J].計算機應(yīng)用研究，2014（3）:950-953.

[4]武曉波，王世新，肖春生.Delaunay三角網(wǎng)的生成算法研究[J].測繪學(xué)報，1999（1）:28-35.

[5]吳佳奇，徐愛功.Delaunay三角網(wǎng)生長法的一種改進方法[J].測繪科學(xué)，2012（2）:103-104.

[6]Shamos M，Hoey D.Closest point problems[C]// Proceeding of the 16th Annual IEEE Symposium on Foundation of Computer Science，1975:151-162.

[7]Liu Jian-fei， Yan Jin-hui，S.H.Lo.A new insertion sequence for incremental Delaunay triangulation[J].Acta Mechanica Sinica，2013（1）: 99-109.

[8]欒曉巖.一種TIN生成算法及其三維顯示[J].海洋測繪，2004（5）:39-41.

[9]向傳杰，朱玉文.一種高效的Delaunay三角網(wǎng)合并生成技術(shù)[J].計算機應(yīng)用，2002（11）:34-36.

[10]俞亞磊，羅永龍，郭良敏，等．Delaunay三角網(wǎng)中任意約束線段嵌入的算法 [J].測繪科學(xué)，2013，38（4）:61-63.

[11]陳定造，林奕新，劉東峰.三維Delaunay三角剖分快速點定位算法研究 [J].計算機工程與科學(xué)，2009（5）:79-81.

[12]劉學(xué)軍，符鋅砂，趙建三.三角網(wǎng)數(shù)字地面模型快速構(gòu)建算法研究[J].中國公路學(xué)報，2000（2）:31-36.

[13]湯國安，劉學(xué)軍，閭國年.數(shù)字高程模型及地學(xué)分析的原理與方法[M].北京:科學(xué)出版社，2005.

[14]宋占峰，蒲浩，詹振炎.基于三角網(wǎng)數(shù)字地面模型快速定位算法的研究[J].中國鐵道科學(xué)，2002（1）: 63-66.

[15]劉少華，吳東勝，羅小龍等.Delaunay三角網(wǎng)中點目標(biāo)快速定位算法研究 [J].測繪科學(xué)，2007（2）: 69-70.

[16]李小秋，許民獻，尹志永.Delaunay三角網(wǎng)關(guān)鍵技術(shù)探討[J].測繪工程，2011（6）:61-63，67.

[17]王龍浩，王解先.基于逐點插入法的Delaunay三角網(wǎng)快速生成算法[J].工程勘察，2013（10）:75-79.

[18]Jian Hui Xi.An Improved algorithm based on incremental insertion in delaunay triangulation[J]. Applied Mechanics and Materials，2013:1691-1694.

[19]徐道柱，劉海硯.Delaunay三角網(wǎng)建立的改進算法[J].測繪與空間地理信息，2007（1）:38-41.

[20]楊小運，陳和平，顧進廣等.約束Delaunay三角網(wǎng)生成算法的研究與應(yīng)用[J].計算機工程與設(shè)計，2012（5）:1842-1846.

[21]蒲浩，宋占峰，詹振炎.快速構(gòu)建三角網(wǎng)數(shù)字地形模型方法的研究[J].中國鐵道科學(xué)，2001（6）:100-105.

[22]劉云，夏興東，黃北生.基于分治算法與逐點插入法的Delaunay三角網(wǎng)建立算法的改進 [J].現(xiàn)代測繪，2010（4）:14-16.

[23]鄒永貴，張濤.改進的平面域Delaunay三角網(wǎng)生成算法[J].計算機工程與應(yīng)用，2013（20）:171-174.

[24]張詠，劉長星，楊瑜華，等.基于融和算法的二維Delaunay三角網(wǎng)任意點定位研究 [J].測繪科學(xué)，2010（2）:85-88.

[25]張詠，楊瑜華，董漢軍.二維Delaunay三角網(wǎng)的任意點插入算法研究 [J].地理與地理信息科學(xué)，2009（4）:45-18.

[26]徐旭，李源，陳學(xué)工.一種基于插入法的Delaunay三角網(wǎng)生成算法 [J].電腦與信息技術(shù)，2010（4）: 29-31.

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

[28]趙巖，張子平.一種動態(tài)構(gòu)建Delaunay三角網(wǎng)的算法[J].測繪工程，2008（3）:24-27.

[29]李小麗，陳花竹.基于格網(wǎng)劃分的Delaunny三角剖分算法研究 [J].計算機與數(shù)字工程，2011（7）: 57-59.

[30]許多文.不規(guī)則三角網(wǎng)（TIN）的構(gòu)建及應(yīng)用[D].贛州：江西理工大學(xué)，2010.

[31]胡金星，馬照亭，吳煥萍，等.基于格網(wǎng)劃分的海量數(shù)據(jù)Delaunay三角剖分[J].測繪學(xué)報，2004（2）: 163-167.

[32]姜志偉，王山東，王伶俐，等.基于格網(wǎng)和方向法索引的Delaunny三角網(wǎng)生成算法 [J].測繪工程，2014，23（2）:57-60.

[33]王濤.地貌信息提取中的結(jié)構(gòu)化問題研究[D].武漢:武漢大學(xué)，2005.

Overview of point location algorithm of Delaunay triangulation on plane domain

LIU Qin-qin
（School of Computer Science，Shaanxi Normal University，Xi’an 710062，China）

Triangulated irregular network has been used to visualize the terrain modeling and the generation algorithm has been great concerned.The algorithms of Delaunay triangulation are the main algorithms when establishing TIN.This thesis presents the status of Delaunay triangulation algorithms and reviewed popular triangle location algorithms.Finally，the paper makes an in-depth an anlysis of the limitation of the existing literature and put forward the issues worthy of further discussion.Understanding these may give new insights into the algorithms of Delaunay triangulation and provides the guidance on the theory and method.

Delaunay；triangulation irregular network；incremental insertion；point location

TP391

：A

：1674－6236（2017）01-0047-05

2015-12-18稿件編號：201512196

劉琴琴（1990—），女，山西呂梁人，碩士研究生。研究方向：三維重建。