Delaunay三角網(wǎng)生長法的優(yōu)化與應(yīng)用

韋云艦，盧 中

（1.甘肅省地質(zhì)礦產(chǎn)勘查開發(fā)局第三地質(zhì)礦產(chǎn)勘查院，甘肅 蘭州 730050；2.中交第二航務(wù)工程勘察設(shè)計院有限公司，湖北 武漢 430071）

工程測量中常采用不規(guī)則三角網(wǎng)（TIN）模型來表示地形。為了使三角形能更好地對地形變化進(jìn)行擬合，應(yīng)盡量使三角形接近等邊，三角形的最小角最大。經(jīng)證實(shí)，一般情況下在所有可能形成的三角網(wǎng)模型中，Delaunay三角網(wǎng)是最優(yōu)的。由于Delaunay三角網(wǎng)構(gòu)網(wǎng)復(fù)雜，因此不同算法的執(zhí)行效率存在較大差異?，F(xiàn)有較成熟的Delaunay三角網(wǎng)構(gòu)網(wǎng)方法主要包括三角網(wǎng)生長法、逐點(diǎn)插入法和分治法3種，各有利弊[1-4]。本文以經(jīng)典Delaunay三角網(wǎng)生長法為基礎(chǔ)，對三角形尋找第三點(diǎn)的方法進(jìn)行了優(yōu)化，明顯提升了該方法的執(zhí)行效率；并將三角網(wǎng)成果用于提取道路斷面，分析了其實(shí)用性。

1 經(jīng)典Delaunay三角網(wǎng)生長法

Delaunay三角網(wǎng)生長法是基于Delaunay三角網(wǎng)的空圓特性的，即Delaunay三角網(wǎng)中任意一個三角形的外接圓內(nèi)不存在其他點(diǎn)?；诖?， Delaunay三角網(wǎng)生長法的構(gòu)網(wǎng)步驟為：①任選點(diǎn)庫中的一個點(diǎn)P1；②遍歷點(diǎn)庫，尋找距點(diǎn)P1最近的點(diǎn)P2，并與之相連構(gòu)成第一邊，添加到邊庫中；③遍歷點(diǎn)庫，尋找第三點(diǎn)與P1、P2構(gòu)成三角形，使之外接圓滿足空圓特性，并將第三點(diǎn)與P1、P2的連線添加到邊庫中，相應(yīng)的三角形添加到三角形庫中（如ΔP1P2P4外接圓內(nèi)存在點(diǎn)P3，不滿足條件，而ΔP1P2P3外接圓內(nèi)不存在其他點(diǎn)，滿足條件，如圖1所示）；④遍歷邊庫，判斷各邊兩側(cè)是否應(yīng)構(gòu)建新的三角形，若邊兩側(cè)均存在三角形或不存在其他點(diǎn)，則該邊已構(gòu)建完成，否則重復(fù)步驟③、步驟④，直至所有邊均構(gòu)建完成，如圖2所示，如邊P1P2左側(cè)存在ΔP1P2P3、右側(cè)無點(diǎn)，則無需構(gòu)造新的三角形，該邊已構(gòu)建完成，邊P1P3右側(cè)存在ΔP1P2P3、左側(cè)無三角形且仍存在其他點(diǎn)，則應(yīng)繼續(xù)尋找第三點(diǎn)構(gòu)建新的三角形。

圖1 Delaunay三角網(wǎng)構(gòu)建過程

圖2 Delaunay三角網(wǎng)構(gòu)建結(jié)果

2 算法優(yōu)化

由Delaunay三角網(wǎng)的構(gòu)建過程可知，其耗時操作主要在尋找第三點(diǎn)上，因此算法優(yōu)化主要用于簡化第三點(diǎn)的尋找過程[5-9]。

2.1 排除封閉點(diǎn)

封閉點(diǎn)的概念由賀全兵[10]等提出，在尋找第三點(diǎn)構(gòu)網(wǎng)的過程中會不斷產(chǎn)生封閉點(diǎn)。以P1為起始點(diǎn)經(jīng)過3次遍歷后的結(jié)果如圖3所示，此時點(diǎn)P3已被三角形所包圍，稱之為封閉點(diǎn)。封閉點(diǎn)將不再參與下一次遍歷邊庫尋找第三點(diǎn)的過程，因此第4次遍歷前可將點(diǎn)P3從備選點(diǎn)庫中移除。通過動態(tài)地排除封閉點(diǎn)，可將第三點(diǎn)的備選范圍不斷縮小，以減少尋點(diǎn)時間。

尤磊[11]等在封閉點(diǎn)概念的基礎(chǔ)上提出了以優(yōu)先點(diǎn)為中心的Delaunay三角網(wǎng)構(gòu)建方法，是對排除封閉點(diǎn)方法的進(jìn)一步優(yōu)化。具體方法是對于新增的三角形角點(diǎn)Pi，優(yōu)先擴(kuò)展以Pi為角點(diǎn)的邊，待Pi成為封閉點(diǎn)后將其從備選點(diǎn)庫中移除，此時稱Pi為優(yōu)先點(diǎn)。采用該方法能更快地將優(yōu)先點(diǎn)變?yōu)榉忾]點(diǎn)，優(yōu)化備選點(diǎn)庫，提高構(gòu)網(wǎng)效率。

圖3 封閉點(diǎn)示意圖

2.2 第三點(diǎn)排序

由Delaunay三角網(wǎng)的空圓特性和最大最小角特性可知，第三點(diǎn)大概率會出現(xiàn)在前兩點(diǎn)附近（點(diǎn)集邊緣的三角形除外）。如圖4所示，在進(jìn)一步尋找P1P6左側(cè)三角形的第三點(diǎn)時，第三點(diǎn)大概率會是距離P1P6中點(diǎn)（設(shè)為P1-6）最近的P8、P9、P10之一，而不會是遠(yuǎn)處的Pn、Pn+1。由于點(diǎn)集中點(diǎn)的順序是無規(guī)律的，每次判斷某點(diǎn)是否為第三點(diǎn)時，均需遍歷點(diǎn)集中的其他點(diǎn)是否在第三點(diǎn)的外接圓內(nèi)，極為耗時，因此本文算法在每次尋找第三點(diǎn)時均會根據(jù)備選點(diǎn)到前兩點(diǎn)的距離進(jìn)行排序，即最靠近P1P6中點(diǎn)P1-6的點(diǎn)優(yōu)先進(jìn)行空圓判斷。設(shè)點(diǎn)P1、P2、…、Pn坐標(biāo)依次為（X1,Y1）、（X2,Y2）、…、（Xn,Yn），即P1-6P8長度可表示為：

本文采用冒泡排序法選取距離前兩點(diǎn)最近的i個點(diǎn)優(yōu)先進(jìn)行空圓判斷，尋找第三點(diǎn)。由于每次排序均需根據(jù)式（1）計算所有備選點(diǎn)到前兩點(diǎn)中點(diǎn)的距離，考慮到對于計算機(jī)而言，浮點(diǎn)類型數(shù)據(jù)的加減法執(zhí)行效率比乘除法高數(shù)十倍，因此以式（2）代替式（1），可近似篩選距離最近的點(diǎn)，可大幅提升冒泡排序效率。

冒泡排序法需重復(fù)遍歷待排序的數(shù)組，依次對比相鄰元素，若相鄰元素排序錯誤則交換其順序，因此選取距離最近的i個點(diǎn)需進(jìn)行i次遍歷。遍歷次數(shù)越大，即篩選的最近點(diǎn)越多，目標(biāo)點(diǎn)出現(xiàn)在最近點(diǎn)中的概率越大，但排序耗時也越長，因此需測試選擇最佳遍歷次數(shù)。本文選用10 000個不規(guī)則排序的三角網(wǎng)點(diǎn)作為測試數(shù)據(jù)，測試了遍歷次數(shù)、最近點(diǎn)包含目標(biāo)點(diǎn)的概率、構(gòu)網(wǎng)時間三者的關(guān)系，結(jié)果如表1所示，可以看出，當(dāng)篩選的最近點(diǎn)逐漸增多時，最近點(diǎn)包含目標(biāo)點(diǎn)的概率將迅速增大，但難以達(dá)到100%，此時最近點(diǎn)不包含目標(biāo)點(diǎn)的情況主要出現(xiàn)在三角網(wǎng)邊緣的狹長三角形中。以圖5為例，在尋找P1P2右側(cè)的Delaunay三角形時，目標(biāo)點(diǎn)為Pn，而采用排序法優(yōu)先選取的最近點(diǎn)依次為P3、P4、P5、P6等，這種情況在三角網(wǎng)邊緣難以避免，因此遍歷次數(shù)應(yīng)以三角網(wǎng)的構(gòu)網(wǎng)時間為依據(jù)，取最佳遍歷次數(shù)為7。

表1 三角網(wǎng)生成時間匯總表（取樣點(diǎn)為10 000）

圖4 第三點(diǎn)排序方法

圖5 三角網(wǎng)邊緣構(gòu)網(wǎng)示意圖

2.3 算法執(zhí)行效率比較

本文采用優(yōu)化前后的Delaunay三角網(wǎng)生長法對不同數(shù)量的樣本點(diǎn)進(jìn)行處理，并對構(gòu)網(wǎng)時間進(jìn)行匯總，結(jié)果如表2所示，可以看出，優(yōu)化后的Delaunay三角網(wǎng)生長法的執(zhí)行效率得到了明顯提升，隨著樣本點(diǎn)數(shù)量的增加，效率提升效果將更為明顯。程序的執(zhí)行效率受編程語言、計算機(jī)性能、采樣點(diǎn)排序等諸多因素影響，本文采用Java語言編寫程序，程序運(yùn)行于Windows10 64位系統(tǒng)中，計算機(jī)處理器為Intel Core i5 2.30GHz，內(nèi)存為8G，采樣點(diǎn)為完全隨機(jī)樣本。

表2 樣本數(shù)量與構(gòu)網(wǎng)時間匯總表

3 基于Delaunay三角網(wǎng)的斷面提取方法

由地面高程點(diǎn)構(gòu)成的Delaunay三角網(wǎng)可用于表示地形起伏，當(dāng)高程點(diǎn)密度足夠時，可在三角網(wǎng)的基礎(chǔ)上內(nèi)插指定點(diǎn)位高程?；诖耍稍贒elaunay三角網(wǎng)的基礎(chǔ)上提取道路橫斷面，具體方法為：①根據(jù)設(shè)計斷面端點(diǎn)坐標(biāo)和點(diǎn)間距計算斷面節(jié)點(diǎn)坐標(biāo)；②根據(jù)節(jié)點(diǎn)平面坐標(biāo)判斷節(jié)點(diǎn)所在三角形；③根據(jù)三角形角點(diǎn)三維坐標(biāo)確定三角形所在平面方程，再代入斷面節(jié)點(diǎn)平面坐標(biāo)，計算節(jié)點(diǎn)高程。

為了提高程序執(zhí)行效率，判斷節(jié)點(diǎn)是否在三角形內(nèi)時采用向量法。如圖6所示，判斷斷面節(jié)點(diǎn)Ti是否在ΔP1P2P3內(nèi)時，可將向量表示為向量和向量的矢量和，即

當(dāng)m、n滿足以下3個條件時，可判定節(jié)點(diǎn)Ti在ΔP1P2P3內(nèi)。

設(shè)ΔP1P2P3所在平面方程為Z=A×X+B×Y+C，Pi點(diǎn)的三維坐標(biāo)為(Xi,Yi,Zi)，代入平面方程解得：

代入節(jié)點(diǎn)Ti的平面坐標(biāo)(XTi,YTi)，得到其高程，則有：

圖6 斷面提取過程示意圖

4 案例分析

本文的實(shí)驗(yàn)數(shù)據(jù)源自上饒至浦城高速公路（江西境內(nèi)）的新建工程，項(xiàng)目定測外業(yè)時間緊、任務(wù)重，且存在大面積山區(qū)密林地段。定測時正值冬季，樹葉相對稀少，利于激光穿透植被，常規(guī)測量手段施測困難，因此項(xiàng)目的橫斷面測量采用機(jī)載激光雷達(dá)施測。機(jī)載激光雷達(dá)外業(yè)作業(yè)平均航高為200m，點(diǎn)云平均密度小于10cm。在測區(qū)范圍內(nèi)，選取合適的特征點(diǎn)利用RTK進(jìn)行檢測，結(jié)果如表3所示，可以看出，激光雷達(dá)數(shù)據(jù)可靠，可滿足斷面測量精度需求。

本文采用均值法提取平均點(diǎn)密度為3m的點(diǎn)云用于生成三角網(wǎng)，并提取道路橫斷面，將提取的橫斷面成果與實(shí)測橫斷面進(jìn)行對比，結(jié)果如圖7所示，可以看出，采用程序提取的橫斷面成果與實(shí)測成果吻合良好，誤差主要集中于變坡處，若適當(dāng)提高橫斷面節(jié)點(diǎn)的提取密度可使變坡處的擬合效果更好。本文提取橫斷面節(jié)點(diǎn)的間距為1m，橫斷面提取結(jié)果與RTK實(shí)測結(jié)果相比最大較差小于0.2m，可滿足精度需求，方法具備可行性。

圖7 橫斷面示意圖

表3 激光雷達(dá)數(shù)據(jù)檢測結(jié)果統(tǒng)計表

5 結(jié) 語

本文在Delaunay三角網(wǎng)生長法的構(gòu)網(wǎng)過程中，通過排除封閉點(diǎn)和第三點(diǎn)排序的方法對原有方法進(jìn)行了優(yōu)化。經(jīng)驗(yàn)證，優(yōu)化后的Delaunay三角網(wǎng)生長法的執(zhí)行效率得到了明顯提升。本文利用優(yōu)化后的Delaunay三角網(wǎng)生長法將機(jī)載激光雷達(dá)施測的高密度點(diǎn)云數(shù)據(jù)生成三角網(wǎng)，并在此基礎(chǔ)上對道路橫斷面數(shù)據(jù)進(jìn)行提取，經(jīng)RTK檢測可知，提取的橫斷面數(shù)據(jù)成果精度良好，方法具備可行性。