《地圖數(shù)據(jù)結(jié)構(gòu)》課件

計算機地圖制圖城市與環(huán)境科學學院1《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第1頁!第二章地圖數(shù)據(jù)結(jié)構(gòu)2．1地圖數(shù)據(jù)的描述方法地圖數(shù)據(jù)：地圖諸要素的數(shù)字化表示，是以點、線、面等方式采用編碼技術(shù)對地理空間物體進行特征描述及在物體間建立相互聯(lián)系的數(shù)據(jù)集。一、地圖對地理空間的描述地圖是現(xiàn)實世界的模型，它按照一定的比例和投影原則，有選擇地將復雜的三維地理空間的某些內(nèi)容投影到二維平面介質(zhì)上，并用符號將這些內(nèi)容要素表現(xiàn)出來。2《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第2頁!地圖學中，把地理空間的實體分為點、線、面三種要素(對象)，分別用點狀、線狀、面狀符號來表示。點實體點實體是有特定的位置、維數(shù)為0的實體。實體點：用來代表一個實體；如城市注記點：用于定位注記；北京內(nèi)點：用于記錄多邊形的屬性，存在于多邊形內(nèi)；結(jié)點：表示線的終點和起點；3《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第3頁!(3)面(多邊形)實體面(多邊形)實體是維數(shù)為2的實體，由一個封閉的坐標點序列外加內(nèi)點表示，是對湖泊、島嶼、地塊等現(xiàn)象的描述。具有以下特征：周長；面積；島或非島；內(nèi)島或齒狀；重疊性等內(nèi)面：不包括邊界的面廣義多邊形（其他多邊形覆蓋面的周邊以外的面，它沒有外環(huán)，有一個或多個內(nèi)環(huán)）虛多邊形（以其他多邊形為界的多邊形）4《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第4頁!2．屬性特征屬性特征用以描述事物或現(xiàn)象的特性，如事物或現(xiàn)象的類別、等級、數(shù)量、名稱等，用來說明“是什么”。屬性特征通常分定性和定量兩種：（1）定性特征包括名稱、類型等；（2）定量特征包括數(shù)量、等級等。3．時間特征時間特征用以描述地理實體隨著時間而變化的特征。目前的計算機地圖制圖還較少考慮到地圖數(shù)據(jù)的時間特征，只考慮其屬性特征與空間特征的結(jié)合。由于地圖數(shù)據(jù)具有時間維，過時的信息雖不具有現(xiàn)勢性，卻可以作為歷史性數(shù)據(jù)保存起來，但這樣做會增大計算機地圖制圖表示和處理數(shù)據(jù)的難度。5《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第5頁!三、地圖數(shù)據(jù)的基本類型根據(jù)地圖數(shù)據(jù)的特征，可以把地圖數(shù)據(jù)分為空間數(shù)據(jù)、關(guān)系數(shù)據(jù)、屬性數(shù)據(jù)三類。1．空間數(shù)據(jù)也稱幾何數(shù)據(jù)，即描述地理現(xiàn)象或地理實體的空間位置、形狀、大小等的數(shù)據(jù)。根據(jù)地理要素的空間分布待征和空間實體分類，可以將地理空間數(shù)據(jù)分為點、線、面三種類型。6《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第6頁!2．空間數(shù)據(jù)的表示方法

一般地，表示地理現(xiàn)象的空間數(shù)據(jù)可以細分為：類型數(shù)據(jù)：例如考古地點、道路線和土壤類型的分布等；面域數(shù)據(jù)：例如隨機多邊形的中心點、行政區(qū)域界線和行政單元等；網(wǎng)絡(luò)數(shù)據(jù)：例如道路交點、街道和街區(qū)等；樣本數(shù)據(jù)：例如氣象站、航線和野外樣方的分布區(qū)等；曲面數(shù)據(jù)：例如高程點、等高線和等值區(qū)域；文本數(shù)據(jù)：例如地名、河流名稱和區(qū)域名稱；符號數(shù)據(jù)：例如點狀符號、線狀符號和面狀符號（暈線）等（如圖2-2所示）。

7《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第7頁!3．關(guān)系數(shù)據(jù)關(guān)系數(shù)據(jù)是描述空間數(shù)據(jù)之間的空間關(guān)系的數(shù)據(jù)。上述點、線、面空間位置數(shù)據(jù)之間存在著某種特定的拓撲關(guān)系。這類數(shù)據(jù)表達了各類地理實體空間位置之間的相互關(guān)系，如空間數(shù)據(jù)的相鄰、關(guān)聯(lián)、包含等。各種地理要素的空間位置數(shù)據(jù)在地圖上的關(guān)系，可以概括為點、線、多邊形之間的9種形式的拓撲關(guān)系：點—點、點—線、點—面；線—點、線—線、線—面；面與點、面與線、面與面。最常用的空間實體關(guān)系有6種，即：點—點、點—線、點—面；線—線、線—面；面—面。8《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第8頁!4．屬性數(shù)據(jù)屬性數(shù)據(jù)是描述空間實體屬性特征的數(shù)據(jù)，也稱非幾何數(shù)據(jù)，即描述地理現(xiàn)象或地理實體的定性或定量指標，包括語義與統(tǒng)計數(shù)據(jù)，如類型、等級、名稱、狀態(tài)等。有時也把描述時間特征的數(shù)據(jù)納入該類。屬性數(shù)據(jù)中的定性(或定量)指標通常要經(jīng)編碼轉(zhuǎn)換才能被計算機接受。為了方便計算機存儲、管理和使用這些編碼，需要研究統(tǒng)一的分類系統(tǒng)和編碼。有關(guān)這方面的詳細內(nèi)容將在本書第3章中進行介紹。9《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第9頁!矢量數(shù)據(jù)——它通過記錄坐標值的方式盡可能精確地表示呈點、線、面狀分布的地理實體。2、矢量數(shù)據(jù)的表達在計算機地圖制圖中，各地理要素在二維平面上的矢量數(shù)據(jù)表達為：點—0維矢量：由一（x，y）坐標值表示；線—1維矢量：由一串有序的（x，y）坐標表示；面—2維矢量：由一串有序的且首尾坐標相同的（x，y）10《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第10頁!3、矢量數(shù)據(jù)結(jié)構(gòu)的表示矢量數(shù)據(jù)結(jié)構(gòu)是最早用于表達地圖空間數(shù)據(jù)的一種常見的數(shù)據(jù)結(jié)構(gòu)，在計算機地圖制圖中，表示矢量數(shù)據(jù)的結(jié)構(gòu)時應考慮以下問題：方便存儲和處理與屬性數(shù)據(jù)的聯(lián)系矢量數(shù)據(jù)之間的拓撲關(guān)系表示矢量數(shù)據(jù)的方法有多種，但基本上相似。下面按考慮問題的多寡分別介紹矢量數(shù)據(jù)的簡單結(jié)構(gòu)和拓撲結(jié)構(gòu)及其有關(guān)的編碼方法。11《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第11頁!②線數(shù)據(jù)結(jié)構(gòu)形式當然也可采用將屬性數(shù)據(jù)單獨存放的方式標志碼和屬性碼的含義與點的數(shù)據(jù)結(jié)構(gòu)相同；坐標對數(shù)n：構(gòu)成該線的坐標對個數(shù)；坐標串：是構(gòu)成線的矢量坐標對序列，共有n對標志碼屬性碼坐標對數(shù)n坐標串（x1，y1）……坐標串（x1，y1）……坐標對數(shù)n標志碼屬性碼標志碼+12《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第12頁!簡單數(shù)據(jù)結(jié)構(gòu)的編碼形式因在矢量的簡單數(shù)據(jù)結(jié)構(gòu)中不考慮拓撲關(guān)系，故其編碼方法僅記錄空間實體的位置、標志及屬性信息，而不記錄拓撲關(guān)系。常見的編碼方法有獨立實體法和點位字典法①獨立實體法在獨立實體法中，每個點線面都直接跟隨它的空間坐標。每個實體的坐標都獨立存儲，毫不顧及相鄰的多邊形或線或點狀地物。具體形式如下：13《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第13頁!下圖是兩種表述方法的比較：A1237C6345B1763582015105005101520ABC12345678多邊形地物編碼坐標數(shù)據(jù)項AT301X1，Y1；X2，Y2；X3，Y3；X7，Y7；X1，Y1BT302X1，Y1；X7，Y7；X3，Y3；X6，Y6；X5，Y5；X8，Y8；X1，Y1CT305X3，Y3；X4，Y4；X5，Y5；X6，Y6；X3，Y3獨立實體編碼14《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第14頁!（2）拓撲數(shù)據(jù)結(jié)構(gòu)及編碼

地圖上兩點間距離或方向會隨地圖投影的不同而發(fā)生變化，故僅用距離或方向不能很好地描述地圖要素間的空間關(guān)系。如果引用拓撲關(guān)系來描述地圖要素間的空間關(guān)系，則不論地圖投影如何變化，其拓撲關(guān)系都不改變。可見拓撲關(guān)系能從本質(zhì)上描述地圖要素間的空間關(guān)系。具有拓撲關(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓撲數(shù)據(jù)結(jié)構(gòu)。拓撲數(shù)據(jù)結(jié)構(gòu)是現(xiàn)代計算機地圖制圖系統(tǒng)所必需的。盡管拓撲數(shù)據(jù)結(jié)構(gòu)的表示方式還沒有固定的格式，也沒有形成標準，但其基本原理是相同的。①拓撲元素——點（節(jié)點）、線（鏈、弧、邊）、面（多邊形）②基本拓撲關(guān)系——鄰接、關(guān)聯(lián)、包含15《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第15頁!在計算機地圖制圖系統(tǒng)中，也可能用到其他關(guān)系，如層次關(guān)系即相同元素之間的等級關(guān)系。如國家由省組成，省由市組成，市由區(qū)縣組成等。③拓撲關(guān)系的表示方法如何表示拓撲關(guān)系是拓撲數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵，其中幾何數(shù)據(jù)的表示可參照矢量數(shù)據(jù)的簡單數(shù)據(jù)結(jié)構(gòu)。目前的計算機地圖制圖系統(tǒng)中，主要表示的是拓撲元素之間的基本的拓撲關(guān)系，表示方法多種多樣。下面介紹一個常用的方法：節(jié)點、弧段、面塊相互之間的所有關(guān)聯(lián)拓撲關(guān)系都用關(guān)系表表達出來。16《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第16頁!17《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第17頁!18《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第18頁!19《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第19頁!B、結(jié)點連接編輯例如，需要對結(jié)點N1進行編輯，其過程相似。20《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第20頁!拓撲數(shù)據(jù)結(jié)構(gòu)的編碼形式矢量拓撲數(shù)據(jù)結(jié)構(gòu)的一般編碼形式：空間實體的位置+標志+屬性信息+拓撲關(guān)系①空間實體位置：由“節(jié)點坐標文件”和“弧段坐標文件”來體現(xiàn)。②標志碼：同簡單數(shù)據(jù)結(jié)構(gòu)的標志碼。③屬性信息：由屬性特征表來體現(xiàn)。屬性特征分為兩種：一種是類別特征，即它是什么；第二種是具體的說明信息，或者說統(tǒng)計信息，以解決兩個同類目標的不同特征問題。類別特征，一般用“地物類編碼表”表達；而具體說明信息則用“地物屬性表”說明。21《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第21頁!地物屬性表：地物標志碼+所屬地物類碼+具體屬性等。如下表：22《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第22頁!多邊形拓撲關(guān)系的建立

如果使用DIME或者類似的編碼模型，多邊形拓撲關(guān)系的表達需要描述以下實體之間的關(guān)系：多邊形的組成弧段；弧段左右兩側(cè)的多邊形，弧段兩端的節(jié)點；節(jié)點相連的弧段。圖2-4中共有4個節(jié)點，以A、B、C、D表示；6條弧段，用數(shù)字表示；以及I、II、III三個多邊形（圖2-4-a）。首先定義以下概念：由于弧段是有方向的，算法中將弧段A的起始節(jié)點稱為首節(jié)點Ns(A)，而終止節(jié)點為尾節(jié)點NE(A)；考慮到弧段的方向性，沿弧段前進方向，將其相鄰的多邊形分別定義為左多邊形和右多邊形PL(A)和PR(A)。在建立拓撲之前，首先將所有弧段的左右多邊形（在實現(xiàn)中，可以用多邊形的編碼表示）都設(shè)置為空；然后對每個節(jié)點計算與其相連弧段的在連接處的角度，并進行排序（圖2-4-b）（注意，這個排序是循環(huán)的）。23《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第23頁!圖2-4：多邊形拓撲的建立過程24《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第24頁!⑤記錄拓撲關(guān)系的編碼方法：記錄拓撲關(guān)系的編碼方法有多種，常見的有：*雙重獨立地圖編碼（DualIndependentMapEncoding,DIME）：節(jié)點坐標表+弧——點、面拓撲關(guān)系表+屬性特征表它最早是以城市街道為編碼的主體最早是美國人口統(tǒng)計系統(tǒng)采用的一種編碼方法。25《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第25頁!*鏈狀雙重獨立式編碼：節(jié)點坐標表+弧坐標表+弧段表+多邊形表+屬性特征表由美國計算機圖形及空間分析實驗室最先采用的方法節(jié)點坐標表：標志碼+地物類碼+（X，Y）坐標點號地物類碼坐標N1T101X1，Y1N2T102X2，Y2………………節(jié)點坐標表26《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第26頁!多邊形表：標志碼+地物類碼+組成多邊形的弧段號等27《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第27頁!28《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第28頁!B、各個像元可用不同的灰度值來表示相應的屬性值。各像元內(nèi)其屬性是均一的。因為，在柵格數(shù)據(jù)中，地表被分割為規(guī)則排列、相互鄰接的方形地塊，每個地塊與一像元相對應。因此C、柵格數(shù)據(jù)的比例尺（分辨率）：像元（柵格）的大小與地表相應單元的大小之比。D、柵格數(shù)據(jù)記錄的是屬性本身，位置可由對應的行列號確定。29《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第29頁!柵格數(shù)據(jù)的一般組織方法30《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第30頁!2、柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)是以規(guī)則的像元陣列來表示地圖上空間地物或現(xiàn)象的分布的數(shù)據(jù)結(jié)構(gòu)，其陣列中的每個數(shù)據(jù)表示地物或現(xiàn)象的屬性特征?？梢哉f，柵格數(shù)據(jù)結(jié)構(gòu)就是像元陣列，像元的行列號確定實體的空間位置，像元的值表示實體的類型、等級等屬性。（1）簡單柵格數(shù)據(jù)結(jié)構(gòu)最簡單的柵格數(shù)據(jù)結(jié)構(gòu)是將柵格數(shù)據(jù)看做一個數(shù)據(jù)矩陣，逐行記錄各像元代碼，這種記錄柵格數(shù)據(jù)的編碼方法——直接柵格編碼柵格文件：按直接柵格編碼記錄柵格數(shù)據(jù)的文件。通常在文件頭中還存有該柵格數(shù)據(jù)的行數(shù)和列數(shù)。31《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第31頁!直接柵格編碼具有簡單、直觀、信息無壓縮和處理方便的特點，但因沒有壓縮，占用了大量的內(nèi)存空間。（2）柵格數(shù)據(jù)的壓縮編碼基本思想：對于一個柵格圖形，常常有相鄰若干柵格單元具有相同的屬性代碼，因此，可采用某種方法壓縮那些重復的內(nèi)容。常見的方法：鏈碼（ChainEncoding)游程碼(Run-lengthEncoding)塊碼(BlockEncoding)四叉樹碼(QuadtreeEncoding)32《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第32頁!0123456701234561234563,270123456鏈式編碼對多邊形的表示具有很強的壓縮能力，且具有一定的運算功能，如面積和周長計算等，且探測邊界急彎部分容易，適用于存儲圖形數(shù)據(jù)。其缺點是對疊置運算難實施，對局部修改將改變整體結(jié)構(gòu)，效率低，而且相鄰邊界有冗余33《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第33頁!方法一：屬性值（屬性代碼）+重復個數(shù)柵格數(shù)據(jù)矩陣A逐行單獨編碼34《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第34頁!柵格數(shù)據(jù)矩陣C串行編號編碼序號+屬性代碼+游程長1A112C13A44C25B46C27B48C29B310C335《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第35頁!柵格數(shù)據(jù)矩陣行號屬性值列號屬性值列號……6B逐行混合編碼1，A，6562，A，5，C，6463，A，4，C，6464，B，4，C，6465，B，4，C，6366，B，3，C，636《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第36頁!方法三:按行的順序存儲多邊形內(nèi)的各個像元的列號，即在某行上從左至右存儲屬該多邊形的始末像元的列號。37《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第37頁!12345678910111213141516123456789AAAAAA10AAAAAAAAAA11AAAAAAAAA12AAAAAAAAA13AAAAAAAAAAAA14AAAAAAAAAAAA15AAAAAAAA169,2,1,A9,3,1,A9,6,1,A9,8,1,A9,9,2,A10,1,1,A10,2,1,A10,3,4,A10,7,2,A11,1,2,A11,9,1,A12,7,2,A12,9,1,A13,9,1,A13,12,1,A13,13,1,A13,14,1,A13,15,2,A14,5,1,A14,6,1,A14,7,2,A14,9,2,A14,11,2,A14,13,2,A38《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第38頁!13456910151618131411191227817A1B6NWSWSENE1112CDE81097…………父指針子指針樹叉葉子葉子——不可分；樹叉——可再分。39《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第39頁!常規(guī)四叉樹除了要記錄葉結(jié)點外，還要記錄樹叉結(jié)點，結(jié)點之間的聯(lián)系靠指針表達。從上圖可看出每個結(jié)點需要6個量表達：父結(jié)點（前趨），四個子結(jié)點指針（后繼）和本結(jié)點的屬性值。這就需要大量的存儲空間，所以在數(shù)據(jù)壓縮方面常規(guī)四叉樹結(jié)構(gòu)作用不大，但在數(shù)據(jù)索引和圖幅索引等方面得到了很好的應用。為壓縮數(shù)據(jù)人們則多采用線性四叉樹方法。40《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第40頁!基于四進制的Morton碼(MQ)及四叉樹的建立步：將十進制的行列號（II，JJ）轉(zhuǎn)換成二進制數(shù)（Ib,Jb）表示。JJ01234567Jb00011011100101110111IIIb000101210311410051016110711141《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第41頁!第三步，在排好的線性表中，依次檢查每四個相鄰MQ碼對應的屬性值，如果相同則合并為一個大塊，否則將這四個格網(wǎng)記錄下來，內(nèi)容包括MQ碼、屬性值。再依次檢查每四個相鄰的大塊的屬性值，若不同則記錄下來，如果相同則合并，如此直到?jīng)]有可合并的為止。42《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第42頁!基于十進制的線性四叉樹編碼基于四進制的編碼存在著一個問題。大多數(shù)語言不支持四進制變量，需要用十進制的Morton碼——MD。因此人們逐漸提出采用十進制的Morton碼作為線性四叉樹的地址碼。方法：設(shè)十進制表示的行、列號在計算機內(nèi)的二進制分別為：43《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第43頁!然后再將得到的Md由二進制數(shù)轉(zhuǎn)換為十進制數(shù)即可。用類似的方法，也可以由Md碼反求柵格單元的行列號（大家在下面可以自己做一做）JJ01234567Jb011011100101110111IIIb000145161720211123671819222321089121324252829311101114152627303141003233363748495253510134353839505154556110404144455657606171114243464758596263Md碼行號列號44《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第44頁!在排好的線性表中，依次檢查每四個相鄰Md碼對應的屬性值，如果相同則合并為一個大塊，否則將這四個格網(wǎng)記錄下來，內(nèi)容包括Md碼、屬性值。再依次檢查每四個相鄰的大塊的屬性值，若不同則記錄下來，如果相同則合并，如此直到?jīng)]有可合并的為止。45《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第45頁!**具體過程：如下步：確定十進制線性四叉樹的Morton地址碼1514111011313129810276320115410000113102011000JbJJIbII行號Md碼列號46《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第46頁!該編碼方法的優(yōu)點是：壓縮率高，且解壓方便；陣列中各部分的分辨率可變，即可減少存量，又可精確地表示圖形結(jié)構(gòu)，易于進行圖形操作和運算。缺點是：具有相同形狀和大小的多邊形可得出完全不同的編碼，不利于形狀的分析和模式識別。014523678912131011141514121300145236789121310111415014

2367

47《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第47頁!yxoOX0Y0PYpXpII=INT（（Y0-YP）/d）JJ=INT（（XP-X0）/d）II,JJdII=INT（（Y0-YP）/d）JJ=INT（（XP-X0）/d）48《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第48頁!X1，Y1X2，Y2D、將求得的交點柵格化，并將其所在的柵格“賦值”。如圖II1=INT（（Y0-Y1）/d）JJ1=INT（（X1-X0）/d）II1JJ1II2=INT（（Y0-Y2）/d）JJ2=INT（（X2-X0）/d）II2JJ2Y中心線=Y0-II1*d-3/2*dY中心線=Y0-II1*d-5/2*dY中心線=Y0-II1*d-7/2*d49《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第49頁!這里，之所以要分兩種情況處理，是為了使產(chǎn)生的被“賦值的柵格相互連通，避免出現(xiàn)間斷現(xiàn)象50《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第50頁!掃描線開始掃描，當K=1時，為條掃描線其方程為：逐列掃描X=XC=X0+JJ1*d+3/2*dk≤JJ2-JJ1-1？結(jié)束NY求當前掃描線的直線方程：X=XC求掃描線與直線的交點坐標：X=XC；

Y=Y1+（XC-X1）*（Y2-Y1）/（X2-X1）對交點進行柵格化：II=[（Y0-Y）/d]；JJ=[（X-X0）/d]遞進掃描：K=K+1；XC=XC+d51《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第51頁!3、面的柵格化面域的柵格化可分以下幾步進行：步將面域的邊界柵格化用前面介紹的線段柵格化的方法對組成面域的每條邊進行柵格化，如圖：52《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第52頁!第三步配對填充逐行掃描柵格數(shù)據(jù)，從左到右，將每行中的L和R配對，并在每對L-R之間填上代表該多邊形面域的特定色度值。在配對時，可不顧“N”的存在，但在配對填充結(jié)束后，應將剩余的N或R（L）置換成面域灰度值。53《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第53頁!下面介紹幾種矢量向柵格轉(zhuǎn)換的算法：（多邊形填充）*內(nèi)部點擴散算法

該算法由每個多邊形一個內(nèi)部點（種子點）開始，向其八個方向的鄰點擴散，判斷各個新加入點是否在多邊形邊界上，如果是邊界點，則新加入點不作為種子點，否則把非邊界點的鄰點作為新的種子點與原有種子點一起進行新的擴散運算，并將該種子點賦予多邊形的編號。重復上述過程，直到所有種子點填滿多邊形為止。擴散算法程序設(shè)計比較復雜，需要在柵格陣列中進行搜索，占用內(nèi)存大。54《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第54頁!*掃描線法：根據(jù)行（或列）中心線與面邊界的交點，排序，配對，填充。123456當中心掃描線與多邊形相切時，要把切點分成兩個點；當掃描線與某一邊有部分重合時，只記錄重合的起點和終點。以利于配對。圖中有可能成為切點的拐點是①⑤⑥③大家看一看它們有什么特點？55《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第55頁!該算法簡單可靠，而且僅采用加減運算，又不考慮邊界的順序，故運算速度快。**舉一例說明：下行線的左邊為：右多邊形號-左多邊形號上行線的左邊為：左多邊形號-右多邊形號222552255552555525555222222222222222220000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3000033330000333-5-5-5-3-2-2003333-2-200333-2-2-2-5-5-5-3002255552002255522022222222022220222255555550002555500225555200225552202222222202222022220000555000255550022555520022555220222222220222202222000055500025555002255552002255522022222222022220222256《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第56頁!2、線狀柵格數(shù)據(jù)的矢量化通常要分為四個步驟：柵格數(shù)據(jù)的二值化；細化；矢量化；曲線的光滑。57《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第57頁!全彩色灰度二值黑白58《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第58頁!b、最大數(shù)值法(骨架法）利用原始柵格數(shù)據(jù)計算格線交點的V值=四個相鄰柵格灰度值的和，選取V最大的點；如果細化后仍嫌太粗，可將所有最大V值點的灰度值重新賦為1，而將其它V值賦為0，進而再運用本方法進行細化，選取其中最大的V值點；為防止斷線，最后一次取V>2的值點。59《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第59頁!c、剝皮法從曲線的邊緣開始，每次剝掉等于一個柵格寬的一層，直到最后留下連通的由單個柵格點組成的圖形。（不允許剝?nèi)е虑€不連通的柵格）方法：步，從第0行0列開始，逐行（列）尋找灰度值為1的柵格，記錄起始像元的行、列號（i，j）；第二步，以（i，j）為中心，按順時針方向檢測其八方向相鄰的灰度值；60《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第60頁!3若NB=1，則其灰度值記為“3”，它可以被剝?nèi)ト鐖D所示（為什么不直接賦值為“0”？）I，J若NB≥2，則其灰度值記為“2”（Why？），它不可以被剝?nèi)，J第四步，尋找與（I，j）相鄰的邊緣點，按順時針方向跟蹤。新的邊緣點為最后檢測到的灰度為1的像元。11IJ111I+1,J+12I+1，J-161《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第61頁!C、矢量化（常采用跟蹤的方法）：步，逐行(逐列)尋找灰度為1的柵格作為起始柵格；第二步，計算當前所找柵格中心點坐標，并將其柵格值賦為0；第三步，以當前找到的柵格為中心，從上一柵格開始順時針方向判別其八方向相鄰，把首先找到的灰度值為1的像元作為前進的方向上的下一個待處理的像元；第四步，判斷是否檢測到當前柵格的八方向相鄰的灰度值都為0（或已到邊界），若是，則轉(zhuǎn)到步；否則轉(zhuǎn)到第二步。直到跟蹤完為止。62《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第62頁!（3）以（i，j）為中心，順時針方向檢查其八方向相鄰的灰度值，新的邊緣點為最后檢測到的灰度值為1的像元；（4）判斷新的邊緣點是否已跟蹤到了起始像元，若是，則轉(zhuǎn)到第五步；否則轉(zhuǎn)到第二步；（5）對矢量化后的面域進行光滑處理63《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第63頁!具體步驟如下：（1）邊界點和節(jié)點的提取采用2×2柵格對圖像全圖掃描邊界點：如果窗口內(nèi)四個柵格有兩個不同的編號，則為邊界點；并保留各柵格所有多邊形編號；節(jié)點：如果窗口內(nèi)四個柵格有二個以上不同的編號（或?qū)蔷€上柵格兩兩相同的情況）則標識為節(jié)點（不同邊界弧段的圖形不連通），保留各柵格原編號信息;其余的歸零處理。64《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第64頁!abc65《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第65頁!結(jié)點：表示線的終點和起點；節(jié)點：它是兩條或多條連線或鏈的拓撲連結(jié)點拐點：表示線段和弧段的內(nèi)部點（特殊的節(jié)點）。(2)線實體（亦稱為線段、弧、鏈、環(huán)等）線實體是維數(shù)為1的實體，由一系列坐標點表示。特征：實體長度：從起點到終點的總長；彎曲度：用于表示如道路拐彎時彎曲的程度；方向性：如河流從上游到下游，公路有單雙向之分；66《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第66頁!二、地圖數(shù)據(jù)的基本特征地圖數(shù)據(jù)具有空間特征、屬性特征及時間特征。1．空間特征(1)空間位置空間位置用以描述事物或現(xiàn)象的地理位置，又稱幾何特征、定位特征。通常用地理坐標系、平面直角坐標系來表示，也稱幾何特征，包括空間實體的位置、大小、形狀、分布狀況等，表明“在哪里”。(2)空間關(guān)系地理空間實體之間存在的一些具有空間特性的關(guān)系拓撲關(guān)系：拓撲變化下的拓撲不變量，如鄰接關(guān)系、關(guān)聯(lián)關(guān)系和包含關(guān)系等；方位關(guān)系：實體在地理空間中的某種順序，如左右、東南西北等；度量關(guān)系：用地理空間中的度量來描述的實體之間的關(guān)系，如實體之間的距離67《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第67頁!圖2-1：空間數(shù)據(jù)的基本特性[JackDangermond,1984]68《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第68頁!(1)點類型點類型可以描述如城鄉(xiāng)居民地、工廠、學校、醫(yī)院、機關(guān)、車站、山峰、隘口等現(xiàn)象。這里，“點”是一個相對的抽象概念，即從較大的空間規(guī)模上來觀測這些地物，就能把它們都歸結(jié)為點狀分布的地理現(xiàn)象，因此能用一個點的坐標(或柵格像元)來描述其空間位置。而如果從較小的空間尺度上來觀察這些地理現(xiàn)象，它們中的多數(shù)將可以用一個面狀特征來描述。例如同一個城市，在小比例尺地圖上表現(xiàn)為點狀分布，而在大比例尺地圖上則可表現(xiàn)為面狀分布，其內(nèi)部表示了十分詳細的城市街道分布狀況。(2)線類型線類型描述如河流、運河、海岸、鐵路、公路、地下管網(wǎng)、行政邊界等線狀分布的地理現(xiàn)象。這里的“線”(有時也稱“弧”)也是一個相對的抽象概念。它們的空間位置數(shù)據(jù)是一線狀坐標串(或柵格像元集合)。(3)面類型面類型描述如土地、水域、森林、草原、沙漠等具有大范圍連續(xù)(或斷續(xù))面狀分布特征的現(xiàn)象。這里的“面”是一個相對的抽象概念，有時實地上不一定有明顯的邊界。描述面狀特征的空間數(shù)據(jù)是一封閉的面坐標串(或柵格像元集合)，通常稱之為多邊形。69《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第69頁!GIS中各種數(shù)據(jù)以及其表現(xiàn)70《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第70頁!它們之間的相互關(guān)系：鄰接、關(guān)聯(lián)、相交、相離、包含、重合L-SP-SS-SL-LP-L相離相交鄰接重合包含P-P71《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第71頁!第二節(jié)地圖的數(shù)據(jù)結(jié)構(gòu)地圖的數(shù)據(jù)結(jié)構(gòu)主要指地圖數(shù)據(jù)中空間數(shù)據(jù)的結(jié)構(gòu)，是指幾何數(shù)據(jù)以什么形式在計算機中存儲和處理。地圖的數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)一、矢量數(shù)據(jù)結(jié)構(gòu)1、矢量數(shù)據(jù)的概念矢量本身是數(shù)學上的概念運用到地理信息系統(tǒng)中。矢量數(shù)據(jù)結(jié)構(gòu)是表達地圖空間數(shù)據(jù)的一種常見的數(shù)據(jù)結(jié)構(gòu)，72《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第72頁!其中，一維矢量可以閉合，但不能與自身相交。如果相交，則應以交點為界將一維矢量分成幾個一維矢量。如下圖：（一維矢量可能空間關(guān)系）abcd73《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第73頁!（1）簡單數(shù)據(jù)結(jié)構(gòu)及編碼簡單的矢量數(shù)據(jù)結(jié)構(gòu)不考慮拓撲關(guān)系，可用于矢量數(shù)據(jù)的存儲、處理、顯示、輸出以及一般的查詢和檢索。有點、線、面三種基本的矢量數(shù)據(jù)結(jié)構(gòu)形式。①點數(shù)據(jù)結(jié)構(gòu)形式標志碼屬性碼（x，y）標志碼屬性碼標志碼（x，y）+或標志碼具有唯一性，是按某種原則進行的編碼（如順序）屬性碼是與點有關(guān)的基本屬性的編碼，可有多個。（x，y）是定位坐標74《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第74頁!③面（多邊形）數(shù)據(jù)結(jié)構(gòu)形式常見的兩種形式標志碼屬性碼坐標對數(shù)n坐標串（x1，y1）……（x1，y1）標志碼屬性碼弧段數(shù)n弧段標志碼集弧段標志碼01坐標對數(shù)n坐標串（x1，y1）……弧段標志碼n坐標對數(shù)m坐標串（x1，y1）…………有N個這種方法可能會產(chǎn)生大量的數(shù)據(jù)冗余這種方法保證了多邊形公共邊的唯一性75《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第75頁!對面狀實體而言，最末一點的坐標與點相等。使用這種方法時，除了外輪廓線以外，多邊形的邊界線數(shù)據(jù)均獲取和存儲兩次，這就會產(chǎn)生重疊或列隙（當取值誤差時），并產(chǎn)生數(shù)據(jù)冗余。為了消除裂縫，需要二次編輯。②點位字典法以公用點位字典為基礎(chǔ)建立一些系統(tǒng)，這克服了獨立實體編碼的某些局限性。點位字典包含地圖上每一個邊界點的坐標，然后建立點、線、面的邊界表，它們由點位序號構(gòu)成。即：點位字典表：點號、坐標（X，Y）點實體：標志碼，地物編碼，點號線實體：標志碼，地物編碼，（點號1，……點號n）面實體：標志碼，地物編碼，（點號1，……點號n，點號1）76《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第76頁!ABC12345678點號坐標數(shù)據(jù)項01X1，Y102X2，Y203X3，Y304X4，Y405X5，Y506X6，Y607X7，Y708X8，Y8點位字典表多邊形地物編碼點號AT3011，2，3，7BT3021，7，3，6，5，8CT3053，4，5，6點位字典表編碼77《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第77頁!鄰接——相同拓撲元素之間的關(guān)系如節(jié)點與節(jié)點、鏈與鏈、面與面等。鄰接關(guān)系是借助于不同類型的拓撲元素描述的，如點通過鏈而鄰接；線通過點而鄰接；面通過點線而鄰接關(guān)聯(lián)——是不同拓撲元素之間的關(guān)系P1P2L1L2S1S2L1L2L3P1S1S2L1L2L3包含——是面與其它拓撲元素之間的關(guān)系如點、線、面在某面內(nèi)78《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第78頁!N1N2N3N4N5N6N7A1A2A3A4A5A6A7A8A9A10B1B2B3B4B5B1B2B3B4B5A1A2A3A4A5A6A7A8A9A10N1N2N3N4N5N6N7面弧點79《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第79頁!“-”表示面中含有島80《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第80頁!雖然建立拓撲關(guān)系比較麻煩，但這種關(guān)系一旦建立，就為數(shù)據(jù)的采集、圖形編輯和維護數(shù)據(jù)的一致性提供了大大的方便。反之還可利用共享數(shù)據(jù)來進行拓撲編輯。這種拓撲編輯，不但保證數(shù)字化原始數(shù)據(jù)的自動查錯，而且可以自動形成封閉的多邊形邊界，為由各個單獨存儲的弧段組成所需要的各類多邊形及建立空間數(shù)據(jù)庫奠定基礎(chǔ)。具體算法如下：A、多邊形連接編輯例如需要對多邊形B1進行編輯，其算法過程為：從（弧—點、面文件）中，檢索出與當前編輯的多邊形B1相關(guān)的所有記錄81《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第81頁!*在檢出的記錄中，檢查當前編輯的多邊形B1所處的位置：如果B1位在左，將之與右相交換，同時也將該記錄的節(jié)點位置作相應的變換，如果B1位在右，則所有數(shù)據(jù)記錄不作改變。按上要求則檢出的記錄應變?yōu)椋?從轉(zhuǎn)換的記錄中，任取一個節(jié)點為起點，按順連接，使其能暢通并閉合。如果不能閉合或記錄缺損或多余，說明文件有錯，必須修改。82《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第82頁!如果首尾不能響應，或有缺損或多余，則表明文件有錯，須改正，才能將其用于節(jié)點文件和多邊形文件的自動生成以及數(shù)據(jù)庫的建立。83《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第83頁!地物類編碼表：地物類碼+地物名+制圖符號碼+屬性表名等。如下表：84《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第84頁!④拓撲關(guān)系：如前所講用節(jié)點、弧段、面塊相互之間的關(guān)聯(lián)拓撲關(guān)系表表達出來。

記錄拓撲關(guān)系的編碼方法有多種，常見的有：*雙重獨立地圖編碼（DualIndependentMapEncoding,DIME）：節(jié)點坐標表+弧——點、面拓撲關(guān)系表+屬性特征表它最早是以城市街道為編碼的主體最早是美國人口統(tǒng)計系統(tǒng)采用的一種編碼方法。85《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第85頁!建立拓撲的算法如下：（1）得到條弧段A，并設(shè)置為當前弧段；（2）判斷PL(A)和PR(A)是否為空。如果都非空，轉(zhuǎn)到步，當所有弧段處理完畢后，算法結(jié)束；（3）如果左多邊形為空，則創(chuàng)建一個新的多邊形P，多邊形的條弧段為當前弧段，并設(shè)置PL(A)=P，設(shè)置搜尋起始節(jié)點為Ns(A)，搜尋當前節(jié)點為NE(A)。如果右多邊形為空，則創(chuàng)建一個新的多邊形P，多邊形的條弧段為當前弧段，并設(shè)置PR(A)=P，設(shè)置搜尋起始節(jié)點N0=NE(A)，搜尋當前節(jié)點NC=NS(A)。（4）判斷N0和NC是否相等，如果是，則多邊形所有弧段都已經(jīng)找到，轉(zhuǎn)到步。（5）檢查與當前節(jié)點相連接的、已經(jīng)排列好的弧段序列，將當前弧段的下一條弧段A'作為多邊形的第二條弧段。（6）如果NC=NS(A')，設(shè)置PL(A')=P，NC=NE(A)；如果NC=NE(A')，設(shè)置PR(A')=P，NC=NS(A)，轉(zhuǎn)到第四步。如圖2-4-c所示，如果從弧段4開始搜尋，找到節(jié)點C后，根據(jù)弧段的排序，下一條弧段是2；然后找到節(jié)點A，弧段1，整個搜尋結(jié)束，建立多邊形I，其組成弧段為4、2、1。按照這種算法，生成多邊形的弧段從多邊形內(nèi)部看，是逆時針排列的。如果節(jié)點弧段排序為順時針，則算法中用PL(A)代替PR(A)，用PR(A)代替PL(A)，生成的多邊形弧段是順時針排列的。86《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第86頁!圖2-5：帶“島”的多邊形建立拓撲的結(jié)果

多邊形拓撲的建立，要注意多邊形帶“島”的情況，按照上述算法，對于帶“島”的多邊形，或者稱為環(huán)，其包含的弧段構(gòu)成了多個閉合曲線，并且“島”的弧段排序是順時針的（圖2-5）（實際上，從環(huán)狀多邊形內(nèi)部看，它仍然是逆時針的）。87《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第87頁!點號地物類碼坐標N1T101X1，Y1N2T102X2，Y2………………節(jié)點坐標表88《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第88頁!弧坐標表：標志碼+地物類碼+弧上的節(jié)點弧段表：標志碼+地物類碼+起點+終點+左多邊形+右多邊形+內(nèi)點（指向中間的指針）弧坐標表、弧段表可以合并如下：89《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第89頁!綜上所述，為了將空間數(shù)據(jù)存入計算機：首先，將空間數(shù)據(jù)抽象為不同的專題（或圖層）；其次，將專題層抽象成不同的類型；第三，將某一類型中的地理要素或?qū)嶓w分解為點、線、面狀目標；第四，每個目標數(shù)據(jù)由定位數(shù)據(jù)（坐標）+拓撲數(shù)據(jù)+屬性數(shù)據(jù)組成。這樣具有相同分類碼的目標組成類型；多個相關(guān)聯(lián)的類型構(gòu)成專題層；若干個專題層構(gòu)成圖幅；全部數(shù)據(jù)組成數(shù)據(jù)庫。90《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第90頁!二、柵格數(shù)據(jù)結(jié)構(gòu)1、柵格數(shù)據(jù)的概念柵格數(shù)據(jù)：是由二維平面表像對應位置上像元灰度值所組成的陣列形式的數(shù)據(jù)。對柵格數(shù)據(jù)的有關(guān)說明A、像元（像素）：將地圖制圖區(qū)域的二維平面按行和列作規(guī)則劃分，形成一個柵格陣列，其中各柵格陣列元素就是像元（像素）。91《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第91頁!柵格數(shù)據(jù)的表示方法點——用一個柵格表示；線——用沿其走向的一組相鄰柵格表示面——用其所覆蓋的相鄰柵格的集合表示92《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第92頁!有關(guān)相鄰柵格單元四方向相鄰八方向相鄰一般講，四方向相鄰的柵格圖形線畫顯得粗壯，但階梯（鋸齒）明顯；而八方向相鄰的柵格圖形顯得平滑圓潤。93《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第93頁!直接柵格編碼方法：AAAAABBBAABBAABB方法一：逐行從左向右AAAAABBBAABBAABBAAAAABBBAABBAABB方法二：奇數(shù)行從左向右，偶數(shù)行從右向左AAAABBBAAABBBBAA94《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第94頁!①鏈碼（又稱Freeman碼、邊界碼）主要用記錄線狀地物或面狀地物的邊界:由某一起點和一系列在基本方向上的單位矢量組成。單位矢量的長度默認為一個柵格單元，每個后續(xù)點可能位于其前繼點的8個基本方向之一。前兩個數(shù)字表示起點的行列號，從第三個數(shù)字開始是每個后續(xù)點的單位矢量方向95《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第95頁!②游程碼逐行將相鄰同值的網(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度。游程編碼結(jié)構(gòu)的建立方法ABC原始地面ABC柵格化柵格數(shù)據(jù)矩陣96《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第96頁!柵格數(shù)據(jù)矩陣B逐行混合編碼A，6A，5，C，1A，4，C，2B，4，C，2B，4，C，2B，3，C，3代碼，個數(shù)97《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第97頁!方法二：屬性值（屬性代碼）+位置A逐行單獨編碼柵格數(shù)據(jù)矩陣行號屬性值列號61，A，652，A，562，C，643，A，463，C，644，B，464，C，645，B，465，C，636，B，366，C，698《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第98頁!C串行點號編碼（序號）屬性值(游程終)點號10A,1011C,1115A,1517C,1721B,2123C,2327B,2729C,2932B,3235C,3599《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第99頁!③塊碼塊式編碼是將游程編碼擴大到二維的情況，把多邊形范圍分成由像元組成的正方形，然后對各個正方形進行編碼。編碼原則：行號、列號、邊長、屬性代碼采用這種結(jié)構(gòu)，如果一個多邊形所能包含的正方形越大，邊界越簡單，效果越好。面積計算具有明顯的優(yōu)勢。100《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第100頁!四叉樹結(jié)構(gòu)上面我們討論了塊式編碼，現(xiàn)在我們反過來想一想，當我們把一幅圖柵格化的時候，能不能把屬性一致的區(qū)域的柵格單元作大一些，而在有細節(jié)的區(qū)域的柵格單元作小一些，從而使存儲的數(shù)據(jù)少一些呢？答案是可以的。這種思路可用四叉樹編碼來實現(xiàn)。四叉樹編碼的基本思想:首先把一幅圖像或柵格地圖等分成四部分，逐塊檢查其格網(wǎng)值，如果某個格的所有值相同，則這個格就不再往下分割；否則，把它再分割成四個子區(qū)域，這樣直到每個子塊都只含有相同的屬性值為止。101《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第101頁!上面稱為“top-down”的從上而下的分割方法，這種方法速度較慢，且有大量重復檢查才能確定劃分，如圖中的7、8、9區(qū)域需要檢查4次。常規(guī)四叉樹也可以采用“bottom-up”的方式，對柵格數(shù)據(jù)按一定順序進行檢測，如果每相鄰四個格網(wǎng)值相同，則進行合并，逐次往上遞歸。這種方式，速度較快。102《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第102頁!線性四叉樹基本思想：不記錄中間節(jié)點，不需要指針，只存儲最后葉結(jié)點信息，包括結(jié)點的位置（地址）、屬性值。線性四叉樹葉結(jié)點的編號需要遵照一定的規(guī)則，這種編號稱為地址碼，隱含了葉結(jié)點的位置信息。最常用的地址碼是四進制或十進制的Morton碼。103《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第103頁!第二步：Morton碼MQ=2·Ib+JbJJ01234567Jb00011011100101110111IIIb0000000010100111001011101111010020030120131021031121132100200210300311201211301313110220230320331221231321334100200201210211300301310311510120220321221330230331231361102202212302313203213303317111222223232233322323332333104《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第104頁!JJ01234567Jb00011011100101110111IIIb000000001010011100101110111101002003012013102103112113210020021030031120121130131311022023032033122123132133410020020121021130030131031151012022032122133023033123136110220221230231320321330331711122222323223332232333233301MQ屬性值00000010002000300100011001200130020002100220023003000310032003301000101010201030105《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第105頁!106《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第106頁!例如：II=5JJ=5Ib=101Jb=101Md=（110011）2Md=51107《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第107頁!二維游程編碼結(jié)構(gòu)我們注意到，在生成的線性四叉樹結(jié)構(gòu)表中雖然我們對數(shù)據(jù)進行了壓縮，但仍存在前后結(jié)點值相同的情況，因而可以采取進一步的壓縮表達，即將屬性值相同的前后結(jié)點合并成一個值，形成一個線性表列。其記錄規(guī)則：先記錄入口地址和格網(wǎng)值，依次掃描線性表，若后一格網(wǎng)的值與前一格網(wǎng)值不同，記錄后一格網(wǎng)的地址和格網(wǎng)值，可直接形成線性表。這種記錄方法，非常類似于傳統(tǒng)的一維行程編碼，所以也稱為二維游程編碼108《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第108頁!第二步：確定十進制線性四叉樹表0145236789121310111415屬性值1014121513084第三步：二維行程編碼1412130109《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第109頁!第三節(jié)矢量、柵格轉(zhuǎn)換矢柵的相互轉(zhuǎn)換，一直是地理信息系統(tǒng)的技術(shù)難題之一。一、矢量格式向柵格格式轉(zhuǎn)換矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)也稱柵格化，其目的在于方便地進行空間分析，因為柵格數(shù)據(jù)對于多要素的重疊操作運算較矢量數(shù)據(jù)容易實現(xiàn)。習慣上，在矢量數(shù)據(jù)中，點的坐標用（X，Y）來表示，而在柵格數(shù)據(jù)中，點的坐標用點所在柵格的行列號（I，J）來表示。1、點的柵格化將點P的矢量坐標（XP，YP）換算成柵格的行、列號（II，JJ）110《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第110頁!2、線段的柵格化線段柵格化步驟如下：A、兩端點柵格化B、求出這兩個端點位置的行數(shù)差和列數(shù)差：行數(shù)差=II2-II1、列數(shù)差=JJ2-JJ1C、計算直線與柵格中心線的交點坐標若行數(shù)差≥列數(shù)差，則逐行求出本行中心線與已知直線的交點坐標111《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第111頁!若行數(shù)差＜列數(shù)差，則逐列求出本列中心線與已知直線的交點坐標：將求得的交點柵格化，并將其所在的柵格“賦值”。X1,y1X2,y2112《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第112頁!具體編程思路如下開始直線兩端點柵格化II1=[（Y0-Y1）/d]；JJ1=[（X0-X1）/d]II2=[（Y0-Y2）/d]；JJ2=[（X0-X2）/d]計算兩端點的行數(shù)差和列數(shù)差行數(shù)差R=II2-II1；列數(shù)差C=JJ2-JJ1Y=Y1+（X-X1）*（Y2-Y1）/（X2-X1）建立直線方程：R≥C？YN逐行處理逐列處理113《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第113頁!掃描線開始掃描，當K=1時，為條掃描線其方程為：逐行掃描Y=YC=Y0-II1*d-3/2*dk≤II2-II1-1？結(jié)束NY求當前掃描線的直線方程：Y=YC求掃描線與直線的交點坐標：Y=YC；

X=X1+（YC-Y1）*（X2-X1）/（Y2-Y1）對交點進行柵格化：II=[（Y0-Y）/d]；JJ=[（X-X0）/d]遞進掃描：K=K+1；YC=YC-d114《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第114頁!RRNRRRNRNNNRNNNLNNRNRNNNNNNNNNNNNLLNLLLLL第二步對各個柵格像元加標記上升像元標上“L”，下降像元被標上“R”，平坦處或升降變換處的像元被標上“N”，為了反映面域的拓撲關(guān)系，可約定，面域的外廓按順時針方向組織數(shù)據(jù)，內(nèi)廓按逆時針方向組織數(shù)據(jù)。115《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第115頁!LLLLLNLLNNNNNNNNRNRNNNNNNLNNNRNNNRNRRRNRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR116《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第116頁!117《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第117頁!*邊界代數(shù)算法（BoundaryAlgebraFilling—BAF)：是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換的算法?；舅枷耄合葘⑦吔邕M行柵格化；對每幅地圖的全部具有左右多邊形編號的邊界弧段，沿其前進方向逐個搜索，當邊界上行時，將邊界線位置與左圖框之間的網(wǎng)格加上一個值=（左多邊形編號）-（右多邊形編號）；當邊界下行時，將邊界線位置與左圖框之間的網(wǎng)格加上一個值=（右多邊形編號）-（左多邊形編號）；而不管邊界線的排列順序。118《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第118頁!二、柵格向矢量的轉(zhuǎn)換轉(zhuǎn)換的目的：將柵格數(shù)據(jù)分析的結(jié)果，通過矢量繪圖裝置輸出；為了數(shù)據(jù)壓縮；將自動掃描儀獲取的柵格數(shù)據(jù)加入矢量形式的數(shù)據(jù)庫。轉(zhuǎn)換方法：1、點的矢量化對于任意一個柵格點P而言，其轉(zhuǎn)換公式為119《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第119頁!為了便于進行柵格數(shù)據(jù)向矢量數(shù)據(jù)的轉(zhuǎn)換，需要對原始柵格圖像進行二值化處理，因為太多的灰度級不便于進行矢量化處理。A、二值化二值化處理就是將柵格數(shù)據(jù)壓縮到只有黑白兩個灰度級0或1的圖像。（原圖可能是彩色的，或0~255級灰度級）設(shè)在原柵格數(shù)據(jù)（G（I，J））的灰度區(qū)間[Lmin，Lmax]，設(shè)定一閾值（Lt）∈[Lmin，Lmax]，二值化后的B（I，J）為：＜120《地圖數(shù)據(jù)結(jié)構(gòu)》課件共128頁，您現(xiàn)在瀏覽的是第120頁!B、柵格數(shù)據(jù)的細化將要素占有的網(wǎng)格集縮減成為具有單網(wǎng)格寬的網(wǎng)格集的過程（使得每一條線只保留代表其軸線的位置的單個柵格的寬度）。a、經(jīng)典的細化算法通過3×3的柵格像元陣來確定如何細化：凡是去掉后