空間數(shù)據(jù)的結(jié)構(gòu)與編碼

空間數(shù)據(jù)的結(jié)構(gòu)與編碼空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第1頁。3.1空間數(shù)據(jù)及其編碼

1、數(shù)據(jù)空間性的內(nèi)含從數(shù)據(jù)編碼看1）數(shù)據(jù)的空間地理分布特征；

2）非結(jié)構(gòu)化數(shù)據(jù)的特征；3）空間數(shù)據(jù)之間存在著拓?fù)潢P(guān)系；4）空間數(shù)據(jù)是海量數(shù)據(jù)。空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第2頁。2、空間數(shù)據(jù)的編碼

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第3頁。3、數(shù)據(jù)編碼的過程

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第4頁。4、空間物體的幾何類型

（1）點(diǎn)狀分布特征如城鎮(zhèn)、企事業(yè)單位、基地、氣象站、山峰、火山口等。（2）線狀分布特征河流、海岸線、鐵路、公路、地下管線，行政邊界等。（3）面狀分布特征如土壤、森林、草原、沙漠、湖泊等，通常稱多邊形。（4）體狀分布特征如高層建筑、水體、云體、山體、礦體等?？傊?，空間現(xiàn)象十分復(fù)雜，為此將其抽象到空間對象（目標(biāo)）來表達(dá)空間實(shí)體。空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第5頁。3.2空間數(shù)據(jù)的拓?fù)潢P(guān)系

1、描述地理要素空間性的信息：幾何信息、拓?fù)湫畔缀涡畔ⅲɡ碚摶A(chǔ)是幾何學(xué)geometry)用空間坐標(biāo)的位置、方向、角度、距離、面積等信息描述物體的幾何形狀和數(shù)量特征；拓?fù)湫畔ⅲɡ碚摶A(chǔ)是拓?fù)鋵W(xué)topology)用幾何關(guān)系的相連、相鄰、包含等信息描述物體元素之間的關(guān)系；空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第6頁。2、拓?fù)鋵W(xué)中空間元素拓?fù)鋵W(xué)是幾何學(xué)的一個分支，其基本元素：結(jié)點(diǎn)（NOD）：弧段的交點(diǎn)。島結(jié)點(diǎn)是特殊結(jié)點(diǎn)?；《危ˋRC）：相鄰兩結(jié)點(diǎn)之間的坐標(biāo)鏈。島邊界弧段是特殊弧段。多邊形（polygon）（圖斑或面）：有限弧段組成的封閉區(qū)。關(guān)系的性質(zhì)可分為：相鄰、相連、相交、相離、相重、包含等?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第7頁。從拓?fù)浣嵌瓤?，幾何形狀不同的事物其拓?fù)潢P(guān)系可能相同

點(diǎn)之間拓?fù)潢P(guān)系（鄰接性）的描述面之間拓?fù)潢P(guān)系（鄰接性）的描述空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第8頁。3、空間數(shù)據(jù)的拓?fù)潢P(guān)系

1）拓?fù)涞年P(guān)聯(lián)性

表示不同類型元素（結(jié)點(diǎn)、弧段、多邊形）之間的關(guān)系

多邊形弧段號弧段號起點(diǎn)終點(diǎn)結(jié)點(diǎn)弧段

p1a1a5a6a1N2N1N1a1a3a5P2a2a4a6a2N2N3N2a1a2a6P3a3a4a5a3N3N1N3a2a3a4p4a7a4N3N4N4a4a5a6a5N1N4N5a7a6N4N2a7N5N5

a3N1a1a5p3N4p1N3a4P4a6N5a7p2a2N2空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第9頁。2）拓?fù)涞泥徑有院瓦B通性

表示同類型元素（結(jié)點(diǎn)、弧段、多邊形）之間的關(guān)系多邊形之間的鄰接性；弧段之間的鄰接性；結(jié)點(diǎn)之間的連通性p1p2p3p4a1a2a3a4a5a6a7N1N2N3N4N5

P1\110a1\110110N1\1110p21\11a21\11010N21\110p311\0a311\1100N311\10p4010\a4011\110N4111\0a51011\10N50000\a611011\0a7000000\多邊形鄰接矩陣弧段鄰接矩陣結(jié)點(diǎn)連通矩陣空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第10頁。3）拓?fù)涞陌?/p>

P1p2p2p1p3p1p3p2面的簡單包含面的多層包含面的等價包含面包含點(diǎn)面包含線線包含點(diǎn)空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第11頁。

4）拓?fù)潢P(guān)系表（拓?fù)潢P(guān)系以關(guān)連表達(dá)最為重要）

關(guān)聯(lián)性相鄰（連）性相離性相交性包含性重合性點(diǎn)與點(diǎn)線與線面與面點(diǎn)與線點(diǎn)與面線與面空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第12頁。3.3矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

基于矢量模型的數(shù)據(jù)結(jié)構(gòu)稱矢量數(shù)據(jù)結(jié)構(gòu)1、矢量數(shù)據(jù)的特點(diǎn)

2、矢量數(shù)據(jù)的獲取空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第13頁。3、無拓?fù)潢P(guān)系的矢量模型

無拓?fù)潢P(guān)系的矢量模型實(shí)質(zhì)上是面向?qū)嶓w的一種數(shù)據(jù)模型。它以單個的空間實(shí)體為數(shù)據(jù)組織和存儲的基本單位。它采用面向?qū)ο蟮能浖_發(fā)方式，每個對象有自己的特性、自己的行為。只記錄空間目標(biāo)的位置坐標(biāo)和屬性信息，不記錄空間拓?fù)潢P(guān)系。如采用坐標(biāo)系列編碼。點(diǎn)目標(biāo)（x,y)線目標(biāo)(x1y1,x2y2,…….xnyn)面目標(biāo)(x1y1,x2y2,…….xnyn,x1y1)具體實(shí)現(xiàn)形式可將點(diǎn)，線，面直接用空間坐標(biāo)點(diǎn)數(shù)據(jù)表示；也可將坐標(biāo)點(diǎn)組成文件，每個點(diǎn)給予一個點(diǎn)號，而點(diǎn)，線，面用點(diǎn)號數(shù)據(jù)表示。空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第14頁。

無拓?fù)潢P(guān)系的矢量模型優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)簡單，直觀，便于用戶接受；（2）便于系統(tǒng)的維護(hù)和更新。缺點(diǎn)：（1）數(shù)據(jù)余度大，如多邊形公共邊重復(fù)存儲，但沒有存儲多邊形之間的關(guān)系。相鄰多邊形易產(chǎn)生偽多邊形。解決的辦法是建立多邊形邊界表；（2）缺乏拓?fù)湫畔?，如鄰域信息等，不便于拓?fù)浞治觯ㄅR時建立拓?fù)潢P(guān)系）；（3）對島處理能力差，無法建立外多邊形的關(guān)系?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第15頁。

1）GIS中建立拓?fù)潢P(guān)系的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)緊密、拓?fù)潢P(guān)系明確，便于空間數(shù)據(jù)的拓?fù)洳樵兒屯負(fù)浞治鋈缇W(wǎng)絡(luò)分析；（2）便于系統(tǒng)內(nèi)數(shù)據(jù)共享；缺點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜，不便于系統(tǒng)的維護(hù)和更新，如局部實(shí)體的變化要重建拓?fù)潢P(guān)系；（2）對單個實(shí)體的操作效率不高，如增加、刪除、修改一個實(shí)體時涉及一系列的文件和數(shù)據(jù)庫表格；（3）難以表達(dá)復(fù)雜的地理實(shí)體。4、拓?fù)潢P(guān)系的矢量模型空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第16頁。2）拓?fù)潢P(guān)系的關(guān)聯(lián)表達(dá)

顯式表示

(a)多邊形、弧段、結(jié)點(diǎn)（自上到下）

多邊形弧段弧段結(jié)點(diǎn)

P1a4a5a6a1N1N2P2a1a8a5a2N2N4P3a3a6a7a3N4N5P4a2a7a8a4N1N5a5N1N3a6N3N5a7N3N4a8N2N3（b）結(jié)點(diǎn)、弧段、多邊形結(jié)點(diǎn)弧段N1a1a4a5N2a1a2a8N3a5a6a7a8N4a2a3a7N5a3a4a6

弧段左多邊形右多邊形

a10P2a20p4a30p3a4p10a5p2p1a6p3p1a7p4p3a8p4p2空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第17頁。半顯式表示

弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形坐標(biāo)

a1N1N20P2a2N2N40p4a3N4N50p3a4N1N5p10a5N1N3p2p1a6N3N6p3p1a7N3N4p4p3a8N2N3p4p2。

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第18頁。5、具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)模型例

1）點(diǎn)狀數(shù)據(jù)結(jié)構(gòu)點(diǎn)狀地物數(shù)據(jù)結(jié)構(gòu)較簡單。也可建立索引等。標(biāo)識符坐標(biāo)點(diǎn)屬性編碼注釋

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第19頁。

點(diǎn)實(shí)體標(biāo)識符類型（簡單點(diǎn)、結(jié)點(diǎn)、文字說明）序列號坐標(biāo)點(diǎn)（X，Y）相關(guān)屬性符號簡單點(diǎn)比例尺方向指針結(jié)點(diǎn)符號排列文字說明字體方向字符大小其它屬性空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第20頁。2）線狀數(shù)據(jù)結(jié)構(gòu)

線狀地物坐標(biāo)點(diǎn)數(shù)據(jù)表

線標(biāo)識符序號坐標(biāo)系列點(diǎn)屬性編碼注釋線狀地物坐標(biāo)索引表線標(biāo)識符序號起點(diǎn)序號終點(diǎn)序號XminXmaxYminYmax空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第21頁。

3)鏈狀雙重獨(dú)立面狀數(shù)據(jù)結(jié)構(gòu)

(1）多邊形文件多邊形號弧段號周長面積

p1a4a5a6p2...（2）弧段索引文件弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形XminXmaxYminYmax

a1N1N20P2a2N2N40p4a3N4N50p3a4N1N5p10a5N1N3p2p1a6N3N6p3p1a7N3N4p4p3a8N2N3p4p2(3）弧段坐標(biāo)文件弧段號坐標(biāo)點(diǎn)

a1x1y1,x2y2,….…….

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第22頁。6、拓?fù)潢P(guān)系的自動生成1）歐拉定理----用于檢驗(yàn)拓?fù)潢P(guān)系歐拉定理認(rèn)為a,n,P之間存在如下關(guān)系：

c=n-a+P；其中c為常數(shù)是多邊形圖的一個特征。C值為2;例1右圖實(shí)線部分n=2，a=3，p=3C=n-a+P=2–3+3=2例2加虛線上部分n=3，a=5，P=4，

C=3-5+4=2歐拉定理主要用于檢查點(diǎn)、線、面中是否存在多余或漏掉的圖形元素?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第23頁。

2）拓?fù)潢P(guān)系的自動生成（1）點(diǎn)、線拓?fù)潢P(guān)系的生成在圖形采集和編輯中同時生成點(diǎn)、線拓?fù)潢P(guān)系弧段起結(jié)點(diǎn)終結(jié)點(diǎn)結(jié)點(diǎn)弧段

a1N1N2N1a1a2N2N3N2a1a2a3N2N4N3a2

弧段起結(jié)點(diǎn)終結(jié)點(diǎn)結(jié)點(diǎn)弧段

a1N1N2N1a1a2N2N3N2a1a2a3a3N2N4N3a2N4a3

a1a2a1a3a2N1N2N3N1N2N3N4空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第24頁。（2）坐標(biāo)鏈（弧段）的求交的方法弧段的包絡(luò)矩形：弧段坐標(biāo)鏈中最大最小值XminYminXmaxYmax組成的矩形稱該弧段的包絡(luò)矩形；多邊形的包絡(luò)矩形：組成多邊形的所有坐標(biāo)鏈中最大最小值組成的矩形稱該多邊形的包絡(luò)矩形；XminYminXmaxYmaxXmaxYmaxXminYmin空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第25頁。

（3）多邊形拓?fù)潢P(guān)系的生成多邊形通常分為獨(dú)立多邊形、帶島的多邊形、公共邊界多邊形及復(fù)合多邊形。其中最基礎(chǔ)的是具有公共邊界的多邊形。在建立多邊形拓?fù)潢P(guān)系之前，首先已建立了點(diǎn)、線拓?fù)潢P(guān)系。多邊形拓?fù)潢P(guān)系的生成的核心是自動生成每個多邊形有那些弧段組成，同時填入弧段的左右多邊形號，并生成如下兩個文件。多邊形弧段弧段左多邊形右多邊形

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第26頁。以結(jié)點(diǎn)為中心生成拓?fù)潢P(guān)系

以當(dāng)前弧段結(jié)點(diǎn)為軸，按順時針（或逆時針）旋轉(zhuǎn)，遇到第一個弧段即為當(dāng)前弧段的后續(xù)弧段。連續(xù)以弧段的結(jié)點(diǎn)按順時針（或逆時針）搜索，可得到一閉合多邊形。經(jīng)拓?fù)鋵W(xué)證明：如上搜索，當(dāng)?shù)玫介]合多邊形的各弧段按順時針（或逆時針）排列時，此邊界為得到內(nèi)邊界（如島邊界）；當(dāng)?shù)玫介]合多邊形的各弧段按逆時針（或順時針）排列時，此邊界為外邊界。內(nèi)邊界是指該邊界圍成的區(qū)域其外圍是連通區(qū)域；外邊界是指該邊界圍成的區(qū)域其外圍是不連通區(qū)域。實(shí)際上島邊界數(shù)據(jù)的特殊性很易找出?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第27頁。（3）島的歸屬的判斷島的歸屬的判斷原則：（a）外邊界多邊形的包絡(luò)矩形必定包容內(nèi)邊界多邊形的包絡(luò)矩形，這是出現(xiàn)連通域的必要條件，但不是充分條件。（b）一個內(nèi)邊界多邊形只能對應(yīng)一個連通域的外邊界多邊形。（c）閉合多邊形A對閉合多邊形B是包容性的判斷只要在B多邊形邊界上取一點(diǎn)，檢查該點(diǎn)是否在閉合多邊形A內(nèi)。AB空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第28頁。(4）多邊形屬性的賦給前面已得到了組成各個多邊形的相應(yīng)的弧段及其排列，為完成拓?fù)潢P(guān)系生成的全部工作，還要確定下面兩個問題。(a)多邊形內(nèi)點(diǎn)及屬性的賦給(b)左右多邊形的確定連續(xù)以弧段的結(jié)點(diǎn)按順時針（或逆時針）搜索，得到外邊界的閉合多邊形弧段以逆時針排列；內(nèi)邊界的閉合多邊形弧段以順時針排列,實(shí)際輸入弧段的方向可能同排列方向一致，也可能不一致；如兩者一致：該弧段所包含的多邊形內(nèi)點(diǎn)及屬性為左多邊形；如如兩者不一致：該弧段所包含的多邊形內(nèi)點(diǎn)及屬性為右多邊形。在此基礎(chǔ)上生成數(shù)據(jù)文件。順時針走包含右多邊形逆時針走包含左多邊形左多變形右多變形空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第29頁。

7、拓?fù)渚庉嬐負(fù)渚庉嬘脕頇z查生成拓?fù)潢P(guān)系的正確性，并進(jìn)行編輯處理，主要問題有：1）重復(fù)輸入線的檢查出現(xiàn)很多小的偽多邊形。2）漏線段的檢查。出現(xiàn)懸線，多邊形不封閉。3）圖與屬性不一致檢查圖與屬性匹配檢查，并輸出不匹配處。4）邏輯關(guān)系的檢查歐拉定理檢查DIME檢查，以多邊形為例空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第30頁。3.4柵格數(shù)據(jù)結(jié)構(gòu)及其編碼一、柵格數(shù)據(jù)的特點(diǎn)空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第31頁。二、柵格數(shù)據(jù)的獲取空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第32頁。三、柵格數(shù)據(jù)的組織

數(shù)據(jù)的組織的目的是在計(jì)算機(jī)內(nèi)組織好數(shù)據(jù)，使達(dá)到最優(yōu)的數(shù)據(jù)存取，最少的存儲空間，最短的處理時間。柵格數(shù)據(jù)的結(jié)構(gòu)實(shí)質(zhì)是組織矩陣，使用行列號位置表示每個象元，位置值表示屬性或編碼值。其組織存儲通常有三種方法：。以象元為記錄序列。用數(shù)組來存不同圖層上同位置象元的屬性值。省空間。以層為單位，每層以象元為序記錄坐標(biāo)及屬性值。簡單，量大、。以層為單位，每層以目標(biāo)為序記錄坐標(biāo)及屬性值。

象元1象元2..坐標(biāo)x坐標(biāo)y層1屬性值層2屬性值。。層1

象元1

坐標(biāo)x

坐標(biāo)y

屬性值象元2

。。層2.層1

目標(biāo)1

屬性值象元1坐標(biāo)象元2坐標(biāo)

..

目標(biāo)2

。。層2.可隱含地址值空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第33頁。（1）遞歸分割，可從上到下；弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形XminXmaxYminYmax如如兩者不一致：該弧段所包含的多邊形內(nèi)點(diǎn)及屬性為右多邊形。P1\110a1\110110N1\1110坐標(biāo)x樹的度指所有結(jié)點(diǎn)度的最大值；弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形坐標(biāo)連續(xù)以弧段的結(jié)點(diǎn)按順時針（或逆時針）搜索，得到外邊界的閉合多邊形弧段以逆時針排列；標(biāo)識符坐標(biāo)點(diǎn)屬性編碼注釋坐標(biāo)點(diǎn)（X，Y）前面已得到了組成各個多邊形的相應(yīng)的弧段及其排列，為完成拓?fù)潢P(guān)系生成的全部工作，還要確定下面兩個問題。3）線性四叉樹的特點(diǎn)坐標(biāo)x1、描述地理要素空間性的信息：幾何信息、拓?fù)湫畔⒂脭?shù)組來存不同圖層上同位置象元的屬性值。首先線性四叉樹具有四叉樹的形式。a4N1N5p10gk柵格元素的屬性值實(shí)際上島邊界數(shù)據(jù)的特殊性很易找出?；《危ˋRC）：相鄰兩結(jié)點(diǎn)之間的坐標(biāo)鏈。

四、柵格數(shù)據(jù)的壓縮編碼

1、鏈?zhǔn)骄幋a-----線狀地物編碼空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第34頁。3）線性四叉樹的特點(diǎn)只要在B多邊形邊界上取一點(diǎn)，檢查該點(diǎn)是否在閉合多邊形A內(nèi)。a1N1N2N1a1（3）多邊形拓?fù)潢P(guān)系的生成位編碼值為0，1，對行號貢獻(xiàn)值為0點(diǎn)狀地物數(shù)據(jù)結(jié)構(gòu)較簡單。標(biāo)識符坐標(biāo)點(diǎn)屬性編碼注釋1、描述地理要素空間性的信息：幾何信息、拓?fù)湫畔W2SE3弧段起結(jié)點(diǎn)終結(jié)點(diǎn)結(jié)點(diǎn)弧段a611011\0（1）四叉樹的四進(jìn)制編碼數(shù)據(jù)的組織的目的是在計(jì)算機(jī)內(nèi)組織好數(shù)據(jù)，使達(dá)到最優(yōu)的數(shù)據(jù)存取，最少的存儲空間，最短的處理時間。只要在B多邊形邊界上取一點(diǎn)，檢查該點(diǎn)是否在閉合多邊形A內(nèi)。a3N4N50p3多邊形號弧段號周長面積位編碼值為2，3，對行號貢獻(xiàn)值為1二進(jìn)制行值001前面已得到了組成各個多邊形的相應(yīng)的弧段及其排列，為完成拓?fù)潢P(guān)系生成的全部工作，還要確定下面兩個問題。a3N1a1

110030770000101222234443344466220042700122443456空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第35頁。2、游程編碼

對塊狀地物的柵格數(shù)據(jù)進(jìn)行壓縮編碼

方式（gk,lk)游程終止編碼中g(shù)k柵格元素的屬性值lk游程的終止列號(0,1)(4,3)(7,8)(4,5)(7,8)(4,4)(8,6)(7,8)(0,2)(4,3)(8,6)(7,8)(0,2)(8,6)(7,7)(8,8)(0,3)(8,8)(0,4)(8,8)(0,5)(8,8)游程長度編碼中g(shù)k柵格元素的屬性值lk游程的連續(xù)長度。（0,1)(4,2)(7,5)(4,5)(7,3)(4,4)(8,2)(7,2)(0,2)(4,1)(8,3)(7,2)(0,2)(8,4)(7,1)(8,1)(0,3)(8,5)(0,4)(8,4)(0,5)(8,3)空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第36頁。3、四叉樹編碼1）樹數(shù)據(jù)結(jié)構(gòu)線性表結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)隊(duì)列結(jié)構(gòu)棧結(jié)構(gòu)邏輯結(jié)構(gòu)樹結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)順序存儲結(jié)構(gòu)物理結(jié)構(gòu)（存儲結(jié)構(gòu)）非順序存儲結(jié)構(gòu)（鏈?zhǔn)酱鎯Y(jié)構(gòu)）在數(shù)據(jù)結(jié)構(gòu)中樹屬于非線性數(shù)據(jù)結(jié)構(gòu)。她是有一個或多個結(jié)點(diǎn)組成的有限集合T1，T2，T3TN，其中有一個是根結(jié)點(diǎn)，余下的被分成N個互不相交的集合，這些集合的每一個又都是樹，T1，T2，T3TN被稱為根的子樹?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第37頁。結(jié)點(diǎn)的度指每個結(jié)點(diǎn)的后繼結(jié)點(diǎn)；樹的度指所有結(jié)點(diǎn)度的最大值；結(jié)點(diǎn)的層次樹既具有遞歸結(jié)構(gòu)，又的具有層次結(jié)構(gòu)，即結(jié)點(diǎn)的層次數(shù)樹的深度（或高度）指所有結(jié)點(diǎn)層次的最大值一空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第38頁。2）常規(guī)四叉樹四叉樹是指樹中的每個結(jié)點(diǎn)最多只有四棵子樹，即樹中任一結(jié)點(diǎn)的度數(shù)不的大于4。

主要用在數(shù)據(jù)索引，圖幅索引等。

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第39頁。常規(guī)四叉樹的其特點(diǎn)

（1）遞歸分割，可從上到下；

（2）除了記錄葉結(jié)點(diǎn)外，還要記錄中間結(jié)點(diǎn)。通常以指針來聯(lián)系結(jié)點(diǎn)之間的關(guān)系，包括前趨結(jié)點(diǎn)、后續(xù)結(jié)點(diǎn)（最多4個）、及本結(jié)點(diǎn)的屬性值。（3）常規(guī)四叉樹不僅要記錄每個結(jié)點(diǎn)，還要記錄結(jié)點(diǎn)的前趨結(jié)點(diǎn)和后續(xù)結(jié)點(diǎn)，以反映結(jié)點(diǎn)之間的聯(lián)系，存儲空間大，操作復(fù)雜（因?yàn)閷Y(jié)點(diǎn)進(jìn)行運(yùn)算時，首先要作對樹的遍歷運(yùn)算。在GIS和圖象處理中不用常規(guī)四叉樹，而用線性四叉樹。

空間數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第40頁。

A

NW0NE1SW2SE3四叉樹的分解過程四叉樹的分解過程是將一幅圖等分成四部分，檢查其格網(wǎng)值，如格網(wǎng)子區(qū)的值相同就不再分割，否則遞歸分割，直到每個子塊含有相同值為止?？臻g數(shù)據(jù)的結(jié)構(gòu)與編碼全文共49頁，當(dāng)前為第41頁。3）線性四叉樹的特點(diǎn)

首先線性四叉樹具有四叉樹的形式。一幅2nx

2n柵格陣列的圖用四叉樹分割時，具有的最大深度為n，即可分為0,1,2,3…n層第0