韋云艦，盧 中

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

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

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

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

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

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

2 算法優(yōu)化

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

2.1 排除封閉點

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

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

圖3 封閉點示意圖

2.2 第三點排序

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

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

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

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

圖4 第三點排序方法

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

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

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

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

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

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

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

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

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

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

圖6 斷面提取過程示意圖

4 案例分析

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

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

圖7 橫斷面示意圖

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

5 結(jié) 語

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