二章空間數(shù)據(jù)結(jié)構(gòu)及編碼

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第1頁。地理空間數(shù)據(jù)建模Gis怎樣組織數(shù)據(jù)以模擬地理事物和現(xiàn)象的呢?舉例二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第2頁。我們將gis所抽象,表達的地理事物和現(xiàn)象,稱為空間對象;空間對象的位置相互關(guān)系,稱為空間關(guān)系二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第3頁。a空間對象點狀空間對象(0維對象)線狀空間對象面狀空間對象體狀空間對象除空間維數(shù)特性外,空間對象還可以從其復(fù)雜性,規(guī)則性,人為性等角度認識和區(qū)分二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第4頁。b空間關(guān)系通常分為3類度量空間關(guān)系順序空間關(guān)系拓撲空間關(guān)系

-------連接性

-------包含

-------鄰接性二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第5頁?？臻g數(shù)據(jù)結(jié)構(gòu)和空間數(shù)據(jù)模型研究地理空間數(shù)據(jù)組織和管理.兩者之間的關(guān)系,與一般的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)模型的關(guān)系有兩點相似之處.其一,空間數(shù)據(jù)結(jié)構(gòu)所作的數(shù)據(jù)組織工作,比空間數(shù)據(jù)模型更基層些,它偏重數(shù)據(jù)表達的物理實現(xiàn),而空間數(shù)據(jù)模型涉及到空間數(shù)據(jù)管理的層次.其二，同普通數(shù)據(jù)的數(shù)據(jù)模型一樣,空間數(shù)據(jù)模型的命名通常與相應(yīng)的空間數(shù)據(jù)結(jié)構(gòu)相同.二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第6頁。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第7頁。

定義特點：數(shù)據(jù)的空間性數(shù)據(jù)的屬性數(shù)據(jù)的時間性二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第8頁。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第9頁。地理要素之間的空間區(qū)位關(guān)系可抽象為點、線（或?。?、多邊形（區(qū)域）之間的空間幾何關(guān)系，其關(guān)系如下

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第10頁。歐氏平面上實體對象所具有的拓撲和非拓撲屬性拓撲屬性一個點在一個弧段的端點一個弧段是一個簡單弧段（弧段自身不相交）一個點在一個區(qū)域的邊界上一個點在一個區(qū)域的內(nèi)部一個點在一個區(qū)域的外部一個點在一個環(huán)的內(nèi)部一個面是一個簡單面（面上沒有“島”）一個面的連續(xù)性（給定面上任意兩點，從一點可以完全在面的內(nèi)部沿任意路徑走向另一點）非拓撲屬性兩點之間的距離一個點指向另一個點的方向弧段的長度一個區(qū)域的周長一個區(qū)域的面積二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第11頁。弧屬性表（AAT）多邊形屬性表（PAT）#－id多邊形標(biāo)識碼周長面積108.418-4.50621048.5962.07831024.2961.14441012.2330.30151034.3250.983＃－id弧標(biāo)識碼起始結(jié)點終到結(jié)點弧左多邊形弧右多變形弧長13831321.51523343351.04033541132.10643722242.23353615124.12063953521.09373445512.1931.本圖有多少個多邊形和??？2.哪個多邊形是包含于另一個中？3.哪個多邊形和多邊形102相鄰？4.手工建立一個簡單示意圖表明本圖的空間格局二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第12頁。二、柵格數(shù)據(jù)結(jié)構(gòu)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第13頁。

定義：又稱為網(wǎng)格結(jié)構(gòu)，它是將地表劃分成為緊密相鄰的網(wǎng)格陣列。每個網(wǎng)格的位置由行列號定義。它包含一個代碼，以表示該網(wǎng)格的屬性或指向?qū)傩杂涗浀闹羔?。注意：柵格?shù)據(jù)模型是將連續(xù)空間離散化，即用二維鋪蓋或劃分覆蓋整個連續(xù)空間，這種鋪蓋可以分為規(guī)則的和不規(guī)則的二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第14頁。三角形、方格和六角形劃分

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第15頁。柵格數(shù)據(jù)模型二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第16頁。00002000000200000102033000023333002033330020033002000000二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第17頁。線面點二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第18頁。

面積占優(yōu)法

中心點法

重要性法

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第19頁。直接?xùn)鸥窬幋a行程編碼塊碼鏈?zhǔn)骄幋a四叉樹結(jié)構(gòu)二維行程編碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第20頁。基本思路：對于一幅柵格圖像，常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。游程長度編碼（Run-LengthCodes）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第21頁。1）只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及相同的代碼重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。兩種方案（屬性值，長度）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第22頁。

例如

（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）。0744444477774777444487780840877808800800887888880000888800000888壓縮比的大小是與圖的復(fù)雜程度成反比的，在變化多的部分，游程數(shù)就多，變化少的部分游程數(shù)就少，圖件越簡單，壓縮效率就越高44：64二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第23頁。2）逐個記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼編碼如下（沿列方向）（1，0），（2，4），（4，0）；（1，4），（4，0）；（1，4），（5，8），（6，0）；（1，7），（2，4），（4，8），（7，0）；（1，7），（2，4），（3，8），（8，0）；（1，7），（3，8）；（1，7），（6，8）；（1，7），（5，8）。（屬性值，屬性發(fā)生變化的位置）0744444477774777444487780840877808800800887888880000888800000888二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第24頁。特點：屬性的變化愈少，行程愈長，則壓縮的比例越大，壓縮比與圖的復(fù)雜程度成反比。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第25頁。

塊碼是游程長度編碼擴展到二維的情況，采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置（行、列號）和半徑，再加上記錄單位的代碼組成。塊碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第26頁。對圖所示圖像的塊碼編碼如下：

(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。0744444477774777444487780840877808800800887888880000888800000888該例中塊碼用了120個整數(shù)，比直接編碼還多，這是因為例中為描述方便，柵格劃分很粗糙，在實際應(yīng)用中，柵格劃分細，數(shù)據(jù)冗余多的多，才能顯出壓縮編碼的效果，而且還可以作一些技術(shù)處理，如行號可以通過行間標(biāo)記而省去記錄，行號和半徑等也不必用雙字節(jié)整數(shù)來記錄，可進一步減少數(shù)據(jù)冗余。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第27頁。塊碼具有可變的分辨率，即當(dāng)代碼變化小時圖塊大，就是說在區(qū)域圖斑內(nèi)部分辨率低；反之，分辨率高。塊碼與游程長度編碼相似，隨著圖形復(fù)雜程度的提高而降低效率，就是說圖斑越大，壓縮比越高；圖斑越碎，壓縮比越低。塊碼在合并、插入、檢查延伸性、計算面積等操作時有明顯的優(yōu)越性。然而在某些操作時，則必須把游程長度編碼和塊碼解碼，轉(zhuǎn)換為基本柵格結(jié)構(gòu)進行。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第28頁。鏈碼（ChainCodes）

鏈碼又稱為弗里曼鏈碼[Freeman]或邊界鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向的凹凸度等運算十分方便，比較適合于存儲圖形數(shù)據(jù)。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第29頁。缺點是對邊界進行合并和插入等修改編輯工作比較困難，對局部的修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的邊界將被重復(fù)存儲而產(chǎn)生冗余。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第30頁。

基本思想：將一幅柵格地圖或圖像等分為四部分，逐塊檢查其格網(wǎng)屬性值（或灰度），如果某個子區(qū)的所有格網(wǎng)值都相同，則這個子區(qū)就不再繼續(xù)分割，否則還要把這個子區(qū)再分割，直到每個子塊都只含有相同的屬性值或灰度為止。

四叉樹結(jié)構(gòu)四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運算可以在編碼數(shù)據(jù)上直接實現(xiàn)，大大地提高了運算效率，是優(yōu)秀的柵格壓縮編碼之一二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第31頁。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第32頁。1）從四叉樹的特點可知，一幅2n*2n

柵格陣列圖，具有的最大深度數(shù)為n，可能具有的層次為0，1，2，……..n注意二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第33頁。2）每一層的柵格寬度，即每層邊上包含的最大柵格數(shù)，反映了所在葉結(jié)點表示的正方形集合的大小，其值為：2（最大深度-當(dāng)前層次）例如：一幅23×23

的柵格陣列，它具有的最大深度為3，可能層次分別為0，1，2，3。其中：第0層邊長上的最大柵格數(shù)為2（3-0）＝8

第1層邊長上的最大柵格數(shù)為2（3-1）＝4

第2層邊長上的最大柵格數(shù)為2（3-2）＝2

第3層邊長上的最大柵格數(shù)為2（3-3）＝1二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第34頁。111100001111000011100000111000003344400033444000334400003344000011011010344004034000層1層2層3層（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第35頁。常規(guī)四叉樹除了記錄葉結(jié)點之外，還要記錄中間結(jié)點。結(jié)點之間借助指針聯(lián)系，每個結(jié)點需要用六個量表達，即四個葉結(jié)點指針、一個父結(jié)點指針和一個結(jié)點的屬性或灰度值。這些指針不僅增加了數(shù)據(jù)儲存量，而且增加了操作的復(fù)雜性。常規(guī)四叉樹與線性四叉樹二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第36頁。線性四叉樹只存儲最后葉結(jié)點的信息。包括葉結(jié)點的位置、深度和本結(jié)點的屬性或灰度值線性四叉樹葉結(jié)點的編號需要遵循一定的規(guī)則，這種編號成為地址碼，它隱含了葉結(jié)點的位置和深度信息。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第37頁。a.基于深度和層次碼的線性四叉樹的編碼它是通過記錄葉結(jié)點的深度碼和層次碼來描述葉結(jié)點的位置碼幾種線性四叉樹的編碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第38頁。111100001111000011100000111000003344400033444000334400003344000011011010344004034000層1層2層3層（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第39頁。

該地址碼的十進制為：？層次碼深度碼第一層第二層第三層00111100110層1層2層3層（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第40頁。b.基于四進制的線性四叉樹編碼0層1層2層3層（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）第一層第二層第三層033二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第41頁。思考請為23×23

柵格陣列中的每個柵格建立基于四進制的四叉樹編碼方式的地址碼？你能找出何種規(guī)律？二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第42頁。000001010011100101110111000000001010011100101110111001002003012013102103112113010020021030031120121130131011022023032033122123132133100200201210211300301310311101202203212213302303312313110220221230231320321330331111222223232233322323332333二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第43頁。

先將柵格的行列號轉(zhuǎn)換為二進制，得二進制行號Iyb，列號Ixb，則M=2×Iyb＋Ixb如結(jié)點7：

M=2*011+011＝033二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第44頁。如果知道基于四進制四叉樹編碼方式的地址碼，你能知道它的行列號碼嗎？思考二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第45頁。若該位的編碼值為0，1，則行號Iyb值為0；若該位的編碼值為2，3，則行號Iyb值為1；若該位的編碼值為0，2，則列號Ixb值為0；若該位的編碼值為1，3，則列號Ixb值為1；

如：M碼為：103

二進制行值Iyb為：001

二進制列值Ixb為：101二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第46頁。000001010011100101110111000000001010011100101110111001002003012013102103112113010020021030031120121130131011022023032033122123132133100200201210211300301310311101202203212213302303312313110220221230231320321330331111222223232233322323332333000001010011100101110111000000110010100203003101103203310020213003013110130230311022233233111二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第47頁。規(guī)則：首先將二維柵格數(shù)據(jù)的行列號轉(zhuǎn)換為二進制，然后交叉放入Morton碼中，即為線性四叉樹的地址碼：行號＝5（101）；列號＝7（111）

Morton＝110111＝55c.基于十進制的線性四叉樹編碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第48頁。

請快速建立8*8柵格陣列中的每個柵格的Morton思考二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第49頁。0000010100111001011101110000145161720210012367181922230108912132425282901110111415262730311003233363748495253101343538395051545511040414445565760611114243464758596263M碼屬性值004050607480124……….….….…..…..….…..二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第50頁。二維行程編碼二維行程編碼二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第51頁。再議游程編碼a.定義游程編碼結(jié)構(gòu)游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列X1,X2,X3…..XN，映射為相應(yīng)的二元序列（Ai，Pi），i＝1，k，且k<=n.其中，A為屬性值，P為游程，k為游程序號二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第52頁。2255275577755555序號二元組序列1（2，2）2（5，2）3（2，1）4（7，1）5（5，2）6（7，3）7（5，5）二元映射二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第53頁。這種結(jié)構(gòu)特別適合于二值圖數(shù)據(jù)的表示，如圖1111111000001111100001111序號二元組序號1（1，7）2（0，5）3（1，5）4（0，4）5（1，4）二元映射二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第54頁。b.游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通?？赏ㄟ^事先測試，估算圖層的數(shù)據(jù)冗余度Re：Re＝1－Q/(M×N)Q：圖層內(nèi)相鄰屬性值變化次數(shù)的累加和M：為圖層網(wǎng)格的行數(shù)N：為圖層網(wǎng)格的列數(shù)當(dāng)?shù)闹荡笥?/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第55頁。當(dāng)柵格數(shù)據(jù)為規(guī)則的數(shù)字地形高程即DEM時，由于這種類型數(shù)據(jù)的相鄰的數(shù)據(jù)具有高度的相關(guān)性，可通過差分映射進行預(yù)處理，然后在采用游程長度壓縮編碼法。例如二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第56頁。2468357824682581122223221222223332321223差分二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第57頁。為了提高系統(tǒng)對這些數(shù)據(jù)的訪問效率，通常采用索引順序文件的方法來組織數(shù)據(jù)。當(dāng)由位置參數(shù)訪問其屬性特征時，利用邏輯順序和邏輯地址的關(guān)系，很快在索引文件中找到指向數(shù)據(jù)文件欲訪柵格的指針，并求出其邏輯地址，就能找到該柵格的屬性。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第58頁。柵格行序號逐行游程累計數(shù)0102..10037..572游程序號編碼值0001000200030004.0007..0572R1R2R3R4.R7.R572索引文件數(shù)據(jù)文件二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第59頁。數(shù)據(jù)文件像元1X坐標(biāo)Y坐標(biāo)層1屬性層2屬性層3屬性層n屬性像元2像元n以像元為記錄的序列。優(yōu)點：因為n層中每個像元實際是只存儲了一層的像元坐標(biāo)，節(jié)約存儲空間；每個網(wǎng)格單元的多主題或多層之間比較相對容易實現(xiàn)。不足之處在于不能完全各主題的空間關(guān)系，即由于每個網(wǎng)格單元位置單獨編碼，要比較不同層的網(wǎng)格單元組是很困難的二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第60頁。以層為基礎(chǔ)，每一層又以像元順序記錄它的坐標(biāo)和屬性值，一層記錄完后再記錄第二層。這種方法較為簡單，但需要的存貯空間最大。數(shù)據(jù)文件層1x坐標(biāo)Y坐標(biāo)屬性值像元2像元n像元1層2層n二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第61頁。

以層為基礎(chǔ)，但每一層內(nèi)則以多邊形（也稱制圖單元）為序記錄多邊形的屬性值和充滿多邊形的各像元的坐標(biāo)。

數(shù)據(jù)文件層1屬性值多邊形2多邊形n多邊形1層2層n像元1坐標(biāo)像元2坐標(biāo)像元n坐標(biāo)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第62頁。圖形文件如：TIFF、GIF、JPEG文件可用各種圖像壓縮算法作均稱壓縮，TIFF和GIF文件用無損壓縮，使原圖被精確重構(gòu)，而JPEG采用有損壓縮，它可達到很大的壓縮比，但不能完整重構(gòu)原圖像。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第63頁。課內(nèi)作業(yè)一、右圖

1.以第3行，第5列為例說明如何將二維刪格數(shù)據(jù)的行列號轉(zhuǎn)換為Morton碼二、舉例說明：與塊碼相比，四叉樹在表示柵格結(jié)構(gòu)時有何不足？0044004454404400二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第64頁。

三、編寫程序，實現(xiàn)以下功能

1）將直接?xùn)鸥窬幋a文件轉(zhuǎn)換為RLE格式文件

2）將RLE柵格數(shù)據(jù)文件轉(zhuǎn)換為線性四叉樹編碼文件（基于十進制的線性四叉樹編碼）課外作業(yè)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第65頁。（a）塊碼分割（b）四叉樹分割二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第66頁。小知識點

——柵格數(shù)據(jù)類型衛(wèi)星影像數(shù)字高程模型數(shù)字正射影像二進制掃描文件數(shù)字柵格圖形圖形文件特定地理信息系統(tǒng)軟件的柵格數(shù)據(jù)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第67頁。小知識點

——柵格數(shù)據(jù)文件為導(dǎo)入要用的柵格數(shù)據(jù)，GIS軟件包必須有數(shù)據(jù)結(jié)構(gòu)和壓縮方法的信息。此類信息通常包含在頭文件中，頭文件的功能類似于元數(shù)據(jù)。例如：衛(wèi)星影像的頭文件（常以.hdr為擴展名）包含了有關(guān)影像數(shù)據(jù)的信息，如數(shù)據(jù)結(jié)構(gòu)方法，行列數(shù)，光譜波段數(shù)，每個波段每一像元的比特數(shù)。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第68頁。三、矢量數(shù)據(jù)結(jié)構(gòu)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第69頁。

矢量結(jié)構(gòu)：即通過記錄坐標(biāo)的方式盡可能精確地表示點、線、多邊形等地理實體.注意：由于坐標(biāo)空間設(shè)為連續(xù)，所以允許任意位置、長度和面積的精確定義。但是，其精度僅受數(shù)字化設(shè)備的精度和數(shù)值記錄字長的限制，在一般情況下，比柵格結(jié)構(gòu)精度高得多。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第70頁。矢量數(shù)據(jù)模型二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第71頁。對于點實體（0維對象），沒有長度和寬度

只記錄其在特定坐標(biāo)系下的坐標(biāo)和屬性代碼；二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第72頁。線實體（1維對象），只有長度沒有寬度：用一系列足夠短的直線首尾相接表示一條曲線。

矢量結(jié)構(gòu)中只記錄這些小線段的端點坐標(biāo)，將曲線表示為一個坐標(biāo)序列，坐標(biāo)之間認為是以直線段相連，在一定精度范圍內(nèi)可以逼真地表示各種形狀的線狀地物。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第73頁?！岸噙呅巍痹诘乩硇畔⑾到y(tǒng)中是指一個任意形狀、邊界完全閉合的空間區(qū)域。

其邊界將整個空間劃分為兩個部分：包含無窮遠點的部分稱為外部，另一部分稱為多邊形內(nèi)部。

多邊形的邊界線同線實體一樣，可以被看作是由一系列多而短的直線段組成。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第74頁。矢量數(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)及編碼全文共110頁，當(dāng)前為第75頁。1）簡單數(shù)據(jù)結(jié)構(gòu)

a.面條（Spaghetti方式）在簡單數(shù)據(jù)結(jié)構(gòu)中，空間數(shù)據(jù)按照以基本的空間對象（點、線、多邊形）為單位進行單獨組織，不含有拓撲關(guān)系數(shù)據(jù)，最典型的是面條（Spaghetti方式）

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第76頁。

由多邊形邊界的x、y坐標(biāo)對集合及說明信息組成，是最簡單的一種多邊形矢量編碼，如上圖記為以下坐標(biāo)文件：10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；x33,y33；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；x19,y19；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；x21,y21；二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第77頁。

坐標(biāo)序列法文件結(jié)構(gòu)簡單，易于實現(xiàn)以多邊形為單位的運算和顯示。特點：

1.數(shù)據(jù)按點、線或多邊形為單元組織，數(shù)據(jù)編排直觀，數(shù)字化操作簡單

2．多邊形之間的公共邊界被數(shù)字化和存儲兩次，由此產(chǎn)生冗余和碎屑多邊形；

3．每個多邊形自成體系而缺少鄰域信息，難以進行鄰域處理，如消除某兩個多邊形之間的共同邊界；

4.島只作為一個單個的圖形建造，沒有與外包多邊形的聯(lián)系；

5．不易檢查拓撲錯誤。這種方法可用于簡單的粗精度制圖系統(tǒng)中

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第78頁。

該法采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，方法是對所有邊界點進行數(shù)字化，將坐標(biāo)對以順序方式存儲，由點索引與邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu)

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第79頁。

以下分別為右圖的多邊形文件和線文件樹狀索引示意圖。其文件結(jié)構(gòu)如下：線與多邊形之間的樹狀索引二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第80頁。點與邊界線之間的樹狀索引二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第81頁。采用上述的樹狀結(jié)構(gòu)，前圖的多邊形數(shù)據(jù)記錄如下：1）點文件點號坐標(biāo)1x1,y12x2,y2……40x40,y402）線文件線號起點終點點號I161,2,3,4,5,6II686,7,8…………X333333,34,35,36,37,38,39,40,333）多邊形文件多邊形編號多邊形邊界10I,II,IX20III,VII,VIII,IX,X30X40IV,VI,VII50II,III,IV,V二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第82頁。樹狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問題，在簡化過于復(fù)雜的邊界線或合并相鄰多邊形時可不必改造索引表，鄰域信息和島狀信息可以通過對多邊形文件的線索引處理得到

但是比較繁瑣，因而給相鄰函數(shù)運算，消除無用邊，處理島狀信息以及檢查拓撲關(guān)系帶來一定的困難，而且兩個編碼表都需要以人工方式建立，工作量大且容易出錯

二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第83頁。2）拓撲數(shù)據(jù)結(jié)構(gòu)拓撲型數(shù)據(jù)結(jié)構(gòu)由弧段坐標(biāo)文件、結(jié)點文件和多邊形文件等一系列含拓撲關(guān)系的數(shù)據(jù)文件組成。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第84頁。結(jié)點文件由結(jié)點記錄組成，存貯每個結(jié)點的結(jié)點號、結(jié)點坐標(biāo)及與該結(jié)點連接的弧段等弧段坐標(biāo)文件存貯組成弧段的點的坐標(biāo)弧段文件由弧記錄組成，存貯弧段的起止結(jié)點號和左右多邊形號；多邊形文件由多邊形記錄組成，存貯多邊形號、組成多邊形的弧段號以及多邊形的周長、面積、中心點坐標(biāo)。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第85頁。DIME(雙重獨立坐標(biāo)地圖編碼，DualIndependentMapEncoding)編碼系統(tǒng)

DIME是美國人口調(diào)查局在人口調(diào)查的基礎(chǔ)上發(fā)展起來的，它通過有向編碼建立了多邊形、邊界、節(jié)點之間的拓撲關(guān)系，DIME編碼成為其它拓撲編碼結(jié)構(gòu)的基礎(chǔ)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第86頁。拓撲整合的地理編碼和參考系統(tǒng)（TIGER)多邊形轉(zhuǎn)換器（POLYVRT）二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第87頁。拓撲數(shù)據(jù)結(jié)構(gòu)最重要的技術(shù)特征和貢獻是具有拓撲編輯功能。這種拓撲編輯功能，不但保證數(shù)字化原始數(shù)據(jù)的自動差錯編輯，而且可以自動形成封閉多邊形邊界，為由各個單獨存儲的弧段組成所需要的各類多邊形及建立空間數(shù)據(jù)庫奠定基礎(chǔ)。拓撲編輯功能包括多邊形編輯和結(jié)點編輯二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第88頁。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第89頁?；《翁柶瘘c終點左多邊形右多邊形a2N2N40p4a7N3N4p4p3a8N2N3p4p2弧段號起點終點左多邊形右多邊形a2N4N2p40a7N3N4p4p3a8N2N3p4p2弧段號起點終點左多邊形右多邊形a2N4N2p40a8N2N3p4p2a7N3N4p4p3N1N3N5N2N4P2P1P4P3二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第90頁。N1N3N5N2N4P2P1P4P3二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第91頁。弧段號起點終點左多邊形右多邊形a8N2N3p4p2a6N3N5p3p1a7N3N4p4p3a5N1N3p2p1弧段號起點終點左多邊形右多邊形a8N2N3p4p2a6N5N3p1p3a7N4N3p3p4a5N1N3p2p1弧段號起點終點左多邊形右多邊形a5N1N3p2p1a6N5N3p1p3a7N4N3p3p4a8N2N3p4p2二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第92頁。3）曲面數(shù)據(jù)結(jié)構(gòu)曲面是指連續(xù)分布現(xiàn)象的覆蓋表面，具有這種覆蓋表面的要素有地形、降水量、溫度、磁場等。表示和存儲這些要素的基本要求是必須便于連續(xù)現(xiàn)象在任一點的內(nèi)插計算，因此經(jīng)常采用不規(guī)則三角網(wǎng)來擬合連續(xù)分布現(xiàn)象的覆蓋表面，稱為TIN（TriangulatedIrregularNetwork）數(shù)據(jù)結(jié)構(gòu)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第93頁。這種基于TIN的曲面數(shù)據(jù)結(jié)構(gòu)，通常用于數(shù)字地形的表示，或者按照曲面要素的實測點分布，將它們連成三角網(wǎng)，三角網(wǎng)中每個三角形要求盡量接近等邊形狀，并保證由最鄰近的點構(gòu)成的三角形，即三角形的邊長之和最小。在所有可能的三角網(wǎng)中，狄洛尼（Delaunay）三角網(wǎng)在地形擬合方面表現(xiàn)最為出色。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第94頁。狄洛尼（Delaunay）三角網(wǎng)：為相互鄰接且互相不重疊的三角形的集合，每一個三角形的外接圓內(nèi)不不含其他的點。狄洛尼三角形外接圓不包含其他點的特性被用作從一系列不重合的平面點建立狄洛尼三角網(wǎng)的基本法則，可以稱為狄洛尼法則二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第95頁。34271865三角形的標(biāo)識碼相鄰三角形三角形頂點頂點坐標(biāo)和特征值?1?2?31st2st3stX1，y1，z1X2，y2，z2X3，y3，z3ABCD127ABCD二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第96頁。四、矢柵結(jié)合的數(shù)據(jù)結(jié)構(gòu)二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第97頁。有多種形式，最簡單也最實用的是不對矢量結(jié)構(gòu)數(shù)據(jù)和柵格結(jié)構(gòu)數(shù)據(jù)做任何特殊處理，直接將他們分別存儲在同一個GIS的空間數(shù)據(jù)庫系統(tǒng)中，并通過共同的ID號將各空間對象的矢量數(shù)據(jù)，柵格數(shù)據(jù)及屬性數(shù)據(jù)關(guān)聯(lián)在一起。二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第98頁。實體ID矢量數(shù)據(jù)柵格數(shù)據(jù)屬性數(shù)據(jù)缺點：矢量和柵格兩套數(shù)據(jù)均要無遺漏的在系統(tǒng)中存儲，會給系統(tǒng)的存儲空間帶來壓力二章空間數(shù)據(jù)結(jié)構(gòu)及編碼全文共110頁，當(dāng)前為第99頁。

為了解決失柵混合增加存儲空間這一問題，并更加有效的將矢量、柵格數(shù)據(jù)結(jié)構(gòu)結(jié)合