董 箭，張志衡，彭認燦，李改肖，王 沫

1. 海軍大連艦艇學(xué)院軍事海洋與測繪系，遼寧 大連 116018； 2. 海軍大連艦艇學(xué)院海洋測繪工程軍隊重點實驗室，遼寧 大連 116018

數(shù)字水深模型(DDM)是反映水深變化的數(shù)字化模型，也是用深度表達海底地形特征的一種常用數(shù)字模型，根據(jù)水深點數(shù)據(jù)組織方式的不同，分為規(guī)則格網(wǎng)DDM(GRID_DDM)和不規(guī)則三角網(wǎng)DDM(TIN_DDM)[1-6]。緩沖區(qū)分析是二維GIS空間分析的基本功能，是確定二維地理實體的空間鄰近度或影響范圍的重要手段[7-9]。三維條件下的緩沖區(qū)分析稱為緩沖體分析，由于DDM所固有的單值曲面特性，其緩沖體分析又被稱為緩沖面分析[10-11]。近年來，隨著人類對海底世界的全方位加速探索，應(yīng)用面向海底三維空間分析的DDM緩沖面構(gòu)建技術(shù)對于解決海底污染源擴散、水下潛航器航行安全保障、海底礦藏分布探明和海底地形多尺度表達等問題具有重要的理論和現(xiàn)實意義[11-19]。

目前有關(guān)三維緩沖體構(gòu)建算法的研究主要包括矢量算法和柵格算法兩類[10-13,20-23]。矢量算法所構(gòu)建的緩沖體精度較高，但其涉及大量的三維空間幾何求交運算，復(fù)雜度較高，運行效率較低[10-13]。文獻[12]通過對布爾運算拓撲關(guān)系完整性、邏輯判斷一致性及運算容差統(tǒng)一性的條件約束，提出了一種基于高效布爾運算的三維矢量緩沖區(qū)生成算法，然而布爾運算的構(gòu)建機理決定了該算法受目標實體復(fù)雜度及采樣點拓撲關(guān)系的影響較大，算法時間復(fù)雜度相對較高。文獻[13]利用帶符號的歐氏距離變換技術(shù)及緩沖半徑對目標模型離散化后的體素進行緩沖控制點的條件篩選，結(jié)合隱式曲面重構(gòu)模型構(gòu)建三維緩沖區(qū)的參考曲面，提出了一種基于空間填充思想的三維緩沖區(qū)分析算法，由于體素拓撲關(guān)系維護及隱式曲面重構(gòu)過程相對復(fù)雜，算法效率較低。柵格算法主要采用三維歐氏距離變換方法，實現(xiàn)了對各類地理要素的三維緩沖體構(gòu)建，與矢量算法相比，其算法簡單且較易實現(xiàn)，運行效率較高。但此類算法只針對于柵格數(shù)據(jù)，適用范圍較窄且所構(gòu)建的緩沖體精度較低[10-11,20-23]。文獻[11]針對單值曲面這類特殊的地理要素，提出了一種基于滾動球模型的單值曲面緩沖體邊界生成算法，通過單值曲面邏輯并運算法則的構(gòu)造，避免了柵格采樣點距離場的重復(fù)計算，算法時間復(fù)雜度降至O(nr2)。文獻[20]利用三維歐氏距離的遞推延續(xù)性質(zhì)，將柵格曲面的三維歐氏距離變換分解為n個n×n的像素點(柵格單元)的二維二值圖像的二維歐式距離變換過程來構(gòu)建緩沖體，算法復(fù)雜度為O(n6)。文獻[22]通過優(yōu)化方法減少需要參與距離計算和比較的二維圖像個數(shù)與二維圖像中特征點的個數(shù)，使算法的時間復(fù)雜度降至O(n3lgn)。文獻[23]設(shè)計了一種體元信息由生長元向周圍鄰域傳遞的等值面擴張路徑，提出了一種基于桶數(shù)據(jù)結(jié)構(gòu)的柵格三維緩沖體生成算法，時間復(fù)雜度為O(V)(V為體元個數(shù))。

與GRID_DDM相比，由于TIN_DDM采用原始采樣點作為模型數(shù)據(jù)，可以更好地反映海底地形地貌(如山脊、山谷、地形斷裂線等)，對起伏程度較大區(qū)域的地形描述更加精細，也更加有利于提高緩沖面分析結(jié)論的準確性[1-2]。然而，當前三維緩沖體構(gòu)建的算法研究大部分為柵格算法，主要針對GRID_DDM而無法直接應(yīng)用于TIN_DDM。研究較少的矢量算法雖可以應(yīng)用于TIN_DDM，但構(gòu)建過程中需要大量處理復(fù)雜的三維空間幾何求交運算，算法運算效率較低，且最終構(gòu)建的矢量緩沖面難以存儲和表達。

為解決現(xiàn)有三維緩沖體構(gòu)建算法在處理TIN_DDM這類特殊地理空間要素時存在的模型精度與算法效率這一矛盾問題，本文將GRID_DDM緩沖面構(gòu)建的滾動球模型應(yīng)用擴展至TIN_DDM緩沖面的構(gòu)建過程，建立了滾動球半徑閾值關(guān)聯(lián)的緩沖面精度定量調(diào)控模型，分析論證了關(guān)鍵采樣點判定準則與滾動球半徑的數(shù)值關(guān)聯(lián)關(guān)系，提出了TIN_DDM緩沖面快速構(gòu)建的滾動球加速優(yōu)化算法，實現(xiàn)了大數(shù)據(jù)量TIN_DDM緩沖面的多次快速構(gòu)建。

1 滾動球模型在TIN_DDM緩沖面構(gòu)建中的應(yīng)用擴展及局限性分析

1.1 基于TIN_DDM的滾動球模型構(gòu)建

滾動圓變換是當前自動生成二維線或面要素緩沖區(qū)邊界的通用算法，其實質(zhì)是對組成二維線或面要素的無限個采樣點的緩沖區(qū)求并而獲得二維線或面要素的緩沖區(qū)邊界[7,11]。文獻[11]在柵格算法的基礎(chǔ)上，針對GRID_DDM這類單值曲面，對滾動圓進行三維擴展，提出滾動球模型構(gòu)建原理，采用與滾動圓變換類似的方法自動獲得三維空間單值曲面要素的緩沖面，所提模型主要依據(jù)三維緩沖體邊界的數(shù)學(xué)定義和單值曲面的特性進行三維緩沖面構(gòu)建。

由文獻[11]可知，三維緩沖體邊界的數(shù)學(xué)定義為

B(T,r)={P(x,y,z)|{dmin(P,QT)|QT(xT,yT,zT)∈T}=r}

(1)

式中，B(T,r)表示地理要素T的緩沖半徑為r的緩沖體邊界;P(x,y,z)表示緩沖體邊界B(T,r)上的任意一點;QT(xT,yT,zT)表示地理要素T上任意采樣點;dmin(P,QT)表示緩沖體邊界B(T,r)上的P點至地理要素T上各個QT點間的三維歐氏距離最小值。

基于上述三維緩沖體邊界概念，三維緩沖體邊界等價于地理要素T上無限個采樣點的等距離球面的并集。但對于由有限個離散水深采樣點構(gòu)成的DDM，若在保證緩沖面構(gòu)建精度的前提下，三維緩沖面可等價于DDM上有限個水深采樣點的等距離球面的并集。然而，等距離球面并集的計算涉及大量三維空間幾何求交運算，效率相對低下，且所生成的上下緩沖面存儲與表達均較為困難。為提高算法運行效率，文獻[11]針對GRID_DDM這類特殊單值曲面，提出一種基于柵格算法的單值曲面邏輯并運算法則。該運算法則為：GRID_DDM采樣點間上(下)緩沖面的并集運算可簡化為各自上(下)緩沖面在z軸方向上的極大(小)取值過程，即可通過GRID_DDM采樣點及周圍各個離散水深點的等距離球面在采樣點z軸方向交點的極大(小)值來確定該采樣點對于的上(下)緩沖面點。滾動球模型中的單值曲面邏輯并運算法則通過單一坐標軸方向的數(shù)值比較實現(xiàn)了三維空間幾何求交的運算簡化，具有較高的算法運算效率，且算法本身對DDM數(shù)據(jù)類型的依賴性較小。由此，本文提出將滾動球模型應(yīng)用進一步擴展至TIN_DDM緩沖面構(gòu)建過程的設(shè)想，其具體實施步驟為：①采用矢量算法精確計算各個采樣點的等距離球面；②利用基于柵格算法的單值曲面邏輯并運算法則依次計算各個采樣點在z軸方向上的上(下)緩沖面點坐標；③以三角網(wǎng)形式對TIN_DDM上(下)緩沖面進行存儲和表達。盡管上述算法設(shè)想在理論層面上可較好地解決TIN_DDM緩沖面構(gòu)建算法運算效率低下及生成緩沖面的存儲與表達方面的問題，但實際應(yīng)用中滾動球模型在構(gòu)建過程中仍存在一定的精度與效率方面的矛盾。因此，需進一步分析論證滾動球模型在TIN_DDM緩沖面構(gòu)建過程中的精度與效率局限性，設(shè)計并提出相應(yīng)的模型優(yōu)化方案，以滿足當前TIN_DDM緩沖面構(gòu)建的實際應(yīng)用需求。

1.2 滾動球模型在TIN_DDM緩沖面構(gòu)建中的精度局限性分析

滾動球模型在TIN_DDM緩沖面構(gòu)建過程中的精度損失主要體現(xiàn)在以下兩個方面：①由于采用TIN_DDM上有限個水深采樣點的等距離球面進行求交運算來構(gòu)建矢量緩沖面，導(dǎo)致所構(gòu)建的矢量緩沖面與TIN_DDM的三角網(wǎng)面之間并不嚴格滿足三維緩沖體邊界的數(shù)學(xué)定義，存在模型構(gòu)建原理上的精度缺陷；②為提高模型運算效率，采用基于柵格算法的單值曲面邏輯并運算法則對各個等距離球面進行求交運算，其本質(zhì)為對所構(gòu)建的TIN_DDM矢量緩沖面進行三角網(wǎng)格化處理，以便于生成緩沖面的存儲與表達，盡管在一定程度上簡化了模型的計算過程，但同時也造成了模型構(gòu)建過程中的精度損失。

圖1 TIN_DDM矢量緩沖面構(gòu)建過程中的模型精度分析Fig.1 The situation of model precision analysis during the construction of TIN_DDM vector butter surface

(2)

(3)

圖2 TIN_DDM矢量緩沖面三角網(wǎng)格化過程中的模型精度分析Fig.2 The situation of model precision analysis during the triangulation of TIN_DDM vector butter surface

(4)

(5)

基于上述分析，采用滾動球模型所構(gòu)建的TIN_DDM緩沖面上各點與真實TIN_DDM緩沖面之間的誤差最大值ωmax為

(6)

1.3 滾動球模型在TIN_DDM緩沖面構(gòu)建中的效率局限性分析

評定算法優(yōu)劣性的指標主要為算法精度和運算效率。在GIS實際應(yīng)用中，當算法精度滿足應(yīng)用需求時，對于TIN_DDM這類數(shù)據(jù)量較大的模型，算法執(zhí)行效率將顯得尤為重要。由1.1節(jié)中基于TIN_DDM的滾動球模型構(gòu)建過程可知，TIN_DDM緩沖面構(gòu)建的關(guān)鍵在于其上各點z坐標值的計算，而緩沖面上各點z坐標值的確定主要通過借鑒文獻[11]中所提的基于柵格算法的單值曲面邏輯并運算法則進行計算。假設(shè)TIN_DDM中水深采樣點的個數(shù)為n且各點均勻分布(分布密度為ρ)，則對于其中每個水深采樣點所對應(yīng)的緩沖面點的z坐標值，均需要遍歷滾動球在XOY平面覆蓋范圍內(nèi)的水深點(水深點個數(shù)n′=ρπr2)，并判斷各個采樣點的等距離球面是否在所選水深采樣點的z軸方向上形成極值。從而，對于每個水深采樣點需進行ρπr2次計算，整個TIN_DDM緩沖面的構(gòu)建過程需進行nρπr2次運算，即算法的時間復(fù)雜度為O(nr2)。

隨著多波束等先進水深測量設(shè)備的廣泛運用，TIN_DDM中包含的水深采樣點數(shù)量日益劇增，單次多波束水深測量獲得的采樣點數(shù)據(jù)量可達百萬甚至千萬級別。水深采樣點數(shù)據(jù)量的日益劇增盡管有利于海底地形的精細化表達，但同時也決定了進行TIN_DDM緩沖面構(gòu)建的時間成本巨大。此外，考慮到不同行業(yè)不同層次的應(yīng)用需求，實踐中往往需要利用不同緩沖半徑多次構(gòu)建TIN_DDM緩沖面，這對TIN_DDM緩沖面構(gòu)建算法的效率提出了更為嚴格的效率要求。因此，需進一步探索影響TIN_DDM緩沖面構(gòu)建效率的關(guān)鍵因素及其內(nèi)在關(guān)聯(lián)，簡化算法流程，避免冗余運算，以實現(xiàn)面向TIN_DDM緩沖面構(gòu)建的滾動球模型進行加速優(yōu)化。

2 面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型

2.1 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點判定準則及步驟

柵格條件下單值曲面邏輯并運算法則以一維條件下的數(shù)值比較運算對TIN_DDM采樣點等距離面的曲面求交運算進行了等效簡化，實現(xiàn)了給定緩沖半徑條件下TIN_DDM緩沖面的快速構(gòu)建。需要指出的是，該法則的運用并未實質(zhì)性地減少參與等距離面構(gòu)建的TIN_DDM采樣點數(shù)量，對于工程實踐中可能出現(xiàn)的高密度TIN_DDM緩沖面多次重復(fù)構(gòu)建應(yīng)用，緩沖半徑對算法時間復(fù)雜度的數(shù)值影響會逐漸增強，成為制約算法執(zhí)行效率的主要因素。因此，以緩沖半徑為關(guān)聯(lián)紐帶，分析和論證有效參與TIN_DDM緩沖面構(gòu)建的關(guān)鍵采樣點與算法時間復(fù)雜度間的關(guān)聯(lián)關(guān)系，構(gòu)建緩沖半徑不相關(guān)的TIN_DDM緩沖面加速構(gòu)建算法成為解決高密度TIN_DDM緩沖面多次重復(fù)構(gòu)建效率問題的技術(shù)前提。

柵格條件下單值曲面邏輯并運算法則需對每個TIN_DDM采樣點進行ρπr2次計算，以此確定該TIN_DDM采樣點對應(yīng)的緩沖面邊界點。然而，一方面，柵格條件下單值曲面邏輯并運算法則的極值特性決定了該緩沖面邊界點必然唯一存在其至TIN_DDM距離等于緩沖半徑的關(guān)鍵采樣點，且兩者間距離為該緩沖面邊界點至TIN_DDM采樣點間的最小值；另一方面，柵格條件下單值曲面邏輯并運算法則的極值特性也證明了任意TIN_DDM采樣點對應(yīng)緩沖面邊界點解算過程中的ρπr2次計算，可由該采樣點與其對應(yīng)的關(guān)鍵采樣點間(實際有效參與緩沖面構(gòu)建的采樣點)的一次數(shù)值計算等效替代。由此，準確快速判定任意緩沖面邊界點至TIN_DDM距離等于緩沖半徑的關(guān)鍵采樣點成為減少冗余等距離球面求交運算，提高算法執(zhí)行效率的核心問題。如圖3所示，曲面T為單值曲面地理要素；曲面B1為曲面T的上緩沖面；Qi、Q1和Q2點分別為單值曲面地理要素T上的三點；L1L2為Qi點的z軸方向；P′點為以Q1采樣點為球心的等距離球面在L1L2方向上形成極大值點；P′點至Q1點的距離為滾動球半徑r；P′點至Q2點的距離為d。

圖3 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點Fig.3 The situation of the key point during TIN_DDM butter surface construction

圖3中，由于P′點為Q1采樣點的等距離球面在L1L2方向上所形成的極大值點，則單值曲面地理要素T上其余采樣點的等距離球面在L1L2方向的交點均位于P′點之下。對于曲面T上與Q1點相異的任意一點Q2而言，則P′點至Q2點的距離d始終大于滾動球半徑r，即Q1點為P′點在曲面T上的最近點(且距離等于滾動球半徑r)。因此，在上(下)緩沖面點z軸方向上形成極大(小)值的等距離球面所對應(yīng)的球心采樣點即為該上(下)緩沖面點所對應(yīng)的TIN_DDM上的最近點(即TIN_DDM緩沖面構(gòu)建的關(guān)鍵采樣點)。基于上述分析，本文提出如下TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點判定步驟：

(1) 以r為滾動球半徑，依次構(gòu)建TIN_DDM中各水深采樣點Qi的等距離球面。

(2) 判斷各個等距離球面是否在水深采樣點Qi的z軸方向上形成極大(小)值。

(3) 以形成極大(小)值的等距離球面所對應(yīng)的球心采樣點標記為采樣點Qi的上(下)緩沖面點所對應(yīng)的TIN_DDM上(下)緩沖面構(gòu)建關(guān)鍵采樣點。

2.2 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑的數(shù)值關(guān)聯(lián)性分析

由2.1節(jié)中分析可知，滾動球半徑r與TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點的判定具有一定的關(guān)聯(lián)關(guān)系。一般情況下，當滾動球半徑r發(fā)生變化時，需重復(fù)前述步驟依次判定TIN_DDM緩沖面構(gòu)建的關(guān)鍵采樣點，并構(gòu)建新的TIN_DDM緩沖面。這對于大數(shù)據(jù)量條件下的TIN_DDM應(yīng)用不同緩沖半徑進行多次重復(fù)緩沖面構(gòu)建的實際應(yīng)用而言，顯然難以滿足其效率需求?？紤]到滾動球半徑的取值具有連續(xù)有界的變化規(guī)律，且在滾動球半徑變化不大的條件下，TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點的判定結(jié)論具有一定相似性。因此，需進一步分析滾動球半徑連續(xù)變化條件下TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點判定結(jié)論的變化趨勢，建立滾動球半徑與TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點的數(shù)值關(guān)聯(lián)關(guān)系，構(gòu)建面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型，實現(xiàn)滾動球半徑變化弱相關(guān)的TIN_DDM緩沖面高效構(gòu)建算法。

圖4 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑的數(shù)值關(guān)聯(lián)性分析Fig.4 The situation of numerical correlation analysis between the key point during TIN_DDM butter surface construction and the roll radius

圖4(a)中，當滾動球半徑r從0開始變化時，采樣點Pi的z軸方向上形成極值點的等距離球面所對應(yīng)的構(gòu)建關(guān)鍵采樣點同樣為采樣點Pi，即此時構(gòu)建關(guān)鍵采樣點Pj與采樣點Pi為同一點。如圖4(b)所示，隨著滾動球半徑r的逐漸增大，采樣點Pi的鄰域內(nèi)必然存在一定數(shù)量的采樣點等距離球面與Pi點的z軸方向(L1L2方向)相交。

(7)

(8)

對TIN_DDM中所有采樣點所對應(yīng)的TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑的數(shù)值關(guān)聯(lián)性進行分析，將其記錄在如圖5所示的TIN_DDM上緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈中。其中P1至Pl為TIN_DDM中的各水深采樣點；j1至jl為各水深采樣點所對應(yīng)的TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點個數(shù)；0rl1rl2…rljl表示各TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點的滾動球半徑范圍臨界值；Pl1Pl2…Pljl表示各半徑范圍所對應(yīng)的TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點。

采用上述面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型，通過對TIN_DDM進行前期預(yù)處理，建立TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，對面向TIN_DDM緩沖面構(gòu)建的滾動球模型進行加速優(yōu)化。在后期應(yīng)用中，只需進行簡單查詢即可實現(xiàn)任意緩沖半徑條件下TIN_DDM緩沖面的快速構(gòu)建，算法時間復(fù)雜度降至O(n)，可滿足不同行業(yè)不同層次對于利用不同緩沖半徑多次構(gòu)建TIN_DDM緩沖面的應(yīng)用效率需求。

圖5 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈Fig.5 The situation of numerical correlation data link between the key point during TIN_DDM butter surface construction and the roll radius

3 試驗結(jié)果與分析

為驗證算法的可行性，本文通過Matlab編程實現(xiàn)了基于滾動球模型的TIN_DDM緩沖面構(gòu)建算法(以下簡稱算法Ⅰ)和基于滾動球加速優(yōu)化模型的TIN_DDM緩沖面快速構(gòu)建算法(以下簡稱算法Ⅱ)，并利用Matlab的三維顯示功能對兩類算法的試驗結(jié)果進行了可視化顯示與分析。

試驗所采用的數(shù)據(jù)為我國東海某海區(qū)的不規(guī)則三角網(wǎng)數(shù)字水深模型的水深數(shù)據(jù)，共包含12 477個水深點；試驗環(huán)境為Inter(R)core(TM)i3處理器，主頻為3.4 GHz，內(nèi)存為2 G。采用兩種算法分別對原始TIN_DDM海底地形表面構(gòu)建緩沖半徑為500、1000、1500、2000、2500和3000 m的緩沖面，利用Matlab程序?qū)Ω骶彌_半徑的上下緩沖面的空間三角網(wǎng)進行可視化顯示并利用Surfer8.0軟件繪制各數(shù)據(jù)等深距為5m的等深線圖，試驗結(jié)果如表1所示。圖中紅方框所圈區(qū)域為TIN_DDM海底地形表面及其上下緩沖面所對應(yīng)的凹地形區(qū)域，紅橢圓圈所圈區(qū)域為TIN_DDM海底地形表面及其上下緩沖面所對應(yīng)的凸地形區(qū)域。

表1 試驗結(jié)果分析

續(xù)表1

續(xù)表1

續(xù)表1

試驗結(jié)果表明：①算法Ⅰ與算法Ⅱ的試驗結(jié)果相同；②上緩沖面的凹地形區(qū)域均有被填平或縮小的趨勢，且隨著緩沖半徑的增大，填平或縮小的趨勢逐漸變大，上緩沖面的凸地形區(qū)域形態(tài)雖然受到周圍地形的影響發(fā)生變化，但仍然保持凸部形態(tài)；③下緩沖面的凸地形區(qū)域均有被削平或縮小的趨勢，且隨著緩沖半徑的增大，削平或縮小的趨勢逐漸變大，下緩沖面的凹地形區(qū)域形態(tài)雖然受到周圍地形的影響發(fā)生變化，但仍然保持凹部形態(tài)；④由等深線圖可以看出，由于TIN_DDM上緩沖面“填凹保凸”和下緩沖面“削凸保凹”的特性，TIN_DDM緩沖面均逐漸趨于平坦，且各自然鄰點間的z坐標值變化幅度隨滾動球半徑的增大而減小。

此外，為驗證本文方法在模型精度保持上的優(yōu)勢，以文獻[12]所提算法構(gòu)建矢量緩沖面作為參考，借鑒TIN_DDM精度評估最常用的逐點檢查法來對3種算法所構(gòu)建緩沖面的精度進行對比分析，將檢查點按照50×50的網(wǎng)格進行分布，其中水深數(shù)據(jù)的測量中誤差σ為1 m，TIN_DDM平面Delaunay三角網(wǎng)中各自然鄰點間的最大間距值dmax為31.2 m。對文獻[12]所提算法和算法Ⅰ、Ⅱ(算法Ⅰ、Ⅱ試驗結(jié)果相同)所構(gòu)建的上緩沖面進行精度對比統(tǒng)計分析，試驗結(jié)果如表2所示。

表2 文獻[12]所提算法與算法Ⅰ、Ⅱ所構(gòu)建緩沖面精度對比統(tǒng)計

Tab.2 The comparing accuracy of the buffer surface constructed by the reference [12] and algorithm Ⅰ or Ⅱm

緩沖半徑檢查點最大差值檢查點最小差值對比精度值5001.9850.8531.94310001.9040.6471.54115001.7540.4971.29620001.4230.3081.10725001.2210.1681.00330001.0960.0860.788

最后，為體現(xiàn)本文所提面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型的效率優(yōu)勢，選取同一海區(qū)水深采樣點密度相差不大的3塊TIN_DDM進行試驗。試驗1的水深點數(shù)為12 477，試驗2的水深點數(shù)為18 825，試驗3的水深點數(shù)為25 042。對算法Ⅰ、Ⅱ的耗時情況分別進行統(tǒng)計分析，結(jié)果如圖6所示。此外，本文還嘗試利用文獻[12]所提算法構(gòu)建TIN_DDM矢量緩沖面，但由于三維空間求交運算消耗內(nèi)存較大，當前試驗環(huán)境已不支持整體TIN_DDM矢量緩沖面構(gòu)建及三維顯示。此處選取緩沖半徑為500 m，選取試驗1中70個水深采樣點進行矢量緩沖面構(gòu)建，其算法耗時為204 s。對于其中單個水深采樣點的等距離球面與其余等距離球面的求交運算時間平均為2.91 s。預(yù)估其整體TIN_DDM矢量緩沖面構(gòu)建時間為36 308 s，已遠遠超過算法Ⅰ和算法Ⅱ最大緩沖半徑時的緩沖面構(gòu)建時間，且隨著緩沖半徑的增大，參與各點等距離球面求交運算的其余等距離球面將更多，算法運行時間將更大。

圖6 各算法耗時統(tǒng)計圖Fig.6 The time loss of each algorithm

試驗結(jié)果表明：①本文所提算法Ⅱ前期需要進行數(shù)據(jù)預(yù)處理，主要建立TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，以實現(xiàn)對滾動球模型的加速優(yōu)化，而算法Ⅰ無須進行前期預(yù)處理；②在同一TIN_DDM內(nèi)不同緩沖半徑下的緩沖面構(gòu)建過程中，算法Ⅰ將滾動球模型應(yīng)用擴展至TIN_DDM緩沖面構(gòu)建中，采用單值曲面邏輯并運算法則代替大量的幾何求交運算，大大縮短算法耗時，將時間復(fù)雜度降至O(nr2)，而算法Ⅱ在算法Ⅰ的基礎(chǔ)上進行改進，通過TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點與滾動球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，對面向TIN_DDM緩沖面構(gòu)建的滾動球模型進行加速優(yōu)化，將后期應(yīng)用的時間復(fù)雜度降至O(n)；③隨著緩沖半徑的增大，算法Ⅰ的耗時逐漸增大，主要是由于隨著滾動球半徑的增大，參與各采樣點z軸方向上極值點確定的等距離球面逐漸增多，導(dǎo)致算法耗時增加，而算法Ⅱ后期主要通過簡單的數(shù)據(jù)查詢方式確定TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點，其算法耗時受緩沖半徑變化的影響較小，且各緩沖半徑的上下緩沖面構(gòu)建時間相差不大；④在不同TIN_DDM內(nèi)，算法Ⅰ的時間復(fù)雜度為O(nr2)，在同一緩沖半徑的條件下，其算法耗時與TIN_DDM的點數(shù)成正比關(guān)系，而對于算法Ⅱ，其前期預(yù)處理過程耗時與TIN_DDM數(shù)據(jù)點數(shù)和各水深采樣點所對應(yīng)的TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點個數(shù)均具有直接關(guān)系，則其算法前期預(yù)處理耗時與TIN_DDM的點數(shù)呈正相關(guān)關(guān)系，在后期應(yīng)用過程中，算法通過數(shù)據(jù)查詢方式確定TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點，其后期算法耗時與TIN_DDM的點數(shù)成正比關(guān)系。

4 結(jié) 論

本文在分析借鑒基于滾動球模型的單值曲面緩沖體邊界生成算法的基礎(chǔ)上，通過將滾動球模型引入至TIN_DDM緩沖面的構(gòu)建過程，提出了一種基于滾動球加速優(yōu)化模型的TIN_DDM緩沖面快速構(gòu)建算法。首先，針對滾動球模型在TIN_DDM緩沖面構(gòu)建過程中存在的精度應(yīng)用局限，分析論證了影響滾動球模型精度的關(guān)鍵誤差累積規(guī)律，并以滾動球半徑為關(guān)鍵閾值，建立了滾動球整體精度的定量評估與控制模型；其次，針對大數(shù)據(jù)量TIN_DDM緩沖面多次構(gòu)建的應(yīng)用效率需求，闡明了關(guān)鍵采樣點與滾動球半徑對TIN_DDM緩沖面構(gòu)建效率的影響機理，建立了關(guān)鍵采樣點的判定準則及與滾動球半徑的數(shù)值關(guān)聯(lián)關(guān)系，構(gòu)建了面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型；最后，結(jié)合試驗分析對本文模型與算法進行了精度與效率的驗證。試驗結(jié)果表明，本文算法可有效控制TIN_DDM緩沖面的構(gòu)建誤差，且可在一次數(shù)據(jù)預(yù)處理的前提下，實現(xiàn)大數(shù)據(jù)量TIN_DDM緩沖面的多次快速構(gòu)建。需要指出的是，本文方法主要針對單值曲面這類特殊形態(tài)的地理要素，通用性不強，且在算法解算過程中，并未涉及TIN_DDM數(shù)據(jù)分塊索引的建立與管理，難以實現(xiàn)模型的并行運算與處理。下一步將嘗試利用所提算法構(gòu)建非單值曲面緩沖體邊界，并進一步研究如何根據(jù)實際TIN_DDM水深采樣點分布情況進行數(shù)據(jù)的自適應(yīng)分塊及算法的并行運算等問題。