三維數(shù)據(jù)結(jié)構(gòu)及其分類

三維數(shù)據(jù)結(jié)構(gòu)及其分類

姓名:

班級:

學(xué)號:

日期:

三維數(shù)據(jù)結(jié)構(gòu)及其分類

一、引言

隨著GIS理論的日趨成熟及其應(yīng)用的不斷拓展，其很多商業(yè)化的GIS軟件的

功能也漸漸完善。但是絕大多數(shù)的商品化GIS軟件包還只是在二維平面基礎(chǔ)上對

現(xiàn)實世界的實體及實體之間的關(guān)系的模擬和處理，而我們生活在三維的世界里，

所涉及到的有關(guān)氣象、水文、采礦、災(zāi)難、污染等方面的自然現(xiàn)象都是三維的，

明顯當(dāng)我們僅僅用二維的方法和思路解釋和處理三維問題時，就不能夠精確地或

正確地反映、存儲、分析、處理和顯示地理空間信息。因此，為更逼真精確地描

述現(xiàn)實三維世界，研討和討論三維數(shù)據(jù)結(jié)構(gòu)顯得尤為重要。

二、三維數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是即數(shù)據(jù)的規(guī)律結(jié)構(gòu)形式，我們所熟識的是二維數(shù)據(jù)結(jié)構(gòu)，從類別上分,

二維數(shù)據(jù)結(jié)構(gòu)包括矢量數(shù)據(jù)結(jié)構(gòu)、柵格數(shù)據(jù)結(jié)構(gòu)、矢量-柵格一體化數(shù)據(jù)結(jié)構(gòu)等，

這主要是依據(jù)其數(shù)據(jù)模型進行分類的，即柵格數(shù)據(jù)模型、矢量數(shù)據(jù)模型、面對對

象數(shù)據(jù)模型等，這與我們通常先建立數(shù)據(jù)模型，再依據(jù)數(shù)據(jù)模型選用合適的數(shù)據(jù)

結(jié)構(gòu)對數(shù)據(jù)進行組織的思路是全都的。

通常我們所說的三維景觀可視化和已經(jīng)具有的2.5維表面建模都還不是真正

意義上的三維，比如采用DEM數(shù)據(jù)建立的三維景觀模型可視化，或者采用多屬

性的實體的某一屬性作為第三維對平面圖形進行三維顯示等。如采用v=f(x,y)表

達一個二維系統(tǒng)，(x,y)是二維平面坐標(biāo)，v是對應(yīng)點的屬性值，當(dāng)v表示高程時，

就可以表示數(shù)字高程模型。但這里v受x,y變化的影響；而真正意義上的三維數(shù)

據(jù)模型中，三維變量之間應(yīng)是相互獨立的。也就是說，對于一個真正的三維數(shù)據(jù)

模型，可以用V=f(x,y,z)來描述,其中z是自變量,不受x,y變化的影響,即(x,y,z)

是在三維空間連續(xù)變化的?？偟膩碚f，即是與二維相比，三維多出了一維，但仍

舊可以將二維的觀點引入對三維的討論之中。

三維空間數(shù)據(jù)模型是人們對客觀世界的理解和抽象，是建立三維空間數(shù)據(jù)庫

的理論基礎(chǔ)。三維空間數(shù)據(jù)結(jié)構(gòu)是三維空間數(shù)據(jù)模型的詳細實現(xiàn)，是客觀對象在

計算機中的底層表達，是對客觀對象進行可視表現(xiàn)的基礎(chǔ)。

引入二維空間數(shù)據(jù)模型的部分理念后，且在三維空間里進一步作適當(dāng)合理的

擴展，地理實體可以分為點、線、面和體四種基本元素，由這四種元素構(gòu)成簡單

的三位目標(biāo)。這樣，將地理實體的三維空間分成細小的單元，稱之為體元素或體

元，并將其作為三維空間討論的原子項，并用二值化的思想推斷體元與實體之間

的關(guān)系，即體元包含在實體內(nèi)，則賦值為1,否則賦值為0.體元可以是正立方體、

正方體、四周體或其它非規(guī)章外形等。

在對三維數(shù)據(jù)模型作了較為成熟的熟識之后，三維數(shù)據(jù)結(jié)構(gòu)的建立便于有了

肯定的依據(jù)。為了實現(xiàn)將三維的空間實體模型在計算機之中存儲、處理、檢索、

查詢、分析和顯示，必需采用適于計算機表達、存儲和管理的三維數(shù)據(jù)結(jié)構(gòu)對現(xiàn)

實建立的三維數(shù)據(jù)模型進行表達。同樣，考慮二維數(shù)據(jù)結(jié)構(gòu)，并將其在三維空間

進行拓展，可以得到對應(yīng)的三維數(shù)據(jù)結(jié)構(gòu)，即八叉樹三維數(shù)據(jù)結(jié)構(gòu)。

采用八叉樹來表示三維形體，既可以看成是四叉樹方法在三維空間的推廣，

也可以是用三維體素列陣表示形體方法的一種改進。其規(guī)律結(jié)構(gòu)可以定義如下。

假設(shè)要表示的形體T可以放在一個充分大的實體C內(nèi),C的邊長為21形體

TC,它的八叉樹可以用以下遞歸的方法來定義：八叉樹的每個節(jié)點與C的一個子

立方體對應(yīng)，樹根與C本身相對應(yīng)，假如T=C,那么T的八叉樹僅有樹根，假如

T不等于C,則C等分為八個子立方體，每個子立方體與樹根的一個子節(jié)點相對

應(yīng)。只要某個子立方體不是完全空白或完全為T所占據(jù)，就要被八等分，從而對

應(yīng)的節(jié)點也就有了八個子節(jié)點。這樣遞歸推斷、分割始終要進行到節(jié)點所對應(yīng)的

立方體或是完全空白，或者是完全為T占據(jù)，或是其大小已是預(yù)先定義的體素大

小，并且對它與T之交作肯定的“舍入”，使體素或認為是空白的，或認為是T

占據(jù)的。如此所生成的八叉樹上的節(jié)點可以分為三類：一是灰節(jié)點，對應(yīng)的立方

體部分地為T所占據(jù)；二是白節(jié)點，對應(yīng)的立方體中無T的內(nèi)容；三是黑節(jié)點，

對應(yīng)的立方體全為T所占據(jù)。后兩類又稱為葉節(jié)點。

與四叉樹結(jié)構(gòu)相類似的八叉樹結(jié)構(gòu)可以沿用四叉樹的有關(guān)方法。依據(jù)存儲方

式的不同，八叉樹可以分為常規(guī)的、線形的、一對八的八叉樹等等。

1）規(guī)章的八叉樹

八叉樹的存儲結(jié)構(gòu)是用一個有九個字段的紀錄來表示樹中的每個結(jié)點，其中

一個字段用來秒蘇該結(jié)點的特性，其余的八段用來作為存放指向其八個子結(jié)點的

指針。但是規(guī)章八叉樹的缺陷較多，最大的問題就是指針占用了很大的空間。因

此雖然其易于理解把握，但存儲代價太大。

2）線形八叉樹

線形八叉樹注意考慮的是如何提高空間采用率，用某一預(yù)先確定的次序遍歷

八叉樹，將八叉樹轉(zhuǎn)換成一貫線形表，表的每個元素與一個結(jié)點相對應(yīng)。線形八

叉樹不僅節(jié)約存儲空間，對某些運算也比較便利，但是不夠敏捷。

3）一對八式的八叉樹

在一對八式的八叉樹中，一個非葉結(jié)點有八個子結(jié)點，假如一個紀錄與一個

結(jié)點對應(yīng)，那么在這個紀錄中描述的是這個結(jié)點的八個子結(jié)點的特征值，而指針

給出的則是該八個子結(jié)點所對應(yīng)紀錄的存放處，而且還隱含地假設(shè)了這些子結(jié)點

紀錄存放的次序。也就是說，即使某個紀錄是不必要的，那么相應(yīng)的存儲位置也

必需空閑在那里，以保證不會錯誤地存取到其它同層結(jié)點的紀錄。很明顯，當(dāng)它

不是完全八叉樹的時候，存儲空間會有肯定的鋪張。為了克服這種缺陷，一是增

加計算量，即在存取相應(yīng)結(jié)點紀錄之前，首先檢查它的父結(jié)點紀錄，看一下之前

有幾個葉結(jié)點，從而可以知道應(yīng)當(dāng)如何存取所需結(jié)點紀錄。這種方法可以減小存

儲需求，但會增加計算量；另一個是在紀錄中增加肯定的信息，使計算工作適當(dāng)

削減或者更便利。例如在原紀錄中增加三個字節(jié)，一分為八，每個字節(jié)點對應(yīng)三

位，代表它的子結(jié)點在指針指向區(qū)域中的偏移。因此，要找到它的子結(jié)點紀錄位

置，只要固定地把指針指向的位置加上這個偏移量乘上紀錄所占的字節(jié)數(shù)，就是

所要的位置，因而一個結(jié)點可以描述為：

偏移指針SWESWTNWBNWTSETSEBNETNEB

用這種方式所得到的八叉樹和以前相同，只是每個紀錄前多了三個字節(jié)。

三、分類

與二維數(shù)據(jù)結(jié)構(gòu)類比，可將三維數(shù)據(jù)結(jié)構(gòu)分為三維矢量數(shù)據(jù)結(jié)構(gòu)、三維柵格

數(shù)據(jù)結(jié)構(gòu)、矢量柵格一體化三維數(shù)據(jù)結(jié)構(gòu)、面對對象三維數(shù)據(jù)結(jié)構(gòu)、鑲嵌數(shù)據(jù)結(jié)

構(gòu)等?；阼偳稊?shù)據(jù)模型的三維數(shù)據(jù)結(jié)構(gòu)可以采用有四周體格網(wǎng)法、單純形剖分

法、空間枚舉法、單元分解法等表達；基于矢量的數(shù)據(jù)模型的三維數(shù)據(jù)結(jié)構(gòu)可以

采用線框表示法、實體模型法、表面剖分法等表達；基于分析型的數(shù)據(jù)模型的三

維數(shù)據(jù)結(jié)構(gòu)可以采用非勻稱有理B樣條函數(shù)等進行表達;此外還有混合型數(shù)據(jù)結(jié)

構(gòu)，其可用構(gòu)造幾何體法、面對對象思想以及與樹結(jié)構(gòu)相結(jié)合進行表達。其中三

維數(shù)據(jù)結(jié)構(gòu)的最重要的一個分類依據(jù)就是實際應(yīng)用，通過對現(xiàn)實世界表達的需要

分析以尋求采用一種合適的三維數(shù)據(jù)結(jié)構(gòu)來表達三維空間實體及實體之間的關(guān)

系。但其從二維空間數(shù)據(jù)結(jié)構(gòu)進行拓展來定義三維數(shù)據(jù)結(jié)構(gòu)以及結(jié)合三維的特點

在適當(dāng)三維模型構(gòu)建的基礎(chǔ)之上進行三維數(shù)據(jù)結(jié)構(gòu)的定義對采用三維數(shù)據(jù)結(jié)構(gòu)

來討論現(xiàn)實世界的三維空間實體以及其關(guān)系供應(yīng)了科學(xué)的方法。

四、結(jié)論

三維數(shù)據(jù)模型的構(gòu)建和三維數(shù)據(jù)結(jié)構(gòu)的組織對于三維空間數(shù)據(jù)的收集、存