摘  要： 三角網(wǎng)生長法具有獨特的優(yōu)勢，但將其擴展到三維的研究遠(yuǎn)遠(yuǎn)少于逐點插入法、分治法以及二者的合成算法，研究擴展三角網(wǎng)生長法實現(xiàn)三維DT剖分的算法。引入k近鄰思想優(yōu)化了原始算法，時間復(fù)雜度可達(dá)O（NlogN），且改進(jìn)對二維、三維算法都有效。通過AE二次開發(fā)完成了數(shù)據(jù)操作、算法實現(xiàn)和二維、三維顯示等功能，后續(xù)能夠較方便地添加和擴展ArcGIS相關(guān)功能以及其他數(shù)據(jù)挖掘算法模塊。用兩組6個點集數(shù)據(jù)進(jìn)行實驗分析，網(wǎng)格構(gòu)建時間對比驗證了算法性能。

　　關(guān)鍵詞： 三維DT剖分；三角網(wǎng)生長法；k近鄰思想；AE

　　空間剖分是實現(xiàn)空間索引與鄰近查找的重要途徑，與映射法、四叉樹/八叉樹法以及推進(jìn)波前法（Advancing Front Technique）等針對離散點集實現(xiàn)的其他剖分方法相比，狄洛尼三角化DT（Delaunay Triangulation）剖分[1]具有數(shù)據(jù)結(jié)構(gòu)簡單、描述能力強大、唯一的、兼具全局和局部最優(yōu)等特性，因而被廣泛運用于地學(xué)、計算機圖形學(xué)和地理信息系統(tǒng)等領(lǐng)域。

　　DT剖分算法方面，目前國內(nèi)外研究集中在逐點插入法改進(jìn)、分治法與逐點插入法集成以及分布并行處理等方面[2]。逐點插入法改進(jìn)一般從初始三角形構(gòu)建、點定位和局部優(yōu)化3個方面入手，其中局部優(yōu)化是決定算法效率的關(guān)鍵，數(shù)據(jù)量大時優(yōu)化過程極為耗時。分割合并思想是分治法的核心，子網(wǎng)構(gòu)建可以采用任意算法（包括逐點插入法與生長法）實現(xiàn)[3]。分布并行處理相當(dāng)于省去了分治法中向下遞歸的分割步驟[4]，在海量數(shù)據(jù)場合更具優(yōu)勢[4-6]。

　　但生長法思路簡單、算法設(shè)計容易實現(xiàn)、構(gòu)網(wǎng)精度高、占內(nèi)存小，生長過程直接生成Delaunay三角形，無需分割、合并、點定位、局部優(yōu)化等前期和后續(xù)操作。近年來，由于其在點集較小時也有較好性能，分布并行方式和分治法結(jié)合生長法的研究也開始出現(xiàn)[6-7]。隨著計算機硬件性能的改善以及分布并行處理方面的進(jìn)步，算法設(shè)計在時空復(fù)雜度方面的約束越來越小，但對生長法原始算法改進(jìn)點搜索策略[8]以極大提高算法效率也是必要的。

　　相比二維DT剖分已有大量成熟的研究和應(yīng)用成果，三維DT剖分仍在發(fā)展之中，但由于四面體網(wǎng)格具有很多優(yōu)秀特性，已經(jīng)引起許多領(lǐng)域的重視[9-10]?，F(xiàn)有文獻(xiàn)中的研究成果表明，雖然通過擴展3種經(jīng)典的二維DT剖分算法都可以完成該任務(wù)，但在三維情況下集成分治法和逐點插入法、實現(xiàn)二者優(yōu)勢互補的難度遠(yuǎn)遠(yuǎn)高于二維情況，而生長法（空間復(fù)雜度優(yōu)于分治法，時間復(fù)雜度在一般情況下與逐點插入法持平）思路簡單、容易實現(xiàn)的優(yōu)勢更加明顯?，F(xiàn)有文獻(xiàn)中對此研究較少，但采用生長法實現(xiàn)三維DT剖分是合理的選擇。

　　本文將針對二維離散點集提出的生長法擴展到三維，通過優(yōu)化改進(jìn)提高其效率，并在AE（ArcGIS Engine）開發(fā)環(huán)境中實現(xiàn)。

1 算法設(shè)計

　　1.1 算法基礎(chǔ)

　　不同于二維DT剖分得到二維Delaunay三角形網(wǎng)格D-TIN（Delaunay Triangulation Irregular Network），三維DT剖分得到的是三維Delaunay四面體網(wǎng)格D-TEN（Delaunay Tetrahedron Network），它能保存原始數(shù)據(jù)，有精確表示目標(biāo)和復(fù)雜空間拓?fù)潢P(guān)系的能力，已有一些基于  D-TIN的鄰近研究[11]，這方面的應(yīng)用潛力還很大。  D-TEN是三維表達(dá)的工具，與之對應(yīng)的算法設(shè)計與實現(xiàn)是三維數(shù)據(jù)處理分析需要解決的重要問題。D-TIN的網(wǎng)格單元三角形由點-線-面的結(jié)構(gòu)構(gòu)成，D-TEN的網(wǎng)格單元四面體由點-線-面-體的結(jié)構(gòu)構(gòu)成，其數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)模型是設(shè)計二維、三維DT剖分算法的基礎(chǔ)。

　　DT剖分算法的核心內(nèi)容和關(guān)鍵步驟是Delaunay準(zhǔn)則的運用，二維DT剖分算法的Delaunay準(zhǔn)則包括“空圓準(zhǔn)則”與“最大最小角準(zhǔn)則”由二維擴展到三維，就得到三維DT剖分算法的“空球準(zhǔn)則”（D-TEN中任一四面體的外接球內(nèi)無其他點）與“最大最小立體角準(zhǔn)則”（重置D-TEN中任何兩個相鄰四面體的公共面，最小立體角不會增大）。

　　需要注意兩點：若不存在4點共圓和5點共球的情況，則點集DT剖分唯一[12]；二維情況下，“空圓準(zhǔn)則”與“最大最小角準(zhǔn)則”等價[13]，但三維情況下，“空球準(zhǔn)則”和“最大最小立體角準(zhǔn)則”不等價[14]，由于“空球準(zhǔn)則”的實現(xiàn)難度較小，目前實際應(yīng)用中多被采用。

　　1.2 算法思路

　　生長法構(gòu)建D-TEN的思路與構(gòu)建D-TIN類似。參考二維情況是先構(gòu)建一個起始三角形作為種子，然后以它的邊為基準(zhǔn)向外生長；所以三維情況則是先構(gòu)建一個起始四面體作為種子，然后以它的面為基準(zhǔn)向外生長。

　　具體步驟為：（1）將點集中距離最近的兩點連線作為基線，根據(jù)空圓法則搜索第三點，連線成三角形作為基準(zhǔn)面；（2）根據(jù)空球法則，在基準(zhǔn)面的外側(cè)（基準(zhǔn)面的頂點按逆時針順序排列，并把面的法向指向定為面的外側(cè)）找尋第4點來構(gòu)建四面體，并且使構(gòu)成四面體4個面的三角形的頂點，從四面體外向里看時總是按逆時針順序排列，即面的法向都朝外（和基準(zhǔn)面重合的面法向恰好和基準(zhǔn)面反轉(zhuǎn)）；（3）以四面體的3個新面（除基準(zhǔn)面外）作為新的基準(zhǔn)面。重復(fù)步驟（2）、（3）直至所有的點連線完畢。

　　1.3 優(yōu)化改進(jìn)

　　生長法最重要也是最耗時的環(huán)節(jié)在于以基準(zhǔn)線（面）根據(jù)空圓（球）準(zhǔn)則找尋第3（4）點的過程，原始算法需要遍歷點集中所有點，效率很低。1.2節(jié)的算法步驟中通過頂點逆時針排序定出線（面）的方向性，據(jù)此限定在基準(zhǔn)線的右側(cè)（基準(zhǔn)面的外側(cè)）搜索點，一定程度上減少了需要遍歷的點數(shù)，提高了算法效率，但還可以進(jìn)一步改進(jìn)。

　　無論是構(gòu)網(wǎng)前預(yù)先分割區(qū)域[15]還是構(gòu)網(wǎng)時限定搜索范圍[16]，甚至兩種方式結(jié)合采用[17-18]，都是通過限定搜索范圍來間接限制搜索點數(shù)；還可以用“距離最近”來直接限制搜索點數(shù)。參考文獻(xiàn)[4]用并行方式構(gòu)建Delaunay三角網(wǎng)，子網(wǎng)構(gòu)建方法之一采用改進(jìn)的生長法。生長法第3點搜索實際上是尋找最近點問題，以最近點搜索算法找到最近點作為第3點連接為三角形，但以最近點算法直接代替準(zhǔn)則判斷有些欠妥。參考文獻(xiàn)[19]中也用距離最近的概念來描述算法準(zhǔn)則：以所選點與基準(zhǔn)線（面）端點構(gòu)成圓（球）的中心和基準(zhǔn)線（面）的距離最近作為選點依據(jù)，此時顯然不會有其他點在圓（球）內(nèi)，其實還是空圓（球）準(zhǔn)則的變形。

　　Delaunay準(zhǔn)則不是簡單地直接找距離基準(zhǔn)線（面）或其端點最近點就可以代替的，以當(dāng)前基準(zhǔn)找點生成當(dāng)前三角形（四面體）時不是簡單地連接與基準(zhǔn)或者其端點距離最近的點就行。只能說距離基準(zhǔn)線（面）較近的點對生成三角形（四面體）貢獻(xiàn)較大[18]，還需要對這些點進(jìn)行準(zhǔn)則判斷。距離最近的思路可取，但應(yīng)該是距離基準(zhǔn)線（面）的端點的“綜合距離”最近的點。也就是說，距離基準(zhǔn)端點“都比較近”的點才可能是合適點；反過來，合適點肯定在距離基準(zhǔn)端點“都比較近”的點中，這個“都比較近”有點難以用數(shù)學(xué)精確定義，但可以借鑒k近鄰思想。找到一個基準(zhǔn)線（面）端點的k近鄰點集，再在該點集中以準(zhǔn)則判斷來找到最終合適點，這種做法相當(dāng)于直接限定搜索點數(shù)。由k近鄰的含義可知，如果在近鄰點集中找到某點滿足準(zhǔn)則：近鄰點集中的其他點都在基線（面）和該點構(gòu)成的三角形（四面體）的外接圓（球）外，那么對整個點集顯然也能滿足。

　　1975年，SHAMOS M I等人[20]研究了最近點問題，指出允許預(yù)處理時找到點集中加入新點的k個最近點時間下限為logN，并給出了k=1的算法實例和詳細(xì)論證[21]。因此構(gòu)網(wǎng)前先對點集排序預(yù)處理，以二維為例，可以按先X后Y的規(guī)則定義點間大小關(guān)系直接用歸并排序，也可以用Hash表將空間點映射到一維再進(jìn)行排序，時間復(fù)雜度均為O（NlogN），但會提高算法的空間復(fù)雜度。每次搜索先找出基準(zhǔn)線（面）的每個端點的k個近鄰點，然后在這些近鄰點中按準(zhǔn)則找點，k取值從1開始直到找到合適點。找近鄰點集時間復(fù)雜度為O（logN），在數(shù)量很少的近鄰點中找滿足準(zhǔn)則的點時間復(fù)雜度為O（1）。所以，每次找第3（4）點的時間復(fù)雜度為O（logN），算法總時間復(fù)雜度為O（NlogN）。SHAMOS M I和HOEY D指出對N個點構(gòu)建Delaunay三角網(wǎng)時間復(fù)雜度至少為O（NlogN），生長法原始算法時間復(fù)雜度最壞情況為   O（N2），最好情況為O（N3/2）[20]，經(jīng)過優(yōu)化，算法時間復(fù)雜度可達(dá)到該下限。

2 程序?qū)崿F(xiàn)

　　綜合考慮算法實現(xiàn)的難度以及與已經(jīng)實現(xiàn)的三維地理空間數(shù)據(jù)分析功能的兼容性，本文用C#在Visual Studio 2012中開發(fā)AE程序?qū)崿F(xiàn)生長法用于二維和三維DT剖分，包括D-TIN、D-TEN的網(wǎng)格構(gòu)建和圖形繪制，其中三維圖形繪制通過ArcGIS 3D分析擴展部分的核心模塊ArcScene[22]實現(xiàn)。開發(fā)環(huán)境為：聯(lián)想G530筆記本電腦，主頻2.13 GHz的Intel酷睿雙核CPU，2 GB內(nèi)存，250 GB硬盤，Windows 7系統(tǒng)。D-TIN的2維、2.5維及D-TEN的3維網(wǎng)格圖形如圖1、圖2所示。

3 實驗分析

　　由于D-TIN、D-TEN數(shù)據(jù)模型的不同，采用兩組不同性質(zhì)的空間離散點集數(shù)據(jù)分別測試D-TIN和D-TEN的構(gòu)建與繪制，每組3個點集間具有同樣性質(zhì)但是數(shù)據(jù)規(guī)模不同。5次重復(fù)實驗花費時間取平均值，構(gòu)建時間與繪制時間分開統(tǒng)計，因為主要是為了對比構(gòu)建時間。表1、表2分別為D-TIN、D-TIN的構(gòu)建和繪制時間。

　　隨著點數(shù)的成倍增加，構(gòu)建時間接近線性對數(shù)增長，偏差約為5%~6%，這里沒有列出做過的大于10萬數(shù)據(jù)量的實驗，但小數(shù)據(jù)量也能得出這一增長規(guī)律，說明二三維DT剖分算法復(fù)雜度接近O（NlogN），對二三維算法的改進(jìn)都有效，算法高效生成網(wǎng)格的性能得到了驗證。繪制方式為一次性繪制整個網(wǎng)格圖形，但網(wǎng)格的繪制速度仍然遠(yuǎn)遠(yuǎn)小于構(gòu)建速度，三維網(wǎng)格繪制更慢，說明AE在三維可視化圖形快速繪制方面還有待改進(jìn)。

　　二維情況下，生長法的空間復(fù)雜度優(yōu)于分治法，時間復(fù)雜度在一般情況下與逐點插入法持平，思路簡明、算法容易設(shè)計與實現(xiàn)是其主要優(yōu)勢。三維情況下，集成分治法和逐點插入法、實現(xiàn)二者優(yōu)勢互補的難度遠(yuǎn)遠(yuǎn)高于二維情況，而生長法簡單易實現(xiàn)等優(yōu)勢更加明顯。

　　本文研究表明，將生長法擴展到三維用于三維DT剖分，經(jīng)改進(jìn)優(yōu)化后算法復(fù)雜度可降低至O（NlogN），已經(jīng)具備處理大數(shù)據(jù)量點集的能力。此外，計算機性能的不斷改善，結(jié)合分治法或通過并行處理，生長法生成 D-TEN完全能夠滿足處理海量數(shù)據(jù)的需求。

　　選擇ArcEngine開發(fā)程序?qū)崿F(xiàn)算法，可以方便地添加和擴展ArcGIS的相關(guān)功能，如三維空間查詢、分析和運算，促進(jìn)三維DT剖分的理論研究和實際應(yīng)用相結(jié)合。D-TEN能表示復(fù)雜的空間拓?fù)潢P(guān)系，往往在與其他領(lǐng)域的應(yīng)用結(jié)合中很有作用，比如由聚類等傳統(tǒng)數(shù)據(jù)挖掘算法發(fā)展出來空間聚類、時空聚類等。接下來的工作是根據(jù)三維DT剖分得到的點間拓?fù)潢P(guān)系編寫聚類算法，進(jìn)而對空間離散點進(jìn)行三維層次上的聚類分析等。

　　參考文獻(xiàn)

　　[1] 陳定造.空間離散點集Delaunay三角剖分的算法優(yōu)化及實現(xiàn)[D].廣州：廣東工業(yè)大學(xué)，2008.

　　[2] 余杰，呂品，鄭昌文.Delaunay三角網(wǎng)構(gòu)建方法比較研究[J].中國圖像圖形學(xué)報，2010，15（8）：1158-1167.

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

　　[4] 張真.海量數(shù)據(jù)Delaunay三角網(wǎng)的并行構(gòu)建算法[J].計算機工程與科學(xué)，2013，35（4）：1-7.

　　[5] BLANDFORD D K， BLELLOCH E G， KADOW C. Engineering a compact parallel Delaunay algorithm in 3D[C].Proceedings of the 22th ACM Symposium on Computational Geometry， New York： ACM， 2006：292-300.

　　[6] 袁舒，楊烜.基于Delaunay三角網(wǎng)生長法的并行圖像插值方法[J].計算機應(yīng)用與軟件，2012，29（3）：62-68.

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

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

　　[9] Li Yanbo， Zhang Tianchi， Zhang Jing， et al. Almost-Good delaunay tetrahedron modeling for surgery simulation[C]. Proceedings of 2010 Second International Asia Symposium on Intelligent Interaction and Affective Computing and 2010 Second International Conference on Innovation Management （ASIA-ICIM 2010）， Wuhan：ASIA-ICIM， 2010：611-621.

　　[10] 李麗.三維空間Delaunay三角剖分算法的研究及應(yīng)用[D].大連：大連海事大學(xué)，2010.

　　[11] 閆超德，趙艷坤，郭王，等.基于Delaunay三角網(wǎng)的鄰近區(qū)域測度及其應(yīng)用[J].地理與地理信息科學(xué)，2013，29（2）：125-126.

　　[12] CAVENDISH J C， FIELD D A， FREY W H. An approach to automatic three-dimensional finite element mesh generation[J]. International Journal for Numerical Methods in Engineering，1985，21（2）：329-347.

　　[13] LEE D T， SCHACHTER B J. Two algorithms for constructing a delaunay triangulation[J]. International Journal of Computer and Information Sciences， 1980，9（3）：219-242.

　　[14] 崔凌國.約束Delaunay四面體剖分及其相關(guān)算法的研究[D].西安：西北工業(yè)大學(xué)，2006.

　　[15] 閆超德，郭王，白建軍，等．最大空圓約束下的最鄰近計算方法[J]．測繪科學(xué)，2012，37（6）：157-159.

　　[16] 韋文杰，周振紅，彭記永，等.一種改進(jìn)的Delaunay三角網(wǎng)生長算法[J].氣象與環(huán)境科學(xué)，2008，31（2）：80-82.

　　[17] 王會然.一種生長法快速構(gòu)造三角網(wǎng)的算法研究[J].城市勘測，2010（2）：146-149.

　　[18] 劉剛，李永樹，張永艦.基于不規(guī)則三角網(wǎng)構(gòu)建的網(wǎng)格生長算法[J].計算機工程，2011，37（12）：56-58，61.

　　[19] 郭際元，龔君芳.由三維離散數(shù)據(jù)生成四面體格網(wǎng)算法研究[J].地球科學(xué)-中國地質(zhì)大學(xué)學(xué)報，2002，27（3）：271-273.

　　[20] SHAMOS M I， HOEY D. Closest-point problems[C]. Proceedings of the 16th Annual Symposium on the Foundations of Computer Science（FOCS），1975：151-162.

　　[21] SHAMOS M I. Geometric complexity[C]. Proceedings of the Seventh ACM Symposium on the Theory of Computing，1975.

　　[22] 王曉利，馬大喜.基于ArcScene的遙感影像三維可視化技術(shù)研究與應(yīng)用[J].計算機與現(xiàn)代化，2012（6）：54-57.