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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 四叉樹定義

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

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

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

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

在樹中，記錄被存儲在葉子的位置上。這一名字的由來是因為記錄被存儲在端點上，他們上面再沒有節(jié)點了。分支被稱作節(jié)點。數(shù)的順序是每節(jié)點的分支(也稱孩子)數(shù)。在四叉樹中，每個節(jié)點通常有4個孩子，因此順序是4。四叉樹的葉子數(shù)也是4。為達到想要的記錄所進行的查找操作次數(shù)成為樹的深度。

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

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

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

(1) 從四叉樹的根節(jié)點開始，判斷該節(jié)點是否與指定的范圍相交。

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

(3) 如果相交，再對節(jié)點的4個子節(jié)點進行同樣的處理，直到找到所有沒有子節(jié)點的節(jié)點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 四叉樹的C++實現(xiàn)過程

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

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

(2) CQTreeNode用于抽象四叉樹節(jié)點。

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

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

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

(1) CRect

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

// Effect: -矩形坐標范圍

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

// precision 坐標計算的精度

// Brief : -

template

class CRect

{

public:

CRect();

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

virtual ～CRect();

//

}

①自動拆分范圍

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

// Rtn: -

// Brief : -

CRect GetLTRect();

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

// Rtn: -

// Brief : -

CRect GetRTRect();

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

// Rtn: -

// Brief : -

CRect GetLBRect();

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

// Rtn: -

// Brief : -

CRect GetRBRect();

②范圍相交判斷

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

// In : -

// In : -

// Rtn : -

// Brief : -

bool Inter(TCoor x, TCoor y);

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

// In : -

// Rtn : -

// Brief : -

bool Inter(const CRect& rhs);

(2) CQTreeNode

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

// Effect: -四叉樹節(jié)點

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

// TData : -節(jié)點攜帶的數(shù)據(jù)的類型

// 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: -判斷指定的點位是否在節(jié)點內(nèi)部

// In : -

// In : -

// Brief : -

bool IsCoorInNode(TCoor x, TCoor y) const;

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

CRect _rect;

// 四個子節(jié)點

CQTreeNode* _lt; // 左上

CQTreeNode* _rt; // 右上

CQTreeNode* _lb; // 左下

CQTreeNode* _rb; // 右下

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

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

(3) CQTreeDataBase

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

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

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

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

template

class CQTreeDataBase

{

public:

explicit CQTreeDataBase() { }

virtual ～CQTreeDataBase() { }

// 獲取X坐標

virtual TCoor X() const = 0;

// 獲取Y坐標

virtual TCoor Y() const = 0;

};

(4) CQTreeBase

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

// Effect: -四叉樹基類

// TCoor : -坐標的類型，例如int,float,double等

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

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

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

template

class CQTreeBase

{

public:

// 矩形范圍

typedef CRect CRect;

// 四叉樹節(jié)點

typedef CQTreeNode CQTreeNode;

// Effect: -構(gòu)造一個四叉樹對象

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

// In : -四叉樹的最大深度，深度達到最大值的節(jié)點，將停止拆分

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

// 當節(jié)點攜帶的數(shù)據(jù)點位個數(shù)超過該值時，節(jié)點將自動拆分

// Brief : -

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

virtual ～CQTreeBase();

// ……

};

關(guān)鍵接口：

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

// Effect: - 矩形檢索

// In : - 坐標范圍

// In : -

// In : -

// In : -

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

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

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

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

// Effect: - 矩形檢索

// In : - 坐標范圍

// In : -

// In : -

// In : -

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

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

// Brief : -

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

②點檢索，實現(xiàn)四叉樹的點位檢索

// Effect: - 點檢索

// In : -

// In : -

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

// Brief : -

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

// Effect: - 點檢索

// In : -

// In : -

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

// Brief : -

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

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

// Effect: - 添加一個數(shù)據(jù)點到樹中

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

// Rtn : -

// Brief : -

bool AddData(TData* data);

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

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

// In : -

// Rtn : -

// Brief : -

virtual bool SpiltNode(CQTreeNode* node);

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

protected:

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

ushort _maxDepth; // 樹的最大深度

ulong_maxDataNum;

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

3.5 四叉樹在三維建模算法中的主要應用

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

(1) 緩存地表等高線

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

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

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

(2) 計算地表邊界高程

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

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

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

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

此時，有兩種優(yōu)化方案來解決這個問題：

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

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

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

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

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

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

②對邊界z值插值的準確性，理論上會更高。因為獲取了邊界內(nèi)外的高程點進行了計算。

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

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

圖10 邊界分段處理法插值

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

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

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

圖11 地層尖滅于一點

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

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

地層邊緣處理過程主要如下：

①處理地層尖滅

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

對問題進行進一步分析可知，找到底面邊界上的每一個點A對應的頂面邊界上的點B，并將B的z值作為A的z值，即可完成底面邊界z值計算的任務(圖12)。

圖12 底面邊界點z值使用頂面邊界z值

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

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

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

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

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

當然，此處和“處理地層尖滅”實際上是一個問題，需要從頂面的邊界中，檢索出底面邊界的每一個點對應的頂面邊界點，然后在三角化時，需要將頂面邊界和底面邊界相對的點連接在一起(圖14)。檢索的過程，和處理“處理地層尖滅”是相同的，此處不做詳細介紹。三角化的具體算法，也不在此處進行討論。

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

[9] 劉揚,宮阿都,李京.基于數(shù)據(jù)分層分塊的海量三維地形四叉樹簡化模型[J].測繪學報,2010,39(4):410-415.

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

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

[12]安聰榮,劉展,王心眾.基于層面結(jié)構(gòu)的地質(zhì)塊體拓撲關(guān)系的自動構(gòu)建[J].測繪學報,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

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

P628

A

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