二維離散點集Delaunay三角網(wǎng)生長算法的改進

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

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

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

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

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

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

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

1.2 通過夾角余弦擴展

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

2 生長算法效率的改進

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

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

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

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

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

算法詳解：

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

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

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

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

3 進一步加速生長算法

3.1 齊對稱網(wǎng)格

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

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

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

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

4.2 生長法效率的對比

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

此處所對比的文獻是參考文獻中[4]，[9]，[10]文獻。

5 結(jié)論

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

參考文獻：

[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)的一種新型生長法——殼外插入法[J].鐵道科學與工程學報，2007，4（6）：67-72

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

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

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

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

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

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