網(wǎng)格總分并行式Delaunay三角網(wǎng)建模方法

韓元利

中鐵第四勘察設(shè)計院集團有限公司，湖北 武漢430063

1 引 言

Delaunay三角網(wǎng)（Delaunay triangulated irregular network，Delaunay－TIN）的構(gòu)建通常有兩種方法：一是根據(jù)其幾何特性給出的依據(jù)“任意四點不共圓”特性［1］的構(gòu)建法；二是基于Voronoi圖衍生定義的生成法。

相較于Delaunay三角網(wǎng)來自Voronoi圖的定義而言，構(gòu)建法因為直接面向點集數(shù)據(jù)構(gòu)模，在國內(nèi)外研究應(yīng)用更多，文獻［2］給出了學(xué)術(shù)上認可的Delaunay三角網(wǎng)構(gòu)TIN的主流方法，包括插入法、生長法及分治－綜合方法，其中逐點插入法［3］因為簡單穩(wěn)定而被廣泛應(yīng)用，但由于插入法的效率會隨著三角網(wǎng)數(shù)量的增加急劇下降，不適合大規(guī)模點集構(gòu)TIN；生長算法［4］因為確立生成點困難且效率不占優(yōu)勢因而應(yīng)用受限；分治－綜合法［5－7］通常以插入法實現(xiàn)子網(wǎng)格內(nèi)部建模后再進行子網(wǎng)的整合，但整合的過程相對比較復(fù)雜耗時。文獻［8—9］分別給出了兩種基于Voronoi圖的生成算法，生成法需要首先構(gòu)建Voronoi圖，構(gòu)建的方法多種多樣，效率上不能簡單與直接構(gòu)建法相比。

三角網(wǎng)構(gòu)建算法從構(gòu)TIN形式上講分為完全Delaunay三角網(wǎng)與受限D(zhuǎn)elaunay三角網(wǎng)（constrained Delaunay triangulation，CDT），文獻［10］就是為保障諸如道路、河溝等表達而在前者基礎(chǔ)上進行約束的構(gòu)TIN方法。絕大部分三角網(wǎng)的生成算法是構(gòu)建于歐氏空間的，文獻［11］基于應(yīng)用的需要從球空間角度論述了一種立面構(gòu)TIN方法，而文獻［12］基于數(shù)據(jù)來源的不同研究了在柵格空間中進行構(gòu)TIN的不同實現(xiàn)。

插入法構(gòu)TIN的基本方法就是在已知網(wǎng)上確立插入點的影響域［13］，通過插入點與影響域的邊界重構(gòu)替代原來的域內(nèi)三角形，外接圓的判斷方法雖然簡單，但如何快速從大量急劇增加的三角形中查找到域內(nèi)三角形，成為海量空間點構(gòu)TIN的重要瓶頸。分治－綜合建模方法就是采取化整為零、分大為小的方法實現(xiàn)對大空間的網(wǎng)格分割后在較小的網(wǎng)格中按插入法各自構(gòu)TIN得到各個網(wǎng)格的子三角網(wǎng)，然后再實現(xiàn)各個子網(wǎng)的合并。其困難是子網(wǎng)綜合的復(fù)雜性既影響了構(gòu)TIN的穩(wěn)定性，也增加了額外的時間消耗，同時遞歸的處理方式也不能達到并行處理的效果。

在這3種傳統(tǒng)算法之上，文獻［13—14］還給出了一種利用良好的數(shù)據(jù)組織形式或虛擬網(wǎng)格結(jié)構(gòu)從邏輯上區(qū)域化記錄一個搜索起始三角形，顯著提高插入點影響域搜索效率的方法，是一種邏輯上區(qū)域化的改進型插入法，沒有復(fù)雜的子網(wǎng)合并過程。

在應(yīng)用層面，隨著大數(shù)據(jù)時代的到來，各種并行構(gòu) TIN［15］、多核異構(gòu)并行構(gòu) TIN［16］或是流式構(gòu)TIN［17］應(yīng)對大數(shù)據(jù)高效需求的算法研究成為熱點。本文結(jié)合對空間的物理分割，借鑒分治－綜合法的局部處理策略，融合生長法的膨脹思維，逆向思維，采取相反的先分后總、由外而內(nèi)的收縮建模方法，避免了網(wǎng)格之間復(fù)雜的綜合過程，是一種新型的總分式空間建模方法。與分治方法相同的是，其根本實現(xiàn)構(gòu)TIN的手段也是插入法構(gòu)TIN。通過基于LOD概念的層次網(wǎng)格劃分，實現(xiàn)了由整體到局部、先總后分的構(gòu)TIN實現(xiàn)，并運用多線程技術(shù)高效地實現(xiàn)了各個子網(wǎng)格的并行構(gòu)TIN。

2 基本原理

設(shè)海量點云數(shù)據(jù)N在投影空間上構(gòu)成的最小外接矩形區(qū)域為S，算法的核心思想是：對大空間S細分為｛S0，S1，S2，…，Sm｝個子空間，使得任意兩個子空間Si，Sj有Si∩Sj＝φ，且有S＝。

與傳統(tǒng)的分治－綜合法相比，為了讓網(wǎng)格間的綜合變得相對簡單，通常采用四叉樹的均分網(wǎng)格形式［18］進行空間劃分，即相同層級的網(wǎng)格其空間大小是相同的，但本文算法中，由于沒有后期復(fù)雜的網(wǎng)格拓撲綜合過程，對網(wǎng)格的劃分完全可以根據(jù)點群的局部密集度來進行。其劃分原則是假定點是均勻分布的，按照總共需要的子網(wǎng)塊數(shù)及空間的縱橫比來確立。如以規(guī)模上限LN＝200為例，當(dāng)一個網(wǎng)格里的點數(shù)大于200時，該網(wǎng)格需要平均地分為C×R個子網(wǎng)格，結(jié)合網(wǎng)格的空間大小（設(shè)網(wǎng)格空間長WG、HG）與網(wǎng)格內(nèi)點的數(shù)量N，C與R的計算規(guī)則如下

按式（1）對整個大區(qū)域進行遞歸邏輯空間分割后，點云與網(wǎng)格的映射關(guān)系如圖1所示。

圖1 自適應(yīng)網(wǎng)格劃分圖Fig.1 Self－adaptive grid division

定義：對給定的Delaunay三角網(wǎng)，頂點P及網(wǎng)格S，如果頂點P的所有三角形均包含于網(wǎng)格S內(nèi)部，則稱點P為網(wǎng)格S中的邏輯內(nèi)部點，P∈Inner｛S｝；否則稱P為邏輯外部點，P∈Outer｛S｝，如圖2所示。

圖2中對給定的網(wǎng)格S，M、N均為網(wǎng)格中的頂點，物理劃分上

邏輯劃分上

很顯然有

圖2 網(wǎng)格的邏輯內(nèi)部點定義Fig.2 Definition of grid logical interior points

由式（2）可見物理劃分與邏輯劃分上的不同特性，上述判斷的依據(jù)是根據(jù)已經(jīng)存在的Delaunay三角網(wǎng)。三角網(wǎng)的構(gòu)建實質(zhì)是建立點與點之間的拓撲邏輯關(guān)系，根據(jù)Delaunay三角網(wǎng)的構(gòu)建特性，對給定的點集，其Delaunay三角網(wǎng)是唯一確定的［19］，與建模的過程無關(guān)。

對給定的點云集N及給定的網(wǎng)格區(qū)域S，無論是否已對點云構(gòu)建Delaunay三角網(wǎng)，S中的任意點P其歸屬于Inner｛S｝還是歸屬于Outer｛S｝是確定的。這一認識對總分并行式構(gòu)建三角網(wǎng)思想提供了根本的理論支持：對每一個子網(wǎng)格Si中的所有點再進行邏輯劃分，預(yù)先形成網(wǎng)格內(nèi)部Inner｛Si｝與網(wǎng)格外部 Outer｛Si｝的集合。首先從總體布局上對每一個網(wǎng)格邏輯外部點Outer｛Si｝利用傳統(tǒng)的Delaunay插入法建立全局三角網(wǎng)，然后分別對各個網(wǎng)格的邏輯內(nèi)部點Inner｛Si｝進行構(gòu)TIN，由前述定義可知，Inner｛Si｝中的點拓撲三角形都會局限于網(wǎng)格內(nèi)部，有益于各網(wǎng)格并行構(gòu)TIN的實施。

困難的是，在未建立完整的三角網(wǎng)之前，雖然點P與網(wǎng)格Si的內(nèi)外部關(guān)系是確定的，但是卻難以確立，從而導(dǎo)致上述思想的實施困難。但可以依據(jù)空間點的鄰近關(guān)系對Si中每一個點P建立其對網(wǎng)格Si的影響力因子公式，定義為

式中，Oi為網(wǎng)格Si的中心點，即網(wǎng)格中的點離網(wǎng)格中心距離越近，對網(wǎng)格中心的影響力越大，越有可能是屬于Inner｛Si｝，反之則越有可能屬于Outer｛Si｝，如圖3所示，設(shè)ξ為某一方向上的界定邏輯內(nèi)外部點的影響因子閾值，則有

可見存在方向與分割閾值ξ界定的困難，但如果將網(wǎng)格Si中的所有點按到中心Oi的距離從大到小進行排序，則隊列前面的點比隊列后面的點更有可能屬于Outer｛Si｝。

圖3 基于方位劃分的網(wǎng)格邏輯內(nèi)外部界定Fig.3 Definition of grid logical interior points

在此基礎(chǔ)上要界定方向與分割閾值ξ，首先要確立一個方向原點，由于網(wǎng)格中心Oi并不真實地存在于網(wǎng)格Si中，為避免方向判斷上的困難，選取離中心最近的隊列尾結(jié)點作為方向的原點。

定義：在網(wǎng)格Si的所有頂點集中，定義最靠近網(wǎng)格中心的頂點為網(wǎng)格的參考中心點，記為。

為了建立各網(wǎng)格的方向三角形，對Si頂點隊列進行微調(diào)整，將置首，優(yōu)先構(gòu)建起網(wǎng)格的方向三角形及網(wǎng)格間的均衡三角網(wǎng)。如此對方向的確立可以按與關(guān)聯(lián)的方向三角形來進行判斷，n個關(guān)聯(lián)三角形就可以將周圍360°方向角劃分為n個具體的區(qū)域方位。

定義：在總分式網(wǎng)格建模過程中，網(wǎng)格Si中以為頂點的所有三角形稱為方向三角形。由方向三角形所覆蓋的區(qū)域稱為網(wǎng)格的閉包區(qū)域DT。閉包區(qū)域上所有邊界頂點均位于網(wǎng)格Si的內(nèi)部時，稱為物理閉包區(qū)域DTP；同樣可以定義與閉包區(qū)域邊界直接關(guān)聯(lián)的外部頂點均為網(wǎng)格邏輯內(nèi)部點的區(qū)域為邏輯閉包區(qū)域DTT。

從算法目的上，前面所有定義的目的就是為了在適當(dāng)情形下啟用網(wǎng)格的分化并行建模，如圖4所示。

圖4 網(wǎng)格的邏輯內(nèi)部點定義Fig.4 Definition of grid logical interior points

對兩個相鄰網(wǎng)格A、B，如果分別啟用一個獨立線程進行建模，由于拓撲關(guān)系的存在，兩個閉包之外的三角形就有可能同時被兩個線程同時進行訪問修改，從而引發(fā)線程間的并發(fā)沖突，雖然從并發(fā)程序上可以通過鎖存控制來讓某一個線程進行等待來保障程序進行下去，但過于頻繁的并發(fā)沖突處理將會嚴重地影響到算法的效率，因此，從算法思維上減少并發(fā)訪問沖突是非常必要的。

DT、DTP、DTT給出的定義也都是針對方向三角形的建模過程的，理論上講，DTT區(qū)域由于外圍頂點也是網(wǎng)格自身的內(nèi)部資源，不會與相鄰網(wǎng)格存在并發(fā)沖突，但DTT在建模過程中是難以確立的。但可以根據(jù)對DT的初步判斷來盡可能地減少沖突，推遲甚至避免性能不高的線程啟用。判斷條件逐步檢測如下：

（1）網(wǎng)格建模的初期，屬于自己內(nèi)部的三角形數(shù)量相對較少，網(wǎng)格間共享的三角形比較多，因此可以從實現(xiàn)周期上進行控制，對網(wǎng)格的前若干個插入點建模時不作多線程檢測及啟用多線程；實踐經(jīng)驗是前200個頂點免檢基本可以達到穩(wěn)定的并行處理效果。

（2）如果DT不是DTP，則DT一定也不是DTT區(qū)域。這時沖突會大量存在，達不到進行網(wǎng)格獨立建模的基本條件，不能采用多線程進行。

（3）對DT邊界的外圍關(guān)聯(lián)三角形的頂點進行判斷，相當(dāng)于沿DT向外作了一個三角形的緩沖拓展得到一個新的閉合區(qū)域DT′。對DT′進行類似步驟（2）的判斷，當(dāng)DT′為網(wǎng)格的物理閉包區(qū)域時，再啟用多線程進行建模，可以極大地減少并發(fā)沖突的發(fā)生。

對步驟（3）的檢測實施需要求取閉包區(qū)域的外圍緩沖區(qū)域，也需要消耗較多的計算時間，如果直接利用拓撲關(guān)系，使用方向三角形的鄰接三角形頂點來進行判斷，可以簡化檢測過程同時能夠起到如完全緩沖檢測相接近的沖突減少效果，如圖5中所示。從理論技術(shù)上，現(xiàn)在還無法確切地在建模過程中區(qū)分出內(nèi)外部邏輯點及邏輯閉包區(qū)域，要做的工作就是盡量減少并發(fā)沖突發(fā)生的可能性，無法避免的沖突再交由線程的安全訪問機制進行解決，但這些概念的提出，卻有助于總分式并行構(gòu)TIN算法的提出與技術(shù)實施。

圖5 網(wǎng)格檢索封閉閉包區(qū)域Fig.5 Grid enclosed area searching

3 實現(xiàn)過程

在前面的網(wǎng)格劃分及網(wǎng)格內(nèi)的數(shù)據(jù)進行排序等預(yù)處理后，可以利用傳統(tǒng)的插入構(gòu)TIN法來逐步構(gòu)建三角網(wǎng)。插入構(gòu)TIN法是一種性能非常穩(wěn)定的構(gòu)TIN方法，根據(jù)檢索定位插值點所在的三角形的方法，可以分為查找插入法和拓撲插入法。查找插入法需要對每一個生成的三角形進行逐一搜索并判斷插入點是否在三角形中，隨著三角形數(shù)據(jù)的急劇增加，查找效率會急劇下降，對海量點云數(shù)據(jù)構(gòu)TIN不可接受，但其不依賴拓撲關(guān)系，無先決條件要求。拓撲插入法通常是通過指定的起始三角形依據(jù)拓撲關(guān)系通過方向搜索［13］的方式沿路徑找到插入點所在的三角形，比查找插入法有更高的效率，但與起始三角形的維系和搜索路徑長度有關(guān)。

本文充分發(fā)揮兩者的各自優(yōu)勢并綜合運用，實現(xiàn)建立三角網(wǎng)的全過程?？偡质綐?gòu)建三角網(wǎng)的方法是基于每一個網(wǎng)格Si的循環(huán)處理。對每一個網(wǎng)格Si（0≤i≤m）的一次處理過程定義為一個處理周期，為描述方便，記網(wǎng)格Si中點的最大個數(shù)為LN，實際點數(shù)為Ni（0＜Ni≤LN），網(wǎng)格的第k（0＜k≤LN）個處理周期插入點為Pki，構(gòu)成的三角網(wǎng)記為DTS（k），則第k周期構(gòu)TIN結(jié)束后，參與構(gòu)建的三角網(wǎng)的頂點數(shù)可記為

在不同的處理周期中，可以采用不同的方法建立三角網(wǎng)：

（1）k＝1時，三角網(wǎng)為空，無初始條件且三角形數(shù)量較少，采用查找插入法對每一個網(wǎng)格的構(gòu)建起始的均勻三角網(wǎng)。

一個處理周期后就可以確立方向三角形，建立三角形之間的拓撲關(guān)系及指定用于方向拓撲搜索的起始三角形。但考慮到此時三角形數(shù)量并不多，且DT（Si）具有明顯的外部三角形特征，查找插入效率與方向搜索插入效率相比不會有太大的劣勢，故還可以再多執(zhí)行幾個周期，如k→K，K＝2，3，4，5，6…，通?？蓤?zhí)行到k＝5，此時不僅三角網(wǎng)的數(shù)量已顯著增加，除外的個插入點，按點集均勻分布特征評估將分別位于網(wǎng)格Si的四角點附近，可以初步形成網(wǎng)格內(nèi)的閉包區(qū)域，有助于后續(xù)方向搜索與邏輯內(nèi)部點的判斷。

K個周期執(zhí)行完成后，將采用方向拓撲搜索法插入構(gòu)TIN，需要指定起始三角形，自外而內(nèi)的插入法有一個顯著的特征是，每一個周期完成后插入點所構(gòu)成的新三角形中，均至少存在一個與頂點關(guān)聯(lián)的三角形，指定其中一個三角形為網(wǎng)格Si的起始三角形，為下一個周期的頂點插入構(gòu)TIN提供檢索條件。與文獻［13］確立的起始三角形相比，這種綁定網(wǎng)格中心的指定具有非常短的搜索路徑，對Si的n個方向三角形而言，其搜索長度不大于n/2個三角形。

（2）對k＝K＋1至LN個執(zhí)行周期，采用方向拓撲搜索插入法依次對各個網(wǎng)格進行建模并更新網(wǎng)格關(guān)聯(lián)的起始三角形。若網(wǎng)格Si中待插入點Ni－k≤0，則表明該網(wǎng)格已經(jīng)提前完成建模，不再對其進行處理。

按上述步驟，完成LN個周期后，能夠保障所有網(wǎng)格中的所有點均已構(gòu)建到三角網(wǎng)中，不需要引入并行線程就可以完成三角網(wǎng)的整體建模。由于更臨近的起始三角形指定及更高效的方向搜索方式，其效率已明顯優(yōu)于分治－綜合方法給出效率值，在普通PC機上，處理212 459個點建模時，效率可達9.23s。圖6展示了不同周期時三角網(wǎng)的構(gòu)成結(jié)構(gòu)。

圖6 三角網(wǎng)建模插值到k個采樣點時效果圖Fig.6 Interpolation of the k－th sampling points to the triangulation model

從圖6可以看出，與傳統(tǒng)的插入法相比，由于插點排序的存在，在總體構(gòu)TIN過程中會優(yōu)先在網(wǎng)格間的外圍區(qū)域形成穩(wěn)定的Delaunay三角形，構(gòu)成計算機內(nèi)存中的靜態(tài)數(shù)據(jù)，不僅有效地提高了后續(xù)構(gòu)TIN的訪問效率，更可以在大規(guī)模構(gòu)TIN過程中逐步輸出這些成果并從內(nèi)存中釋放空間。

為了更加高效地提高建模效率，可以在上一步的每一個周期末對網(wǎng)格待插入點集進行邏輯內(nèi)部點的判斷，然后運用計算機多線程并行技術(shù)獨立運用拓撲插入法對余下的點集進行建模。檢測方法前面已經(jīng)給出，但檢測與多線程開啟也是有系統(tǒng)額外開銷的，可以對具備較大訪問沖突的前若干個周期（如k＜200）不進行檢測，或?qū)W(wǎng)格中剩余插值點數(shù)小于一定數(shù)量的網(wǎng)格不進行檢測與獨立線程的啟用，如Ni－k＜200，因為這種情形啟用一個新線程的時間資源開銷可能比直接在主線程中完成的開銷更大或相當(dāng)，并行線程在大量點集下啟用更具規(guī)模優(yōu)勢。

4 試驗分析

除了點云總數(shù)量SN、網(wǎng)格規(guī)模限定LN、查找插入點數(shù)K等控制參數(shù)對算法效率有直接影響外，插入法構(gòu)TIN都會涉及頻繁地大量刪除影響域內(nèi)的三角形。經(jīng)過試驗表明，批量進行三角形隊列刪除整理比針對每一個插入采樣點進行即時刪除具備更高的效率，這樣可以通過標記無效來排除三角形，等到無效三角形的個數(shù)達到給定規(guī)模數(shù)DTN時再從隊列由后向前地進行一次性刪除。

試驗結(jié)果如圖7所示，當(dāng)DTN＝5000時，具備最優(yōu)的隊列重整效果。

圖7 三角形統(tǒng)一刪除個數(shù)與構(gòu)TIN效率關(guān)系圖Fig.7 Relationship between deleted number of triangle and modeling efficiency

通過引入多線程并行構(gòu)TIN機制后，有效地提高了整體空間構(gòu)TIN的效率，同等測試條件下構(gòu)TIN的時間由先前的9.23s減少為5.76s，同時當(dāng)網(wǎng)格中限制點數(shù)LN趨大時，構(gòu)TIN的時間消耗依然保持了穩(wěn)中有降的規(guī)模優(yōu)勢，如圖8所示。

經(jīng)過綜合測試，當(dāng)DTN＝10 000時，各項指標與構(gòu)TIN的效率如表1所示。

通過試驗結(jié)果可以進一步看出：當(dāng)點云規(guī)模相當(dāng)，網(wǎng)格限定一致的情形下，網(wǎng)格內(nèi)查找插入法使用點數(shù)k越多，耗時越多，這與順序查找插入法的特性相吻合的；但同時，k越大，生成的有效三角形數(shù)越多，這同樣表明查找插入法具有局部拓撲插入法不可比擬的全面覆蓋特性。因此，保持適當(dāng)規(guī)模的查找插入數(shù)量是非常必要的。

圖8 網(wǎng)格最大點數(shù)上限與構(gòu)TIN效率關(guān)系圖Fig.8 Relationship between the max number of grid points and modeling efficiency

表1 總分并行式構(gòu)TIN算法的效率測試Tab.1 Efficiency test of whole－step TIN construction

5 結(jié)論與展望

本文提出的總分式并行構(gòu)TIN技術(shù)通過算法與編程技術(shù)的綜合應(yīng)用，能夠顯著提升傳統(tǒng)地形數(shù)據(jù)建模的吞吐量，有利于實現(xiàn)更大區(qū)域的實時整體建模，有利于實現(xiàn)更精細數(shù)據(jù)的細節(jié)建模。算法實現(xiàn)簡單、運行穩(wěn)定，能夠為數(shù)字區(qū)域、數(shù)字城市、數(shù)字地球提供強有力的數(shù)據(jù)整合建模，對大型工程的數(shù)字化實現(xiàn)提供了非?，F(xiàn)實的實現(xiàn)手段。下一步將研究明確界定網(wǎng)格內(nèi)外部的先前判定理論來替代逐步檢測機制、開展更大點云規(guī)模的構(gòu)TIN測試以更全面量化統(tǒng)計多線程的沖突數(shù)、不同參數(shù)條件下的算法效率統(tǒng)計與優(yōu)化外，同時將針對網(wǎng)絡(luò)傳輸下的空間大數(shù)據(jù)流式建模展開應(yīng)用研究，以更好地滿足網(wǎng)絡(luò)環(huán)境下大區(qū)域地形的實時建模表達。

［1］DELAUNAY B.Sur la sphère vide，Izvestia Akademii Nauk SSSR［J］.Otdelenie Matematicheskikh i Estestven－nykh Nauk，1934（7）：793－800.

［2］WU Xiaobo，WANG Shixin，XIAO Chunsheng.A New Study of Delaunay Triangulation Creation［J］.Acta Geodaetica et Cartographica Sinica，1999，28（1）：28－35.（武曉波，王世新，肖春生.Delaunay三角網(wǎng)的生成算法研究［J］.測繪學(xué)報，1999，28（1）：28－35.）

［3］LEWIS B A，ROBINSON J S.Triangulation of Planar Regions with Applications［J］.The Computer Journal，1978，21（4）：324－332.

［4］GREEN P J，SIBSON R.Computing Dirichlet Tesselations in the Plane［J］.The Computer Journal，1978，21（2）：168－173.

［5］LEE D T，SCHACHTER B J.Two Algorithms for Constructing a Delaunay Triangulation［J］.International Journal of Computer ＆Information Sciences，1980，9（3）：219－242.

［6］HU Jinxing，MA Zhaoting，WU Huanping，et al.Massive Data Delaunay Triangulation Based on Grid Partition Method［J］.Acta Geodaetica et Cartographica Sinica，2004，33（2）：163－167.（胡金星，馬照亭，吳煥萍，等.基于格網(wǎng)劃分的海量數(shù)據(jù)Delaunay三角剖分［J］.測繪學(xué)報，2004，33（2）：163－167.）

［7］RUI Yikang，WANG Jiechen.A New Study of Compound Algorithm Based on Sweepline and Divide－and－conquer Algorithms for Constructing Delaunay Triangulation［J］.Acta Geodaetica et Cartographica Sinica，2007，33（2）：163－167.（芮一康，王結(jié)臣.Delaunay三角形構(gòu)網(wǎng)的分治掃描線算法［J］.測繪學(xué)報，2007，33（2）：163－167.）

［8］DWYER R A.A Faster Divide－and－conquer Algorithm for Constructing Delaunay Triangulations［J］.Algorithmica，1987，2（1－4）：137－151.

［9］MOSTAFAVI M A，GOLD C M，DAKOWICZ M.Delete and Insert Operations in Voronoi/Delaunay Methods and Applications［J］.Computers ＆ Geosciences，2003，29（4）：523－530.

［10］CHEN Chujiang，WANG Defeng.CDT Fast Generation from Mass Geographic Data and Real Time Updating［J］.Acta Geodaetica et Cartographica Sinica，2002，31（8）：262－265.（陳楚江，王德峰.海量數(shù)據(jù)CDT快速建立及其實時更新［J］.測繪學(xué)報，2002，31（8）：262－265.）

［11］ZHANG Fan，HUANG Xianfeng，LI Deren.Spherical Projection Based Triangulation for One Station Terrestrial Laser Scanning Point Cloud［J］.Acta Geodaetica et Cartographica Sinica，2009，38（1）：48－54.（張帆，黃先鋒，李德仁.基于球面投影的單站地面激光掃描點云構(gòu)網(wǎng)方法［J］.測繪學(xué)報，2009，38（1）：48－54.）

［12］CUI Xueseng，YANG Shenglong，F(xiàn)AN Wei.Grid Based Local Subdivision Algorithms for Constructing Triangulated Irregular Network under Restriction Conditions［J］.Acta Geo－daetica et Cartographica Sinica，2008，37（2）：196－199.（崔雪森，楊勝龍，樊偉.基于柵格局部細分的帶約束條件的不規(guī)則三角網(wǎng)生成算法［J］.測繪學(xué)報，2008，37（2）：196－199.）

［13］PU Hao，SONG Zhanfeng，ZHAN Zhenyan.On the Method for Fast Constructing Delaunay Triangulation DTM［J］.China Railway Science，2001，22（6）：100－105.（蒲浩，宋占峰，詹振炎.快速構(gòu)建三角網(wǎng)數(shù)字地形模型方法的研究［J］.中國鐵道科學(xué)，2001，22（6）：100－105.）

［14］XIA Shaofang，CHEN Lichao，LIU Jia.High Efficient Algorithm for Building Delaunay Triangulation Based on Virtual Grid［J］.Computer Engineering and Design，2009，30（1）：238－240.（夏少芳，陳立潮，劉佳.基于虛擬網(wǎng)格的高效Delaunay三角網(wǎng)生成算法研究［J］.計算機工程與設(shè)計，2009，30（1）：238－240.）

［15］LI Jian，LI Deren，SHAO Zhenfeng.A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing［J］.Geomatics and Information Science of Wuhan University，2013.7，38（7）：794－798.（李堅，李德仁，邵振峰.一種并行計算的流數(shù)據(jù)Delaunay構(gòu)網(wǎng)算法［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2013，38（7）：794－798.）

［16］WU H Y，GUAN X F，GONG J Y.Para Stream：A Parallel Streaming Delaunay Triangulation Algorithm for LiDAR Points on Multicore Architectures［J］.Computers ＆Geosciences，2011，37（9）：1355－1363.

［17］ISENBURG M，LIU Y X，SHEWCHUK J，et al.Streaming Computation of Delaunay Triangulations［J］.ACM Transactions on Graphics，2006，25（3）：1049－1056.

［18］SONG Zhanfeng，PU Hao，ZHAN Zhenyan.Study on an Algorithm for Fast Constructing Delaunay Triangulation［J］.Journal of the China Railway Society，2001，23（5）：85－91.（宋占峰，蒲浩，詹振炎.快速構(gòu)建Delaunay三角網(wǎng)算法研究［J］.鐵道學(xué)報，2001，23（5）：85－91.）

［19］MILES R E.Solution to Problem 67－15（Probability Distribution of a Network of Triangles）［J］.Society for Industrial and Applied Mathematics，1969，11（3）：399－402.