第二章GIS數(shù)據(jù)結(jié)構(gòu)作業(yè)ppt課件

1、寫出下圖的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)文件寫出下圖的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)文件55圖圖2-18）。）。ABCDOabcdefghijklmn123456789101112DIME：Dual lndependent Map Encoding，雙重對偶獨(dú)立地，雙重對偶獨(dú)立地圖編碼。圖編碼。鏈狀鏈狀DIME：是對：是對DIME的一種改進(jìn)。在的一種改進(jìn)。在DIME中，一條邊只能用直中，一條邊只能用直線兩端點(diǎn)的序號及相鄰的面域來表示，而在鏈狀線兩端點(diǎn)的序號及相鄰的面域來表示，而在鏈狀DIME中，將若干中，將若干直線段合為一個(gè)弧段或鏈段），每個(gè)弧段可以有許多中間點(diǎn)。直線段合為一個(gè)弧段或鏈段），每個(gè)弧段可以有許多中間點(diǎn)。201020

2、08矢量數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)l 用離散的點(diǎn)描述空間對象與特征，定位明顯，屬性隱含l 用拓?fù)潢P(guān)系描述空間對象之間的關(guān)系l 面向目標(biāo)操作，精度高，數(shù)據(jù)冗余度小l 與遙感等圖象數(shù)據(jù)難以結(jié)合l 輸出圖形質(zhì)量號，精度高第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008柵格數(shù)據(jù)結(jié)構(gòu)含義柵格數(shù)據(jù)結(jié)構(gòu)含義 柵格數(shù)據(jù)結(jié)構(gòu)將空間分割成有規(guī)則的網(wǎng)格，在各個(gè)網(wǎng)格上給出相應(yīng)的柵格數(shù)據(jù)結(jié)構(gòu)將空間分割成有規(guī)則的網(wǎng)格，在各個(gè)網(wǎng)格上給出相應(yīng)的屬性值來表示地理實(shí)體的一種數(shù)據(jù)組織形式。屬性值來表示地理實(shí)體的一種數(shù)據(jù)組織形式。二、柵格數(shù)據(jù)結(jié)構(gòu)二、柵格數(shù)據(jù)結(jié)構(gòu)第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型柵格結(jié)構(gòu)中空間實(shí)

3、體的表示柵格結(jié)構(gòu)中空間實(shí)體的表示點(diǎn)：由一個(gè)單元網(wǎng)格表。其數(shù)值與近鄰網(wǎng)格值明顯不同。點(diǎn)：由一個(gè)單元網(wǎng)格表。其數(shù)值與近鄰網(wǎng)格值明顯不同。線段：由一串有序的相連單元網(wǎng)格表示，每個(gè)單元最多只有兩個(gè)相鄰單元。線段：由一串有序的相連單元網(wǎng)格表示，每個(gè)單元最多只有兩個(gè)相鄰單元。各個(gè)網(wǎng)格的值比較一致，但與鄰域的值差異較大。各個(gè)網(wǎng)格的值比較一致，但與鄰域的值差異較大。多邊形：由聚集在一起的相互連接的單元網(wǎng)格組成。多邊形：由聚集在一起的相互連接的單元網(wǎng)格組成。區(qū)域內(nèi)部的網(wǎng)格值相同或差異較小，但與鄰域網(wǎng)格的值差異較大。區(qū)域內(nèi)部的網(wǎng)格值相同或差異較小，但與鄰域網(wǎng)格的值差異較大。20102008 空間實(shí)體表示示例空間實(shí)

4、體表示示例點(diǎn)實(shí)體面實(shí)體線實(shí)體點(diǎn)實(shí)體線實(shí)體線實(shí)體面實(shí)體面實(shí)體第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008特點(diǎn)：屬性明顯，定位隱含。獲取方法： (1) 手工網(wǎng)格法； (2) 掃描數(shù)字化法； (3) 分類影像輸入法； (4) 數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換法。8 8 8 88 8 8 88 8 8 88 8 8 888 8 88 8 8 88 8 88 8 888888888888 8 8881111111111111122222222222322第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008手工網(wǎng)格法手工網(wǎng)格法(透明網(wǎng)格透明網(wǎng)格)采集輸入步驟采集輸入步驟A 確定柵格單元大小

5、B 準(zhǔn)備柵格網(wǎng)C 對柵格單元進(jìn)行編碼D 讀取柵格單元值E 數(shù)據(jù)錄入第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008 1 H = (min Ai )1/2 2柵格數(shù)據(jù)的精度柵格數(shù)據(jù)的精度 在柵格數(shù)據(jù)結(jié)構(gòu)中，網(wǎng)格通常是正方形，有時(shí)也采用矩形、等邊三角形在柵格數(shù)據(jù)結(jié)構(gòu)中，網(wǎng)格通常是正方形，有時(shí)也采用矩形、等邊三角形和六邊形等，網(wǎng)格邊長決定了柵格數(shù)據(jù)的精度。和六邊形等，網(wǎng)格邊長決定了柵格數(shù)據(jù)的精度。合理的格網(wǎng)尺寸：合理的格網(wǎng)尺寸： 為研究區(qū)最小圖班的為研究區(qū)最小圖班的1/21/2長。長。*第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008A.OBC中心點(diǎn)法重要性法長度

6、占優(yōu)法面積占優(yōu)法柵格結(jié)構(gòu)數(shù)據(jù)中混合像元的處理柵格結(jié)構(gòu)數(shù)據(jù)中混合像元的處理方案一方案二：縮小柵格單元的面積第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型百分比法百分比法20102008中心點(diǎn)法中心點(diǎn)法用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼。代碼。 中心點(diǎn)法BACAAAACCAAACCCAACCCCCABCCCCBBBCCCCCCBCCC第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008柵格面積占優(yōu)法柵格面積占優(yōu)法以占柵格最大的地物類型或現(xiàn)象特征決定柵格代碼。以占柵格最大的地物類型或現(xiàn)象特征決定柵格代碼。 單位格網(wǎng)面積占優(yōu)法

7、第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008長度占優(yōu)法長度占優(yōu)法當(dāng)覆蓋的格網(wǎng)過中心部位時(shí)，橫線占據(jù)該格中的大部分長度當(dāng)覆蓋的格網(wǎng)過中心部位時(shí)，橫線占據(jù)該格中的大部分長度的屬性值定為該柵格的代碼。的屬性值定為該柵格的代碼。 單位柵格長度占優(yōu)法第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008重要性法重要性法根據(jù)柵格內(nèi)不同地物的重要性，選取最主要的地物類根據(jù)柵格內(nèi)不同地物的重要性，選取最主要的地物類型決定相應(yīng)的柵格單元代碼。對于特別重要的地理實(shí)型決定相應(yīng)的柵格單元代碼。對于特別重要的地理實(shí)體，其所在的區(qū)域盡管面積很小或不在中心，也采取體，其所在的區(qū)域盡管面積很

8、小或不在中心，也采取保留的原則，如機(jī)場、稀有金屬礦區(qū)域等。保留的原則，如機(jī)場、稀有金屬礦區(qū)域等。 重要性法BDCCBBCCBAACBAAAABC機(jī)場機(jī)場D第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008柵格數(shù)據(jù)的優(yōu)點(diǎn)柵格數(shù)據(jù)的優(yōu)點(diǎn) 地理要素表達(dá)比較直觀，直接記錄空間實(shí)體的屬性值，數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)簡地理要素表達(dá)比較直觀，直接記錄空間實(shí)體的屬性值，數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)簡單，并容易實(shí)現(xiàn)多元數(shù)據(jù)的疊合操作等。單，并容易實(shí)現(xiàn)多元數(shù)據(jù)的疊合操作等。柵格數(shù)據(jù)的缺點(diǎn)柵格數(shù)據(jù)的缺點(diǎn)數(shù)據(jù)冗余度大，造成存儲(chǔ)空間的浪費(fèi)數(shù)據(jù)冗余度大，造成存儲(chǔ)空間的浪費(fèi)像元大小的變化，對數(shù)據(jù)精度、長度、面積等的度量有較大影響像元大

9、小的變化，對數(shù)據(jù)精度、長度、面積等的度量有較大影響 。柵格結(jié)構(gòu)的主要類型柵格結(jié)構(gòu)的主要類型完全柵格結(jié)構(gòu)完全柵格結(jié)構(gòu)游程編碼結(jié)構(gòu)游程編碼結(jié)構(gòu)四叉樹數(shù)據(jù)結(jié)構(gòu)四叉樹數(shù)據(jù)結(jié)構(gòu)塊狀編碼和鏈?zhǔn)骄幋a塊狀編碼和鏈?zhǔn)骄幋a第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型201020081 1、柵格矩陣結(jié)構(gòu)、柵格矩陣結(jié)構(gòu)最簡單的一種柵格結(jié)構(gòu)，柵格數(shù)據(jù)被看作為一個(gè)距陣，逐行或最簡單的一種柵格結(jié)構(gòu)，柵格數(shù)據(jù)被看作為一個(gè)距陣，逐行或逐列記錄屬性代碼。逐列記錄屬性代碼。常用的方法是限制一個(gè)柵格只存儲(chǔ)柵格的一種屬性，并且把屬常用的方法是限制一個(gè)柵格只存儲(chǔ)柵格的一種屬性，并且把屬性限制在性限制在02550255的整數(shù)范圍內(nèi)雙

10、字節(jié)對應(yīng)一個(gè)像元）。的整數(shù)范圍內(nèi)雙字節(jié)對應(yīng)一個(gè)像元）。第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型2010200811112221113111222211331122222233312224444333122244443331222244443311112244433第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型柵格矩陣結(jié)構(gòu)柵格矩陣結(jié)構(gòu)柵格矩陣結(jié)構(gòu)特點(diǎn)柵格矩陣結(jié)構(gòu)特點(diǎn)數(shù)據(jù)存儲(chǔ)簡單，數(shù)據(jù)無壓縮，無損失。數(shù)據(jù)存儲(chǔ)簡單，數(shù)據(jù)無壓縮，無損失。數(shù)據(jù)存儲(chǔ)量大，如果每個(gè)像元用二個(gè)字節(jié)表示，存儲(chǔ)空間為：數(shù)據(jù)存儲(chǔ)量大，如果每個(gè)像元用二個(gè)字節(jié)表示，存儲(chǔ)空間為：m(m(行行) ) n( n(列列) ) (

11、 (字節(jié)字節(jié)) )。11 1 1 2 2 2 1 1 1 311 1 2 2 2 2 1 1 3 31 1 2 2 2 2 2 2 3 3 31 2 2 2 4 4 4 4 3 3 31 2 2 2 4 4 4 4 3 3 31 2 2 2 2 4 4 4 4 3 31 1 1 1 2 2 4 4 4 3 320102008 游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程編碼結(jié)構(gòu)是游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。量

12、，消除數(shù)據(jù)間的冗余。第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型2 2 游程游程( (行程、變長行程、變長) )編碼結(jié)構(gòu)編碼結(jié)構(gòu)20102008第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型1111222111311122221133112222223331222444433312224444333122224444331111224443311 11 2 2 2 111311 12 2 2 2 113311 22 2 2 2 233312 22 4 4 4 433312 22 4 4 4 433312 22 2 4 4 443311 11 2 2 4 4433(1,4), (2,3

13、), (1,3), (3,1)(1,3), (2,4), (1,2), (3,2)(1,2), (2,6), (3,3)(1,1), (2,3), (4,4), (3,3)(1,1), (2,3), (4,4), (3,3)(1,1), (4,2), (4,4), (3,2)(1,4), (2,2), (4,3), (3,2)游程編碼完全柵格編碼 游程編碼的主要規(guī)則游程編碼的主要規(guī)則有相同屬性值的鄰近像元被合有相同屬性值的鄰近像元被合并在一起稱為一個(gè)游程，游并在一起稱為一個(gè)游程，游程用一對數(shù)字表達(dá)；程用一對數(shù)字表達(dá)；每個(gè)游程對中的第一個(gè)值表示每個(gè)游程對中的第一個(gè)值表示游程屬性值游程屬性值(類別

14、類別)，第二個(gè)，第二個(gè)值表示游程長度值表示游程長度 。20102008第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型游程編碼存儲(chǔ)游程編碼存儲(chǔ)( (文件文件) )方法方法采用索引順序文件的方法來組織數(shù)據(jù)。采用索引順序文件的方法來組織數(shù)據(jù)。(1,4), (2,3), (1,3), (3,1)(1,3), (2,4), (1,2), (3,2)(1,2), (2,6), (3,3)(1,1), (2,3), (4,4), (3,3)(1,1), (2,3), (4,4), (3,3)(1,1), (4,2), (4,4), (3,2)(1,4), (2,2), (4,3), (3,2)柵格行序號

15、行游程累計(jì)數(shù)1428312416519623727游程序號編碼值，長度0011，40022，20034，30043，20241，40252，30261，30273，120102008 游程編碼結(jié)構(gòu)可以壓縮圖象存儲(chǔ)空間，壓縮效果與圖幅的屬性變化有關(guān)，圖幅屬性的變化越小，行程越長，壓縮比例越大，即壓縮比與圖的復(fù)雜程度成反比。 一般通過事先預(yù)測來估算數(shù)據(jù)的冗余度： QRe=1 m.n式中：Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和，m為圖層網(wǎng)格的行數(shù)， n為圖層網(wǎng)格的列數(shù)當(dāng) Re 1/5時(shí)，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果。第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型m*n/K 壓縮效果可由壓縮比

16、表示：式中：為流程總數(shù)圖層內(nèi)相鄰屬性值變化次數(shù)的累加和），m為圖層網(wǎng)格的行數(shù)， n為圖層網(wǎng)格的列數(shù)。壓縮比越大，表明壓縮效果越顯著。四叉樹編碼四叉樹編碼1 1、 基本思想：基本思想：將將2n2n2n2n象元組成的圖像按四個(gè)象限進(jìn)行遞歸象元組成的圖像按四個(gè)象限進(jìn)行遞歸分割，判斷屬性是否單一：分割，判斷屬性是否單一：單一：不分；不單一：遞歸分割。單一：不分；不單一：遞歸分割。最后得到一顆四分叉的倒向樹。最后得到一顆四分叉的倒向樹。一種可變分率的非均勻網(wǎng)格系統(tǒng)。是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。 AABBAABBABBBAAAB2、 四叉樹的樹形表示：四叉樹的樹形表示：用一倒立樹表示這種分割和分割

17、結(jié)果用一倒立樹表示這種分割和分割結(jié)果根根節(jié)點(diǎn)）：整個(gè)區(qū)域根根節(jié)點(diǎn)）：整個(gè)區(qū)域樹叉父結(jié)點(diǎn)）：還需分割的塊樹叉父結(jié)點(diǎn)）：還需分割的塊葉葉節(jié)點(diǎn)）：不能再分割的塊葉葉節(jié)點(diǎn)）：不能再分割的塊高：深度、分幾級，幾次分割高：深度、分幾級，幾次分割每個(gè)樹叉均有每個(gè)樹叉均有4個(gè)分叉，叫四叉樹。個(gè)分叉，叫四叉樹。SW0SE1NE3NW220102008第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型、建立四叉樹結(jié)構(gòu)的方式、建立四叉樹結(jié)構(gòu)的方式自上而下方式自上而下方式(top-down):(top-down):常規(guī)四叉樹常規(guī)四叉樹 從頂層開始，即先檢測全區(qū)域，其值不單調(diào)時(shí)再四劃分，直到數(shù)值或內(nèi)容單調(diào)從頂層開始，即

18、先檢測全區(qū)域，其值不單調(diào)時(shí)再四劃分，直到數(shù)值或內(nèi)容單調(diào)為止。為止。自下而上方式自下而上方式(bottom-up):(bottom-up):線性四叉樹線性四叉樹 從底層開始，即以像元大小為結(jié)點(diǎn)，每記錄四個(gè)結(jié)點(diǎn)時(shí)，即生成父結(jié)點(diǎn)。從底層開始，即以像元大小為結(jié)點(diǎn)，每記錄四個(gè)結(jié)點(diǎn)時(shí)，即生成父結(jié)點(diǎn)。4 4、四叉樹結(jié)構(gòu)類型、四叉樹結(jié)構(gòu)類型根據(jù)四叉樹存儲(chǔ)結(jié)構(gòu)的不同，可以將四叉樹結(jié)構(gòu)類型分為根據(jù)四叉樹存儲(chǔ)結(jié)構(gòu)的不同，可以將四叉樹結(jié)構(gòu)類型分為: : 常規(guī)四叉樹：自上而下方式常規(guī)四叉樹：自上而下方式線性四叉樹：自下而上方式線性四叉樹：自下而上方式20102008常規(guī)四叉樹編碼常規(guī)四叉樹編碼第第3 3層層第第2 2層

19、層第第1 1層層第第0 0層層根結(jié)點(diǎn)根結(jié)點(diǎn)葉結(jié)點(diǎn)葉結(jié)點(diǎn)父結(jié)點(diǎn)父結(jié)點(diǎn)（a a順序分解表示順序分解表示（b b常規(guī)四叉樹形表示常規(guī)四叉樹形表示上圖所示，圖上圖所示，圖(a)表示區(qū)域劃分的過程；圖表示區(qū)域劃分的過程；圖(b)為該區(qū)域?qū)?yīng)的常規(guī)四叉樹為該區(qū)域?qū)?yīng)的常規(guī)四叉樹0000000000000000000000000000010011111100111111001111000011110000（1 1常規(guī)四叉樹及編碼常規(guī)四叉樹及編碼20102008常規(guī)四叉樹編碼常規(guī)四叉樹編碼0000000000000000000000000000010011111100111111001111000011110

20、000162345葉結(jié)點(diǎn)編號葉結(jié)點(diǎn)編號1112 137891020102008常規(guī)四叉樹編碼常規(guī)四叉樹編碼從上例中可以看到：一幅從上例中可以看到：一幅2n 2n柵格陣列的圖用四叉樹分割時(shí)，具有的最大柵格陣列的圖用四叉樹分割時(shí)，具有的最大深度為深度為N，即可分為，即可分為0，1，2，n層。層。 如上圖如上圖n=3，具有的最大深度為，具有的最大深度為3。從四叉樹的分解過程看：被分解的圖必須為從四叉樹的分解過程看：被分解的圖必須為2n 2n 個(gè)柵格，對于不滿足個(gè)柵格，對于不滿足2n 2n的圖，在分解前需用的圖，在分解前需用0補(bǔ)足。如：；補(bǔ)足。如：；確定確定n的值，使得大于或等于行、列數(shù)中的大者，取合

21、乎要求的最小自然數(shù)的值，使得大于或等于行、列數(shù)中的大者，取合乎要求的最小自然數(shù)n。建樹時(shí)對補(bǔ)足部分生成的葉結(jié)點(diǎn)可不存儲(chǔ)，這樣存儲(chǔ)量不會(huì)增加。建樹時(shí)對補(bǔ)足部分生成的葉結(jié)點(diǎn)可不存儲(chǔ)，這樣存儲(chǔ)量不會(huì)增加。000000000001111111111111111100111100020301232021 22 2330320 3213223233220102008000000000000000000000000000001001111110011111100111100001111000010231011121330結(jié)點(diǎn)編碼結(jié)點(diǎn)編碼3132 33300301302303SW0SE1NE3NW2常規(guī)四叉樹

22、編碼常規(guī)四叉樹編碼20102008 分割一次，增加一位數(shù)字，大分割在前，小分割在后；碼的位數(shù)表示分割的次數(shù)。分割一次，增加一位數(shù)字，大分割在前，小分割在后；碼的位數(shù)表示分割的次數(shù)。 每一個(gè)位均是不大于每一個(gè)位均是不大于3 3的四進(jìn)制數(shù)表達(dá)位置，由此找出四叉樹葉結(jié)點(diǎn)的具體位置。的四進(jìn)制數(shù)表達(dá)位置，由此找出四叉樹葉結(jié)點(diǎn)的具體位置。完全柵格結(jié)構(gòu)掃描順序示意圖完全柵格結(jié)構(gòu)掃描順序示意圖 SW0SE1NE3NW22002003003000220220230230320320330330200200210210300300310310020020030030120120130130000000010010

23、10010011011100100常規(guī)四叉樹編碼常規(guī)四叉樹編碼20102008常規(guī)四叉樹編碼常規(guī)四叉樹編碼01231011121312012112212320102008常規(guī)四叉樹編碼常規(guī)四叉樹編碼012310111213120121122123常規(guī)四叉樹的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)特點(diǎn)常規(guī)四叉樹的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)特點(diǎn)在常規(guī)四叉樹的數(shù)據(jù)存儲(chǔ)時(shí)，每個(gè)結(jié)點(diǎn)需要六個(gè)變量加以表達(dá)：一個(gè)變量表示父結(jié)點(diǎn)指針?biāo)膫€(gè)變量代表四個(gè)子結(jié)點(diǎn)指針一個(gè)變量代表結(jié)點(diǎn)的灰度或?qū)傩灾怠?l指針不僅增加了數(shù)據(jù)的存儲(chǔ)量，還增加了操作的復(fù)雜性：l如層次數(shù)分割次數(shù)由從父結(jié)點(diǎn)移到根結(jié)點(diǎn)的次數(shù)來確定，結(jié)點(diǎn)所代表的圖像塊的位置需要從根節(jié)點(diǎn)開始逐步推算下來。l

24、常規(guī)四叉樹并不廣泛用于存儲(chǔ)數(shù)據(jù)，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。特點(diǎn)及意義特點(diǎn)及意義20102008線性四叉樹編碼線性四叉樹編碼（2 2線性四叉樹線性四叉樹n它不存儲(chǔ)樹中結(jié)點(diǎn)的關(guān)系，只是通過編碼四叉樹的葉結(jié)點(diǎn)，表示數(shù)據(jù)塊的層次和空間關(guān)系。 每個(gè)葉結(jié)點(diǎn)都具有一個(gè)反映位置的關(guān)鍵字，該關(guān)鍵字的碼也稱為位置碼，以表示它所處的位置。n記錄葉結(jié)點(diǎn)的地址碼定位碼、Morton碼和屬性。n 四進(jìn)制、十進(jìn)制n 深度、幾次分割n優(yōu)點(diǎn)：優(yōu)點(diǎn)：(1)(1)只存儲(chǔ)三個(gè)值，比常規(guī)四叉樹節(jié)省存儲(chǔ)空間；只存儲(chǔ)三個(gè)值，比常規(guī)四叉樹節(jié)省存儲(chǔ)空間；(2)(2)由于記錄節(jié)點(diǎn)地址，既能直接找到其在四叉樹中的走向路徑，由于記錄節(jié)點(diǎn)

25、地址，既能直接找到其在四叉樹中的走向路徑，又可以換算出它在整個(gè)柵格區(qū)域內(nèi)的行列位置；又可以換算出它在整個(gè)柵格區(qū)域內(nèi)的行列位置；(3)(3)壓縮和解壓縮比較方便，各部分的分辨率可不同，既可精確地壓縮和解壓縮比較方便，各部分的分辨率可不同，既可精確地表示圖形結(jié)構(gòu)，又可減少存儲(chǔ)量，易于進(jìn)行大部分圖形操作和運(yùn)算。表示圖形結(jié)構(gòu)，又可減少存儲(chǔ)量，易于進(jìn)行大部分圖形操作和運(yùn)算。地址碼20102008線性四叉樹編碼線性四叉樹編碼101023111213303132 33300301302303MDMQSizeValue004*4124122*21493011*1100000000000000000000000

26、00000010011111100111111001111000011110000線性四叉樹線性四叉樹20102008 線性四叉樹進(jìn)行四進(jìn)制編碼葉結(jié)點(diǎn)位置采用基于四進(jìn)制的Morton碼表示，這種編碼由加拿大學(xué)者M(jìn)orton于1966年提出，稱Morton碼或Peano鍵，四進(jìn)制的Morton碼又稱為MQ碼。 MQ碼是一串?dāng)?shù)字組成，每分割一次增加一位數(shù)，其中每位數(shù)字都是不大于3的四進(jìn)制數(shù)。 以行為序，以左下角為起點(diǎn)，按從左到右，從下到上的順序進(jìn)行編碼四進(jìn)制線性四叉樹編碼(MQ碼)76543210？20030002202303203302002103003100200301201310210300

27、0001010011100101MQ000 001 010 011 100 101 110 111編碼表編碼表20102008MQ編碼計(jì)算方法編碼計(jì)算方法1：四叉樹從上而下構(gòu)成）四叉樹從上而下構(gòu)成）（從整體開始由葉結(jié)點(diǎn)找（從整體開始由葉結(jié)點(diǎn)找Morton碼。碼。 A、分割一次，增加一位、分割一次，增加一位數(shù)字，大分割在前，小分割數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示在后。所以，碼的位數(shù)表示分割的次數(shù)。分割的次數(shù)。 B、每一個(gè)位均是不大于、每一個(gè)位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。的四進(jìn)制數(shù)，表達(dá)位置。由由Morton找出四叉樹葉結(jié)找出四叉樹葉結(jié)點(diǎn)的具體位置。點(diǎn)的具體位置。 2301A

28、AA BAAA A AAB BA A四進(jìn)制線性四叉樹編碼(MQ碼)20102008四進(jìn)制線性四叉樹編碼(MQ碼)MQ編碼計(jì)算方法:四叉樹自下而上合并的方法MQ = 2IB+JB （IB、JB分別為柵格單元行列號的二進(jìn)制數(shù)，其始行列號從0計(jì)。P55圖2-18） 如：已知十進(jìn)制第一行、第五列的柵格單元，求它的MQ碼。首先將十進(jìn)制第一行、第五列轉(zhuǎn)成二進(jìn)制形式，得到 行Ib =(001) 列Jb =(101)其地址碼為: MQ = 2Ib+Jb = 21+101 = 103例例:求求256*256第第20行，第行，第200列的列的?11021200表示表示？2003000220230320330200

29、2103003100200301201310210300000101001110010120102008 圖(a)所示為88列圖，即柵格單元2323，其位置碼的最長位數(shù)是3位。 現(xiàn)對圖 (a)按MQ碼的編碼表，依次檢查每四個(gè)相鄰的MQ對應(yīng)的屬性值，相同合并不同碼位去掉），不同則存盤,直到?jīng)]有能夠合并的子塊為止。然后進(jìn)行排序歸并得到圖 (b) MQ碼。最后再寫成四進(jìn)制線性四叉樹。四進(jìn)制線性四叉樹編碼(MQ碼)00000000000000000000000000000100111111001111110011110000111100002323330230331300301012131011a.區(qū)

30、域柵格表示b.區(qū)域MQ碼MQSizeValue04*41122*213011*11四進(jìn)制四進(jìn)制線性四叉樹線性四叉樹20102008時(shí)間時(shí)間圖像16464圖像2128128圖像3256256自下而上方法1.20s4.23s26.8s自上而下方法1.42s8.42s2min30.2s方法方法圖像大小圖像大小兩種建立四叉樹方法效率的比較兩種建立四叉樹方法效率的比較常規(guī)四叉樹：自上而下方法線性四叉樹：自下而上方法20102008l四進(jìn)制Morton碼直觀上切合四叉樹分割，但許多語言不支持四進(jìn)制變量，需用十進(jìn)制表示Morton碼。l線性四叉樹的十進(jìn)制編碼簡稱MD編碼，它同線性四叉樹的四進(jìn)制編碼主要不同在

31、于編碼值是十進(jìn)制自然數(shù)，其合并過程可直接按自然數(shù)順序進(jìn)行。十進(jìn)制線性四叉樹編碼(M碼)A 10A 11A 14A 15A 8 B 9B 12B 13A 2A 3B 6B 7A 0A 1B 4B 542424343464647475858595962626363404041414444454556565757606061613434353538383939505051515454555532323333363637374848494952525353101011111414151526262727303031318 89 91212131324242525282829292 23 36 67 7

32、18181919222223230 01 14 45 5161617172020212120102008 像元順序以行為序，以左下角為起點(diǎn)，按從左到右，從下到上的順序掃描。 掃描柵格單元的順序代碼稱為十進(jìn)制莫頓碼(Morton碼)或Peano鍵。完全柵格結(jié)構(gòu)掃描順序示意圖完全柵格結(jié)構(gòu)掃描順序示意圖 （圖（圖2 22121）SW0SE1NE3NW2424243434646474758585959626263634040414144444545565657576060616134343535383839395050515154545555323233333636373748484949525253

33、53101011111414151526262727303031318 89 91212131324242525282829292 23 36 67 718181919222223230 01 14 45 51616171720202121十進(jìn)制線性四叉樹編碼(M碼)20102008十進(jìn)制線性四叉樹編碼(M碼)方法：按位操作的方法方法：按位操作的方法如行為如行為2 2、列為、列為3 3的柵格的的柵格的MDMD步驟：步驟：(1)(1)行、列號為二進(jìn)制：行、列號為二進(jìn)制： IB= 1 0 JB= 1 1IB= 1 0 JB= 1 1(2)I(2)I行行J J列交叉列交叉 ： 1 1 0 1 = 1

34、31 1 0 1 = 13(3)(3)再化為十進(jìn)制再化為十進(jìn)制. . 例例:求求256*256第第20行，第行，第200列的列的D?如行為20、列為200的柵格的MD步驟：(1)行、列號為二進(jìn)制： IB= 10100 JB= 11001000 二進(jìn)制計(jì)算(2)I行J列交叉 ：0101001001100000 = 21088 附件計(jì)算器(3)再化為十進(jìn)制. 10111415 8912132 367014520102008M與MQMDMQSizeValue004*4124122*21493011*113010220230320330200210300311200020030120130000010

35、1001142424343464647475858595962626363404041414444454556565757606061613434353538383939505051515454555532323333363637374848494952525353101011111414151526262727303031318 89 91212131324242525282829292 23 36 67 718181919222223230 01 14 45 5161617172020212120102008線性四叉樹編碼的優(yōu)點(diǎn)(1)只存儲(chǔ)三個(gè)值，比常規(guī)四叉樹節(jié)省存儲(chǔ)空間；(2)由于記錄節(jié)

36、點(diǎn)地址，既能直接找到其在四叉樹中的走向路徑，又可以換算出它在整個(gè)柵格區(qū)域內(nèi)的行列位置；(3)壓縮和解壓縮比較方便，各部分的分辨率可不同，既可精確地表示圖形結(jié)構(gòu)，又可減少存儲(chǔ)量，易于進(jìn)行大部分圖形操作和運(yùn)算。20102008.寫出下圖的四叉樹結(jié)構(gòu)文件57圖2-20）0 0 0 0 0 00 0 0 0 0 11 1 1 1 1 11 1 1 1 1 11 1 1 1 0 01 1 1 1 0 0000000000001111111111111111100111100020301232021 222330320 32132232332MDMQSizeValue80202*21120302*2132

37、2002*21362102*21483002*21573211*11?補(bǔ)原則補(bǔ)原則?能使四叉樹最簡單能使四叉樹最簡單201020082.寫出下圖的四叉樹結(jié)構(gòu)文件寫出下圖的四叉樹結(jié)構(gòu)文件55圖圖2-18右圖）。右圖）。201020082.寫出下圖的四叉樹結(jié)構(gòu)文件寫出下圖的四叉樹結(jié)構(gòu)文件55圖圖2-18右圖）。右圖）。1141111121151131100123031320030310115113114112110111MDMQSizeValueMDMQSizeValue0002*21151002*21130102*21131102*21120202*21151201*11130301*11141

38、211*11120311*11131221*11120321*11141231*11120331*11141301*11101311*11121321*11121331*11120123031320030310115113114112110111MDMQSizeValueMDMQSizeValue2001*11153002*21122011*11153101*11122021*11143111*11122031*11143121*11112102*21143131*11112202*21143201*11122302*21143211*11113221*11113231*11113302*21

39、11MDMQSizeValueMDMQSizeValue0002*21152001*11150102*21132011*11150202*21152021*11140301*11142031*11140311*1113212*21140321*1114222*21140331*1114232*21141002*2113302*21121102*21123101*11121201*11133111*11121211*11123121*11111221*11123131*11111231*11123201*11121301*11103211*11111311*11123221*11111321*1

40、1123231*11111331*1112332*2111線性四叉樹編碼線性四叉樹編碼MDMQValue000115010113020115030114031113032114100113110112120113121112130110131112200115202114300112312111320112321111線性四叉樹游程編碼線性四叉樹游程編碼（二維行程編碼表）（二維行程編碼表）MDMQValue00011501011302011503011403111303211410011311011212011312111213011013111220011520211430011231211

41、1320112321111MDMQSizeValue80202*21120302*21322002*21362102*21483002*21573211*11線性四叉樹游程編碼線性四叉樹游程編碼（二維行程編碼表）（二維行程編碼表）上表不能用上表不能用線性四叉樹游程編碼表示，線性四叉樹游程編碼表示，因?yàn)閷傩詻]有表示。因?yàn)閷傩詻]有表示。帶指針的二維行程表帶指針的二維行程表MDMQValue0001150101130201150301140311130321141001131101121201131211121301101311122001152021143001123121113201123211

42、11MDMQValue000020(指針)010031(指針)020200(指針)030032(指針)031100(指針)032202(指針)100120(指針)110121(指針)120113(屬性值)121131(指針)130110(屬性值)131300(指針)200115(屬性值)202114(屬性值)300320(指針)312312(指針)320112(屬性值)321111(屬性值)線性四叉樹游程編碼線性四叉樹游程編碼（二維行程編碼表）（二維行程編碼表）20102008用循環(huán)指針將同屬于一個(gè)目標(biāo)的葉結(jié)點(diǎn)鏈接起來：用循環(huán)指針將同屬于一個(gè)目標(biāo)的葉結(jié)點(diǎn)鏈接起來：只要進(jìn)入第一塊就可以順著指針直

43、接提取該地物的所有子塊，從而只要進(jìn)入第一塊就可以順著指針直接提取該地物的所有子塊，從而避免像柵格數(shù)據(jù)那樣為查詢某一個(gè)目標(biāo)需遍歷整個(gè)矩陣，避免像柵格數(shù)據(jù)那樣為查詢某一個(gè)目標(biāo)需遍歷整個(gè)矩陣，大大提高了查詢速度大大提高了查詢速度08324046帶指針的二維行程表帶指針的二維行程表20102008帶指針的二維行程表帶指針的二維行程表二維行程二維行程M碼碼 屬性值屬性值005480164308314320378400448460478二維行程二維行程M碼碼循環(huán)指針屬性值循環(huán)指針屬性值0851683216313037314屬性值）屬性值）3240374440464447460屬性值）屬性值）478屬性值）

44、屬性值）循環(huán)指針指向該地物下一個(gè)子塊的地址碼，并在最后指向該地物本身循環(huán)指針指向該地物下一個(gè)子塊的地址碼，并在最后指向該地物本身 201020083 3塊碼塊碼-游程編碼向二維擴(kuò)展游程編碼向二維擴(kuò)展l采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格。l數(shù)據(jù)對組成：初始行、列，半徑，屬性值l依次掃描，編過的不重復(fù)。特點(diǎn)：特點(diǎn)：具有可變分辨率。即當(dāng)屬性變化小時(shí)圖塊大，對于大塊圖斑記錄單元大，分辨率具有可變分辨率。即當(dāng)屬性變化小時(shí)圖塊大，對于大塊圖斑記錄單元大，分辨率低，壓縮比高。低，壓縮比高。 小塊圖斑記錄單元小，分辨率高，壓縮比低。小塊圖斑記錄單元小，分辨率高，壓縮比低。因此，與行程編碼

45、類似，隨圖形復(fù)雜程度的提高而降低分辯率。因此，與行程編碼類似，隨圖形復(fù)雜程度的提高而降低分辯率。8 0 4 4 7 7 7 7 77 4 4 4 4 4 7 7 76 4 4 4 4 8 8 7 7 5 0 0 4 8 8 8 7 74 0 0 8 8 8 8 7 83 0 0 0 8 8 8 8 82 0 0 0 0 8 8 8 81 0 0 0 0 0 8 8 8 1 2 3 4 5 6 7 8 如：（1,1,0,3),(1,4,1,0),(1,5,1,0),(1,6,3,8)(2,4,1,0),(2,5,1,8),(3,4,2,8),(4,1.)第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)

46、構(gòu)的類型201020080 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，3 3，0 0），（），（1 1，4 4，1 1，0 0），），（1 1，5 5，1 1，0 0），（），（1 1，6 6，3 3，3 3），），（2 2，4 4，1 1，0 0），（），（2 2，5 5，1 1，3 3）；）；（3 3，4 4，2 2，3 3），（），（4 4，1 1，2 2，0 0），），（4 4

47、，3 3，1 1，3 3），（），（4 4，6 6，1 1，3 3）；）；（4 4，7 7，1 1，5 5），（），（4 4，8 8，1 1，3 3），），（5 5，3 3，1 1，2 2），（），（5 5，4 4，1 1，3 3）；）；（5 5，5 5，2 2，3 3），（），（5 5，7 7，2 2，5 5），），（6 6，1 1，1 1，2 2）；（）；（6 6，2 2，1 1，2 2），），（6 6，3 3，1 1，2 2），（），（6 6，4 4，1 1，2 2），），（7 7，1 1，1 1，2 2），（），（7 7，2 2，2 2，2 2）；）；（7 7，4 4，1 1，2 2）

48、，（），（7 7，5 5，1 1，2 2）；）；（7 7，6 6，2 2，5 5），（），（7 7，8 8，1 1，5 5）；）；（8 8，1 1，1 1，0 0），（），（8 8，4 4，1 1，5 5）；）；（8 8，5 5，1 1，5 5），（），（8 8，8 8，1 1，5 5）；）； 第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型201020084 4 鏈?zhǔn)骄幋a或鏈?zhǔn)骄幋a或Freeman (Freeman (弗里曼弗里曼) )鏈碼或邊界鏈碼鏈碼或邊界鏈碼將柵格數(shù)據(jù)線狀地物、面域邊界表示為矢量鏈的記錄。編輯方法：首先定義一個(gè)3x3窗口，中間柵格的走向有8種可能，并將這8種可能07進(jìn)

49、行編碼；再記下地物屬性碼和起點(diǎn)行、列后，進(jìn)行追蹤，得到矢量鏈表。aaaaaaab屬性碼起點(diǎn)行起點(diǎn)列鏈碼鏈碼a84556656b57576654323 優(yōu)點(diǎn)：鏈碼可有效地存貯壓縮柵格數(shù)據(jù)，便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計(jì)算。優(yōu)點(diǎn)：鏈碼可有效地存貯壓縮柵格數(shù)據(jù)，便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計(jì)算。 缺陷：不易做邊界合并，插入操作、編輯較困難對局部修改將改變整體結(jié)構(gòu)）。區(qū)域空間分析困缺陷：不易做邊界合并，插入操作、編輯較困難對局部修改將改變整體結(jié)構(gòu)）。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲(chǔ)。難，相鄰區(qū)域邊界被重復(fù)存儲(chǔ)。 第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型

50、20102008p直接?xùn)鸥窬幋a：直接?xùn)鸥窬幋a：p簡單直觀，是壓縮編碼方法的邏輯原型柵格文件）；簡單直觀，是壓縮編碼方法的邏輯原型柵格文件）；p游程長度編碼：游程長度編碼：p在很大程度上壓縮數(shù)據(jù)，又最大限度的保留了原始柵格結(jié)構(gòu)，編在很大程度上壓縮數(shù)據(jù)，又最大限度的保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易，十分適合于微機(jī)地理信息系統(tǒng)采用；碼解碼十分容易，十分適合于微機(jī)地理信息系統(tǒng)采用；p鏈碼：壓縮效率較高，以接近矢量結(jié)構(gòu)，對邊界的運(yùn)算比較方便，鏈碼：壓縮效率較高，以接近矢量結(jié)構(gòu)，對邊界的運(yùn)算比較方便，但不具有區(qū)域性質(zhì)，區(qū)域運(yùn)算較難；但不具有區(qū)域性質(zhì)，區(qū)域運(yùn)算較難；p塊碼和四叉樹編碼：具有區(qū)域性質(zhì)，又具

51、有可變的分辨率，有較塊碼和四叉樹編碼：具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，四叉樹編碼可以直接進(jìn)行大量圖形圖象運(yùn)算，效率高的壓縮效率，四叉樹編碼可以直接進(jìn)行大量圖形圖象運(yùn)算，效率較高，是很有前途的編碼方法。較高，是很有前途的編碼方法。第三節(jié)第三節(jié) 空間數(shù)據(jù)結(jié)構(gòu)的類型空間數(shù)據(jù)結(jié)構(gòu)的類型20102008矢量與柵格數(shù)據(jù)結(jié)構(gòu)的比較80優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)矢矢量量數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)1便于面向現(xiàn)象(土壤類、土地利用單元等)的數(shù)據(jù)表示2數(shù)據(jù)結(jié)構(gòu)緊湊、冗余度低,便于描述線或邊界。3有利于網(wǎng)絡(luò)、檢索分析，提供有效的拓?fù)渚幋a，對需要拓?fù)湫畔⒌牟僮鞲行А?圖形顯示質(zhì)量好、精度高1數(shù)據(jù)結(jié)構(gòu)復(fù)雜，各自定義，不

52、便于數(shù)據(jù)標(biāo)準(zhǔn)化和規(guī)范化，數(shù)據(jù)交換困難。2多邊形疊合分析比較困難, ，沒有柵格有效，表達(dá)空間變化性能力差。 3不能像數(shù)字圖像那樣做增強(qiáng)處理4軟件與硬件的技術(shù)要求比較高,顯示與繪圖成本比較柵柵格格數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)1數(shù)據(jù)結(jié)構(gòu)簡單，易數(shù)據(jù)交換2空間分析和地理現(xiàn)象的模擬均比較容易3有利于與遙感數(shù)據(jù)的匹配應(yīng)用和分析4輸出方法快速，成本比較低廉1現(xiàn)象識別的效果不如矢量方法,難以表達(dá)拓?fù)洹?投影轉(zhuǎn)換比較困難3圖形數(shù)據(jù)量大,數(shù)據(jù)結(jié)構(gòu)不嚴(yán)密不緊湊，需用壓縮技術(shù)解決該問題4柵格地圖的圖形質(zhì)量比較低，圖形輸出不美觀，線條有鋸齒，需用增加?xùn)鸥駭?shù)量來克服，但會(huì)增加數(shù)據(jù)文件。20102008矢量與柵格數(shù)據(jù)結(jié)構(gòu)的選擇 在在GIS建立過程中，應(yīng)根據(jù)應(yīng)用目的和應(yīng)用特點(diǎn)、可能獲得的數(shù)據(jù)建立過程中，應(yīng)根據(jù)應(yīng)用目的和應(yīng)用特點(diǎn)、可能獲得的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件配置情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)。精度以及地理信息系統(tǒng)軟件和硬件配