1、第4章 空間數(shù)據(jù)結(jié)構(gòu)1主要內(nèi)容4.1 矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)4.2 柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)4.4 鑲嵌數(shù)據(jù)結(jié)構(gòu)鑲嵌數(shù)據(jù)結(jié)構(gòu)4.5 柵格結(jié)構(gòu)與矢量數(shù)據(jù)結(jié)構(gòu)的比較柵格結(jié)構(gòu)與矢量數(shù)據(jù)結(jié)構(gòu)的比較 24.2 柵格數(shù)據(jù)結(jié)構(gòu)34.2 柵格數(shù)據(jù)結(jié)構(gòu)4.2.1 柵格單元的確定柵格單元的確定 4.2.2 完全柵格數(shù)據(jù)結(jié)構(gòu)完全柵格數(shù)據(jù)結(jié)構(gòu) 4.2.3 壓縮柵格數(shù)據(jù)結(jié)構(gòu)壓縮柵格數(shù)據(jù)結(jié)構(gòu) 44.2 柵格數(shù)據(jù)結(jié)構(gòu)p網(wǎng)格結(jié)構(gòu)(raster或grid cell)或像元結(jié)構(gòu)(pixel) 以表示空間對(duì)象n每個(gè)柵格空間對(duì)象的屬性特征n其由柵格陣列中每個(gè)單元的來確定。p柵格數(shù)據(jù)結(jié)構(gòu)表示的地表是不連續(xù)的，是量化和近似離散的數(shù)據(jù)，

2、一個(gè)柵格單元對(duì)應(yīng)于小塊地理范圍。5p對(duì)于柵格數(shù)據(jù)結(jié)構(gòu)n點(diǎn)點(diǎn)：為一個(gè)像元n線線：在一定方向上連接成串的相鄰像元集合。n面面：聚集在一起的相鄰像元集合。6點(diǎn)線面70000090000900000009070070090700760097777900077079000770709000000yx點(diǎn)、線、面數(shù)據(jù)的點(diǎn)、線、面數(shù)據(jù)的矢量與柵格矢量與柵格表示表示8Representation of point, line, and area features: raster format on the left and vector format on the right.柵格數(shù)據(jù)類型柵格數(shù)據(jù)類型1衛(wèi)星影像

3、衛(wèi)星影像2數(shù)字高程模型（數(shù)字高程模型（DEM）3數(shù)字正射影像圖（數(shù)字正射影像圖（DOM）4二進(jìn)制掃描文件二進(jìn)制掃描文件5數(shù)字柵格數(shù)字柵格影像影像6圖形文件圖形文件：如：如JPG、TIFF、GIF等等7特定地理信息系統(tǒng)軟件特定地理信息系統(tǒng)軟件的柵格數(shù)據(jù)的柵格數(shù)據(jù) .grd4.2.1柵格單元的確定柵格單元的確定1. 柵格數(shù)據(jù)的參數(shù)（1）。柵格單元通常為矩形或。特殊的情況下按經(jīng)緯網(wǎng)劃分。（2）。柵格單元的尺寸，即。柵格柵格單元的合理尺寸單元的合理尺寸應(yīng)能有效地逼近空間對(duì)象的分布特征，以保證空間數(shù)據(jù)的精度。 保證保證最小圖斑不丟失為原則最小圖斑不丟失為原則（3） 和國家基本比例尺地形圖公里網(wǎng)的交點(diǎn)相一

4、致，或者和已有的柵格系統(tǒng)數(shù)據(jù)相一致，并同時(shí)使用作為柵格系統(tǒng)的坐標(biāo)軸。（4） 柵格的坐標(biāo)系統(tǒng)與國家坐標(biāo)系統(tǒng)平行101.柵格數(shù)據(jù)的參數(shù)11X：列：列Y：行：行西南角格網(wǎng)坐標(biāo)西南角格網(wǎng)坐標(biāo)（XWS，YWS） （500，500）格網(wǎng)分辨率格網(wǎng)分辨率 302. 柵格數(shù)據(jù)單元值確定12CAB面面積積占占優(yōu)優(yōu)重重要要性性中心點(diǎn)法中心點(diǎn)法A位于柵格中心處位于柵格中心處的地物類型決定的地物類型決定其取值。其取值。常用于常用于連續(xù)分布連續(xù)分布特性特性的地理現(xiàn)象。的地理現(xiàn)象。C選取最重要的地選取最重要的地物類型為單元值。物類型為單元值。常用于有常用于有特殊意特殊意義而面積較小義而面積較小的的地理要素地理要素A占區(qū)域

5、面積最大占區(qū)域面積最大的地物類型取值的地物類型取值適用于適用于分類較細(xì)、分類較細(xì)、地物斑塊較小地物斑塊較小地地理要素理要素為了逼近原始數(shù)據(jù)精度，除了采用這幾種取值方法外，還可以采用縮小單個(gè)柵格單元的面積，增加?xùn)鸥駟卧倲?shù)的方法 13abc345abcac距離距離: 7/4 (5)面積面積: 7 (6)幾何偏差幾何偏差屬性偏差屬性偏差如ac距離以像元邊線計(jì)算則為7，以像元個(gè)數(shù)為單位則為4。 三角形的面積為6個(gè)平方單位，而右圖中則為7個(gè)平方單位，這種誤差隨像元的增大而增加。 中心點(diǎn)法中心點(diǎn)法面積占優(yōu)法面積占優(yōu)法4. 柵格數(shù)據(jù)的編碼方法p4.2.2完全柵格數(shù)據(jù)結(jié)構(gòu)n直接?xùn)鸥窬幋ap4.2.3壓縮柵格數(shù)

6、據(jù)結(jié)構(gòu)n游程長度編碼n鏈?zhǔn)綌?shù)據(jù)編碼n四叉樹編碼n分塊壓縮編碼144.2.2完全柵格數(shù)據(jù)結(jié)構(gòu)1.直接?xùn)鸥窬幋ap將柵格看做一個(gè)數(shù)據(jù)矩陣，逐行逐個(gè)記錄代碼數(shù)據(jù)p優(yōu)點(diǎn)：簡單、直觀，無壓縮p缺點(diǎn)：存在大量冗余，精度提高有限制。15完全柵格數(shù)據(jù)的組織完全柵格數(shù)據(jù)的組織有三種基本方式：基于像元、基于層（波段）和基于行.bsq （band sequential）基于層（波段）的方式16柵格數(shù)據(jù)文件柵格數(shù)據(jù)文件波段波段1像元像元1，1像元像元1，2像元像元1，m像元像元m，n波段波段2波段波段k.bil （band interleaved by line）基于行的方式17柵格數(shù)據(jù)文件柵格數(shù)據(jù)文件行行1波段波段1

7、行行2像元像元1n波段波段2 像元像元1n波段波段k 像元像元1n行行m.bip （band interleaved by pixel）基于像元方式18柵格數(shù)據(jù)文件柵格數(shù)據(jù)文件像元像元1，1像元像元1，2波段波段1波段波段k像元像元m，n2.游程長度編碼（Run-Length Encoding），將每行中具有映射為一個(gè)游程，每個(gè)游程的數(shù)據(jù)結(jié)構(gòu)為（A，P），A表示屬性值，P代表該游程。p屬性變化越少，壓縮比例越大，適合于的柵格。199999000099090000900977000000770000007777000077770000777700007777原始柵格數(shù)據(jù)( 9 , 4 ) , (

8、 0 , 4 ) ,( 9 , 3 ) , ( 0 , 5 ) ,(0,1)(9,2),(0,1),(7,2),(0,2),( 0 , 4 ) , ( 7 , 2 ) , ( 0 , 2 ) ,( 0 , 4 ) , ( 7 , 4 ) ,( 0 , 4 ) , ( 7 , 4 ) ,( 0 , 4 ) , ( 7 , 4 ) ,(0,4),(7,4)2.游程長度編碼（Run-Length Encoding）p優(yōu)點(diǎn)：n柵格加密時(shí)，數(shù)據(jù)量不會(huì)明顯增加，壓縮效率高，最大限度保留原始柵格結(jié)構(gòu)，n編碼解碼運(yùn)算簡單，且易于檢索、疊加、合并等操作，得到廣泛應(yīng)用。p缺點(diǎn)：n不適合于類型連續(xù)變化或類型區(qū)域分散

9、的數(shù)據(jù)。203. 鏈?zhǔn)綌?shù)據(jù)編碼（Chain Encoding，弗里曼Freeman）p鏈?zhǔn)骄幋a主要是。它把線狀地物和面狀地物的邊界表示為：由某一起始點(diǎn)開始并按某些基本方向確定的?；痉较蚩啥x為：東0，東南l，南2，西南3，西4，西北5，北6，東北7等八個(gè)基本方向。p編碼過程：n起始點(diǎn)的尋找一般遵循從上到下，從左到右從上到下，從左到右的原則；n當(dāng)發(fā)現(xiàn)沒有記錄過的點(diǎn)，且數(shù)值不為0時(shí)，就是一條線或邊界的；n記下該，然后按順時(shí)針方向?qū)ほE，找到相鄰的等值點(diǎn)，并按八個(gè)方向編碼。213. 鏈?zhǔn)綌?shù)據(jù)編碼（Chain Encoding，弗里曼Freeman） 鏈?zhǔn)骄幋a表特征碼 起點(diǎn)行 起點(diǎn)列 鏈碼 線 1 5

10、 3223323 面 3 6 0213246676226 67 70 01 12 23 34 45 5鏈?zhǔn)骄幋a的方向代碼鏈?zhǔn)骄幋a的方向代碼 鏈?zhǔn)骄幋a示意圖鏈?zhǔn)骄幋a示意圖 3 32 22 23 33 32 23 33 32 24 46 66 67 76 60 02 21 1起始點(diǎn)起始點(diǎn)起始點(diǎn)起始點(diǎn)4 4p優(yōu)點(diǎn)：n鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)壓縮能力n且具有一定的運(yùn)算功能，如面積和周長計(jì)算等，探測邊界急彎和凹進(jìn)部分等都比較容易，比較適于存儲(chǔ)圖形數(shù)據(jù)。p缺點(diǎn)：n對(duì)邊界做合并和插入等修改編輯比較困難；n類似矢量結(jié)構(gòu)，不具有區(qū)域的性質(zhì)，對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施；n而且由于鏈碼以每個(gè)區(qū)域

11、為單位存儲(chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)生冗余。 234. 四叉樹編碼（Quad tree Encoding）p四叉樹概述：一種可變分辨率的非均勻網(wǎng)格系統(tǒng)。p基本思想：將一幅柵格數(shù)據(jù)層或圖像等分為四部分，逐塊檢查其格網(wǎng)屬性值（或灰度）；如果某個(gè)子區(qū)的所有格網(wǎng)值都具有相同的值，則這個(gè)子區(qū)就不再繼續(xù)分割，否則還要把這個(gè)子區(qū)再分割成四個(gè)子區(qū)；這樣依次地分割，直到每個(gè)子塊都只含有相同的屬性值或灰度為止。n最上面的一個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)于整個(gè)圖形。n不能再分的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，可能落在不同的層上，該結(jié)點(diǎn)代表子象限單一的代碼，所有葉子結(jié)點(diǎn)所代表的方形區(qū)域覆蓋了整個(gè)圖形。n從上到下，從左到右為葉子

12、結(jié)點(diǎn)編號(hào)，最下面的一排數(shù)字表示各子區(qū)的代碼。p為了保證四叉樹分解能不斷的進(jìn)行下去，要求圖形必須為2n2n的柵格陣列。n 為極限分割次數(shù)，n1是四叉樹最大層數(shù)或最大高度.24方法：1. 自上而下2. 自下而上 A B A A A B A A B B25AAAAA BBBAABBAABBB BA AAAAAA BBBAABBAABBB BA A1）常規(guī)四叉樹p記錄這棵樹的葉結(jié)點(diǎn)外，中間結(jié)點(diǎn)，結(jié)點(diǎn)之間的聯(lián)系用指針聯(lián)系，p每個(gè)結(jié)點(diǎn)需要：n父結(jié)點(diǎn)指針、四個(gè)子結(jié)點(diǎn)的指針和本結(jié)點(diǎn)的屬性值。p指針不僅增加了數(shù)據(jù)的存儲(chǔ)量，還增加了操作的復(fù)雜性：n如層次數(shù)（分割次數(shù)）由從父結(jié)點(diǎn)移到根結(jié)點(diǎn)的次數(shù)來確定，結(jié)點(diǎn)所代表的

13、圖像塊的位置需要從根節(jié)點(diǎn)開始逐步推算下來。p常規(guī)四叉樹并不廣泛用于存儲(chǔ)數(shù)據(jù)，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。262）線性四叉樹p只記錄葉結(jié)點(diǎn)的信息，包括葉結(jié)點(diǎn)的位置，深度（幾次分割）和屬性。p葉結(jié)點(diǎn)的編號(hào)遵循一定的規(guī)則，這種編號(hào)稱為地址碼，常用的有四進(jìn)制、十進(jìn)制Morton碼p優(yōu)點(diǎn)：存貯量小，只對(duì)葉結(jié)點(diǎn)編碼，節(jié)省了大量中間結(jié)點(diǎn)的存儲(chǔ)，地址碼隱含著結(jié)點(diǎn)的位置和分割次數(shù)。線性四叉樹可直接尋址，通過其坐標(biāo)值直接計(jì)算其Morton碼，而不用建立四叉樹。定位碼容易存儲(chǔ)和執(zhí)行實(shí)現(xiàn)集合相加等組合操作。27 3）四進(jìn)制的Morton碼024.44.211321kkkQqqqqqqqMk28方法1（自上而

14、下分割）其始行列號(hào)從0計(jì) 由葉結(jié)點(diǎn)找Morton碼。A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，。B、每一個(gè)位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。 由Morton碼找出四叉樹葉結(jié)點(diǎn)的具體位置。 0123AAAAA BBBAABBA A AABB0303B BA A方法2（自下而上合并的方法）1）計(jì)算二維矩陣每個(gè)元素的下標(biāo)對(duì)應(yīng)的MQ 其始行列號(hào)從0計(jì)。2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。3）依次檢查每四個(gè)相鄰的MQ對(duì)應(yīng)的屬性值，相同合并（不同碼位去掉），不同則存盤,直到?jīng)]有能夠合并的子塊為止。bbQJIM*2290110110A000A001A010A0111A002B0

15、03B012B01310A020A021B030B03111A022A023B032B033304）十進(jìn)制的Morton碼-MDp四進(jìn)制Morton碼直觀上符合四叉樹分割，但許多語言不支持四進(jìn)制變量，需用十進(jìn)制表示Morton碼.1、一種按位操作的方法：(1)行、列號(hào)轉(zhuǎn)換為二進(jìn)制 Ib= 1 0 Jb= 1 1(2)I行J列交叉 1 1 0 1 = 13(3)再化為十進(jìn)制. 實(shí)質(zhì)上是按左上、右上、左下、右下的順序，從零開始對(duì)每個(gè)柵格進(jìn)行自然編碼。315）線性四叉樹的二維行程編碼右圖的壓縮處理過程為：1.按Morton碼讀入一維數(shù)組。 Morton碼：0 1 2 3 4 5 6 7 8 9 10

16、 1112 13 14 15 象元值：A A A B A A B B A A A A B B B B2.四相鄰象元合并，只記錄第一個(gè)象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3.進(jìn)一步用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B 32A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15四叉樹編碼法的優(yōu)點(diǎn)1）容易而有效地計(jì)算多邊形的數(shù)量特征；2

17、）陣列各部分的分辨率是可變的，邊界復(fù)雜部分四叉樹較高即分級(jí)多，分辨率也高，而不需表示許多細(xì)節(jié)的部分則分級(jí)少，分辨率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量；3）柵格到四叉樹及四叉樹到簡單柵格結(jié)構(gòu)的轉(zhuǎn)換比其它壓縮方法容易；4）多邊形中嵌套異類小多邊形的表示較方便。33四叉樹編碼缺點(diǎn)p此外，目前應(yīng)用四叉樹還存下列問題：1) 矢/柵正反變換還不理想。2) 建立四叉樹耗費(fèi)機(jī)時(shí)很多。3) 四叉樹雖可修改，但很費(fèi)事4) 四叉樹未能直接表示物體間的拓?fù)潢P(guān)系。5) 與非樹表示法比較，四叉樹表示法的缺點(diǎn)在于轉(zhuǎn)換的不穩(wěn)定性或叫滑動(dòng)變異例如，兩個(gè)圖像的差異僅由于平移，就會(huì)構(gòu)成極為不同的四叉樹，因而很難根據(jù)四叉樹來

18、判斷這兩個(gè)圖像是否全同，故不利于做形狀分析和模式識(shí)別， 6) 一個(gè)物體的圖像在構(gòu)成四叉樹時(shí)會(huì)被分割到若干個(gè)象限中，使它失去了內(nèi)在的相關(guān)性。345.塊狀編碼塊狀編碼(block code)p采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置(行、列號(hào))和半徑，再加上記錄單元代碼組成。p右圖用12個(gè)單位正方形，5個(gè)4單位的正方形和2個(gè)16 單位的正方形就能完整表示，具體編碼如下： (1,1,2,9)，(1,3,1,9)，(1,4,1,9)，(1,5,2,0)，(1,7,2,0)，(2,3,1,9)，(2,4,1,0)，(3,1,1,0)，(3,2,1,9)，(3,3,1,9)，(3,4,1,0)，(3,5,2,7)，(3,7,2,0)，(4,4,1,0)，(4,2,1,0)，(4,3,1,0)，(4,4,1,0)，(5,1,4,0)，(5,5,4,7)p特點(diǎn)：n一個(gè)多邊形所包含的正方形越大，多邊形的邊界越簡單，塊狀編碼的效率就越好。n塊狀編碼對(duì)大而簡單的多邊形更為有效，而對(duì)那些碎部較多的復(fù)雜多邊形效果并不好。n塊狀編碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。然而對(duì)某些運(yùn)算不適應(yīng)，