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

1. 海軍大連艦艇學(xué)院軍事海洋與測(cè)繪系，遼寧 大連 116018； 2. 海軍大連艦艇學(xué)院海洋測(cè)繪工程軍隊(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ū)分析稱(chēng)為緩沖體分析，由于DDM所固有的單值曲面特性，其緩沖體分析又被稱(chēng)為緩沖面分析[10-11]。近年來(lái)，隨著人類(lèi)對(duì)海底世界的全方位加速探索，應(yīng)用面向海底三維空間分析的DDM緩沖面構(gòu)建技術(shù)對(duì)于解決海底污染源擴(kuò)散、水下潛航器航行安全保障、海底礦藏分布探明和海底地形多尺度表達(dá)等問(wèn)題具有重要的理論和現(xiàn)實(shí)意義[11-19]。

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

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

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

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

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

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

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

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

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

(2)

(3)

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

(4)

(5)

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

(6)

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

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

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

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

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

柵格條件下單值曲面邏輯并運(yùn)算法則以一維條件下的數(shù)值比較運(yùn)算對(duì)TIN_DDM采樣點(diǎn)等距離面的曲面求交運(yùn)算進(jìn)行了等效簡(jiǎn)化，實(shí)現(xiàn)了給定緩沖半徑條件下TIN_DDM緩沖面的快速構(gòu)建。需要指出的是，該法則的運(yùn)用并未實(shí)質(zhì)性地減少參與等距離面構(gòu)建的TIN_DDM采樣點(diǎn)數(shù)量，對(duì)于工程實(shí)踐中可能出現(xiàn)的高密度TIN_DDM緩沖面多次重復(fù)構(gòu)建應(yīng)用，緩沖半徑對(duì)算法時(shí)間復(fù)雜度的數(shù)值影響會(huì)逐漸增強(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)建效率問(wèn)題的技術(shù)前提。

柵格條件下單值曲面邏輯并運(yùn)算法則需對(duì)每個(gè)TIN_DDM采樣點(diǎn)進(jìn)行ρπr2次計(jì)算，以此確定該TIN_DDM采樣點(diǎn)對(duì)應(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)對(duì)應(yīng)緩沖面邊界點(diǎn)解算過(guò)程中的ρπr2次計(jì)算，可由該采樣點(diǎn)與其對(duì)應(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í)行效率的核心問(wèn)題。如圖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)的距離為滾動(dòng)球半徑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)之下。對(duì)于曲面T上與Q1點(diǎn)相異的任意一點(diǎn)Q2而言，則P′點(diǎn)至Q2點(diǎn)的距離d始終大于滾動(dòng)球半徑r，即Q1點(diǎn)為P′點(diǎn)在曲面T上的最近點(diǎn)(且距離等于滾動(dòng)球半徑r)。因此，在上(下)緩沖面點(diǎn)z軸方向上形成極大(小)值的等距離球面所對(duì)應(yīng)的球心采樣點(diǎn)即為該上(下)緩沖面點(diǎn)所對(duì)應(yīng)的TIN_DDM上的最近點(diǎn)(即TIN_DDM緩沖面構(gòu)建的關(guān)鍵采樣點(diǎn))。基于上述分析，本文提出如下TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)判定步驟：

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

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

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

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

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

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

(7)

(8)

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

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

圖5 TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)與滾動(dòng)球半徑的數(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)證算法的可行性，本文通過(guò)Matlab編程實(shí)現(xiàn)了基于滾動(dòng)球模型的TIN_DDM緩沖面構(gòu)建算法(以下簡(jiǎn)稱(chēng)算法Ⅰ)和基于滾動(dòng)球加速優(yōu)化模型的TIN_DDM緩沖面快速構(gòu)建算法(以下簡(jiǎn)稱(chēng)算法Ⅱ)，并利用Matlab的三維顯示功能對(duì)兩類(lèi)算法的試驗(yàn)結(jié)果進(jìn)行了可視化顯示與分析。

試驗(yàn)所采用的數(shù)據(jù)為我國(guó)東海某海區(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。采用兩種算法分別對(duì)原始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)門(mén)IN_DDM海底地形表面及其上下緩沖面所對(duì)應(yīng)的凹地形區(qū)域，紅橢圓圈所圈區(qū)域?yàn)門(mén)IN_DDM海底地形表面及其上下緩沖面所對(duì)應(yīng)的凸地形區(qū)域。

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

續(xù)表1

續(xù)表1

續(xù)表1

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

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

表2 文獻(xiàn)[12]所提算法與算法Ⅰ、Ⅱ所構(gòu)建緩沖面精度對(duì)比統(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)最小差值對(duì)比精度值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)建的滾動(dòng)球加速優(yōu)化模型的效率優(yōu)勢(shì)，選取同一海區(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。對(duì)算法Ⅰ、Ⅱ的耗時(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。對(duì)于其中單個(gè)水深采樣點(diǎn)的等距離球面與其余等距離球面的求交運(yùn)算時(shí)間平均為2.91 s。預(yù)估其整體TIN_DDM矢量緩沖面構(gòu)建時(shí)間為36 308 s，已遠(yuǎn)遠(yuǎn)超過(guò)算法Ⅰ和算法Ⅱ最大緩沖半徑時(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)與滾動(dòng)球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，以實(shí)現(xiàn)對(duì)滾動(dòng)球模型的加速優(yōu)化，而算法Ⅰ無(wú)須進(jìn)行前期預(yù)處理；②在同一TIN_DDM內(nèi)不同緩沖半徑下的緩沖面構(gòu)建過(guò)程中，算法Ⅰ將滾動(dòng)球模型應(yīng)用擴(kuò)展至TIN_DDM緩沖面構(gòu)建中，采用單值曲面邏輯并運(yùn)算法則代替大量的幾何求交運(yùn)算，大大縮短算法耗時(shí)，將時(shí)間復(fù)雜度降至O(nr2)，而算法Ⅱ在算法Ⅰ的基礎(chǔ)上進(jìn)行改進(jìn)，通過(guò)TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)與滾動(dòng)球半徑之間的數(shù)值關(guān)聯(lián)性數(shù)據(jù)鏈，對(duì)面向TIN_DDM緩沖面構(gòu)建的滾動(dòng)球模型進(jìn)行加速優(yōu)化，將后期應(yīng)用的時(shí)間復(fù)雜度降至O(n)；③隨著緩沖半徑的增大，算法Ⅰ的耗時(shí)逐漸增大，主要是由于隨著滾動(dòng)球半徑的增大，參與各采樣點(diǎn)z軸方向上極值點(diǎn)確定的等距離球面逐漸增多，導(dǎo)致算法耗時(shí)增加，而算法Ⅱ后期主要通過(guò)簡(jiǎn)單的數(shù)據(jù)查詢(xún)方式確定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)系，而對(duì)于算法Ⅱ，其前期預(yù)處理過(guò)程耗時(shí)與TIN_DDM數(shù)據(jù)點(diǎn)數(shù)和各水深采樣點(diǎn)所對(duì)應(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)用過(guò)程中，算法通過(guò)數(shù)據(jù)查詢(xún)方式確定TIN_DDM緩沖面構(gòu)建關(guān)鍵采樣點(diǎn)，其后期算法耗時(shí)與TIN_DDM的點(diǎn)數(shù)成正比關(guān)系。

4 結(jié) 論

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