黃浩洋　鄧飛　隆振?！〕ｌ?/p>

摘要：Delaunay三角剖分在計(jì)算幾何、計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)、有限元分析、地理信息系統(tǒng)等鄰域有廣泛的應(yīng)用，是一項(xiàng)極為基礎(chǔ)且重要的離散數(shù)據(jù)網(wǎng)格化技術(shù)。生長(zhǎng)算法是一種重要的Delaunay剖分算法，具有較高的理論價(jià)值和實(shí)際意義，該算法思路簡(jiǎn)單且容易擴(kuò)展，可以拓展到三維點(diǎn)云曲面的構(gòu)造中。但是現(xiàn)有的生長(zhǎng)法效率不高，無法處理海量數(shù)據(jù)，本文經(jīng)研究提出了一種基于Delaunay空?qǐng)A性質(zhì)的改進(jìn)算法，在逐邊定向擴(kuò)展過程中直接利用Delaunay空?qǐng)A性質(zhì)，迅速縮小備選擴(kuò)展點(diǎn)集的范圍，大幅提高了三角網(wǎng)生長(zhǎng)速度。大量的隨機(jī)和規(guī)則數(shù)據(jù)測(cè)試表明該改進(jìn)算法效率提升顯著，與已有生長(zhǎng)算法相比有10倍以上的提高，且數(shù)據(jù)量越大效率提升越明顯。

關(guān)鍵詞： Delaunay三角網(wǎng)；三角網(wǎng)生長(zhǎng)算法；空外接圓特性；計(jì)算機(jī)圖形學(xué)；數(shù)據(jù)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）23-0188-04

Abstract： Delaunay triangulation in computational geometry， computer graphics， computer-aided design， finite element analysis， geographic information systems and other neighbors have a wide range of applications， is an extremely basic and important discrete data gridding techniques. Growth algorithm is an important Delaunay triangulation algorithm， with high theoretical value and practical significance， the algorithm is simple and easy extension ideas， can be extended to construct a three-dimensional point cloud in surface. But the existing growth method is not efficient， can not handle huge amounts of data， this paper presents a study by an empty circle nature of inferences based on Delaunay improved algorithm by-side expansion process through verification extension points and extensions edge meets the Delaunay empty circle the nature of inference， you can quickly narrow the range of options for expansion point set， a substantial increase in the growth rate of triangulation. A lot of random and regular data tests show that the improved algorithm efficiency significantly， compared with the existing algorithms have grown more than 10-fold increase， the greater the efficiency and the amount of data more obvious.

Key words： delaunay triangulation； growth triangulation algorithm； empty circumcircle properties； computer graphics； data

Delaunay三角剖分是計(jì)算幾何中的一種重要算法，在計(jì)算機(jī)輔助設(shè)計(jì)、三維表面重建、三維可視化、有限元分析等方面都有著十分廣泛的應(yīng)用。Delaunay三角網(wǎng)由于具有最小角最大的性質(zhì)，被公認(rèn)為最優(yōu)三角網(wǎng)。根據(jù)三角網(wǎng)構(gòu)建過程的不同，Delaunay三角剖分算法可以分為逐點(diǎn)插入、分治和生長(zhǎng)法三種。逐點(diǎn)插入法于1977年由Lawson提出的，隨后許多學(xué)者進(jìn)行了研究并改進(jìn)，如文獻(xiàn)[5]，該算法思路簡(jiǎn)單易于編程并且內(nèi)存消耗少，但是該算法需要花費(fèi)大量時(shí)間在查詢以及定位三角形，增加了它的時(shí)間復(fù)雜度。分治算法是另一種著名的構(gòu)網(wǎng)算法，許多學(xué)者也對(duì)分治算法進(jìn)行了研究并改進(jìn)如文獻(xiàn)[8]，該算法中的子網(wǎng)合并過程比較復(fù)雜，算法實(shí)現(xiàn)難度相對(duì)較大。實(shí)際應(yīng)用中逐點(diǎn)插入法因其實(shí)現(xiàn)簡(jiǎn)單、算法高效且占用內(nèi)存較小而被廣泛應(yīng)用于二維三角網(wǎng)剖分中，但是因?yàn)樗惴ū旧硖攸c(diǎn)，這兩種方法都不易直接擴(kuò)展到三維進(jìn)行三維曲面網(wǎng)格剖分。生長(zhǎng)法是一種利用三角網(wǎng)的判別法則，在逐邊擴(kuò)展中通過一定的生長(zhǎng)法則構(gòu)建Delaunay三角網(wǎng)的方法，該方法的優(yōu)點(diǎn)在于易于擴(kuò)展到三維空間，直接構(gòu)建三維三角網(wǎng)。近年來許多學(xué)者都對(duì)生長(zhǎng)算法進(jìn)行了研究[7-10]，但對(duì)算法效率改進(jìn)都不大，這大大限制了生長(zhǎng)法在實(shí)際工程鄰域中的應(yīng)用。而采用一種基于Delaunay空外接圓性質(zhì)的優(yōu)化算法，在定向擴(kuò)展中以此為條件，可以大幅度提升算法效率。

1 經(jīng)典生長(zhǎng)算法基本步驟

1.1 經(jīng)典生長(zhǎng)算法

經(jīng)典的Delaunay三角網(wǎng)的生長(zhǎng)算法是Brassel和Reif在1979年提出的。算法的基本思路是，先找出離散點(diǎn)集中相距最短的兩個(gè)數(shù)據(jù)點(diǎn)并連接成為一條Delaunay邊，此邊作為初始邊并加入擴(kuò)展隊(duì)列，尋找一個(gè)備選點(diǎn)使其與初始邊滿足Delaunay三角網(wǎng)的判別法則，檢測(cè)備選點(diǎn)與擴(kuò)展邊兩個(gè)端點(diǎn)連接的新擴(kuò)展邊的使用次數(shù)，若沒有一條由擴(kuò)展點(diǎn)形成的擴(kuò)展邊的使用次數(shù)達(dá)到2次以上則加入擴(kuò)展邊隊(duì)列，否則舍棄該備選點(diǎn)。按照上述方法依次處理所有擴(kuò)展邊，直至最終完成。算法1是經(jīng)典Delaunay三角網(wǎng)生長(zhǎng)算法，算法1如下：

1.2 通過夾角余弦擴(kuò)展

算法1中對(duì)于每一條擴(kuò)展邊，按照滿足Delaunay三角網(wǎng)的判別法則尋找擴(kuò)展點(diǎn)的過程就是算法2。算法2根據(jù)當(dāng)前已經(jīng)存在的一條Delaunay擴(kuò)展邊，遍歷所有數(shù)據(jù)點(diǎn)找到距離擴(kuò)展邊中點(diǎn)最近的點(diǎn)作為備選點(diǎn)，檢測(cè)備選點(diǎn)引出的兩條新擴(kuò)展邊的使用次數(shù)，若有任意一條新擴(kuò)展邊使用次數(shù)達(dá)到2次以上則舍棄該備選點(diǎn)，然后比較備選點(diǎn)與擴(kuò)展邊端點(diǎn)構(gòu)成的兩向量的之間夾角的余弦值。找出余弦值最小的點(diǎn)作為擴(kuò)展點(diǎn)算法2如下：

2 生長(zhǎng)算法效率的改進(jìn)

2.1 直接通過空外接圓性質(zhì)擴(kuò)展

通過表1可以看出經(jīng)典生長(zhǎng)算法效率很低，能夠處理的離散點(diǎn)集的規(guī)模較小，不具有實(shí)際應(yīng)用效果。算法1基本的三角網(wǎng)生長(zhǎng)算法的核心部分是算法2夾角余弦擴(kuò)展算法。造成算法2效率低的原因是邊擴(kuò)展過程中，需要逐點(diǎn)驗(yàn)證是否滿足最小角最大的性質(zhì)等，這樣算法2的時(shí)間復(fù)雜度為 。

空外接圓性質(zhì)是一種驗(yàn)證是否為Delaunay三角形的方法。但是可以直接將該性質(zhì)用于定向擴(kuò)展中，把經(jīng)過擴(kuò)展點(diǎn)和被擴(kuò)展邊的兩點(diǎn)的圓是否滿足空外接圓特性作為判斷條件，逐點(diǎn)檢測(cè)，直到尋找到一個(gè)滿足判斷條件的擴(kuò)展點(diǎn)，并將新擴(kuò)展邊加入擴(kuò)展邊隊(duì)列中。

2.2 空外接圓性質(zhì)擴(kuò)展的圖解以及證明

根據(jù)公式確定外界圓后，對(duì)算法2進(jìn)行改進(jìn)，當(dāng)算法2在已知擴(kuò)展邊以及擴(kuò)展方向以后，首先擴(kuò)展方向上取出任意一點(diǎn)作為擴(kuò)展點(diǎn)（為了提高算法效率，可以取生長(zhǎng)方向上距離擴(kuò)展邊最近的一個(gè)點(diǎn)）經(jīng)過兩次判定，第一次判定從擴(kuò)展點(diǎn)到擴(kuò)展邊兩個(gè)端點(diǎn)的兩條邊，有任意一條邊使用次數(shù)達(dá)到2次以上時(shí)，舍棄該擴(kuò)展點(diǎn)，第二次判定則為判斷擴(kuò)展點(diǎn)和擴(kuò)展邊的兩端點(diǎn)的圓內(nèi)部還有多少數(shù)據(jù)點(diǎn)，將這些數(shù)據(jù)點(diǎn)作為下一次備選點(diǎn)集，重復(fù)上述步驟直到備選點(diǎn)集大小為1時(shí)，并將該備選點(diǎn)作為擴(kuò)展點(diǎn)。此為算法3，是對(duì)算法2的改進(jìn)。

算法詳解：

1） 2-3行是確定創(chuàng)建兩個(gè)滾動(dòng)數(shù)組便于存放下一次與當(dāng)前需要擴(kuò)展的點(diǎn)集。

2） 5-6行是確定是否找到擴(kuò)展點(diǎn)滿足空外接圓特性，沒有則繼續(xù)查找。

3） 7-12行是根據(jù)當(dāng)前擴(kuò)展點(diǎn)與擴(kuò)展邊確定外接圓C，然后將外接圓內(nèi)部的擴(kuò)展都加入點(diǎn)集合A，并將A作為下一次檢測(cè)的點(diǎn)集。

經(jīng)過一些數(shù)據(jù)測(cè)試，得到直接利用空外接圓性質(zhì)生長(zhǎng)效率表，如表2：

3 進(jìn)一步加速生長(zhǎng)算法

3.1 齊對(duì)稱網(wǎng)格

在大量點(diǎn)集的搜索算法中，為了提高搜索效率，對(duì)于不規(guī)則的點(diǎn)集可以采用BSP算法，而對(duì)于均勻的點(diǎn)集可以采用齊對(duì)稱網(wǎng)格算法。

齊對(duì)稱網(wǎng)格算法可以對(duì)整體算法進(jìn)行改進(jìn)，首先將整個(gè)平面分成若干網(wǎng)格并將點(diǎn)與所在網(wǎng)格編號(hào)進(jìn)行映射，對(duì)于算法3，先計(jì)算每一個(gè)網(wǎng)格的外接圓與當(dāng)前圓的位置關(guān)系，如果兩圓相交再利用算法3進(jìn)一步篩選擴(kuò)展點(diǎn)，否則淘汰當(dāng)前網(wǎng)格。

3.2 使用齊對(duì)稱網(wǎng)格優(yōu)化算法

圖3是利用改進(jìn)生長(zhǎng)算法對(duì)正六邊形規(guī)則散點(diǎn)數(shù)據(jù)剖分的效果。由于規(guī)則的六邊形數(shù)據(jù)會(huì)出現(xiàn)共圓現(xiàn)象，生長(zhǎng)算法在邊擴(kuò)展時(shí)會(huì)同時(shí)找到多個(gè)備選點(diǎn)，而本文提出的改進(jìn)算法可以有效處理共圓點(diǎn)數(shù)據(jù)，不會(huì)出現(xiàn)三角形交叉的錯(cuò)誤現(xiàn)象，對(duì)規(guī)則均勻分布的數(shù)據(jù)具有完全一致的剖分效果。

4.2 生長(zhǎng)法效率的對(duì)比

本文提出的改進(jìn)的生長(zhǎng)算法利用Delaunay空外接圓性質(zhì)推論大幅度提高了三角網(wǎng)生長(zhǎng)速度，與現(xiàn)有生長(zhǎng)算法相比效率提升明顯，實(shí)驗(yàn)表明對(duì)于大規(guī)模數(shù)據(jù)該改進(jìn)算法效率提升達(dá)到10倍以上，且數(shù)據(jù)量越大效率提升越明顯。表4列出了本文提出的改進(jìn)算法與其他文獻(xiàn)提出的生長(zhǎng)法效率的對(duì)比。為了確保對(duì)比的客觀和真實(shí)性，各種算法統(tǒng)一使用VS2008開發(fā)環(huán)境實(shí)現(xiàn)，在同一臺(tái)測(cè)試機(jī)器上測(cè)試，測(cè)試機(jī)硬件條件：CPU為Intel-3610QM 2.3GHZ，內(nèi)存4GB。

此處所對(duì)比的文獻(xiàn)是參考文獻(xiàn)中[4]，[9]，[10]文獻(xiàn)。

5 結(jié)論

Delaunay三角剖分在計(jì)算機(jī)輔助設(shè)計(jì)、三維表面重建、三維可視化、有限元分析等方面都有著十分廣泛的應(yīng)用，是極為重要的一項(xiàng)預(yù)處理技術(shù)。改進(jìn)的Delaunay生長(zhǎng)算法依據(jù)三角剖分中的空?qǐng)A特性，在確定擴(kuò)展點(diǎn)的過程中，加入齊對(duì)稱網(wǎng)格，判斷每個(gè)網(wǎng)格與當(dāng)前擴(kuò)展邊的位置關(guān)系，確定相交關(guān)系后再進(jìn)行遍歷，可以大大縮小搜索點(diǎn)的范圍，提高算法的效率。將改進(jìn)的Delaunay生長(zhǎng)算法與插入算法進(jìn)行對(duì)比，輸入規(guī)模相同的離散點(diǎn)集，得到了相同的三角網(wǎng)，驗(yàn)證了本算法的正確性。本算法思路簡(jiǎn)單，易于擴(kuò)展，可靠性高，生長(zhǎng)速度快，可以對(duì)10萬級(jí)甚至百萬級(jí)別點(diǎn)集合進(jìn)行三角網(wǎng)構(gòu)建，具有明顯的實(shí)際應(yīng)用效果，設(shè)計(jì)思路對(duì)于三維空間的三角剖分也有借鑒意義。

參考文獻(xiàn)：

[1] Ruprecht D，Muller H. Spatial free-form Deformation with Scatte red Data Interpolation Methods[J]. Computers and Graphics， 1995，19（1）：63-71.

[2] Ledoux H， Gold C. An Efficient Natural Neighbour Interpolation Algorithm for Geoscientific Modelling[J].Developments in Spatial Data Handling，2005：97-108.

[3] Perter Su，Robert L Scot Drysdale. A Comparisonof Ssequential，DelaunayTriangulation，Algorithms[J]. Computational Geometry，1997（7）：361-385.

[4] B Yang，S Shang .Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation American Journal of Computational Mathematics[J]. American Journal of Computational Mathematics，2012，2（4）：336-340.

[5] XU Xu，LI Yuan，XG Chen. One algorithm of the Delaunay Triangulation on the Basis of Inserting Algorithm[J]. Computer & Information Technology， 2010

[6] 祝志恒.構(gòu)建Delaunay三角網(wǎng)的一種新型生長(zhǎng)法——?dú)ね獠迦敕╗J].鐵道科學(xué)與工程學(xué)報(bào)，2007，4（6）：67-72

[7] 趙文芳等.離散點(diǎn)集Delaunay三角網(wǎng)生成算法改進(jìn)與軟件開發(fā)[J].測(cè)繪工程，2003，12（4）：22-25.

[8] 劉云，夏興東，黃北生.Delaunay三角網(wǎng)通用合并算子其分治算法的簡(jiǎn)化[J].現(xiàn)代測(cè)繪，2010，33（4）：14-16.

[9] 孫繼忠，胡艷.基于Delaunay三角剖分生成voronoi圖算法[J].計(jì)算機(jī)應(yīng)用，2010，30（1）：75-77.

[10] 陳學(xué)工，陳樹強(qiáng)，王麗青.基于凸殼技術(shù)的Delaunay三角網(wǎng)生成算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（06）：27-29.

[11] 周婷，彭正洪，密新武.Delaunay三角網(wǎng)生長(zhǎng)算法改進(jìn)與實(shí)現(xiàn)[J].圖學(xué)學(xué)報(bào)，2013，34（5）：12-15.

[12] 姬安召，藍(lán)燕.三角網(wǎng)增長(zhǎng)算法構(gòu)建Delaunay三角網(wǎng)DEM的原理與實(shí)現(xiàn)[J].測(cè)繪，2009，32（2）：65-69.