基于四叉樹(shù)算法優(yōu)化檢索效率的三維建模技術(shù)

盧鵬飛，黃軻，龍奎，魏文剛，潘聲勇，楊其菠，江君

(1.重慶市地質(zhì)環(huán)境監(jiān)測(cè)總站，重慶 401120；2.武漢中地?cái)?shù)碼科技有限公司，武漢 430074；3.重慶地質(zhì)礦產(chǎn)研究院，重慶 400042)

基于四叉樹(shù)算法優(yōu)化檢索效率的三維建模技術(shù)

盧鵬飛1，黃軻2，龍奎1，魏文剛2，潘聲勇2，楊其菠2，江君3

(1.重慶市地質(zhì)環(huán)境監(jiān)測(cè)總站，重慶 401120；2.武漢中地?cái)?shù)碼科技有限公司，武漢 430074；3.重慶地質(zhì)礦產(chǎn)研究院，重慶 400042)

三維地質(zhì)建模是研究如何利用GIS軟件將三維空間地質(zhì)實(shí)體真實(shí)地再現(xiàn)，實(shí)現(xiàn)地質(zhì)體的三維可視化和相關(guān)空間分析，為地質(zhì)研究和礦產(chǎn)資源勘查提供技術(shù)支撐。本文在綜合前人研究成果的基礎(chǔ)上，對(duì)目前常用的基于MapGIS的三維地質(zhì)建模方法進(jìn)行了總結(jié)，并提出了一種利用四叉樹(shù)算法優(yōu)化檢索效率的三維建模技術(shù)，對(duì)于解決城市地質(zhì)、工程地質(zhì)、環(huán)境地質(zhì)、三維地質(zhì)填圖中的三維建模問(wèn)題具有重要意義。

三維地質(zhì)建模；MapGIS；四叉樹(shù)；檢索效率

1 引言

三維地質(zhì)建模(Three-dimensional Geological Modeling)，即三維GIS技術(shù)在地學(xué)上的應(yīng)用[1]，以各種原始數(shù)據(jù)(包括鉆孔、剖面、地震數(shù)據(jù)、等深圖、地質(zhì)圖、地形圖、物探數(shù)據(jù)、化探數(shù)據(jù)、工程勘察數(shù)據(jù)、水文監(jiān)測(cè)數(shù)據(jù)等)為基礎(chǔ)，建立能夠反映地質(zhì)構(gòu)造形態(tài)、構(gòu)造關(guān)系及地質(zhì)體內(nèi)部屬性變化規(guī)律的數(shù)字化模型[2]。相對(duì)于傳統(tǒng)的二維地質(zhì)數(shù)據(jù)表示方法，三維模型能夠完整準(zhǔn)確地表達(dá)復(fù)雜地質(zhì)現(xiàn)象的邊界條件及地質(zhì)體內(nèi)含的各種地質(zhì)構(gòu)造，直觀地再現(xiàn)地質(zhì)單元的空間展布及相互關(guān)系，最大限度地提高地質(zhì)分析的直觀性和準(zhǔn)確性[3]。如今在資源和環(huán)境的雙重壓力下，地質(zhì)找礦，地質(zhì)災(zāi)害監(jiān)測(cè)預(yù)警的研究更加深入，傳統(tǒng)的二維地質(zhì)圖主要專(zhuān)注于地表和淺部的地質(zhì)環(huán)境，已經(jīng)無(wú)法滿(mǎn)足地球科學(xué)發(fā)展和資源環(huán)境的需求，人們逐漸開(kāi)始將眼光轉(zhuǎn)向地球深部，對(duì)三維地質(zhì)模型的構(gòu)建提出了要求。

目前，國(guó)內(nèi)對(duì)于三維地質(zhì)建模的研究主要體現(xiàn)在兩個(gè)方面：①三維地質(zhì)建模的基礎(chǔ)原理和技術(shù)研究，包括三維數(shù)據(jù)模型、建模方法等；②三維地質(zhì)模型構(gòu)建的具體方法和應(yīng)用研究[4-6]。在利用城市多專(zhuān)題的地質(zhì)數(shù)據(jù)進(jìn)行三維地質(zhì)模型構(gòu)建時(shí)，針對(duì)不同類(lèi)型、不同特性的地質(zhì)數(shù)據(jù)，選擇不同的三維建模方法[7]。本文綜合前人的研究成果[8-12]，重點(diǎn)總結(jié)三維結(jié)構(gòu)模型的構(gòu)建技術(shù)。

2 常用三維地質(zhì)建模方法對(duì)比

2.1 多源數(shù)據(jù)耦合層狀地質(zhì)體自動(dòng)建模

對(duì)于工程地質(zhì)、水文地質(zhì)等簡(jiǎn)單層狀地質(zhì)體，可采用“鉆孔-剖面/等值線-地層實(shí)體”構(gòu)模的整體建模思路(圖1)。采用所有地層界面共用的網(wǎng)格模板來(lái)構(gòu)建各個(gè)地層面，根據(jù)建模范圍和精度(網(wǎng)格間距)要求生成地形網(wǎng)格。在此基礎(chǔ)上，從基礎(chǔ)數(shù)據(jù)庫(kù)中提取鉆孔點(diǎn)位和分層信息疊加等值線數(shù)據(jù)生成地層面強(qiáng)約束點(diǎn)，從剖面中提取有關(guān)地層邊界線信息，基于地形網(wǎng)格應(yīng)用這兩類(lèi)數(shù)據(jù)進(jìn)行插值計(jì)算構(gòu)造各地層面模型，最后根據(jù)地層之間的疊覆關(guān)系等地質(zhì)信息生成地層實(shí)體模型。同時(shí)，對(duì)于地表模型可添加地形約束，構(gòu)建出真實(shí)地形地貌單元的地質(zhì)模型。對(duì)建立完的地質(zhì)模型，可以不斷的添加各種約束數(shù)據(jù)，指定約束數(shù)據(jù)的影響范圍，對(duì)地質(zhì)模型進(jìn)行反復(fù)的重構(gòu)更新，從而更精確的去表現(xiàn)真實(shí)的地質(zhì)形態(tài)。

圖1 多源數(shù)據(jù)耦合層狀地質(zhì)體自動(dòng)建模

2.2 基于地層分區(qū)圖的地質(zhì)圖快速建模

基于地層分區(qū)圖的地質(zhì)圖快速建模方法采用“自頂向下”的思想，逐層建立每一個(gè)層面的頂層地質(zhì)面(圖2)。最頂層面看作是一個(gè)完整的地質(zhì)面，以這個(gè)完整的地質(zhì)面為基礎(chǔ)，根據(jù)每一個(gè)層面的地質(zhì)分區(qū)圖，向下逐層建立地質(zhì)面。按由粗到精的建模思想進(jìn)行建模，分別按系、統(tǒng)、組、段和巖性等進(jìn)行劃分，依次建立一級(jí)、二級(jí)、三級(jí)和四級(jí)等地質(zhì)模型。使用鉆孔、剖面、等高線、平面地質(zhì)圖、地層分區(qū)圖等多源數(shù)據(jù)作為三維建模的數(shù)據(jù)源，首先進(jìn)行建模數(shù)據(jù)的一致性處理，數(shù)據(jù)處理工作貫穿整個(gè)建模流程。

整體建模過(guò)程為：首先，建立地表地質(zhì)分區(qū)圖約束下的地質(zhì)子面；其次，通過(guò)剝離當(dāng)前需要處理的地層，將后續(xù)地質(zhì)表面建模轉(zhuǎn)化為最上層的地質(zhì)子面建模；然后，通過(guò)標(biāo)準(zhǔn)地層層序，依次構(gòu)建出所有地質(zhì)體的地質(zhì)子面模型；最后，通過(guò)拓?fù)涮幚?，?gòu)建出地層實(shí)體結(jié)構(gòu)模型。

2.3 基于剖面的復(fù)雜地質(zhì)體半自動(dòng)交互建模

根據(jù)地質(zhì)數(shù)據(jù)特點(diǎn)，可應(yīng)用剖面交互式建模方法構(gòu)建基巖地質(zhì)三維地質(zhì)結(jié)構(gòu)模型、第四系地質(zhì)三維地質(zhì)結(jié)構(gòu)模型。

圖2 分區(qū)圖建模流程

由于地質(zhì)專(zhuān)業(yè)不同，勘探線的布置方法不同。實(shí)際建模中往往會(huì)遇到空間位置近似交叉和近似平行的兩種剖面情況，分為基于近似平行剖面的輪廓線拼接和基于單元格的“分區(qū)-拼接”兩種交互建模方法(圖3)。根據(jù)建模范圍內(nèi)的實(shí)際地質(zhì)情況，基巖地質(zhì)模型和第四紀(jì)地質(zhì)模型一般可采用這種建模方法，這種建模方法將復(fù)雜模型進(jìn)行分割，便于觀察和操作，也便于分工合作完成大數(shù)據(jù)量復(fù)雜模型構(gòu)建。

圖3 基于輪廓線拼接的剖面建模

2.4 基于“分區(qū)-拼接”的半自動(dòng)建模

“分區(qū)-拼接”建模方法采用“分治”的方法將復(fù)雜模型進(jìn)行分割，便于觀察和操作，也便于分工合作完成大數(shù)據(jù)量復(fù)雜模型構(gòu)建(圖4)。其建模基本思路為：利用建模區(qū)域內(nèi)多條交叉剖面將空間分割成多個(gè)單元格，用戶(hù)建模的最小單元就是一個(gè)個(gè)單元格，所做工作就是利用單個(gè)單元格內(nèi)一系列閉合輪廓線建立起曲面片，進(jìn)而確定該單元格內(nèi)所有地質(zhì)體的空間幾何形態(tài)，形成一個(gè)單元格地質(zhì)塊，最后將每個(gè)單元格的地質(zhì)塊進(jìn)行合并形成完整的地質(zhì)體模型。對(duì)于非交叉剖面或邊界處無(wú)法自然封閉的單元格，可以通過(guò)手動(dòng)添加輔助線的方式進(jìn)行封閉，之后按照封閉單元格相同方式建模。除剖面數(shù)據(jù)外，在單元格內(nèi)的空白區(qū)域，如果有鉆孔、等值線數(shù)據(jù)能夠揭示地質(zhì)體或地質(zhì)構(gòu)造信息，也可將這些信息在構(gòu)面過(guò)程中加以利用，提高模型精度。

3 利用四叉樹(shù)算法改進(jìn)三維建模技術(shù)

3.1 四叉樹(shù)定義

四叉樹(shù)(也被稱(chēng)為Q樹(shù)、Q-Tree)是在二維圖片中定位像素的唯一適合的算法。因?yàn)槎S空間中，平面像素可以重復(fù)的被分為四部分，樹(shù)的深度由圖片、計(jì)算機(jī)內(nèi)存和圖形的復(fù)雜度決定。在二維平面中，可以使用兩條正交的直線將一個(gè)矩形的區(qū)域劃分為4個(gè)部分，這4個(gè)部分正好與四叉樹(shù)的4個(gè)子節(jié)點(diǎn)對(duì)應(yīng)，如圖5所示。

四叉樹(shù)(quad-tree)每個(gè)節(jié)點(diǎn)最多有4個(gè)子樹(shù)，可以用來(lái)在數(shù)據(jù)庫(kù)中放置和定位文件(稱(chēng)作記錄或鍵)。這一算法通過(guò)不停的把要查找的記錄分成4部分來(lái)進(jìn)行匹配查找直到僅剩下一條記錄為止。

圖4 半自動(dòng)復(fù)雜地質(zhì)體快速交互式建模技術(shù)

圖5 四叉樹(shù)劃分二維區(qū)域?qū)嵗?/p>

在樹(shù)中，記錄被存儲(chǔ)在葉子的位置上。這一名字的由來(lái)是因?yàn)橛涗洷淮鎯?chǔ)在端點(diǎn)上，他們上面再?zèng)]有節(jié)點(diǎn)了。分支被稱(chēng)作節(jié)點(diǎn)。數(shù)的順序是每節(jié)點(diǎn)的分支(也稱(chēng)孩子)數(shù)。在四叉樹(shù)中，每個(gè)節(jié)點(diǎn)通常有4個(gè)孩子，因此順序是4。四叉樹(shù)的葉子數(shù)也是4。為達(dá)到想要的記錄所進(jìn)行的查找操作次數(shù)成為樹(shù)的深度。

對(duì)于地理空間信息，四叉樹(shù)定義是：它的每個(gè)節(jié)點(diǎn)下至多可以有4個(gè)子節(jié)點(diǎn)，通常把一部分二維空間細(xì)分為4個(gè)象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹(shù)節(jié)點(diǎn)中。這個(gè)區(qū)域可以是正方形、矩形或是任意形狀。

3.2 四叉樹(shù)的常規(guī)檢索過(guò)程和構(gòu)建過(guò)程

對(duì)二維空間進(jìn)行劃分之后，可以實(shí)現(xiàn)對(duì)指定點(diǎn)或者指定矩形范圍內(nèi)存在哪些數(shù)據(jù)進(jìn)行快速檢索。通常，進(jìn)行四叉樹(shù)檢索的流程如下：

(1) 從四叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，判斷該節(jié)點(diǎn)是否與指定的范圍相交。

(2) 如果不相交，則在指定的范圍內(nèi)不存在數(shù)據(jù)。

(3) 如果相交，再對(duì)節(jié)點(diǎn)的4個(gè)子節(jié)點(diǎn)進(jìn)行同樣的處理，直到找到所有沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

(4) 第3)步中找到的所有節(jié)點(diǎn)所包含的數(shù)據(jù)，即為最后的檢索結(jié)果。

從檢索的過(guò)程可以看到，檢索的思路類(lèi)似于二分查找，不過(guò)此處使用的是更復(fù)雜的四分法。在不停的四分的過(guò)程中，不斷的將檢索的范圍縮小。相對(duì)于在整個(gè)數(shù)據(jù)集合中進(jìn)行遍歷查找，效率當(dāng)然更高。理論上可以達(dá)到O(n)的時(shí)間復(fù)雜度。而四叉樹(shù)的實(shí)現(xiàn)過(guò)程，又非常簡(jiǎn)單。

所以四叉樹(shù)很適合進(jìn)行二維的數(shù)據(jù)處理，例如二維的空間索引、二維圖像數(shù)據(jù)壓縮，還包括圖像處理、二維快速碰撞檢測(cè)、存儲(chǔ)稀疏數(shù)據(jù)等。圖6是將二維點(diǎn)位數(shù)據(jù)進(jìn)行四叉樹(shù)構(gòu)建的示例。

圖6 二維點(diǎn)位數(shù)據(jù)的四叉樹(shù)構(gòu)建

(1) 首先將所有數(shù)據(jù)使用藍(lán)色的線兩分為四，為樹(shù)中的一級(jí)節(jié)點(diǎn)。

(2) 現(xiàn)在下方的兩個(gè)矩形區(qū)域，每一個(gè)矩形內(nèi)已經(jīng)只有一個(gè)數(shù)據(jù)，可以不進(jìn)行下一級(jí)的細(xì)分了。上方的兩個(gè)矩形區(qū)域，還需要進(jìn)一步細(xì)分。

(3) 使用紅色的線，將上方的兩個(gè)矩形區(qū)域分別重復(fù)步驟(1)進(jìn)行兩分操作，得到樹(shù)的二級(jí)節(jié)點(diǎn)。此時(shí)又有一部分矩形區(qū)域已經(jīng)滿(mǎn)足不需進(jìn)一步細(xì)分的條件。

(4) 將所有不滿(mǎn)足停止細(xì)分條件的矩形進(jìn)行遞歸細(xì)分處理，最后可以得到一個(gè)完整的四叉樹(shù)索引。

3.3 四叉樹(shù)的優(yōu)化方案

通過(guò)大量的數(shù)據(jù)測(cè)試與分析，我們發(fā)現(xiàn)，四叉樹(shù)的檢索效率會(huì)隨著樹(shù)的深度的增加而嚴(yán)重下降。為了解決這個(gè)問(wèn)題，我們對(duì)四叉樹(shù)進(jìn)行了改進(jìn)，在四叉樹(shù)中加入了兩個(gè)閾值。

(1) 四叉樹(shù)的最大深度h可以設(shè)置。

(2) 四叉樹(shù)的每一個(gè)節(jié)點(diǎn)包含的數(shù)據(jù)個(gè)數(shù)n可以設(shè)置。

(3) 進(jìn)行四叉樹(shù)節(jié)點(diǎn)細(xì)分時(shí)，先判斷該節(jié)點(diǎn)的深度是否小于h。如果不小于h，則不進(jìn)行進(jìn)一步細(xì)分；如果小于h，則進(jìn)行下一步判斷。

(4) 判斷節(jié)點(diǎn)所包含的數(shù)據(jù)，是否大于n。如果不大于n，也不進(jìn)行細(xì)分；如果大于n，則進(jìn)行一次細(xì)分。

通過(guò)加入樹(shù)的最大深度h和節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)n兩個(gè)控制項(xiàng)，我們簡(jiǎn)化了四叉樹(shù)的結(jié)構(gòu)，通過(guò)不斷的調(diào)節(jié)h和n兩參數(shù)，達(dá)到檢索效率的最優(yōu)。

另外，為了使得四叉樹(shù)可以較好的擴(kuò)展，以適應(yīng)各種復(fù)雜的應(yīng)用場(chǎng)景，我們采用模板的方式實(shí)現(xiàn)四叉樹(shù)。由于C++不支持浮點(diǎn)數(shù)類(lèi)型(float,double)，我們使用了數(shù)據(jù)精度的倒數(shù)來(lái)確定四叉樹(shù)的檢索精度。

3.4 四叉樹(shù)的C++實(shí)現(xiàn)過(guò)程

簡(jiǎn)單介紹了四叉樹(shù)的原理以及一些簡(jiǎn)單的改進(jìn)方案之后，我們來(lái)看看四叉樹(shù)的一個(gè)C++實(shí)現(xiàn)版本。主要定義了4個(gè)類(lèi)：CRect、CQTreeNode、CQTreeDataBase、CQTreeBase。

(1) CRect用于抽象二維空間范圍。

(2) CQTreeNode用于抽象四叉樹(shù)節(jié)點(diǎn)。

(3) CQTreeDataBase用于抽象二維的數(shù)據(jù)。

(4) CQTreeBase用于抽象四叉樹(shù)。

這4個(gè)類(lèi)相互結(jié)合，最終完成四叉樹(shù)的完整功能實(shí)現(xiàn)。下面是4個(gè)類(lèi)的聲明和關(guān)鍵接口說(shuō)明：

(1) CRect

用于抽象二維空間范圍，還實(shí)現(xiàn)了四叉樹(shù)檢索中的空間范圍相交判斷算法以及空間四分算法，聲明如下：

// Effect: -矩形坐標(biāo)范圍

// TCoor: -坐標(biāo)的數(shù)據(jù)類(lèi)型，如int、float、double等數(shù)值型

// precision 坐標(biāo)計(jì)算的精度

// Brief : -

template

class CRect

{

public:

CRect();

explicit CRect(TCoor xmin, TCoor ymin, TCoor xmax, TCoor ymax);

virtual ～CRect();

//

}

①自動(dòng)拆分范圍

// Effect: -獲取左上角拆分范圍

// Rtn: -

// Brief : -

CRect GetLTRect();

// Effect: -獲取右上角拆分范圍

// Rtn: -

// Brief : -

CRect GetRTRect();

// Effect: -獲取左下角拆分范圍

// Rtn: -

// Brief : -

CRect GetLBRect();

// Effect: -獲取右下角拆分范圍

// Rtn: -

// Brief : -

CRect GetRBRect();

②范圍相交判斷

// Effect: -判斷指定的點(diǎn)位是否在舉行范圍內(nèi)

// In : -

// In : -

// Rtn : -

// Brief : -

bool Inter(TCoor x, TCoor y);

// Effect: -判斷指定的矩形范圍是否和當(dāng)前范圍相交

// In : -

// Rtn : -

// Brief : -

bool Inter(const CRect& rhs);

(2) CQTreeNode

用于抽象四叉樹(shù)節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)二維空間范圍以及數(shù)據(jù)的管理，聲明如下：

// Effect: -四叉樹(shù)節(jié)點(diǎn)

// TCoor : -坐標(biāo)的數(shù)據(jù)類(lèi)型，如int、float、double等數(shù)值型

// TData : -節(jié)點(diǎn)攜帶的數(shù)據(jù)的類(lèi)型

// Brief : -

template

class CQTreeNode

{

public:

// 矩形范圍

typedef CRect CRect;

explicit CQTreeNode(CRect rect, ushort depth);

explicit CQTreeNode(CRect rect, ushort depth, vector datas);

～CQTreeNode();

//

}

關(guān)鍵接口與成員如下：

// Effect: -判斷指定的點(diǎn)位是否在節(jié)點(diǎn)內(nèi)部

// In : -

// In : -

// Brief : -

bool IsCoorInNode(TCoor x, TCoor y) const;

// 節(jié)點(diǎn)的數(shù)據(jù)范圍，所有子節(jié)點(diǎn)的范圍的并集

CRect _rect;

// 四個(gè)子節(jié)點(diǎn)

CQTreeNode* _lt; // 左上

CQTreeNode* _rt; // 右上

CQTreeNode* _lb; // 左下

CQTreeNode* _rb; // 右下

vector _datas; // 節(jié)點(diǎn)數(shù)據(jù)

ushort _depth; // 節(jié)點(diǎn)的深度

(3) CQTreeDataBase

這是一個(gè)抽象類(lèi)，用于抽象二維的數(shù)據(jù)。要求所有的數(shù)據(jù)類(lèi)，必須從此類(lèi)派生。聲明如下：

// Effect: -四叉樹(shù)數(shù)據(jù)基類(lèi)

// TCoor : -坐標(biāo)的數(shù)據(jù)類(lèi)型，如int、float、double等數(shù)值型

// Brief : -定義四叉樹(shù)數(shù)據(jù)必須實(shí)現(xiàn)的接口

template

class CQTreeDataBase

{

public:

explicit CQTreeDataBase() { }

virtual ～CQTreeDataBase() { }

// 獲取X坐標(biāo)

virtual TCoor X() const = 0;

// 獲取Y坐標(biāo)

virtual TCoor Y() const = 0;

};

(4) CQTreeBase

用于抽象四叉樹(shù)，是四叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的完整定義。該類(lèi)使用模板類(lèi)實(shí)現(xiàn)，同時(shí)可以支持派生子類(lèi)，可以很好的進(jìn)行擴(kuò)展，以適應(yīng)不同的業(yè)務(wù)邏輯。聲明如下：

// Effect: -四叉樹(shù)基類(lèi)

// TCoor : -坐標(biāo)的類(lèi)型，例如int,float,double等

// TData : -數(shù)據(jù)的類(lèi)型，必須實(shí)現(xiàn)CQTreeDataBase所指定的接口

// int precision : -坐標(biāo)比較的精度的倒數(shù)，如E-6,則傳入E6

// Brief : - int precision使用精度的倒數(shù)的原因是浮點(diǎn)型不能作為模板參數(shù)

template

class CQTreeBase

{

public:

// 矩形范圍

typedef CRect CRect;

// 四叉樹(shù)節(jié)點(diǎn)

typedef CQTreeNode CQTreeNode;

// Effect: -構(gòu)造一個(gè)四叉樹(shù)對(duì)象

// In : -整體的數(shù)據(jù)范圍，在該范圍之外的數(shù)據(jù)，無(wú)法加入到四叉樹(shù)中

// In : -四叉樹(shù)的最大深度，深度達(dá)到最大值的節(jié)點(diǎn)，將停止拆分

// In : -每一個(gè)四叉樹(shù)節(jié)點(diǎn)可以攜帶的最大數(shù)據(jù)點(diǎn)位個(gè)數(shù)，

// 當(dāng)節(jié)點(diǎn)攜帶的數(shù)據(jù)點(diǎn)位個(gè)數(shù)超過(guò)該值時(shí)，節(jié)點(diǎn)將自動(dòng)拆分

// Brief : -

CQTreeBase(const CRect& rect, ushort maxDepth, ulong maxDataNum);

virtual ～CQTreeBase();

// ……

};

關(guān)鍵接口：

①矩形檢索，實(shí)現(xiàn)在四叉樹(shù)中的矩形范圍檢索

// Effect: - 矩形檢索

// In : - 坐標(biāo)范圍

// In : -

// In : -

// In : -

// Out : - 檢索結(jié)果

// Rtn : - 矩形內(nèi)部或者矩形邊上的點(diǎn)

// Brief : - 數(shù)據(jù)量很大的時(shí)候，不推薦調(diào)用該函數(shù)獲取結(jié)果

bool Search(TCoor xmin, TCoor ymin, TCoor xmax, TCoor ymax, vector& hitedDatas) const;

// Effect: - 矩形檢索

// In : - 坐標(biāo)范圍

// In : -

// In : -

// In : -

// Out: - 檢索結(jié)果

// Rtn: - 與矩形碰撞的節(jié)點(diǎn)

// Brief : -

bool Search(TCoor xmin, TCoor ymin, TCoor xmax, TCoor ymax, vector& hitedNode) const;

②點(diǎn)檢索，實(shí)現(xiàn)四叉樹(shù)的點(diǎn)位檢索

// Effect: - 點(diǎn)檢索

// In : -

// In : -

// Rtn : - 該點(diǎn)所在的節(jié)點(diǎn)

// Brief : -

CQTreeNode* Search(TCoor x, TCoor y) const;

// Effect: - 點(diǎn)檢索

// In : -

// In : -

// Rtn : - 該點(diǎn)所在的節(jié)點(diǎn)的第一個(gè)數(shù)據(jù)

// Brief : -

TData* SearchData(TCoor x, TCoor y) const;

③添加數(shù)據(jù)，實(shí)現(xiàn)添加一個(gè)數(shù)據(jù)到四叉樹(shù)中

// Effect: - 添加一個(gè)數(shù)據(jù)點(diǎn)到樹(shù)中

// In : - 數(shù)據(jù)

// Rtn : -

// Brief : -

bool AddData(TData* data);

④拆分節(jié)點(diǎn)，實(shí)現(xiàn)四叉樹(shù)的節(jié)點(diǎn)拆分功能

// Effect: - 拆分指定的節(jié)點(diǎn)

// In : -

// Rtn : -

// Brief : -

virtual bool SpiltNode(CQTreeNode* node);

⑤關(guān)鍵數(shù)據(jù)成員

protected:

CQTreeNode* _root; // 根節(jié)點(diǎn)

ushort _maxDepth; // 樹(shù)的最大深度

ulong_maxDataNum;

// 樹(shù)節(jié)點(diǎn)的最大數(shù)據(jù)數(shù)量

3.5 四叉樹(shù)在三維建模算法中的主要應(yīng)用

四叉樹(shù)主要用于分割二維空間，構(gòu)建快速索引。前文已經(jīng)介紹了四叉樹(shù)的基本原理，同時(shí)給出了一個(gè)典型的C++實(shí)現(xiàn)。下面將結(jié)合實(shí)際應(yīng)用，說(shuō)明四叉樹(shù)在重慶建模中的一些實(shí)際應(yīng)用。

(1) 緩存地表等高線

構(gòu)建模型的第一步，就是構(gòu)建模型的地表。構(gòu)建地表的數(shù)據(jù)，主要是地表等高線。在重慶建模時(shí)，使用的是一幅高精度的地表等高線。這幅等高線，在構(gòu)建每一個(gè)出露地層的地表面的時(shí)候，都要使用其作為高程數(shù)據(jù)源。

為了避免頻繁地打開(kāi)這幅高精度的等高線而導(dǎo)致系統(tǒng)效率低下的問(wèn)題，我們必須將其緩存在內(nèi)存中。當(dāng)然，常規(guī)的一維線性數(shù)組，是這完成不了這項(xiàng)工作的。

四叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)，恰好解決了這個(gè)問(wèn)題。由于沒(méi)有采用連續(xù)內(nèi)存存儲(chǔ)數(shù)據(jù)，理論上可以使用電腦的所有可用內(nèi)存；同時(shí)，四叉樹(shù)又提供了快速的數(shù)據(jù)檢索支持。所以立即決定使用四叉樹(shù)作為數(shù)據(jù)緩存的方式。在解決了內(nèi)存不足的問(wèn)題的同時(shí)，也為后續(xù)的地表構(gòu)建提供了快速數(shù)據(jù)檢索支持。

(2) 計(jì)算地表邊界高程

在有了四叉樹(shù)緩存的地表等高線數(shù)據(jù)之后，我們使用地層的地表邊界，從四叉中檢索出地層范圍內(nèi)的高程點(diǎn)，進(jìn)行三角化操作，可以得到完整的地表面，如圖7所示。

但是這個(gè)操作有一個(gè)前提，我們的地層地表邊界的z值必須確定。而事實(shí)上的邊界數(shù)據(jù)是沒(méi)有高程的。所以需要通過(guò)地表等高線，對(duì)邊界的z值進(jìn)行插值計(jì)算，來(lái)獲取邊界的z值，這樣才能正確構(gòu)建地表模型。

而地表等高線的數(shù)據(jù)量龐大，插值過(guò)程非常慢，甚至可能由于內(nèi)存不足而無(wú)法計(jì)算出邊界的z值。

圖7 利用邊界范圍和高程點(diǎn)插值構(gòu)建地表模型

此時(shí)，有兩種優(yōu)化方案來(lái)解決這個(gè)問(wèn)題：

①使用地層邊界內(nèi)的高程點(diǎn)對(duì)地層邊界z值進(jìn)行插值(圖8)。

圖8 利用地層邊界內(nèi)的高程點(diǎn)插值

②使用地層邊界一定范圍的緩沖范圍內(nèi)的高程點(diǎn)對(duì)地層邊界z值進(jìn)行插值(圖9)。

圖9 利用地層邊界緩沖范圍內(nèi)的高程點(diǎn)插值

對(duì)比之下，顯然第2種方案更優(yōu)：

①進(jìn)行調(diào)和插值的數(shù)據(jù)量，通常會(huì)更小，插值計(jì)算速度更快。

②對(duì)邊界z值插值的準(zhǔn)確性，理論上會(huì)更高。因?yàn)楂@取了邊界內(nèi)外的高程點(diǎn)進(jìn)行了計(jì)算。

但是地表邊界的緩沖范圍，通常是一個(gè)環(huán)形的區(qū)。然而四叉樹(shù)并不支持環(huán)形復(fù)雜區(qū)檢索，所以必須對(duì)算法思路進(jìn)行調(diào)整。采用對(duì)邊界進(jìn)行分段處理的方法，將邊界上的每一條線段進(jìn)行緩沖處理，得到每一條線段的緩沖范圍，并使用每一個(gè)范圍在四叉樹(shù)中進(jìn)行檢索，最后將檢索得到的高程數(shù)據(jù)合并為一個(gè)集合，對(duì)模型邊界進(jìn)行高程插值計(jì)算，可以得到地表邊界的高程值(圖10)。

可以看到，四叉樹(shù)在計(jì)算地層邊界的高程值時(shí)，在效率和準(zhǔn)確性方面，起到了關(guān)鍵性的作用。解決了大數(shù)據(jù)量下的高程插值導(dǎo)致的內(nèi)存不足和精度不夠的問(wèn)題。

圖10 邊界分段處理法插值

(3) 計(jì)算地層邊緣形態(tài)

在構(gòu)建模型的邊緣部分的時(shí)候，有兩種情況：

①邊緣地層厚度為0，地層在邊緣處尖滅(圖11)，此時(shí)需要處理地層的尖滅問(wèn)題。

圖11 地層尖滅于一點(diǎn)

②邊緣地層有一定的厚度，此時(shí)需要在地層邊緣處構(gòu)建一個(gè)豎直面來(lái)封閉地層模型。

在建模的整個(gè)流程中，地層邊緣形態(tài)是比較難處理的。在構(gòu)建模型這兩種邊緣模型的過(guò)程中，也使用到了四叉樹(shù)作為很重要的一種工具。

地層邊緣處理過(guò)程主要如下：

①處理地層尖滅

通過(guò)一定的技術(shù)手段，我們保證了模型在邊緣處的頂面和底面的邊界點(diǎn)的x、y坐標(biāo)一致。同時(shí)模型的頂面已經(jīng)構(gòu)建完成，頂面邊緣處的x、y、z值以及完整的坐標(biāo)序列已經(jīng)完成計(jì)算。此處的任務(wù)，就是計(jì)算地層底面邊緣的z值。

對(duì)問(wèn)題進(jìn)行進(jìn)一步分析可知，找到底面邊界上的每一個(gè)點(diǎn)A對(duì)應(yīng)的頂面邊界上的點(diǎn)B，并將B的z值作為A的z值，即可完成底面邊界z值計(jì)算的任務(wù)(圖12)。

圖12 底面邊界點(diǎn)z值使用頂面邊界z值

當(dāng)問(wèn)題轉(zhuǎn)化為一個(gè)二維點(diǎn)數(shù)據(jù)檢索的問(wèn)題，那么很自然的就聯(lián)想到使用四叉樹(shù)來(lái)處理。這是四叉樹(shù)的一個(gè)典型的應(yīng)用。使用模型的頂面邊界點(diǎn)，構(gòu)建一個(gè)四叉樹(shù)索引，再到四叉樹(shù)索引中檢索出底面邊界的每一個(gè)點(diǎn)的z即可(四叉樹(shù)的構(gòu)建參考3.4節(jié))。

②構(gòu)建豎直面封閉模型

本身已經(jīng)有一種自動(dòng)三角化的算法，可以實(shí)現(xiàn)側(cè)面的自動(dòng)構(gòu)建。但原算法在處理側(cè)面時(shí)存在一定的缺陷，沒(méi)有將x、y值相同的點(diǎn)進(jìn)行連接(圖13)。

圖13 一種不好的可能的三角化連接方式

這本身并不是一個(gè)非常影響建模效果的問(wèn)題，但是在存在一定角度的情況下，這種三角化很影響建模效果，導(dǎo)致模型的側(cè)面看起來(lái)很不自然。

當(dāng)然，此處和“處理地層尖滅”實(shí)際上是一個(gè)問(wèn)題，需要從頂面的邊界中，檢索出底面邊界的每一個(gè)點(diǎn)對(duì)應(yīng)的頂面邊界點(diǎn)，然后在三角化時(shí)，需要將頂面邊界和底面邊界相對(duì)的點(diǎn)連接在一起(圖14)。檢索的過(guò)程，和處理“處理地層尖滅”是相同的，此處不做詳細(xì)介紹。三角化的具體算法，也不在此處進(jìn)行討論。

圖14 優(yōu)化后的三角化效果

4 結(jié)語(yǔ)

三維地質(zhì)建模在現(xiàn)如今的城市地質(zhì)、三維地質(zhì)填圖研究項(xiàng)目中具有非常重要的作用。本文首先總結(jié)了幾種典型的基于MapGIS的三維地質(zhì)建模方法，然后提出了一種利用四叉樹(shù)算法改進(jìn)三維建模技術(shù)的方法。通過(guò)四叉樹(shù)算法優(yōu)化和改進(jìn)插值點(diǎn)檢索效率能較大的提高三維建模插值速度，極大地節(jié)省了建模時(shí)間。但是由于四叉樹(shù)是主要針對(duì)二維空間地理位置的一種算法，應(yīng)用到三維空間中存在一定的局限性。針對(duì)三維空間有另一種類(lèi)似的優(yōu)化算法，即八叉樹(shù)算法。如何利用八叉樹(shù)算法對(duì)三維地質(zhì)建模技術(shù)進(jìn)行優(yōu)化是后續(xù)改進(jìn)的一個(gè)大方向。

[1] 朱良峰,吳信才,劉修國(guó),等.基于鉆孔數(shù)據(jù)的三維地層模型的構(gòu)建[J].地理與地理信息科學(xué),2004,20(3):26-30.

[2] Simon W Houlding. 3D geoscientific modeling computer technique for geological characterization[M].Springer Verlag,1994.

[3] 陳學(xué)習(xí),吳立新,車(chē)德福,等.基于鉆孔數(shù)據(jù)的含斷層地質(zhì)體三維建模方法[J].煤田地質(zhì)與勘探,2005,33(5):5-8.

[4] 明鏡.三維地質(zhì)建模技術(shù)研究[J].地理與地理信息科學(xué),2011,27(4):14-18.

[5] 潘懋,方裕,屈紅剛.三維地質(zhì)建模若干基本問(wèn)題探討[J].地理與地理信息科學(xué),2007,23(3):1-5.

[6] 焦養(yǎng)泉,朱培民,雷新榮,等.地學(xué)空間信息可視化技術(shù)應(yīng)用研究[J].地質(zhì)科技情報(bào),2005,24(1):1-6.

[7] 潘懋,方裕,屈紅剛.三維地質(zhì)建模若干基本問(wèn)題探討[J].地理與地理信息科學(xué),2007,23(3):1-5.

[8] 張像源,王新春,孟利山.基于DSI算法和多源數(shù)據(jù)耦合的天津市中心城區(qū)工程地質(zhì)三維模型的建立[J].工程勘察,2013,41(5):76-80.

[9] 劉揚(yáng),宮阿都,李京.基于數(shù)據(jù)分層分塊的海量三維地形四叉樹(shù)簡(jiǎn)化模型[J].測(cè)繪學(xué)報(bào),2010,39(4):410-415.

[10]花衛(wèi)華,廖艷云,劉修國(guó),等.基于子面模板庫(kù)的第四紀(jì)三維地質(zhì)模型快速構(gòu)建[J].地球科學(xué)-中國(guó)地質(zhì)大學(xué)學(xué)報(bào),2013,38(5):1128-1134.

[11]明鏡.三維地質(zhì)建模技術(shù)[J].地理與地理信息科學(xué),2011,27(4):14-18.

[12]安聰榮,劉展,王心眾.基于層面結(jié)構(gòu)的地質(zhì)塊體拓?fù)潢P(guān)系的自動(dòng)構(gòu)建[J].測(cè)繪學(xué)報(bào),2012,41(1):147-151.

THREE-DIMENSIONAL MODELING TECHNOLOGY WITH OPTIMIZATION OF RETRIEVAL EFFICIENCY BASED ON QUATREE ALGORITHM

LU Peng-fei1，HUANG Ke2，LONG Kui1,WEI Wen-gang2，PAN Sheng-yong2，YANG Qi-bo2，JIANG Jun3

(1.Chongqing Institute of Geological Environment Monitoring, Chongqing 401120,China; 2.WUHAN ZONDY CYBER-TECH CO., LTD, Wuhan 430074,China; 3.Chongqing Institute of Geology and Mineral Resources, Chongqing 400042,China)

Three-dimensional geological modeling is to study how to obtain the realistically reproduction of the three-dimensional space and geological entity by GIS. It is able to realize three-dimensional visualization and correlation space analysis, providing technical support for geological research and mineral exploration. On the basis of previous research findings, several current three-dimensional geological modeling methods based on MapGIS are summarized. In addition, an improved three-dimensional modeling technology with optimization of retrieval efficiency taking advantage of quatree algorithm is proposed. It has significant meaning for solving problems related to urban geology, engineering geology, environmental geology and three-dimensional geological mapping.

three-dimensional geological modeling； MapGIS； quatree； retrieval efficiency

1006-4362(2017)02-0084-09

2017-02-17 改回日期： 2017-04-12

中國(guó)地質(zhì)調(diào)查局，重慶都市經(jīng)濟(jì)圈城市地質(zhì)調(diào)查(1212011220032)

P628

A

盧鵬飛(1986- )，男，漢族，工程師，本科，主要從事區(qū)域地質(zhì)調(diào)查、城市地質(zhì)三維建模等方面的研究。 E-mail：402443685@qq.com