【正文】 把描述時(shí)間特征的數(shù)據(jù)納入該類。為了方便計(jì)算機(jī)存儲(chǔ)、管理和使用這些編碼，需要研究統(tǒng)一的分類系統(tǒng)和編碼。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 16 第二節(jié) 地圖的數(shù)據(jù)結(jié)構(gòu) 地圖的數(shù)據(jù)結(jié)構(gòu) 主要指地圖數(shù)據(jù)中 空間數(shù)據(jù) 的結(jié)構(gòu)， 是指幾何數(shù)據(jù)以什么形式在計(jì)算機(jī)中存儲(chǔ)和處理。矢量數(shù)據(jù)結(jié)構(gòu)是表達(dá)地圖空間數(shù)據(jù)的一種常見的數(shù)據(jù)結(jié)構(gòu)， 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 17 矢量數(shù)據(jù) ——它通過記錄坐標(biāo)值的方式盡可能精確地表示呈點(diǎn)、線、面狀分布的地理實(shí)體。如果相交，則應(yīng)以交點(diǎn)為界將一維矢量分成幾個(gè)一維矢量。下面按考慮問題的多寡分別介紹矢量數(shù)據(jù)的簡單結(jié)構(gòu)和拓?fù)浣Y(jié)構(gòu)及其有關(guān)的編碼方法。 有點(diǎn)、線、面三種基本的矢量數(shù)據(jù)結(jié)構(gòu)形式。 （ x， y）是定位坐標(biāo) 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 21 ② 線數(shù)據(jù)結(jié)構(gòu)形式 當(dāng)然也可采用將屬性數(shù)據(jù)單獨(dú)存放的方式 標(biāo)志碼和屬性碼的含義與點(diǎn)的數(shù)據(jù)結(jié)構(gòu)相同； 坐標(biāo)對(duì)數(shù) n：構(gòu)成該線的坐標(biāo)對(duì)個(gè)數(shù)； 坐標(biāo)串：是構(gòu)成線的矢量坐標(biāo)對(duì)序列，共有 n對(duì) 標(biāo)志碼 屬性碼 坐標(biāo)對(duì)數(shù) n 坐標(biāo)串（ x1， y1） …… 坐標(biāo)串（ x1， y1） …… 坐標(biāo)對(duì)數(shù) n 標(biāo)志碼 屬性碼 標(biāo)志碼 + 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 22 ③ 面（多邊形）數(shù)據(jù)結(jié)構(gòu)形式 常見的兩種形式 標(biāo)志碼 屬性碼 坐標(biāo)對(duì)數(shù) n 坐標(biāo)串（ x1， y1） …… （ x1， y1） 標(biāo)志碼 屬性碼 弧段數(shù) n 弧段標(biāo)志碼集 弧段標(biāo)志碼 01 坐標(biāo)對(duì)數(shù) n 坐標(biāo)串（ x1， y1） …… 弧段標(biāo)志碼 n 坐標(biāo)對(duì)數(shù) m 坐標(biāo)串（ x1， y1） …… …… 有 N個(gè) 這種方法可能會(huì)產(chǎn)生大量的數(shù)據(jù)冗余 這種方法保證了多邊形公共邊的唯一性 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 23 簡單數(shù)據(jù)結(jié)構(gòu)的編碼形式 因在矢量的簡單數(shù)據(jù)結(jié)構(gòu)中不考慮拓?fù)潢P(guān)系，故其編碼方法僅記錄空間實(shí)體的位置、標(biāo)志及屬性信息，而不記錄拓?fù)潢P(guān)系。每個(gè)實(shí)體的坐標(biāo)都獨(dú)立存儲(chǔ)，毫不顧及相鄰的多邊形或線或點(diǎn)狀地物。使用這種方法 時(shí)，除了外輪廓線以外，多邊形的邊界線數(shù)據(jù)均獲取和存儲(chǔ)兩次，這就會(huì)產(chǎn)生重疊或列隙（當(dāng)取值誤差時(shí)）， 并產(chǎn)生數(shù)據(jù)冗余。 ② 點(diǎn)位字典法 以公用點(diǎn)位字典為基礎(chǔ)建立一些系統(tǒng)，這克服了獨(dú)立實(shí)體編碼的某些局限性 。即： 點(diǎn)位字典表：點(diǎn)號(hào)、坐標(biāo)（ X， Y） 點(diǎn)實(shí)體：標(biāo)志碼，地物編碼，點(diǎn)號(hào) 線實(shí)體：標(biāo)志碼，地物編碼，（點(diǎn)號(hào) 1， …… 點(diǎn)號(hào) n） 面實(shí)體：標(biāo)志碼，地物編碼，（點(diǎn)號(hào) 1， …… 點(diǎn)號(hào) n，點(diǎn)號(hào) 1） 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 25 下圖是兩種表述方法的比較： A 1 2 3 7 C 6 3 4 5 B 1 7 6 3 5 8 20 15 10 5 0 0 5 10 15 20 A B C 1 2 3 4 5 6 7 8 多邊形 地物編碼 坐標(biāo)數(shù)據(jù)項(xiàng) A T301 X1， Y1； X2， Y2； X3， Y3； X7， Y7； X1， Y1 B T302 X1， Y1； X7， Y7； X3， Y3； X6， Y6； X5， Y5； X8， Y8； X1， Y1 C T305 X3， Y3； X4， Y4； X5， Y5； X6， Y6； X3， Y3 獨(dú)立實(shí)體編碼 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 26 A B C 1 2 3 4 5 6 7 8 點(diǎn)號(hào) 坐標(biāo)數(shù)據(jù)項(xiàng) 01 X1， Y1 02 X2， Y2 03 X3， Y3 04 X4， Y4 05 X5， Y5 06 X6， Y6 07 X7， Y7 08 X8， Y8 點(diǎn)位字典表 多邊形 地物編碼 點(diǎn)號(hào) A T301 1， 2， 3， 7 B T302 1， 7， 3， 6， 5， 8 C T305 3， 4， 5， 6 點(diǎn)位字典表編碼 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 27 （ 2）拓?fù)鋽?shù)據(jù)結(jié)構(gòu)及編碼 地圖上兩點(diǎn)間距離或方向會(huì)隨地圖投影的不同而發(fā)生變化，故 僅用距離或方向不能很好地描述地圖要素間的空間關(guān)系 ?？梢娡?fù)潢P(guān)系能從本質(zhì)上描述地圖要素間的空間關(guān)系。 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是現(xiàn)代計(jì)算機(jī)地圖制圖系統(tǒng)所必需的。 ①拓?fù)湓?—— 點(diǎn) （節(jié)點(diǎn)）、 線 （鏈、弧、邊）、 面 （多邊形） ②基本拓?fù)潢P(guān)系 —— 鄰接、關(guān)聯(lián)、包含 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 28 鄰接 —— 相同拓?fù)湓刂g的關(guān)系 如節(jié)點(diǎn)與節(jié)點(diǎn)、鏈與鏈、面與面等。如國家由省組成，省由市組成，市由區(qū)縣組成等。目前的計(jì)算機(jī)地圖制圖系統(tǒng)中，主要表示的是拓?fù)湓刂g的基本的拓?fù)潢P(guān)系，表示方法多種多樣。 N1 N2 N3 N4 N5 N6 N7 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B1 B2 B3 B4 B5 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 N1 N2 N3 N4 N5 N6 N7 面 弧 點(diǎn) 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 31 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 32 “”表示面中含有島 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 33 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 34 雖然建立拓?fù)潢P(guān)系比較麻煩，但這種關(guān)系一旦建立，就為數(shù)據(jù)的采集、圖形編輯和維護(hù)數(shù)據(jù)的一致性提供了大大的方便。這種拓?fù)渚庉?，不但保證數(shù)字化原始數(shù)據(jù)的自動(dòng)查錯(cuò)，而且可以自動(dòng)形成封閉的多邊形邊界，為由各個(gè)單獨(dú)存儲(chǔ)的弧段組成所需要的各類多邊形及建立空間數(shù)據(jù)庫奠定基礎(chǔ)。按上要求則檢出的記錄應(yīng)變?yōu)椋? *從轉(zhuǎn)換的記錄中，任取一個(gè)節(jié)點(diǎn)為起點(diǎn)，按順連接，使其能暢通并閉合。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 37 B、結(jié)點(diǎn)連接編輯 例如，需要對(duì)結(jié)點(diǎn) N1進(jìn)行編輯，其過程相似。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 39 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的編碼形式 矢量拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的一般編碼形式：空間實(shí)體的位置 +標(biāo)志 +屬性信息 +拓?fù)潢P(guān)系 ①空間實(shí)體位置：由 “ 節(jié)點(diǎn)坐標(biāo)文件 ” 和 “ 弧段坐標(biāo)文件 ” 來體現(xiàn)。 ③屬性信息：由屬性特征表來體現(xiàn)。 類別特征，一般用 “ 地物類編碼表 ” 表達(dá)；而具體說明信息則用 “ 地物屬性表 ” 說明。如下表： 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 41 地物屬性表： 地物標(biāo)志碼 +所屬地物類碼 +具體屬性等。 記錄拓?fù)潢P(guān)系的編碼方法有多種，常見的有： *雙重獨(dú)立地圖編碼（ Dual Independent Map Encoding,DIME）：節(jié)點(diǎn)坐標(biāo)表 +弧 ——點(diǎn)、面拓?fù)潢P(guān)系表 +屬性特征表 它最早是以城市街道為編碼的主體 最早是美國人口統(tǒng)計(jì)系統(tǒng)采用的一種編碼方法。 圖 24中共有 4個(gè)節(jié)點(diǎn)，以 A、 B、 C、 D表示； 6條弧段，用數(shù)字表示；以及 I、 II、 III三個(gè)多邊形（圖 24a）。 在建立拓?fù)渲?，首先將所有弧段的左右多邊形（在?shí)現(xiàn)中，可以用多邊形的編碼表示）都設(shè)置為空；然后對(duì)每個(gè)節(jié)點(diǎn)計(jì)算與其相連弧段的在連接處的角度，并進(jìn)行排序（圖24b）（注意，這個(gè)排序是循環(huán)的）。如果都非空，轉(zhuǎn)到第一步，當(dāng)所有弧段處理完畢后，算法結(jié)束； （ 3）如果左多邊形為空，則創(chuàng)建一個(gè)新的多邊形 P，多邊形的第一條弧段為當(dāng)前弧段，并設(shè)置 PL(A)=P，設(shè)置搜尋起始節(jié)點(diǎn)為 Ns(A)，搜尋當(dāng)前節(jié)點(diǎn)為NE(A)。 （ 4）判斷 N0和 NC是否相等，如果是，則多邊形所有弧段都已經(jīng)找到，轉(zhuǎn)到第一步。作為多邊形的第二條弧段。)，設(shè)置 PL(A39。)，設(shè)置PR(A39。 如圖 24c所示，如果從弧段 4開始搜尋，找到節(jié)點(diǎn) C后，根據(jù)弧段的排序，下一條弧段是 2；然后找到節(jié)點(diǎn) A，弧段 1，整個(gè)搜尋結(jié)束，建立多邊形 I，其組成弧段為 1。如果節(jié)點(diǎn)弧段排序?yàn)轫槙r(shí)針，則算法中用 PL(A)代替 PR(A)，用 PR(A)代替 PL(A)，生成的多邊形弧段是順時(shí)針排列的。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 47 ⑤ 記錄拓?fù)潢P(guān)系的編碼方法： 記錄拓?fù)潢P(guān)系的編碼方法有多種，常見的有： *雙重獨(dú)立地圖編碼（ Dual Independent Map Encoding,DIME）：節(jié)點(diǎn)坐標(biāo)表 +弧 ——點(diǎn)、面拓?fù)潢P(guān)系表 +屬性特征表 它最早是以城市街道為編碼的主體 最早是美國人口統(tǒng)計(jì)系統(tǒng)采用的一種編碼方法。這樣具有相同分類碼的目標(biāo)組成類型；多個(gè)相關(guān)聯(lián)的類型構(gòu)成專題層；若干個(gè)專題層構(gòu)成圖幅；全部數(shù)據(jù)組成數(shù)據(jù)庫。 對(duì)柵格數(shù)據(jù)的有關(guān)說明 A、像元（像素）：將地圖制圖區(qū)域的二維平面按行和列作規(guī)則劃分，形成一個(gè)柵格陣列，其中各柵格陣列元素就是像元（像素）。各像元內(nèi)其屬性是均一的。因此 C、柵格數(shù)據(jù)的比例尺（分辨率）：像元（柵格）的大小與地表相應(yīng)單元的大小之比。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 56 柵格數(shù)據(jù)的表示方法 點(diǎn) ——用一個(gè)柵格表示； 線 ——用沿其走向的一組相鄰柵格表示 面 ——用其所覆蓋的相鄰柵格的集合表示 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 57 柵格數(shù)據(jù)的一般組織方法 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 58 有關(guān)相鄰柵格單元 四方向相鄰 八方向相鄰 一般講，四方向相鄰的柵格圖形線畫顯得粗壯，但階梯（鋸齒）明顯；而八方向相鄰的柵格圖形顯得平滑圓潤。可以說，柵格數(shù)據(jù)結(jié)構(gòu)就是像元陣列，像元的行列號(hào)確定實(shí)體的空間位置，像元的值表示實(shí)體的類型、等級(jí)等屬性。 通常在文件頭中還存有該柵格數(shù)據(jù)的行數(shù)和列數(shù)。 （ 2）柵格數(shù)據(jù)的壓縮編碼 基本思想：對(duì)于一個(gè)柵格圖形，常常有相鄰若干柵格單元具有相同的屬性代碼，因此，可采用某種方法壓縮那些重復(fù)的內(nèi)容。單位矢量的長度默認(rèn)為一個(gè)柵格單元，每個(gè)后續(xù)點(diǎn)可能位于其前繼點(diǎn)的 8個(gè)基本方向之一。其缺點(diǎn)是對(duì)疊置運(yùn)算難實(shí)施，對(duì)局部修改將改變整體結(jié)構(gòu)，效率低，而且相鄰邊界有冗余 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 64 ② 游程碼 逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度。 CCCBBBCCBBBBCCBBBBCCAAAACAAAAAAAAAAA654321654321第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 72 ③ 塊碼 塊式編碼是將游程編碼擴(kuò)大到二維的情況，把多邊形范圍分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。面積計(jì)算具有明顯的優(yōu)勢(shì)。這種思路可用四叉樹編碼來實(shí)現(xiàn)。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 75 1 3 4 5 6 9 10 15 16 18 13 14 11 19 12 2 7 8 17 A 1 B 6 NW SW SE NE 11 12 C D E 8 10 9 7 ………… 父指針 子指針 樹叉 葉子 葉子 ——不可分； 樹叉 ——可再分。 常規(guī)四叉樹也可以采用“ bottomup”的方式，對(duì)柵格數(shù)據(jù)按一定順序進(jìn)行檢測(cè)，如果每相鄰四個(gè)格網(wǎng)值相同，則進(jìn)行合并，逐次往上遞歸。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 77 常規(guī)四叉樹 除了要記錄葉結(jié)點(diǎn)外，還要記錄樹叉結(jié)點(diǎn)，結(jié)點(diǎn)之間的聯(lián)系靠指針表達(dá)。 這就需要大量的存儲(chǔ)空間，所以在數(shù)據(jù)壓縮方面常規(guī)四叉樹結(jié)構(gòu)作用不大，但在數(shù)據(jù)索引和圖幅索引等方面得到了很好的應(yīng)用。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 78 線性四叉樹 基本思想：不記錄中間節(jié)點(diǎn)，不需要指針，只存儲(chǔ)最后葉結(jié)點(diǎn)信息，包括結(jié)點(diǎn)的 位置（地址）、屬性值。最常用的地址碼是四進(jìn)制或十進(jìn)制的Morton碼。 JJ 0 1 2 3 4 5 6 7 Jb 00 01 10 11 100 101 110 111 II Ib 0 00 1 01 2 10 3 11 4 100 5 101 6 110 7 111 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 80 第二步： Morton碼 MQ=2再依次檢查每四個(gè)相鄰