【正文】 3 4 5 6 7 Jb 00 01 10 11 100 101 110 111 II Ib 0 00 000 001 010 011 100 101 110 111 1 01 002 003 012 013 102 103 112 113 2 10 020 021 030 031 120 121 130 131 3 11 022 023 032 033 122 123 132 133 4 100 200 201 210 211 300 301 310 311 5 101 202 203 212 213 302 303 312 313 6 110 220 221 230 231 320 321 330 331 7 111 222 223 232 233 322 323 332 333 第二章 地 圖 數(shù) 據 結 構 81 第三步，在排好的線性表中，依次檢查每四個相鄰 MQ碼對應的屬性值，如果相同則合并為一個大塊，否則將這四個格網記錄下來，內容包括 MQ碼、屬性值。 第二章 地 圖 數(shù) 據 結 構 79 基于四進制的 Morton碼 (MQ)及四叉樹的建立 第一步：將十進制的行列號（ II， JJ）轉換成二進制數(shù)（ Ib,Jb）表示。 線性四叉樹葉結點的編號需要遵照一定的規(guī)則，這種編號稱為地址碼，隱含了葉結點的位置信息。 為壓縮數(shù)據人們則多采用線性四叉樹方法。從 上圖 可看出每個結點需要 6個量表達：父結點（前趨），四個子結點指針（后繼）和本結點的屬性值。這種方式，速度較快。 第二章 地 圖 數(shù) 據 結 構 76 上面稱為 “ topdown”的從上而下的分割方法，這種方法速度較慢，且有大量重復檢查才能確定劃分，如圖中的 9區(qū)域需要檢查 4次。 四叉樹編碼的基本思想 : 首先把一幅圖像或柵格地圖等分成四部分，逐塊檢查其格網值，如果某個格的所有值相同，則這個格就不再往下分割；否則，把它再分割成四個子區(qū)域，這樣直到每個子塊都只含有相同的屬性值為止。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 A A A A A A 10 A A A A A A A A A A 11 A A A A A A A A A 12 A A A A A A A A A 13 A A A A A A A A A A A A 14 A A A A A A A A A A A A 15 A A A A A A A A 16 9,2,1,A 9,3,1,A 9,6,1,A 9,8,1,A 9,9,2,A 10,1,1,A 10,2,1,A 10,3,4,A 10,7,2,A 11,1,2,A 11,9,1,A 12,7,2,A 12,9,1,A 13,9,1,A 13,12,1,A 13,13,1,A 13,14,1,A 13,15,2,A 14, 5,1,A 14, 6,1,A 14, 7,2,A 14, 9,2,A 14,11,2,A 14,13,2,A 第二章 地 圖 數(shù) 據 結 構 74 四叉樹結構 上面我們討論了塊式編碼，現(xiàn)在我們反過來想一想，當我們把一幅圖柵格化的時候，能不能把屬性一致的區(qū)域的柵格單元作大一些，而在有細節(jié)的區(qū)域的柵格單元作小一些，從而使存儲的數(shù)據少一些呢？答案是可以的。編碼原則： 行號、列號、邊長、屬性代碼 采用這種結構，如果一個多邊形所能包含的正方形越大，邊界越簡單，效果越好。 游程編碼結構的建立方法 A B C 原始地面 A B C 柵格化 柵格數(shù)據矩陣 第二章 地 圖 數(shù) 據 結 構 65 方法一： 屬性值 （屬性代碼） +重復個數(shù) 柵格數(shù)據矩陣 A逐行單獨編碼 第二章 地 圖 數(shù) 據 結 構 66 柵格數(shù)據矩陣 B逐行混合編碼 A， 6 A， 5， C， 1 A， 4， C， 2 B， 4， C， 2 B， 4， C， 2 B， 3， C， 3 代碼，個數(shù) 第二章 地 圖 數(shù) 據 結 構 67 柵格數(shù)據矩陣 C串行編號編碼 序號 +屬性代碼 +游程長 1 A 11 2 C 1 3 A 4 4 C 2 5 B 4 6 C 2 7 B 4 8 C 2 9 B 3 10 C 3 第二章 地 圖 數(shù) 據 結 構 68 方法二：屬性值 （屬性代碼） +位置 A逐行單獨編碼 柵格數(shù)據矩陣 行號 屬性值 列號 6 1， A ， 6 5 2， A ， 5 6 2， C ， 6 4 3， A ， 4 6 3， C ， 6 4 4， B ， 4 6 4， C ， 6 4 5， B ， 4 6 5， C ， 6 3 6， B ， 3 6 6， C ， 6 第二章 地 圖 數(shù) 據 結 構 69 柵格數(shù)據矩陣 行號 屬性值 列號 屬性值 列號 …… 6 B逐行混合編碼 1， A ， 6 5 6 2， A ， 5， C， 6 4 6 3， A ， 4， C， 6 4 6 4， B ， 4， C， 6 4 6 5， B ， 4， C， 6 3 6 6， B ， 3， C， 6 第二章 地 圖 數(shù) 據 結 構 70 C串行點號編碼 （序號）屬性值 (游程終 )點號 CCCBBBCCBBBBCCBBBBCCAAAACAAAAAAAAAAA35343332313029282726252423222120221817161514131211100908070605040302022010 A, 10 11 C, 11 15 A, 15 17 C, 17 21 B, 21 23 C, 23 27 B, 27 29 C, 29 32 B, 32 35 C, 35 第二章 地 圖 數(shù) 據 結 構 71 方法三 : 按行的順序存儲多邊形內的各個像元的列號，即在某行上從左至右存儲屬該多邊形的始末像元的列號。前兩個數(shù)字表示起點的行列號，從第三個數(shù)字開始是每個后續(xù)點的單位矢量方向 第二章 地 圖 數(shù) 據 結 構 63 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 1 2 3 4 5 6 3,2 7 0 1 2 3 4 5 6 鏈式編碼對多邊形的表示具有很強的壓縮能力，且具有一定的運算功能，如面積和周長計算等，且探測邊界急彎部分容易，適用于存儲圖形數(shù)據。 常見的方法： 鏈碼（ Chain Encoding) 游程碼 (Runlength Encoding) 塊碼 (Block Encoding) 四叉樹碼 (Quadtree Encoding) 第二章 地 圖 數(shù) 據 結 構 62 ① 鏈碼（又稱 Freeman碼、邊界碼） 主要用記錄線狀地物或面狀地物的邊界 : 由某一起點和一系列在基本方向上的單位矢量組成。 第二章 地 圖 數(shù) 據 結 構 60 直接柵格編碼方法： A A A A A B B B A A B B A A B B 方法一：逐行從左向右 A A A A A B B B A A B B A A B B A A A A A B B B A A B B A A B B 方法二：奇數(shù)行從左向右，偶數(shù)行從右向左 A A A A B B B A A A B B B B A A 第二章 地 圖 數(shù) 據 結 構 61 直接柵格編碼具有簡單、直觀、信息無壓縮和處理方便的特點，但因沒有壓縮，占用了大量的內存空間。 （ 1）簡單柵格數(shù)據結構 最簡單的柵格數(shù)據結構是將柵格數(shù)據看做一個數(shù)據矩陣，逐行記錄各像元代碼，這種記錄柵格數(shù)據的編碼方法 ——直接柵格編碼 柵格文件： 按直接柵格編碼記錄柵格數(shù)據的文件。 第二章 地 圖 數(shù) 據 結 構 59 柵格數(shù)據結構 柵格數(shù)據結構是以規(guī)則的像元陣列來表示地圖上空間地物或現(xiàn)象的分布的數(shù)據結構，其陣列中的每個數(shù)據表示地物或現(xiàn)象的屬性特征。 D、柵格數(shù)據記錄的是屬性本身，位置可由對應的行列號確定。 因為，在柵格數(shù)據中，地表被分割為規(guī)則排列、相互鄰接的方形地塊，每個地塊與一像元相對應。 第二章 地 圖 數(shù) 據 結 構 55 B、各個像元可用不同的灰度值來表示相應的屬性值。 第二章 地 圖 數(shù) 據 結 構 53 第二章 地 圖 數(shù) 據 結 構 54 二、柵格數(shù)據結構 柵格數(shù)據的概念 柵格數(shù)據：是由二維平面表像對應位置上像元灰度值所組成的陣列形式的數(shù)據。 第二章 地 圖 數(shù) 據 結 構 48 點號 地物類碼 坐標 N1 T101 X1， Y1 N2 T102 X2， Y2 …… …… …… 節(jié)點坐標表 第二章 地 圖 數(shù) 據 結 構 49 *鏈狀雙重獨立式編碼：節(jié)點坐標表 +弧坐標表 +弧段表 +多邊形表 +屬性特征表 由美國計算機圖形及空間分析實驗室最先采用的方法 節(jié)點坐標表：標志碼 +地物類碼 +（ X， Y）坐標 點號 地物類碼 坐標 N1 T101 X1， Y1 N2 T102 X2， Y2 …… …… …… 節(jié)點坐標表 第二章 地 圖 數(shù) 據 結 構 50 弧坐標表：標志碼 +地物類碼 +弧上的節(jié)點 弧段表：標志碼 +地物類碼 +起點 +終點 +左多邊形 +右多邊形 +內點（指向中間的指針） 弧坐標表、弧段表可以合并 如下： 第二章 地 圖 數(shù) 據 結 構 51 多邊形表：標志碼 +地物類碼 +組成多邊形的弧段號等 第二章 地 圖 數(shù) 據 結 構 52 綜上所述，為了將空間數(shù)據存入計算機： 首先，將空間數(shù)據抽象為不同的專題（或圖層）；其次，將專題層抽象成不同的類型；第三，將某一類型中的地理要素或實體分解為點、線、面狀目標；第四，每個目標數(shù)據由定位數(shù)據（坐標） +拓撲數(shù)據 +屬性數(shù)據組成。 第二章 地 圖 數(shù) 據 結 構 45 圖24：多邊形拓撲的建立過程 第二章 地 圖 數(shù) 據 結 構 46 圖 25：帶“島”的多邊形建立拓撲的結果 多邊形拓撲的建立，要注意多邊形帶“島”的情況，按照上述算法，對于帶“島”的多邊形，或者稱為環(huán)，其包含的弧段構成了多個閉合曲線，并且“島”的弧段排序是順時針的（圖 25）（實際上，從環(huán)狀多邊形內部看，它仍然是逆時針的）。 按照這種算法，生成多邊形的弧段從多邊形內部看，是逆時針排列的。)=P， NC=NS(A)，轉到第四步。)=P， NC=NE(A)；如果 NC= NE(A39。 （ 6）如果 NC=NS(A39。 （ 5）檢查與當前節(jié)點相連接的、已經排列好的弧段序列，將當前弧段的下一條弧段 A39。如果右多邊形為空，則創(chuàng)建一個新的多邊形 P，多邊形的第一條弧段為當前弧段，并設置 PR(A)=P，