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

第三章空間數(shù)據(jù)結(jié)構(gòu)與編碼第一頁，共52頁。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ù)。第二頁，共52頁。2、空間數(shù)據(jù)的編碼

第三頁，共52頁。3、數(shù)據(jù)編碼的過程

第四頁，共52頁。4、空間物體的幾何類型

（1）點狀分布特征如城鎮(zhèn)、企事業(yè)單位、基地、氣象站、山峰、火山口等。（2）線狀分布特征河流、海岸線、鐵路、公路、地下管線，行政邊界等。（3）面狀分布特征如土壤、森林、草原、沙漠、湖泊等，通常稱多邊形。（4）體狀分布特征如高層建筑、水體、云體、山體、礦體等?？傊?，空間現(xiàn)象十分復(fù)雜，為此將其抽象到空間對象（目標(biāo)）來表達(dá)空間實體。第五頁，共52頁。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)系；第六頁，共52頁。2、拓?fù)鋵W(xué)中空間元素拓?fù)鋵W(xué)是幾何學(xué)的一個分支，其基本元素：結(jié)點（NOD）：弧段的交點。島結(jié)點是特殊結(jié)點?；《危ˋRC）：相鄰兩結(jié)點之間的坐標(biāo)鏈。島邊界弧段是特殊弧段。多邊形（polygon）（圖斑或面）：有限弧段組成的封閉區(qū)。關(guān)系的性質(zhì)可分為：相鄰、相連、相交、相離、相重、包含等。第七頁，共52頁。從拓?fù)浣嵌瓤?，幾何形狀不同的事物其拓?fù)潢P(guān)系可能相同

點之間拓?fù)潢P(guān)系（鄰接性）的描述面之間拓?fù)潢P(guān)系（鄰接性）的描述第八頁，共52頁。3、空間數(shù)據(jù)的拓?fù)潢P(guān)系

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

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

多邊形弧段號弧段號起點終點結(jié)點弧段p1a1a5a6a1N2N1N1a1a3a5P2a2a4a6a2N2N3N2a1a2a6P3a3a4a5a3N3N1N3a2a3a4p4a7a4N3N4N4a4a5a6a5N1N4N5a7a6N4N2a7N5N5

a3N1a1a5p3N4p1N3a4P4a6N5a7p2a2N2第九頁，共52頁。2）拓?fù)涞泥徑有院瓦B通性

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

P1\110a1\110110N1\1110p21\11a21\11010N21\110p311\0a311\1100N311\10p4010\a4011\110N4111\0a51011\10N50000\a611011\0a7000000\多邊形鄰接矩陣弧段鄰接矩陣結(jié)點連通矩陣第十頁，共52頁。3）拓?fù)涞陌?/p>

P1p2p2p1p3p1p3p2面的簡單包含面的多層包含面的等價包含面包含點面包含線線包含點第十一頁，共52頁。

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

關(guān)聯(lián)性相鄰（連）性相離性相交性包含性重合性點與點線與線面與面點與線點與面線與面第十二頁，共52頁。3.3矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

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

2、矢量數(shù)據(jù)的獲取第十三頁，共52頁。3、無拓?fù)潢P(guān)系的矢量模型

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

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

1）GIS中建立拓?fù)潢P(guān)系的優(yōu)缺點優(yōu)點：（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ù)共享；缺點：（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜，不便于系統(tǒng)的維護(hù)和更新，如局部實體的變化要重建拓?fù)潢P(guān)系；（2）對單個實體的操作效率不高，如增加、刪除、修改一個實體時涉及一系列的文件和數(shù)據(jù)庫表格；（3）難以表達(dá)復(fù)雜的地理實體。4、拓?fù)潢P(guān)系的矢量模型第十六頁，共52頁。2）拓?fù)潢P(guān)系的關(guān)聯(lián)表達(dá)

顯式表示

(a)多邊形、弧段、結(jié)點（自上到下）多邊形弧段弧段結(jié)點P1a4a5a6a1N1N2P2a1a8a5a2N2N4P3a3a6a7a3N4N5P4a2a7a8a4N1N5a5N1N3a6N3N5a7N3N4a8N2N3（b）結(jié)點、弧段、多邊形結(jié)點弧段N1a1a4a5N2a1a2a8N3a5a6a7a8N4a2a3a7N5a3a4a6弧段左多邊形右多邊形a10P2a20p4a30p3a4p10a5p2p1a6p3p1a7p4p3a8p4p2第十七頁，共52頁。半顯式表示

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

第十八頁，共52頁。5、具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)模型例

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

第十九頁，共52頁。

點實體標(biāo)識符類型（簡單點、結(jié)點、文字說明）序列號坐標(biāo)點（X，Y）相關(guān)屬性符號簡單點比例尺方向指針結(jié)點符號排列文字說明字體方向字符大小其它屬性第二十頁，共52頁。2）線狀數(shù)據(jù)結(jié)構(gòu)

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

線標(biāo)識符序號坐標(biāo)系列點屬性編碼注釋線狀地物坐標(biāo)索引表線標(biāo)識符序號起點序號終點序號XminXmaxYminYmax第二十一頁，共52頁。

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

(1）多邊形文件多邊形號弧段號周長面積p1a4a5a6p2...（2）弧段索引文件弧段起結(jié)點終結(jié)點左多邊形右多邊形XminXmaxYminYmax

a1N1N20P2a2N2N40p4a3N4N50p3a4N1N5p10a5N1N3p2p1a6N3N6p3p1a7N3N4p4p3a8N2N3p4p2(3）弧段坐標(biāo)文件弧段號坐標(biāo)點a1x1y1,x2y2,….…….

第二十二頁，共52頁。6、拓?fù)潢P(guān)系的自動生成1）歐拉定理----用于檢驗拓?fù)潢P(guān)系歐拉定理認(rèn)為a,n,P之間存在如下關(guān)系：c=n-a+P；其中c為常數(shù)是多邊形圖的一個特征。C值為2;例1右圖實線部分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歐拉定理主要用于檢查點、線、面中是否存在多余或漏掉的圖形元素。第二十三頁，共52頁。

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

弧段起結(jié)點終結(jié)點結(jié)點弧段a1N1N2N1a1a2N2N3N2a1a2a3a3N2N4N3a2N4a3

a1a2a1a3a2N1N2N3N1N2N3N4第二十四頁，共52頁。（2）坐標(biāo)鏈（弧段）的求交的方法弧段的包絡(luò)矩形：弧段坐標(biāo)鏈中最大最小值XminYminXmaxYmax組成的矩形稱該弧段的包絡(luò)矩形；多邊形的包絡(luò)矩形：組成多邊形的所有坐標(biāo)鏈中最大最小值組成的矩形稱該多邊形的包絡(luò)矩形；XminYminXmaxYmaxXmaxYmaxXminYmin第二十五頁，共52頁。

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

第二十六頁，共52頁。以結(jié)點為中心生成拓?fù)潢P(guān)系

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

7、拓?fù)渚庉嬐負(fù)渚庉嬘脕頇z查生成拓?fù)潢P(guān)系的正確性，并進(jìn)行編輯處理，主要問題有：1）重復(fù)輸入線的檢查出現(xiàn)很多小的偽多邊形。2）漏線段的檢查。出現(xiàn)懸線，多邊形不封閉。3）圖與屬性不一致檢查圖與屬性匹配檢查，并輸出不匹配處。4）邏輯關(guān)系的檢查歐拉定理檢查DIME檢查，以多邊形為例第三十頁，共52頁。3.4柵格數(shù)據(jù)結(jié)構(gòu)及其編碼一、柵格數(shù)據(jù)的特點第三十一頁，共52頁。二、柵格數(shù)據(jù)的獲取第三十二頁，共52頁。三、柵格數(shù)據(jù)的組織數(shù)據(jù)的組織的目的是在計算機(jī)內(nèi)組織好數(shù)據(jù)，使達(dá)到最優(yōu)的數(shù)據(jù)存取，最少的存儲空間，最短的處理時間。柵格數(shù)據(jù)的結(jié)構(gòu)實質(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.可隱含地址值第三十三頁，共52頁。

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

1、鏈?zhǔn)骄幋a-----線狀地物編碼第三十四頁，共52頁。

110030770000101222234443344466220042700122443456第三十五頁，共52頁。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)第三十六頁，共52頁。3、四叉樹編碼1）樹數(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)非線性數(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é)點組成的有限集合T1，T2，T3TN，其中有一個是根結(jié)點，余下的被分成N個互不相交的集合，這些集合的每一個又都是樹，T1，T2，T3TN被稱為根的子樹。第三十七頁，共52頁。結(jié)點的度指每個結(jié)點的后繼結(jié)點；樹的度指所有結(jié)點度的最大值；結(jié)點的層次樹既具有遞歸結(jié)構(gòu)，又的具有層次結(jié)構(gòu)，即結(jié)點的層次數(shù)樹的深度（或高度）指所有結(jié)點層次的最大值一第三十八頁，共52頁。2）常規(guī)四叉樹四叉樹是指樹中的每個結(jié)點最多只有四棵子樹，即樹中任一結(jié)點的度數(shù)不的大于4。

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

第三十九頁，共52頁。常規(guī)四叉樹的其特點

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

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

第四十頁，共52頁。

A

NW0NE1SW2SE3四叉樹的分解過程四叉樹的分解過程是將一幅圖等分成四部分，檢查其格網(wǎng)值，如格網(wǎng)子區(qū)的值相同就不再分割，否則遞歸分割，直到每個子塊含有相同值為止。第四十一頁，共52頁。3）線性四叉樹的特點

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

2n柵格陣列的圖用四叉樹分割時，具有的最大深度為n，即可分為0,1,2,3…n層第0層，邊長上的最大柵格數(shù)為2n第1層，邊長上的最大柵格數(shù)為2n-1第2層，邊長上的最大柵格數(shù)為2n-2第n層，邊長上的最大柵格數(shù)為2n-n=1其次線性四叉樹的存儲方式同常規(guī)四叉樹不同。在線性四叉樹中只記錄葉結(jié)點信息，如葉結(jié)點的位置，大小、格網(wǎng)值，不存儲中間結(jié)點。在線性四叉樹中葉結(jié)點信息的編碼號按一定規(guī)則，這種編號稱地址碼(位置嗎），以表示它所處的位置。通常分四進(jìn)制編號和十進(jìn)制編號兩種。

第四十二頁，共52頁。4）四叉樹的編碼四叉樹四叉樹對應(yīng)的圖如上一幅23x

23圖，其位置碼的最長位數(shù)是3位，每位數(shù)的數(shù)字是都不大于3的四進(jìn)制數(shù)。第四十三頁，共52頁。（1）四叉樹的四進(jìn)制編碼如下23x

23圖，其位置碼的最長位數(shù)是3位，每位的數(shù)字都是不大于3的四進(jìn)制數(shù)。位置碼的位數(shù)決定于四叉樹分割的層數(shù)，圖形愈復(fù)雜，分割的層數(shù)多，相應(yīng)的位置碼數(shù)愈多。這是自上而下的分割法，核心是檢查全局，其值不單調(diào)是一分四，直到數(shù)值或內(nèi)容單值為止。自下而上的合并法，先將區(qū)域編碼，排序，依此檢查相鄰4個碼的屬性值，相同的合并，反之作為四個葉結(jié)點記錄，依此向上直到最后生成根結(jié)點。第四十四頁，共52頁。四叉樹中四進(jìn)制位置碼的編碼和解碼線性四叉樹地址計算：addres(I,J)=2*Iyb+JybIyb,

Jyb分別是行I，列J的二進(jìn)制形式如第001行（0開始），第101列其地址碼是addres(I,J)=2*1+101=103；反之，知道103碼可算出行列號位編碼值為0，1，對行號貢獻(xiàn)值為0位編碼值為2，3，對行號