摘 要： 三角網生長法具有獨特的優勢，但將其擴展到三維的研究遠遠少于逐點插入法、分治法以及二者的合成算法，研究擴展三角網生長法實現三維DT剖分的算法。引入k近鄰思想優化了原始算法，時間復雜度可達O（NlogN），且改進對二維、三維算法都有效。通過AE二次開發完成了數據操作、算法實現和二維、三維顯示等功能，后續能夠較方便地添加和擴展ArcGIS相關功能以及其他數據挖掘算法模塊。用兩組6個點集數據進行實驗分析，網格構建時間對比驗證了算法性能。
關鍵詞： 三維DT剖分；三角網生長法；k近鄰思想；AE
空間剖分是實現空間索引與鄰近查找的重要途徑，與映射法、四叉樹/八叉樹法以及推進波前法（Advancing Front Technique）等針對離散點集實現的其他剖分方法相比，狄洛尼三角化DT（Delaunay Triangulation）剖分[1]具有數據結構簡單、描述能力強大、唯一的、兼具全局和局部最優等特性，因而被廣泛運用于地學、計算機圖形學和地理信息系統等領域。
DT剖分算法方面，目前國內外研究集中在逐點插入法改進、分治法與逐點插入法集成以及分布并行處理等方面[2]。逐點插入法改進一般從初始三角形構建、點定位和局部優化3個方面入手，其中局部優化是決定算法效率的關鍵，數據量大時優化過程極為耗時。分割合并思想是分治法的核心，子網構建可以采用任意算法（包括逐點插入法與生長法）實現[3]。分布并行處理相當于省去了分治法中向下遞歸的分割步驟[4]，在海量數據場合更具優勢[4-6]。
但生長法思路簡單、算法設計容易實現、構網精度高、占內存小，生長過程直接生成Delaunay三角形，無需分割、合并、點定位、局部優化等前期和后續操作。近年來，由于其在點集較小時也有較好性能，分布并行方式和分治法結合生長法的研究也開始出現[6-7]。隨著計算機硬件性能的改善以及分布并行處理方面的進步，算法設計在時空復雜度方面的約束越來越小，但對生長法原始算法改進點搜索策略[8]以極大提高算法效率也是必要的。
相比二維DT剖分已有大量成熟的研究和應用成果，三維DT剖分仍在發展之中，但由于四面體網格具有很多優秀特性，已經引起許多領域的重視[9-10]。現有文獻中的研究成果表明，雖然通過擴展3種經典的二維DT剖分算法都可以完成該任務，但在三維情況下集成分治法和逐點插入法、實現二者優勢互補的難度遠遠高于二維情況，而生長法（空間復雜度優于分治法，時間復雜度在一般情況下與逐點插入法持平）思路簡單、容易實現的優勢更加明顯。現有文獻中對此研究較少，但采用生長法實現三維DT剖分是合理的選擇。
本文將針對二維離散點集提出的生長法擴展到三維，通過優化改進提高其效率，并在AE（ArcGIS Engine）開發環境中實現。
1 算法設計
1.1 算法基礎
不同于二維DT剖分得到二維Delaunay三角形網格D-TIN（Delaunay Triangulation Irregular Network），三維DT剖分得到的是三維Delaunay四面體網格D-TEN（Delaunay Tetrahedron Network），它能保存原始數據，有精確表示目標和復雜空間拓撲關系的能力，已有一些基于 D-TIN的鄰近研究[11]，這方面的應用潛力還很大。 D-TEN是三維表達的工具，與之對應的算法設計與實現是三維數據處理分析需要解決的重要問題。D-TIN的網格單元三角形由點-線-面的結構構成，D-TEN的網格單元四面體由點-線-面-體的結構構成，其數據結構和數據模型是設計二維、三維DT剖分算法的基礎。
DT剖分算法的核心內容和關鍵步驟是Delaunay準則的運用，二維DT剖分算法的Delaunay準則包括“空圓準則”與“最大最小角準則”由二維擴展到三維，就得到三維DT剖分算法的“空球準則”（D-TEN中任一四面體的外接球內無其他點）與“最大最小立體角準則”（重置D-TEN中任何兩個相鄰四面體的公共面，最小立體角不會增大）。
需要注意兩點：若不存在4點共圓和5點共球的情況，則點集DT剖分唯一[12]；二維情況下，“空圓準則”與“最大最小角準則”等價[13]，但三維情況下，“空球準則”和“最大最小立體角準則”不等價[14]，由于“空球準則”的實現難度較小，目前實際應用中多被采用。
1.2 算法思路
生長法構建D-TEN的思路與構建D-TIN類似。參考二維情況是先構建一個起始三角形作為種子，然后以它的邊為基準向外生長；所以三維情況則是先構建一個起始四面體作為種子，然后以它的面為基準向外生長。
具體步驟為：（1）將點集中距離最近的兩點連線作為基線，根據空圓法則搜索第三點，連線成三角形作為基準面；（2）根據空球法則，在基準面的外側（基準面的頂點按逆時針順序排列，并把面的法向指向定為面的外側）找尋第4點來構建四面體，并且使構成四面體4個面的三角形的頂點，從四面體外向里看時總是按逆時針順序排列，即面的法向都朝外（和基準面重合的面法向恰好和基準面反轉）；（3）以四面體的3個新面（除基準面外）作為新的基準面。重復步驟（2）、（3）直至所有的點連線完畢。
1.3 優化改進
生長法最重要也是最耗時的環節在于以基準線（面）根據空圓（球）準則找尋第3（4）點的過程，原始算法需要遍歷點集中所有點，效率很低。1.2節的算法步驟中通過頂點逆時針排序定出線（面）的方向性，據此限定在基準線的右側（基準面的外側）搜索點，一定程度上減少了需要遍歷的點數，提高了算法效率，但還可以進一步改進。
無論是構網前預先分割區域[15]還是構網時限定搜索范圍[16]，甚至兩種方式結合采用[17-18]，都是通過限定搜索范圍來間接限制搜索點數；還可以用“距離最近”來直接限制搜索點數。參考文獻[4]用并行方式構建Delaunay三角網，子網構建方法之一采用改進的生長法。生長法第3點搜索實際上是尋找最近點問題，以最近點搜索算法找到最近點作為第3點連接為三角形，但以最近點算法直接代替準則判斷有些欠妥。參考文獻[19]中也用距離最近的概念來描述算法準則：以所選點與基準線（面）端點構成圓（球）的中心和基準線（面）的距離最近作為選點依據，此時顯然不會有其他點在圓（球）內，其實還是空圓（球）準則的變形。
Delaunay準則不是簡單地直接找距離基準線（面）或其端點最近點就可以代替的，以當前基準找點生成當前三角形（四面體）時不是簡單地連接與基準或者其端點距離最近的點就行。只能說距離基準線（面）較近的點對生成三角形（四面體）貢獻較大[18]，還需要對這些點進行準則判斷。距離最近的思路可取，但應該是距離基準線（面）的端點的“綜合距離”最近的點。也就是說，距離基準端點“都比較近”的點才可能是合適點；反過來，合適點肯定在距離基準端點“都比較近”的點中，這個“都比較近”有點難以用數學精確定義，但可以借鑒k近鄰思想。找到一個基準線（面）端點的k近鄰點集，再在該點集中以準則判斷來找到最終合適點，這種做法相當于直接限定搜索點數。由k近鄰的含義可知，如果在近鄰點集中找到某點滿足準則：近鄰點集中的其他點都在基線（面）和該點構成的三角形（四面體）的外接圓（球）外，那么對整個點集顯然也能滿足。
1975年，SHAMOS M I等人[20]研究了最近點問題，指出允許預處理時找到點集中加入新點的k個最近點時間下限為logN，并給出了k=1的算法實例和詳細論證[21]。因此構網前先對點集排序預處理，以二維為例，可以按先X后Y的規則定義點間大小關系直接用歸并排序，也可以用Hash表將空間點映射到一維再進行排序，時間復雜度均為O（NlogN），但會提高算法的空間復雜度。每次搜索先找出基準線（面）的每個端點的k個近鄰點，然后在這些近鄰點中按準則找點，k取值從1開始直到找到合適點。找近鄰點集時間復雜度為O（logN），在數量很少的近鄰點中找滿足準則的點時間復雜度為O（1）。所以，每次找第3（4）點的時間復雜度為O（logN），算法總時間復雜度為O（NlogN）。SHAMOS M I和HOEY D指出對N個點構建Delaunay三角網時間復雜度至少為O（NlogN），生長法原始算法時間復雜度最壞情況為 O（N2），最好情況為O（N3/2）[20]，經過優化，算法時間復雜度可達到該下限。
2 程序實現
綜合考慮算法實現的難度以及與已經實現的三維地理空間數據分析功能的兼容性，本文用C#在Visual Studio 2012中開發AE程序實現生長法用于二維和三維DT剖分，包括D-TIN、D-TEN的網格構建和圖形繪制，其中三維圖形繪制通過ArcGIS 3D分析擴展部分的核心模塊ArcScene[22]實現。開發環境為：聯想G530筆記本電腦，主頻2.13 GHz的Intel酷睿雙核CPU，2 GB內存，250 GB硬盤，Windows 7系統。D-TIN的2維、2.5維及D-TEN的3維網格圖形如圖1、圖2所示。
3 實驗分析
由于D-TIN、D-TEN數據模型的不同，采用兩組不同性質的空間離散點集數據分別測試D-TIN和D-TEN的構建與繪制，每組3個點集間具有同樣性質但是數據規模不同。5次重復實驗花費時間取平均值，構建時間與繪制時間分開統計，因為主要是為了對比構建時間。表1、表2分別為D-TIN、D-TIN的構建和繪制時間。
隨著點數的成倍增加，構建時間接近線性對數增長，偏差約為5%~6%，這里沒有列出做過的大于10萬數據量的實驗，但小數據量也能得出這一增長規律，說明二三維DT剖分算法復雜度接近O（NlogN），對二三維算法的改進都有效，算法高效生成網格的性能得到了驗證。繪制方式為一次性繪制整個網格圖形，但網格的繪制速度仍然遠遠小于構建速度，三維網格繪制更慢，說明AE在三維可視化圖形快速繪制方面還有待改進。
二維情況下，生長法的空間復雜度優于分治法，時間復雜度在一般情況下與逐點插入法持平，思路簡明、算法容易設計與實現是其主要優勢。三維情況下，集成分治法和逐點插入法、實現二者優勢互補的難度遠遠高于二維情況，而生長法簡單易實現等優勢更加明顯。
本文研究表明，將生長法擴展到三維用于三維DT剖分，經改進優化后算法復雜度可降低至O（NlogN），已經具備處理大數據量點集的能力。此外，計算機性能的不斷改善，結合分治法或通過并行處理，生長法生成 D-TEN完全能夠滿足處理海量數據的需求。
選擇ArcEngine開發程序實現算法，可以方便地添加和擴展ArcGIS的相關功能，如三維空間查詢、分析和運算，促進三維DT剖分的理論研究和實際應用相結合。D-TEN能表示復雜的空間拓撲關系，往往在與其他領域的應用結合中很有作用，比如由聚類等傳統數據挖掘算法發展出來空間聚類、時空聚類等。接下來的工作是根據三維DT剖分得到的點間拓撲關系編寫聚類算法，進而對空間離散點進行三維層次上的聚類分析等。
參考文獻
[1] 陳定造.空間離散點集Delaunay三角剖分的算法優化及實現[D].廣州：廣東工業大學，2008.
[2] 余杰，呂品，鄭昌文.Delaunay三角網構建方法比較研究[J].中國圖像圖形學報，2010，15（8）：1158-1167.
[3] 武曉波，王世新，肖春生.Delaunay三角網的生成算法研究[J].測繪學報，1999，28（1）：28-35.
[4] 張真.海量數據Delaunay三角網的并行構建算法[J].計算機工程與科學，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三角網生長法的并行圖像插值方法[J].計算機應用與軟件，2012，29（3）：62-68.
[7] 向傳杰，朱玉文.一種高效的Delaunay三角網合并生成技術[J].計算機應用，2002，22（11）：34-36，39.
[8] 吳佳奇，徐愛功.Delaunay三角網生長法的一種改進方法[J].測繪科學，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三角剖分算法的研究及應用[D].大連：大連海事大學，2010.
[11] 閆超德，趙艷坤，郭王，等.基于Delaunay三角網的鄰近區域測度及其應用[J].地理與地理信息科學，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四面體剖分及其相關算法的研究[D].西安：西北工業大學，2006.
[15] 閆超德，郭王，白建軍，等．最大空圓約束下的最鄰近計算方法[J]．測繪科學，2012，37（6）：157-159.
[16] 韋文杰，周振紅，彭記永，等.一種改進的Delaunay三角網生長算法[J].氣象與環境科學，2008，31（2）：80-82.
[17] 王會然.一種生長法快速構造三角網的算法研究[J].城市勘測，2010（2）：146-149.
[18] 劉剛，李永樹，張永艦.基于不規則三角網構建的網格生長算法[J].計算機工程，2011，37（12）：56-58，61.
[19] 郭際元，龔君芳.由三維離散數據生成四面體格網算法研究[J].地球科學-中國地質大學學報，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的遙感影像三維可視化技術研究與應用[J].計算機與現代化，2012（6）：54-57.