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

1、四、三維四、三維GISGIS數(shù)據(jù)模型和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)模型和數(shù)據(jù)結(jié)構(gòu)在計算機三維實體造型系統(tǒng)中，常用的形體表示技術(shù)與方法有: (一)單元分解法：即三維GIS的柵格結(jié)構(gòu)。它以固定形狀(如立方體)的單元體規(guī)則地分布于空間網(wǎng)格位置上。一個形體就是這些具有鄰接關(guān)系的大量固定單元的集合，單元大小決定了單元分解形式的精度。 它具有易于存取給定點的優(yōu)點，能保證空間的唯一性。缺點是各部分關(guān)系不夠明確，需要耗費大量的存儲空間。在實際應(yīng)用中一般采用八叉樹(單元正則形體)或BSP樹(單元大小可變形體)的組織形式。 1.八叉樹:（octree）是一種用于描述三位空間的樹狀數(shù)據(jù)結(jié)構(gòu)。八叉樹的每個節(jié)點表示一個正方體的體積元素

2、，每個節(jié)點有八個子節(jié)點，將八個子節(jié)點所表示的體積元素加在一起就等于父節(jié)點的體積。八叉樹的邏輯結(jié)構(gòu)八叉樹的邏輯結(jié)構(gòu)如下：假設(shè)要表示的形體V可以放在一個充分大的正方體C內(nèi)，C的邊長為2n，形體VC，它的八叉樹可以用以下的遞歸方法遞歸方法來定義： 八叉樹的每個節(jié)點與C的一個子立方體對應(yīng)，樹根與C本身相對應(yīng)，如果VC，那么V的八叉樹僅有樹根，如果VC，則將C等分為八個子立方體，每個子立方體與樹根的一個子節(jié)點相對應(yīng)。只要某個子立方體不是完全空白或完全為V所占據(jù)，就要被八等分，從而對應(yīng)的節(jié)點也就有了八個子節(jié)點。這樣的遞歸判斷、分割一直要進行到節(jié)點所對應(yīng)的立方體或是完全空白，或是完全為V占據(jù)，或是其大小已是

3、預(yù)先定義的體素大小，并且對它與V之交作一定的“舍入”，使體素或認為是空白的，或認為是V占據(jù)的。節(jié)點:灰節(jié)點:它對應(yīng)的立方體部分地為V所占據(jù)；白節(jié)點:它所對應(yīng)的立方體中無V的內(nèi)容；黑節(jié)點:它所對應(yīng)的立方體全為V所占據(jù)。白節(jié)點和黑節(jié)點又稱為葉結(jié)點。形體V關(guān)于C的八叉樹的邏輯結(jié)構(gòu)是一顆樹，其上的節(jié)點要么是葉節(jié)點，要么就是有八個子節(jié)點的灰節(jié)點。根節(jié)點與C相對應(yīng)，其它節(jié)點與C的某個子立方體相對應(yīng)。八叉樹的存貯結(jié)構(gòu) 常規(guī)八叉樹 線性八叉樹 一對八的八叉樹1)1)規(guī)則八叉樹規(guī)則八叉樹 規(guī)則八叉樹的存貯結(jié)構(gòu)用一個有九個字段九個字段的記錄來表示樹中的每個結(jié)點。其中一個字段用來描述該結(jié)點的特性(在目前假定下，只要

4、描述它是灰、白、黑三類結(jié)點中哪一類即可)，其余的八個字段用來作為存放指向其八個子結(jié)點的指針。這是最普遍使用的表示樹形數(shù)據(jù)的存貯結(jié)構(gòu)方式。 規(guī)則八叉樹缺陷較多，最大的問題是指針占用了大量的空間。假定每個指針要用兩個字節(jié)表示，而結(jié)點的描述用一個字節(jié)，那么存放指針要占總的存貯量的94。因此，這種方法雖然十分自然，容易掌握，但在存貯空間的使用率方面不很理想。2)2)線性八叉樹線性八叉樹 線性八叉樹注重考慮如何提高空間利用率。用某一預(yù)先確定的次序遍歷八叉樹(例如以深度第一的方式)，將八叉樹轉(zhuǎn)換成一個線性表，表的每個元素與一個結(jié)點相對應(yīng)。對于結(jié)點的描述可以豐富一點，例如用適當(dāng)?shù)姆绞絹碚f明它是否為葉結(jié)點，如

5、果不是葉結(jié)點時還可用其八個子結(jié)點值的平均值作為非葉結(jié)點的值等等。這樣，可以在內(nèi)存中以緊湊的方式來表示線性表，可以不用指針或者僅用一個指針表示即可。線性八叉樹特點：不僅節(jié)省存貯空間節(jié)省存貯空間，對某些運算也較為方便較為方便。但是為此付出的代價是喪失了一定的靈活性喪失了一定的靈活性。例如為了存取屬于原圖形右下角的子圖形對應(yīng)的結(jié)點，那么必須先遍歷了其余七個子圖形對應(yīng)的所有結(jié)點后才能進行；不能方便地以其它遍歷方式對樹的結(jié)點進行存取，導(dǎo)致了許多與此相關(guān)的運算效率變低。因此盡管不少文章討論了這種八叉樹的應(yīng)用，但是仍很難令人滿意很難令人滿意。 3)3)一對八式的八叉樹一對八式的八叉樹 一個非葉結(jié)點有八個子結(jié)

6、點，為了確定起見，將它們分別標(biāo)記為0，1，2，3，4，5，6，7。從上面的介紹可以看到，如果一個記錄與一個結(jié)點相對應(yīng)，那么在這個記錄中描述的是這個結(jié)點的八個子結(jié)點的特性值。而指針給出的則是該八個子結(jié)點所對應(yīng)記錄的存放處，而且還隱含地隱含地假定了這些子結(jié)點記錄存放的次序記錄存放的次序。也就是說，即使某個記錄是不必要的(例如，該結(jié)點已是葉結(jié)點)，那么相應(yīng)的存貯位置也必須空必須空閑在那里閑在那里，以保證不會錯誤地存取到其它同輩結(jié)點的記錄。這樣當(dāng)然會有一定的浪費，除非它是完全的八叉樹，即所有的葉結(jié)點均在同一層次出現(xiàn)，而在該層次之上的所有層中的結(jié)點均為非葉結(jié)點。2.BSP樹(Binary Space P

7、artioning-Tree):BSP樹是一種二叉樹，它將空間逐級進行一分為二的劃分。二叉樹是一種十分重要的樹型結(jié)構(gòu)。它的特點是，樹中的每個結(jié)點最多只有兩棵子樹，即樹中任何結(jié)點的度數(shù)不得大于。二叉樹的子樹有左右之分，而且，子樹的左右次序是重要的，即使在只有一棵子樹的情況下，也應(yīng)分清是左子樹還是右子樹。定義：二叉樹是結(jié)點的有限集合，這個集合或是空的，或是由一個根結(jié)點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。BSP樹能很好地與空間數(shù)據(jù)庫中空間對象的分布情況相適應(yīng)，但對一般情況而言，BSP樹深度較大，對各種操作均有不利影響。 二叉樹的五種基本形態(tài)二叉樹可以是空集；根可以有空的左子樹或右子樹；

8、或者左、右子樹皆為空。 二叉樹的五種基本形態(tài)如下圖所示。 滿二叉樹、完全二叉樹和不完全二叉樹滿二叉樹(FullBinaryTree) 一棵深度為k且有2k-1個結(jié)點的二又樹稱為滿二叉樹。 特點：（1）每一層上的結(jié)點數(shù)都達到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。（2）滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹(Complete BinaryTree) 若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。 特點：（1）滿二叉樹是完全二叉樹，完全二

9、叉樹不一定是滿二叉樹。（2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。（3）在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點。 非完全二叉樹(Non-Complete BinaryTree)二叉樹存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。1)二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)由一個一維數(shù)組構(gòu)成，二叉樹上的結(jié)點按某種次序分別存入該數(shù)組的各個單元。關(guān)鍵在于結(jié)點的存儲次序，這種次序應(yīng)能反映結(jié)點之間的邏輯關(guān)系（父子關(guān)系），否則二叉樹的基本運算就難以實現(xiàn)。 該方法是把二叉樹的所有結(jié)點按照一定的線性次序存儲到一片連續(xù)的存儲單元中。

10、結(jié)點在這個序列中的相互位置還能反映出結(jié)點之間的邏輯關(guān)系。完全二叉樹結(jié)點編號完全二叉樹結(jié)點編號（1） 編號辦法 在一棵n個結(jié)點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點編號，能得到一個反映整個二叉樹結(jié)構(gòu)的線性序列。 （2） 編號特點 完全二叉樹中除最下面一層外，各層都充滿了結(jié)點。每一層的結(jié)點個數(shù)恰好是上一層結(jié)點個數(shù)的2倍。從一個結(jié)點的編號就可推得其雙親，左、右孩子，兄弟等結(jié)點的編號。假設(shè)編號為i的結(jié)點是ki(1in)，則有：若i1，則ki的雙親編號為 ；若i=1，則Ki是根結(jié)點，無雙親。若2in，則Ki的左孩子的編號是2i；否則，Ki無左孩子，即Ki必定是葉子。因此完全二叉

11、樹中編號 的結(jié)點必定是葉結(jié)點。若2i+1n，則Ki的右孩子的編號是2i+1；否則，Ki無右孩子。若i為奇數(shù)且不為1，則Ki的左兄弟的編號是i-1；否則，Ki無左兄弟。若i為偶數(shù)且小于n，則Ki的右兄弟的編號是i+1；否則，Ki無右兄弟。完全二叉樹的順序存儲 將完全二叉樹中所有結(jié)點按編號順序依次存儲在一個向量bt0.n中。 其中：bt1n用來存儲結(jié)點 bt0不用或用來存儲結(jié)點數(shù)目?！纠肯卤硎乔笆鰣D形所示的完全二叉樹的順序存儲結(jié)構(gòu)，bt0為結(jié)點數(shù)目，b7的雙親、左右孩子分別是bt3、btl4和bt15。 完全二叉樹的存儲結(jié)構(gòu)一般二叉樹的順序存儲 將一般二叉樹添上一些 虛結(jié)點，成為完全二叉樹 為了

12、用結(jié)點在向量中的相對位置來表示結(jié)點之間的邏輯關(guān)系，按完全二叉樹形式給結(jié)點編號 將結(jié)點按編號存入向量對應(yīng)分量，其中虛結(jié)點用表示優(yōu)點和缺點 對完全二叉樹而言，順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。 一般的二叉樹采用順序存儲結(jié)構(gòu)時，雖然簡單，但易造成存儲空間的浪費。 最壞的情況下，一個深度為k且只有k個結(jié)點的右單支樹需要2k-1個結(jié)點的存儲空間。在對順序存儲的二叉樹做插入和刪除結(jié)點操作時，要大量移動結(jié)點。結(jié)點的結(jié)構(gòu) 二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子。 2）二叉樹的鏈式存儲

13、結(jié)構(gòu)二叉鏈表（二叉樹的常用鏈式存儲結(jié)構(gòu)） 在一棵二叉樹中，所有類型為BinTNode的結(jié)點，再加上一個指向開始結(jié)點(即根結(jié)點)的BinTree型頭指針(即根指針)root，就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，并將其稱為二叉鏈表 【例】下面左圖所示二叉樹的二叉鏈表如下面中圖所示。注意：注意： 一個二叉鏈表由根指針一個二叉鏈表由根指針root惟一確定。若二叉樹為空，則惟一確定。若二叉樹為空，則root=NULL；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。 具有具有n個結(jié)點的二叉鏈表中，共有個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有個指針域。其中只有n-1個

14、用來指個用來指示結(jié)點的左、右孩子，其余的示結(jié)點的左、右孩子，其余的n+1個指針域為空。個指針域為空。帶雙親指針的二叉鏈表 經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。 【例】下面右圖是左圖所示的二叉樹的帶雙親指針的二叉鏈表。 注意：二叉樹存儲方法的選擇，主要依賴于所要實施的各種運算的頻度注意：二叉樹存儲方法的選擇，主要依賴于所要實施的各種運算的頻度 （二）構(gòu)造性表示法(Constructive Solid Geometry)它是通過體素(如正方體、球體、三角體等)定義運算而得到新的形體的一種表示方法。最著名的構(gòu)造性表示法

15、是構(gòu)造實體幾何(CSG)法。CSG的體素本身是實體，其運算為剛體運動或正則化的集合運算并、交、差。該法比較適用于機械、建筑等領(lǐng)域。 BAAABB(a)A,B形體的并(b)A,B形體的差(c)A,B形體的交圖4-26 構(gòu)造幾何實體法生成三維實體剛體運動：三維空間中，把一個幾何物體作旋轉(zhuǎn)，平移，及鏡像對稱的運動，稱之為剛體變換。剛體運動也可以理解為保持長度，角度，面積等不變的仿射變換，即保持內(nèi)積和度量不變。正則化把非適定問題轉(zhuǎn)化為適定問題的過程。（一個問題的解是存在的，惟一的和穩(wěn)定的）（三）邊界表示法：即三維G1S的矢量結(jié)構(gòu)，一個形體用其拓撲邊界表示。它記錄形體的幾何元素的幾何信息(頂點、邊、面、

16、體)以及相互連接關(guān)系(拓撲信息)，以便直接存取形體的各個體與面、面的邊界線，以及各個頂點。這樣有利于幾實現(xiàn)以體、面、線、點為基礎(chǔ)的各種幾何運算和操作，以及查詢形體的拓撲信息，例如實體中有哪幾個相連通的部分等等。三維三維GISGIS矢量數(shù)據(jù)結(jié)構(gòu)的拓撲關(guān)系矢量數(shù)據(jù)結(jié)構(gòu)的拓撲關(guān)系:拓撲關(guān)系的建立使得各種空間的操作與信息查詢易于實現(xiàn)。然而三維GIS中的三維拓撲關(guān)系建立是一個棘手的問題，因為所研究目標(biāo)的結(jié)構(gòu)極其復(fù)雜和不規(guī)則。從側(cè)重于礦山實際應(yīng)用的三維GIS研究出發(fā)，認為，復(fù)雜地物可用充滿空間的各種體域、組成體域的曲面、構(gòu)成曲面的邊界環(huán)、組成環(huán)的弧、弧上的結(jié)點來描述。一般來說，體域是目標(biāo)實體的基本構(gòu)成；認

17、為任何復(fù)雜的實體都是由體域(自然的或人工的)構(gòu)成的；體、面、線、點是一個動態(tài)的概念，在不同的比例尺或不同的研究重點時可以相互轉(zhuǎn)換。例如對整個礦井來講，巷道可認為是線域，而對某個工作面來講，巷道則是體域。按上述思路和觀點，考慮保持拓撲信息的完整性、易擴展性，提出用以下6組關(guān)系來描述礦山GIS三維矢量結(jié)構(gòu)的空間拓撲關(guān)系。(1) 復(fù)雜地物體關(guān)系：復(fù)雜地物與組成它的體域。在該拓撲關(guān)系中加入對復(fù)雜地物屬性的描述或指向?qū)傩杂涗浳募闹羔槨?2) 體復(fù)雜地物曲面關(guān)系：體域與由其所構(gòu)成的復(fù)雜地物，體域與包圍該體域的曲面，以及與該體域相鄰的體域。體拓撲結(jié)構(gòu)中可加入對體域?qū)傩缘拿枋觥?3) 曲面環(huán)體域關(guān)系：曲面與

18、組成曲面的環(huán)以及該曲面所包圍的體域(正面鄰體)和包圍該曲面的外部體域(負面鄰體)。一個曲面可能由若干個環(huán)構(gòu)成，其外環(huán)取正，內(nèi)環(huán)取負值。在曲面拓撲結(jié)構(gòu)中加上若干值樣條?。ㄈ绲雀呋。┗虿逯岛瘮?shù)，就可確定該曲面的空間形態(tài)。(4) 環(huán)弧曲面關(guān)系：環(huán)與構(gòu)成該環(huán)的弧以及該環(huán)所包圍的內(nèi)部曲面(內(nèi)鄰曲面)和包圍該環(huán)的外部曲面（外鄰曲面）。(5) 弧結(jié)點環(huán)的關(guān)系：弧與該弧的起結(jié)點、終點及包含該弧的環(huán)。環(huán)有正負之分，環(huán)方向與弧的方向一致時，取正號；反之取負。在弧拓撲結(jié)構(gòu)中加一系列坐標(biāo)串，可確定該弧的形態(tài)。(6) 結(jié)點弧的關(guān)系：結(jié)點及從該結(jié)點出發(fā)的離開弧段和以該結(jié)點為終點的到達弧段。三維三維GISGIS矢量數(shù)據(jù)結(jié)構(gòu)

19、拓撲關(guān)系的建立矢量數(shù)據(jù)結(jié)構(gòu)拓撲關(guān)系的建立如下圖所示為一典型的礦山現(xiàn)象。其物理意義如下：煤層上覆巖層為頁巖（V1），中間為煤層（V2），煤層底板為砂巖（V3）。在煤層中賦存著一層很薄的夾矸（用1，2，3，4點連線的V5所示）。在底板砂巖中開拓了一條運輸集中巷（V4）。另外，還探測到在煤層某處有一瓦斯集聚點（V6）。表1復(fù)雜地物體拓撲如需要詳細描述復(fù)雜地物的屬性，則用屬性記錄文件的方式加以記錄，用指針來穿引。復(fù)雜地物組成的體域?qū)傩?指向記錄文件的指針VV1某運輸集中巷及其圍巖狀況V2V3V4V5V6表2體復(fù)雜地物曲面拓撲體域由體域組成的復(fù)雜地物構(gòu)成體域的曲面鄰體屬性V V1 1V VEFKIEFK

20、I，F(xiàn)GMKFGMK，GHOMGHOM，HEIOHEIO，EHGFEHGF，IKMOIKMOV V2 2頁巖頁巖V V2 2IKLJIKLJ，KMNLKMNL，MOPNMOPN，OIJPOIJP，-IKMO-IKMO，JLNPJLNPV V1 1，V V3 3煤層煤層V V3 3JLBAJLBA，LNCBLNCB，NPDCNPDC，PJADPJAD，-JLNP-JLNP，ABCDABCD，-QTSR-QTSR，-TUXS-TUXS，-QVUT-QVUT，-QRWV-QRWV，-RSXW-RSXW，-UVWX-UVWXV V2 2，V V4 4砂巖砂巖V V4 4QTSRQTSR，TUXSTUXS，QVXUTQVXUT，QRWVQRWV，RSXWRSXW，UVWUVWV V3 3運輸集運輸集中巷中巷V V5 512341234V V2 2夾矸夾矸V V6 65 5V V2 2瓦斯聚瓦斯聚集點集點曲面以指向所包圍的體域方向為正，遠離所包圍的體域為負(右手法則)。 表3曲面環(huán)體域關(guān)系拓撲曲面組成曲面的環(huán)正面相鄰體負面相鄰體值樣條弧/插值函數(shù)EFKIEFKIEFKIEFKIV V1 1域外域外/ /IKMOIKMOIKMOIKMOV V1 1V V2 2JLBAJLBAJLBAJLBA-QTSR-QTSRV V3 3域外域外/ /QTSRQTSRQTSRQTSRV V4