不規(guī)則三角網(wǎng)數(shù)字水深模型緩沖面快速構(gòu)建的滾動球加速優(yōu)化算法

董 箭，張志衡，彭認(rèn)燦，李改肖，王 沫

1. 海軍大連艦艇學(xué)院軍事海洋與測繪系，遼寧 大連 116018； 2. 海軍大連艦艇學(xué)院海洋測繪工程軍隊(duì)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116018

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

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

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

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

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

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

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

由文獻(xiàn)[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)上的任意一點(diǎn);QT(xT,yT,zT)表示地理要素T上任意采樣點(diǎn);dmin(P,QT)表示緩沖體邊界B(T,r)上的P點(diǎn)至地理要素T上各個(gè)QT點(diǎn)間的三維歐氏距離最小值。

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

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)

(8)

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

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

圖5 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎ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 試驗(yàn)結(jié)果與分析

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

試驗(yàn)所采用的數(shù)據(jù)為我國東海某海區(qū)的不規(guī)則三角網(wǎng)數(shù)字水深模型的水深數(shù)據(jù)，共包含12 477個(gè)水深點(diǎn)；試驗(yàn)環(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)進(jìn)行可視化顯示并利用Surfer8.0軟件繪制各數(shù)據(jù)等深距為5m的等深線圖，試驗(yàn)結(jié)果如表1所示。圖中紅方框所圈區(qū)域?yàn)門IN_DDM海底地形表面及其上下緩沖面所對應(yīng)的凹地形區(qū)域，紅橢圓圈所圈區(qū)域?yàn)門IN_DDM海底地形表面及其上下緩沖面所對應(yīng)的凸地形區(qū)域。

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

續(xù)表1

續(xù)表1

續(xù)表1

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

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

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

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

緩沖半徑檢查點(diǎn)最大差值檢查點(diǎn)最小差值對比精度值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ū)水深采樣點(diǎn)密度相差不大的3塊TIN_DDM進(jìn)行試驗(yàn)。試驗(yàn)1的水深點(diǎn)數(shù)為12 477，試驗(yàn)2的水深點(diǎn)數(shù)為18 825，試驗(yàn)3的水深點(diǎn)數(shù)為25 042。對算法Ⅰ、Ⅱ的耗時(shí)情況分別進(jìn)行統(tǒng)計(jì)分析，結(jié)果如圖6所示。此外，本文還嘗試?yán)梦墨I(xiàn)[12]所提算法構(gòu)建TIN_DDM矢量緩沖面，但由于三維空間求交運(yùn)算消耗內(nèi)存較大，當(dāng)前試驗(yàn)環(huán)境已不支持整體TIN_DDM矢量緩沖面構(gòu)建及三維顯示。此處選取緩沖半徑為500 m，選取試驗(yàn)1中70個(gè)水深采樣點(diǎn)進(jìn)行矢量緩沖面構(gòu)建，其算法耗時(shí)為204 s。對于其中單個(gè)水深采樣點(diǎn)的等距離球面與其余等距離球面的求交運(yùn)算時(shí)間平均為2.91 s。預(yù)估其整體TIN_DDM矢量緩沖面構(gòu)建時(shí)間為36 308 s，已遠(yuǎn)遠(yuǎn)超過算法Ⅰ和算法Ⅱ最大緩沖半徑時(shí)的緩沖面構(gòu)建時(shí)間，且隨著緩沖半徑的增大，參與各點(diǎn)等距離球面求交運(yùn)算的其余等距離球面將更多，算法運(yùn)行時(shí)間將更大。

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

試驗(yàn)結(jié)果表明：①本文所提算法Ⅱ前期需要進(jìn)行數(shù)據(jù)預(yù)處理，主要建立TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)與滾動球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，以實(shí)現(xiàn)對滾動球模型的加速優(yōu)化，而算法Ⅰ無須進(jìn)行前期預(yù)處理；②在同一TIN_DDM內(nèi)不同緩沖半徑下的緩沖面構(gòu)建過程中，算法Ⅰ將滾動球模型應(yīng)用擴(kuò)展至TIN_DDM緩沖面構(gòu)建中，采用單值曲面邏輯并運(yùn)算法則代替大量的幾何求交運(yùn)算，大大縮短算法耗時(shí)，將時(shí)間復(fù)雜度降至O(nr2)，而算法Ⅱ在算法Ⅰ的基礎(chǔ)上進(jìn)行改進(jìn)，通過TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)與滾動球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，對面向TIN_DDM緩沖面構(gòu)建的滾動球模型進(jìn)行加速優(yōu)化，將后期應(yīng)用的時(shí)間復(fù)雜度降至O(n)；③隨著緩沖半徑的增大，算法Ⅰ的耗時(shí)逐漸增大，主要是由于隨著滾動球半徑的增大，參與各采樣點(diǎn)z軸方向上極值點(diǎn)確定的等距離球面逐漸增多，導(dǎo)致算法耗時(shí)增加，而算法Ⅱ后期主要通過簡單的數(shù)據(jù)查詢方式確定TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)，其算法耗時(shí)受緩沖半徑變化的影響較小，且各緩沖半徑的上下緩沖面構(gòu)建時(shí)間相差不大；④在不同TIN_DDM內(nèi)，算法Ⅰ的時(shí)間復(fù)雜度為O(nr2)，在同一緩沖半徑的條件下，其算法耗時(shí)與TIN_DDM的點(diǎn)數(shù)成正比關(guān)系，而對于算法Ⅱ，其前期預(yù)處理過程耗時(shí)與TIN_DDM數(shù)據(jù)點(diǎn)數(shù)和各水深采樣點(diǎn)所對應(yīng)的TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)個(gè)數(shù)均具有直接關(guān)系，則其算法前期預(yù)處理耗時(shí)與TIN_DDM的點(diǎn)數(shù)呈正相關(guān)關(guān)系，在后期應(yīng)用過程中，算法通過數(shù)據(jù)查詢方式確定TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)，其后期算法耗時(shí)與TIN_DDM的點(diǎn)數(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)鍵采樣點(diǎn)與滾動球半徑對TIN_DDM緩沖面構(gòu)建效率的影響機(jī)理，建立了關(guān)鍵采樣點(diǎn)的判定準(zhǔn)則及與滾動球半徑的數(shù)值關(guān)聯(lián)關(guān)系，構(gòu)建了面向TIN_DDM緩沖面構(gòu)建的滾動球加速優(yōu)化模型；最后，結(jié)合試驗(yàn)分析對本文模型與算法進(jìn)行了精度與效率的驗(yàn)證。試驗(yàn)結(jié)果表明，本文算法可有效控制TIN_DDM緩沖面的構(gòu)建誤差，且可在一次數(shù)據(jù)預(yù)處理的前提下，實(shí)現(xiàn)大數(shù)據(jù)量TIN_DDM緩沖面的多次快速構(gòu)建。需要指出的是，本文方法主要針對單值曲面這類特殊形態(tài)的地理要素，通用性不強(qiáng)，且在算法解算過程中，并未涉及TIN_DDM數(shù)據(jù)分塊索引的建立與管理，難以實(shí)現(xiàn)模型的并行運(yùn)算與處理。下一步將嘗試?yán)盟崴惴?gòu)建非單值曲面緩沖體邊界，并進(jìn)一步研究如何根據(jù)實(shí)際TIN_DDM水深采樣點(diǎn)分布情況進(jìn)行數(shù)據(jù)的自適應(yīng)分塊及算法的并行運(yùn)算等問題。