45柵格數(shù)據(jù)結(jié)構(gòu)

第四章空間數(shù)據(jù)的表達(dá)§4-4矢量數(shù)據(jù)結(jié)構(gòu)(重點(diǎn)、難點(diǎn))§4-5柵格數(shù)據(jù)結(jié)構(gòu)(重點(diǎn)、難點(diǎn))§4-6混合數(shù)據(jù)結(jié)構(gòu)和一體化數(shù)據(jù)結(jié)構(gòu)(重點(diǎn)、難點(diǎn))§5-8柵格與矢量數(shù)據(jù)結(jié)構(gòu)的選擇與轉(zhuǎn)換(重點(diǎn)、難點(diǎn))休息按“ESC”鍵返回45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第1頁。GIS空間數(shù)據(jù)結(jié)構(gòu)分類示意圖隨著GIS技術(shù)的發(fā)展，空間數(shù)據(jù)結(jié)構(gòu)有了新的內(nèi)容(張超)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第2頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)本節(jié)重點(diǎn)：

柵格數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)及各種數(shù)據(jù)編碼的特點(diǎn)。四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。(P102-113)本節(jié)難點(diǎn)：

四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第3頁。1.敘述四種柵格數(shù)據(jù)存儲(chǔ)的壓縮編碼方法。（2001武大）作業(yè)45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第4頁。思考題1.采用十進(jìn)制Morton碼分別用線性四叉樹和二維行程編碼表示下圖。（2000武大）ABBBAABBBAABBBAA45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第5頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)(P92)返回休息

基于柵格模型的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)稱為柵格數(shù)據(jù)結(jié)構(gòu),指將空間分割成有規(guī)則的網(wǎng)格,在各個(gè)網(wǎng)格上給出相應(yīng)的屬性值來表示地理實(shí)體的一種數(shù)據(jù)組織形式。45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第6頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第7頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)三、空間目標(biāo)的分層表示方法(P93)

在柵格文件中，每個(gè)柵格只能賦予唯一的值，因此，某一個(gè)柵格若有不同的值，則要分別存貯于不同的文件。例如，對(duì)于某個(gè)區(qū)域來說，其土壤和森林覆蓋類型就要分別存貯為土壤和森林?jǐn)?shù)據(jù)文件。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第8頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)三、空間目標(biāo)的分層表示方法

可以有三種可能的數(shù)據(jù)組織方法：

a、以象元為記錄的序列。不同層上同一象元位置上的不同屬性值表示為一個(gè)列數(shù)組；

b、以層為基礎(chǔ)，每一層又以象元為序記錄它的坐標(biāo)和屬性值，每一層記錄后再記錄下一層；

c、以層為基礎(chǔ)，但每一層則以多邊形為序記錄多邊形的屬性值和充滿多邊形的各象元的坐標(biāo)。

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第9頁。地理信息系統(tǒng)原理三、空間目標(biāo)的分層表示方法

45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第10頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)三、空間目標(biāo)的分層表示方法

上述三種方法中：①節(jié)省了許多存儲(chǔ)空間，因?yàn)镹層實(shí)際上只存儲(chǔ)了一層的象元坐標(biāo)；方法③節(jié)省了許多用于存儲(chǔ)屬性值的空間，同一屬性的制圖單元的幾個(gè)象元排列在一起，使地圖分析和制圖處理較為方便；方法②每層每個(gè)象元一一記錄，它的形式最為簡(jiǎn)單。

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第11頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)

在柵格單元中每個(gè)代碼本身明確地代表了實(shí)體的屬性或?qū)傩缘木幋a。四、特點(diǎn)

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第12頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)五、決定柵格單元代碼的方法

通常在一個(gè)柵格單元上會(huì)對(duì)應(yīng)幾種不同的屬性值，而每一個(gè)單元只能取一個(gè)值，為了盡量保持地表的真實(shí)性，保證最大的信息容量。在這種情況下有不同的取值方法：中心點(diǎn)法、面積占優(yōu)法、重要性法、百分比法。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第13頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)五、決定柵格單元代碼的方法

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第14頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)五、決定柵格單元代碼的方法

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第15頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)五、決定柵格單元代碼的方法

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第16頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)五、決定柵格單元代碼的方法

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第17頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第18頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第19頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第20頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第21頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)分辨率與存儲(chǔ)單元示意圖

(1)在高分辨率的情況下將占據(jù)更多的像元或存儲(chǔ)單元；(2)柵格模型是通過同樣顏色或灰度像元來表達(dá)具有相同屬性的面狀區(qū)域的。因此有許多柵格單元或像元與其鄰近的若干像元都具有相同的屬性值。為了節(jié)省存儲(chǔ)空間，對(duì)柵格數(shù)據(jù)進(jìn)行壓縮。下面，將介紹四種常用的數(shù)據(jù)壓縮方法。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第22頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第23頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第24頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第25頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第26頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第27頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)

對(duì)下一圖像的塊狀編碼如下：(1,1,1,0)，(1,2,2,4)，(1,4,1,7)……返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第28頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第29頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第30頁。四叉樹編碼分為：(P102-113)

（1）常規(guī)四叉樹編碼（2）線性四叉樹編碼§4-5柵格數(shù)據(jù)結(jié)構(gòu)45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第31頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)常規(guī)四叉樹編碼常規(guī)四叉樹的生成方法有兩種：(1)自頂向下(top-down)的分割方法:先檢查全區(qū)域，內(nèi)容不完全相同再四分割，往下逐次遞歸。(2)從底向上(down-top)的合并方法：首先對(duì)柵格數(shù)據(jù)按一定的順序檢查四個(gè)相鄰柵格單元的屬性值，如果相同，則進(jìn)行合并，逐次往上遞歸。

返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第32頁。常規(guī)四叉樹編碼的過程返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第33頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)常規(guī)四叉樹編碼常規(guī)四叉樹的特點(diǎn)如下：(1)運(yùn)算量較大。因?yàn)?，大量?shù)據(jù)需要重復(fù)檢查才能確定劃分；（如7、8、9、10等格網(wǎng)需要檢查4次）(2)占用的存儲(chǔ)空間較大。每個(gè)結(jié)點(diǎn)需要六個(gè)變量才能加以表達(dá)：一個(gè)變量表示父結(jié)點(diǎn)指針，四個(gè)變量代表四個(gè)子結(jié)點(diǎn)指針，一個(gè)變量代表本結(jié)點(diǎn)的灰度或?qū)傩灾?。返回休?5柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第34頁。§4-5柵格數(shù)據(jù)結(jié)構(gòu)線性四叉樹編碼：

為了克服常規(guī)四叉樹占用存儲(chǔ)空間大的缺點(diǎn)，人們提出了線性四叉樹的算法。線性四叉樹只存儲(chǔ)最后葉結(jié)點(diǎn)的信息，即結(jié)點(diǎn)的位置、大小和灰度。葉結(jié)點(diǎn)位置采用基于四進(jìn)制或十進(jìn)制的Morton碼表示（加拿大學(xué)者M(jìn)orton于1966年提出）；葉結(jié)點(diǎn)的大小用結(jié)點(diǎn)的深度或?qū)哟伪硎?。Morton碼又稱為M碼。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第35頁。M碼的特點(diǎn)：1、每一位字?jǐn)?shù)都是不大于3的四進(jìn)制數(shù)；2、每經(jīng)過一次分割，增加一位數(shù)字；3、分割的次數(shù)越多，所得的子區(qū)域越小，相應(yīng)的Morton碼位數(shù)越大；45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第36頁。（一）基于四進(jìn)制的Morton碼步驟:1)將十進(jìn)制的行列號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)

2)按MQ碼的計(jì)算公式MQ=計(jì)算對(duì)應(yīng)的MQ碼

分別為柵格單元行列號(hào)的二進(jìn)制數(shù)。下表為8行8列研究區(qū)域的基于四進(jìn)制的MQ碼計(jì)算成果。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第37頁。例如：45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第38頁。線性四叉樹編碼在MQ碼的基礎(chǔ)上生成線性四叉樹的方法有兩種：(1)自頂向下(top-down)的分割方法:按常規(guī)四叉樹的方法進(jìn)行，并直接生成M碼；(2)從底向上(down-top)的合并方法：首先按MQ碼的升序排列方式依次檢查四個(gè)相鄰M碼對(duì)應(yīng)的屬性值，如果相同，則合并為一個(gè)大塊，否則，存儲(chǔ)四個(gè)格網(wǎng)的參數(shù)值（MQ碼、深度、屬性值）。第一輪合并完成后，再依次檢查四個(gè)大塊的值（此時(shí)，僅需檢查每個(gè)大塊中的第一個(gè)值），若其中有一個(gè)值不同或某子塊已存儲(chǔ)，則不作合并而記盤。通過上述方法，直到?jīng)]有能夠合并的子塊為止。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第39頁。自上而下的線性四叉樹編碼過程返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第40頁。（二）基于十進(jìn)制的Morton碼

方法1:將四進(jìn)制的MQ碼轉(zhuǎn)換成十進(jìn)制的MD例如：45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第41頁。（二）基于十進(jìn)制的Morton碼

方法2:按位操作步驟:1)將十進(jìn)制的行列號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)

2)行列交叉得到二進(jìn)制的Morton碼

3)將二進(jìn)制的Morton碼轉(zhuǎn)換成十進(jìn)制的Morton碼45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第42頁。（二）基于十進(jìn)制的Morton碼

例如：已知行列號(hào)I=5,J=7，求十進(jìn)制的Morton碼

45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第43頁?！?-5柵格數(shù)據(jù)結(jié)構(gòu)四叉樹編碼的優(yōu)點(diǎn)：1）陣列各部分的分辯率是可變的，邊界復(fù)雜部分四叉樹較高即分級(jí)多，分辯率也高，而不需表示許多細(xì)節(jié)的部分則分級(jí)少，分辯率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量；2）柵格到四叉樹及四叉樹到簡(jiǎn)單柵格結(jié)構(gòu)的轉(zhuǎn)換比其它壓縮方法容易，由于記錄結(jié)點(diǎn)地址，能直接在四叉樹中的走向路徑，也可以換算出它在整個(gè)柵格區(qū)域中行列位置；返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第44頁。二維行程編碼(P111)

在生成的線性四叉樹中，仍存在前后葉結(jié)點(diǎn)的值相同的情況，因而可以采取進(jìn)一步的壓縮表達(dá)，即將格網(wǎng)值相同的前后結(jié)點(diǎn)合并成一個(gè)值，即得到二維行程編碼。這種二維行程編碼利用了線性四叉樹的地址碼，但沒有結(jié)構(gòu)規(guī)則的四叉樹，甚至已失去了四叉樹的概念。然而它比規(guī)則的四叉樹更省存儲(chǔ)空間，而且對(duì)以后的插入、刪除和修改等操作，因不必保持完整的四叉樹構(gòu)形而變得相當(dāng)簡(jiǎn)便。返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第45頁。二維行程編碼返回休息45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第46頁。八叉樹數(shù)據(jù)結(jié)構(gòu)(P115)

八叉樹數(shù)據(jù)結(jié)構(gòu)是從四叉樹數(shù)據(jù)結(jié)構(gòu)直接發(fā)展而來的，其原理是將空間區(qū)域不斷地分解為八個(gè)同樣大小的子區(qū)域（即將一個(gè)六面的立方體分解為八個(gè)相同的大小的小立方體）分解的次數(shù)越多，子區(qū)域就越小，一直到同一區(qū)域的屬性單一為止。45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第47頁。

按從上到下合并的方式來說，就是將研究區(qū)域先按一定的分辨率將三維空間劃分為三維柵格網(wǎng)格，然后按規(guī)定的順序每次比較八個(gè)相鄰的柵格單元，如果其屬性值相同則合并，否則就記盤，依次遞歸運(yùn)算，直到每個(gè)子區(qū)域均為單值為止。45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第48頁。

八叉樹同樣分為常規(guī)八叉樹和線性八叉樹，常規(guī)八叉樹的結(jié)點(diǎn)要記錄十個(gè)值，即八個(gè)指向子節(jié)點(diǎn)的指針，一個(gè)指向父結(jié)點(diǎn)的指針和一個(gè)屬性值。而線性八叉樹只需記錄葉結(jié)點(diǎn)的地址碼和屬性值。45柵格數(shù)據(jù)結(jié)構(gòu)全文共51頁，當(dāng)前為第49頁。

八叉樹的構(gòu)成方法亦可按線性四叉樹的構(gòu)造原理。首先計(jì)算擴(kuò)展的Morton碼，將二維自變量I，J擴(kuò)展為三維自