第六章 空間數(shù)據(jù)管理

1、.空間數(shù)據(jù)管理空間數(shù)據(jù)管理 本章首先介紹空間數(shù)據(jù)庫、與一般數(shù)據(jù)庫的比本章首先介紹空間數(shù)據(jù)庫、與一般數(shù)據(jù)庫的比較，以及空間數(shù)據(jù)庫的存儲方式。較，以及空間數(shù)據(jù)庫的存儲方式。然后介紹了然后介紹了GIS中兩種重要的數(shù)據(jù)結(jié)構(gòu)：柵格結(jié)中兩種重要的數(shù)據(jù)結(jié)構(gòu)：柵格結(jié)構(gòu)和矢量結(jié)構(gòu)，以及其具體的存儲方式，然后構(gòu)和矢量結(jié)構(gòu)，以及其具體的存儲方式，然后比較了兩種結(jié)構(gòu)的特點，并給出了其相互轉(zhuǎn)換比較了兩種結(jié)構(gòu)的特點，并給出了其相互轉(zhuǎn)換算法。算法。最后介紹了空間檢索中常用的技術(shù)最后介紹了空間檢索中常用的技術(shù)空間索空間索引，介紹了一些常用的空間索引方式，如引，介紹了一些常用的空間索引方式，如BSP樹、樹、R樹、樹、CELL樹

2、等；以及空間數(shù)據(jù)的查詢功能。樹等；以及空間數(shù)據(jù)的查詢功能。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.1地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較(一一)兩者區(qū)別兩者區(qū)別 1）在硬件上）在硬件上，為了處理圖形和圖像數(shù)據(jù)，系統(tǒng)，為了處理圖形和圖像數(shù)據(jù)，系統(tǒng)需要配置專門的輸入和輸出設(shè)備，如數(shù)字化儀、需要配置專門的輸入和輸出設(shè)備，如數(shù)字化儀、繪圖機、圖形圖像的顯示設(shè)備等；許多野外實地繪圖機、圖形圖像的顯示設(shè)備等；許多野外實地采集和臺站的觀測所得到的資源信息是模擬量形采集和臺站的觀測所得到的資源信息是模擬量形式，系統(tǒng)還需要配置模式，系統(tǒng)還需要配置模數(shù)轉(zhuǎn)換設(shè)備，這些設(shè)數(shù)轉(zhuǎn)換設(shè)備，這些設(shè)備

3、往往超過中央處理機的價格，體積也比較大。備往往超過中央處理機的價格，體積也比較大。2）在軟件上）在軟件上，則要求研制專門的圖形和圖像數(shù)，則要求研制專門的圖形和圖像數(shù)據(jù)的分析算法和處理軟件，這些算法和軟件又直據(jù)的分析算法和處理軟件，這些算法和軟件又直接和數(shù)據(jù)的結(jié)構(gòu)及數(shù)據(jù)庫的管理方法有關(guān)。接和數(shù)據(jù)的結(jié)構(gòu)及數(shù)據(jù)庫的管理方法有關(guān)。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.1地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較3）在信息處理的內(nèi)容和采用目的方面）在信息處理的內(nèi)容和采用目的方面，一般的，一般的管理信息系統(tǒng)，主要是查詢檢索和統(tǒng)計分析，處管理信息系統(tǒng)，主要是查詢檢索和統(tǒng)計分析，處理的結(jié)

4、果，大多是制成某種規(guī)定格式的表格數(shù)據(jù)，理的結(jié)果，大多是制成某種規(guī)定格式的表格數(shù)據(jù)，而地理信息系統(tǒng)，除了基本的信息檢索和統(tǒng)計分而地理信息系統(tǒng)，除了基本的信息檢索和統(tǒng)計分析外，主要用于分析研究資源的合理開發(fā)利用，析外，主要用于分析研究資源的合理開發(fā)利用，制定區(qū)域發(fā)展規(guī)劃，地區(qū)的綜合治理方案，對環(huán)制定區(qū)域發(fā)展規(guī)劃，地區(qū)的綜合治理方案，對環(huán)境進行動態(tài)的監(jiān)視和預(yù)測預(yù)報，為國民經(jīng)濟建設(shè)境進行動態(tài)的監(jiān)視和預(yù)測預(yù)報，為國民經(jīng)濟建設(shè)中的決策提供科學依據(jù)，為生產(chǎn)實踐提供信息和中的決策提供科學依據(jù)，為生產(chǎn)實踐提供信息和指導。指導。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.1地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較地理信息系統(tǒng)與一般

5、管理信息系統(tǒng)的比較(二二)兩者共同處兩者共同處兩者都是以計算機為核心的信息處理系統(tǒng)，都具兩者都是以計算機為核心的信息處理系統(tǒng)，都具有數(shù)據(jù)量大和數(shù)據(jù)之間關(guān)系復雜的特點，也都隨有數(shù)據(jù)量大和數(shù)據(jù)之間關(guān)系復雜的特點，也都隨著數(shù)據(jù)庫技術(shù)的發(fā)展在不斷的改進和完善。比較著數(shù)據(jù)庫技術(shù)的發(fā)展在不斷的改進和完善。比較起來，商用的管理信息系統(tǒng)發(fā)展快，用戶數(shù)量大，起來，商用的管理信息系統(tǒng)發(fā)展快，用戶數(shù)量大，而且已有定型的軟件產(chǎn)品可供選用，這也促進了而且已有定型的軟件產(chǎn)品可供選用，這也促進了軟件系統(tǒng)的標準化。地理信息系統(tǒng)，由于上述一軟件系統(tǒng)的標準化。地理信息系統(tǒng)，由于上述一些特點，多是根據(jù)具體的應(yīng)用要求專門設(shè)計，數(shù)些特

6、點，多是根據(jù)具體的應(yīng)用要求專門設(shè)計，數(shù)據(jù)格式和組織管理方法各不相同。據(jù)格式和組織管理方法各不相同。 .1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.2空間數(shù)據(jù)庫空間數(shù)據(jù)庫(一一) 數(shù)據(jù)庫概念數(shù)據(jù)庫概念數(shù)據(jù)庫就是為一定目的服務(wù)，以特定的數(shù)據(jù)存儲的相關(guān)數(shù)據(jù)庫就是為一定目的服務(wù)，以特定的數(shù)據(jù)存儲的相關(guān)聯(lián)的數(shù)據(jù)集合，它是數(shù)據(jù)管理的高級階段，是從文件管聯(lián)的數(shù)據(jù)集合，它是數(shù)據(jù)管理的高級階段，是從文件管理系統(tǒng)發(fā)展而來的。理系統(tǒng)發(fā)展而來的。地理信息系統(tǒng)的數(shù)據(jù)庫（簡稱空間地理信息系統(tǒng)的數(shù)據(jù)庫（簡稱空間數(shù)據(jù)庫或地理數(shù)據(jù)庫）是某一區(qū)域內(nèi)關(guān)于一定地理要素數(shù)據(jù)庫或地理數(shù)據(jù)庫）是某一區(qū)域內(nèi)關(guān)于一定地理要素特征的數(shù)據(jù)集合。特征的數(shù)據(jù)集合。

7、數(shù)據(jù)庫數(shù)據(jù)庫圖書館圖書館數(shù)據(jù)數(shù)據(jù)圖書圖書數(shù)據(jù)模型數(shù)據(jù)模型書卡編目書卡編目數(shù)據(jù)的物理組織數(shù)據(jù)的物理組織圖書存放規(guī)則、書架圖書存放規(guī)則、書架數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)圖書管理員圖書管理員外存外存書庫書庫用戶用戶讀者讀者數(shù)據(jù)存取數(shù)據(jù)存取圖書借閱圖書借閱.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.2空間數(shù)據(jù)庫空間數(shù)據(jù)庫(一一) 空間數(shù)據(jù)庫特點空間數(shù)據(jù)庫特點數(shù)據(jù)量特別大；數(shù)據(jù)量特別大；不僅有地理要素的屬性數(shù)據(jù)（與一般數(shù)據(jù)庫不僅有地理要素的屬性數(shù)據(jù)（與一般數(shù)據(jù)庫中的數(shù)據(jù)性質(zhì)相似），還有大量的空間數(shù)據(jù)；中的數(shù)據(jù)性質(zhì)相似），還有大量的空間數(shù)據(jù)；數(shù)據(jù)應(yīng)用廣泛；數(shù)據(jù)應(yīng)用廣泛；.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.2空間數(shù)據(jù)庫空間數(shù)據(jù)

8、庫(三三)數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)（數(shù)據(jù)庫管理系統(tǒng)（Database Management System，DBMS）是在文件處理系統(tǒng)的基礎(chǔ)上）是在文件處理系統(tǒng)的基礎(chǔ)上進一步發(fā)展的系統(tǒng)。進一步發(fā)展的系統(tǒng)。DBMS在用戶應(yīng)用程序和在用戶應(yīng)用程序和數(shù)據(jù)文件之間起到了橋梁作用數(shù)據(jù)文件之間起到了橋梁作用。DBMS的最大的最大優(yōu)點是提供了兩者之間的數(shù)據(jù)獨立性，即應(yīng)用優(yōu)點是提供了兩者之間的數(shù)據(jù)獨立性，即應(yīng)用程序訪問數(shù)據(jù)文件時，不必知道數(shù)據(jù)文件的物程序訪問數(shù)據(jù)文件時，不必知道數(shù)據(jù)文件的物理存儲結(jié)構(gòu)。當數(shù)據(jù)文件的存儲結(jié)構(gòu)改變時，理存儲結(jié)構(gòu)。當數(shù)據(jù)文件的存儲結(jié)構(gòu)改變時，不必改變應(yīng)用程序。不必改變

9、應(yīng)用程序。 .1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.2空間數(shù)據(jù)庫空間數(shù)據(jù)庫1)采用標準采用標準DBMS存儲空間數(shù)據(jù)的主要問題存儲空間數(shù)據(jù)的主要問題 GIS中空間數(shù)據(jù)記錄是變長的，且要存儲和維護空間中空間數(shù)據(jù)記錄是變長的，且要存儲和維護空間數(shù)據(jù)拓撲關(guān)系；數(shù)據(jù)拓撲關(guān)系；DBMS一般都難以實現(xiàn)對空間數(shù)據(jù)的關(guān)聯(lián)、連通、包一般都難以實現(xiàn)對空間數(shù)據(jù)的關(guān)聯(lián)、連通、包含、疊加等基本操作。含、疊加等基本操作。GIS需要一些復雜的圖形功能，一般的需要一些復雜的圖形功能，一般的DBMS不能支不能支持；持；地理信息是復雜的，單個地理實體的表達需要多個文地理信息是復雜的，單個地理實體的表達需要多個文件、多條記錄、或許包括大地網(wǎng)、

10、特征坐標、拓撲關(guān)系、件、多條記錄、或許包括大地網(wǎng)、特征坐標、拓撲關(guān)系、空間特征量測值、屬性數(shù)據(jù)的關(guān)鍵字以及非空間專題屬空間特征量測值、屬性數(shù)據(jù)的關(guān)鍵字以及非空間專題屬性等；性等； 具有高度內(nèi)部聯(lián)系的具有高度內(nèi)部聯(lián)系的GIS數(shù)據(jù)記錄需要更復雜的安全數(shù)據(jù)記錄需要更復雜的安全性維護系統(tǒng)性維護系統(tǒng)。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.2空間數(shù)據(jù)庫空間數(shù)據(jù)庫2)GIS數(shù)據(jù)管理方法主要數(shù)據(jù)管理方法主要4種類型種類型 對不同的應(yīng)用模型開發(fā)獨立的數(shù)據(jù)管理服務(wù)，這是對不同的應(yīng)用模型開發(fā)獨立的數(shù)據(jù)管理服務(wù)，這是一種基于文件管理的處理方法。一種基于文件管理的處理方法。 在商業(yè)化的在商業(yè)化的DBMS基礎(chǔ)上開發(fā)附加系統(tǒng)。開發(fā)

11、一個基礎(chǔ)上開發(fā)附加系統(tǒng)。開發(fā)一個附加軟件用于存儲和管理空間數(shù)據(jù)和空間分析，使附加軟件用于存儲和管理空間數(shù)據(jù)和空間分析，使用用DBMS管理屬性數(shù)據(jù)。管理屬性數(shù)據(jù)。 使用現(xiàn)有的使用現(xiàn)有的DBMS，通常是以，通常是以DBMS為核心，對系統(tǒng)為核心，對系統(tǒng)的功能進行必要擴充，空間數(shù)據(jù)和屬性數(shù)據(jù)在同一的功能進行必要擴充，空間數(shù)據(jù)和屬性數(shù)據(jù)在同一個個DBMS管理之下。需要增加足夠數(shù)量的軟件和功管理之下。需要增加足夠數(shù)量的軟件和功能來提供空間功能和圖形顯示功能。能來提供空間功能和圖形顯示功能。 重新設(shè)計一個具有空間數(shù)據(jù)和屬性數(shù)據(jù)管理和分析重新設(shè)計一個具有空間數(shù)據(jù)和屬性數(shù)據(jù)管理和分析功能的數(shù)據(jù)庫系統(tǒng)。功能的數(shù)據(jù)

12、庫系統(tǒng)。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織 (一一)數(shù)據(jù)組織分級數(shù)據(jù)組織分級p數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項是可以定義數(shù)據(jù)的最小單位，也叫元素、基本項、數(shù)據(jù)項是可以定義數(shù)據(jù)的最小單位，也叫元素、基本項、字段等，數(shù)據(jù)項與現(xiàn)實世界實體的屬性相對應(yīng)，數(shù)據(jù)項字段等，數(shù)據(jù)項與現(xiàn)實世界實體的屬性相對應(yīng)，數(shù)據(jù)項有一定的取值范圍，稱為域，域以外的任何值對該數(shù)據(jù)有一定的取值范圍，稱為域，域以外的任何值對該數(shù)據(jù)項都是無意義的。項都是無意義的。p記錄記錄記錄是由若干相關(guān)聯(lián)的數(shù)據(jù)項組成，是處理和存儲信息記錄是由若干相關(guān)聯(lián)的數(shù)據(jù)項組成，是處理和存儲信息的基本單位，是關(guān)于一個實體的數(shù)據(jù)總和，構(gòu)成該記錄的基本

13、單位，是關(guān)于一個實體的數(shù)據(jù)總和，構(gòu)成該記錄的數(shù)據(jù)項表示實體的若干屬性。為了唯一標識每個記錄，的數(shù)據(jù)項表示實體的若干屬性。為了唯一標識每個記錄，就必須有記錄標識符，也叫關(guān)鍵字。記錄標識符一般由就必須有記錄標識符，也叫關(guān)鍵字。記錄標識符一般由記錄中的第一個數(shù)據(jù)項擔任，唯一標識記錄的關(guān)鍵字稱記錄中的第一個數(shù)據(jù)項擔任，唯一標識記錄的關(guān)鍵字稱主關(guān)鍵字，其它標識記錄的關(guān)鍵字稱為輔關(guān)鍵字。主關(guān)鍵字，其它標識記錄的關(guān)鍵字稱為輔關(guān)鍵字。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織p文件文件文件是一給定類型的（邏輯）記錄的全部具體值的文件是一給定類型的（邏輯）記錄的全部具體值的集合，文件用文件名稱

14、標識，文件根據(jù)記錄的組織集合，文件用文件名稱標識，文件根據(jù)記錄的組織方式和存取方法可以分為：順序文件、索引文件、方式和存取方法可以分為：順序文件、索引文件、直接文件和倒排文件等。直接文件和倒排文件等。p數(shù)據(jù)庫數(shù)據(jù)庫數(shù)據(jù)庫是比文件更大的數(shù)據(jù)組織，數(shù)據(jù)庫是具有特數(shù)據(jù)庫是比文件更大的數(shù)據(jù)組織，數(shù)據(jù)庫是具有特定聯(lián)系的數(shù)據(jù)的集合，也可以看成是具有特定聯(lián)系定聯(lián)系的數(shù)據(jù)的集合，也可以看成是具有特定聯(lián)系的多種類型的記錄的集合。數(shù)據(jù)庫的內(nèi)部構(gòu)造是文的多種類型的記錄的集合。數(shù)據(jù)庫的內(nèi)部構(gòu)造是文件的集合，這些文件之間存在某種聯(lián)系，不能孤立件的集合，這些文件之間存在某種聯(lián)系，不能孤立存在。存在。 .1.空間數(shù)據(jù)庫空間

15、數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織(二二)數(shù)據(jù)間的邏輯聯(lián)系數(shù)據(jù)間的邏輯聯(lián)系 數(shù)據(jù)間的邏輯聯(lián)系主要是指記錄與記錄之間的數(shù)據(jù)間的邏輯聯(lián)系主要是指記錄與記錄之間的聯(lián)系聯(lián)系。記錄是表示現(xiàn)實世界中的實體的。實體。記錄是表示現(xiàn)實世界中的實體的。實體之間存在著一種或多種聯(lián)系，這樣的聯(lián)系必然之間存在著一種或多種聯(lián)系，這樣的聯(lián)系必然要反映到記錄之間的聯(lián)系上來。數(shù)據(jù)之間的邏要反映到記錄之間的聯(lián)系上來。數(shù)據(jù)之間的邏輯聯(lián)系主要有三種：輯聯(lián)系主要有三種：一對一的聯(lián)系；一對多的一對一的聯(lián)系；一對多的聯(lián)系；多對多的聯(lián)系聯(lián)系；多對多的聯(lián)系。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織(三三)常用數(shù)據(jù)文件

16、常用數(shù)據(jù)文件文件組織主要指數(shù)據(jù)記錄在外存設(shè)備上的組織，文件組織主要指數(shù)據(jù)記錄在外存設(shè)備上的組織，它由操作系統(tǒng)它由操作系統(tǒng)OS進行管理，具體講在外存設(shè)備進行管理，具體講在外存設(shè)備上如何安排數(shù)據(jù)和組織數(shù)據(jù)，以及實施對數(shù)據(jù)上如何安排數(shù)據(jù)和組織數(shù)據(jù)，以及實施對數(shù)據(jù)的訪問方式等問題。操作系統(tǒng)實現(xiàn)的文件組織的訪問方式等問題。操作系統(tǒng)實現(xiàn)的文件組織方式，可以分為方式，可以分為順序文件、索引文件、直接文順序文件、索引文件、直接文件和倒排文件件和倒排文件。.1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織p順序文件順序文件是最簡單的文件組織形式，對記錄按照主關(guān)鍵是最簡單的文件組織形式，對記錄按照主關(guān)鍵

17、字的順序進行組織。字的順序進行組織。 p索引文件索引文件索引文件除了存儲記錄本身（主文件）以外，索引文件除了存儲記錄本身（主文件）以外，還建立了若干索引表，這種帶有索引表的文件還建立了若干索引表，這種帶有索引表的文件叫索引文件。索引表中列出記錄關(guān)鍵字和記錄叫索引文件。索引表中列出記錄關(guān)鍵字和記錄在文件中的位置（地址）。在文件中的位置（地址）。 .1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.3數(shù)據(jù)與文件組織數(shù)據(jù)與文件組織p直接文件直接文件 直接文件又稱隨機文件，其存儲是根據(jù)記錄關(guān)鍵字直接文件又稱隨機文件，其存儲是根據(jù)記錄關(guān)鍵字的值，通過某種轉(zhuǎn)換方法得到一個物理存儲位置，的值，通過某種轉(zhuǎn)換方法得到一個物理存儲位置

18、，然后把記錄存儲在該位置上。查找時，通過同樣的然后把記錄存儲在該位置上。查找時，通過同樣的轉(zhuǎn)換方法，可以直接得到所需要的記錄。轉(zhuǎn)換方法，可以直接得到所需要的記錄。 p倒排文件倒排文件倒排文件是帶有輔索引的文件，其中輔索引是按照倒排文件是帶有輔索引的文件，其中輔索引是按照一些輔關(guān)鍵字來組織索引的。倒排文件的主要優(yōu)點一些輔關(guān)鍵字來組織索引的。倒排文件的主要優(yōu)點是在處理多索引檢索時，可以在輔檢索中先完成查是在處理多索引檢索時，可以在輔檢索中先完成查詢的詢的交交、并并等邏輯運算，得到結(jié)果后再對等邏輯運算，得到結(jié)果后再對記錄進行存取，從而提高查找速度。記錄進行存取，從而提高查找速度。 .1.空間數(shù)據(jù)庫空

19、間數(shù)據(jù)庫1.4矢量和柵格數(shù)據(jù)結(jié)構(gòu)矢量和柵格數(shù)據(jù)結(jié)構(gòu)p矢量數(shù)據(jù)模型矢量數(shù)據(jù)模型在矢量模型中，現(xiàn)實世界的要素位置和范圍可以采在矢量模型中，現(xiàn)實世界的要素位置和范圍可以采用點、線或面表達，與它們在地圖上表示相似，每用點、線或面表達，與它們在地圖上表示相似，每一個實體的位置是用它們在坐標參考系統(tǒng)中的空間一個實體的位置是用它們在坐標參考系統(tǒng)中的空間位置（坐標）定義。位置（坐標）定義。 p柵格數(shù)據(jù)模型柵格數(shù)據(jù)模型在柵格模型中，空間被規(guī)則地劃分為柵格（通常為在柵格模型中，空間被規(guī)則地劃分為柵格（通常為正方形）。地理實體的位置和狀態(tài)是用它們占據(jù)的正方形）。地理實體的位置和狀態(tài)是用它們占據(jù)的柵格的行、列來定義的

20、。每個柵格的大小代表了定柵格的行、列來定義的。每個柵格的大小代表了定義的空間分辨率。義的空間分辨率。 .1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.4矢量和柵格數(shù)據(jù)結(jié)構(gòu)矢量和柵格數(shù)據(jù)結(jié)構(gòu)柵格結(jié)構(gòu)矢量結(jié)構(gòu).1.空間數(shù)據(jù)庫空間數(shù)據(jù)庫1.4矢量和柵格數(shù)據(jù)結(jié)構(gòu)矢量和柵格數(shù)據(jù)結(jié)構(gòu).2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.1柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)(一一)定義定義柵格結(jié)構(gòu)是最簡單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地柵格結(jié)構(gòu)是最簡單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個網(wǎng)球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個網(wǎng)格作為一個象元或象素由行、列定義，并包含一個代格作為一個象元或象素由

21、行、列定義，并包含一個代碼表示該象素的屬性類型或量值，或僅僅包括指向其碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。屬性記錄的指針。p點用一個柵格單元表示；點用一個柵格單元表示；p線狀地物沿線走向的一組相鄰柵格單元表示，每線狀地物沿線走向的一組相鄰柵格單元表示，每個柵格單元最多只有兩個相鄰單元在線上；個柵格單元最多只有兩個相鄰單元在線上；p面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募厦婊騾^(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募媳硎?，每個柵格單元可有多于兩個的相鄰單元同屬表示，每個柵格單元可有多于兩個的相鄰單元同屬一個區(qū)域。一個區(qū)域。 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼

22、2.1柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7

23、7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）點 （b）線 （c）面 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.1柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)(二二)特點特點柵格結(jié)構(gòu)的顯著特點是：柵格結(jié)構(gòu)的顯著特點是：p屬性明顯；屬性明顯；p定位隱含；定位隱含；p易于存儲；易于存儲；p算法簡單；算法簡單；p地表是不連續(xù)，是量化和近似離散的數(shù)據(jù)。地表是不連續(xù)，是量化和近似離散的數(shù)據(jù)。 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.2決定柵格單

24、元代碼的方法決定柵格單元代碼的方法在決定柵格代碼時盡量保持地表的真實性，保證最大的信在決定柵格代碼時盡量保持地表的真實性，保證最大的信息容量。圖息容量。圖7-5所示的一塊矩形地表區(qū)域，內(nèi)部含有所示的一塊矩形地表區(qū)域，內(nèi)部含有A、B、C三種地物類型，三種地物類型，O點為中心點，將這個矩形區(qū)域近似地表點為中心點，將這個矩形區(qū)域近似地表示為柵格結(jié)構(gòu)中的一個柵格單元時，可根據(jù)需要，采取如示為柵格結(jié)構(gòu)中的一個柵格單元時，可根據(jù)需要，采取如下的方式之一來決定柵格單元的代碼。下的方式之一來決定柵格單元的代碼。 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.2決定柵格單元代碼的方法決定柵格單元代碼的方法

25、p中心點法中心點法用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼，用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼，在圖在圖7-5所示的矩形區(qū)域中，中心點所示的矩形區(qū)域中，中心點O落在代碼為落在代碼為C的地物的地物范圍內(nèi)，按中心點法的規(guī)則，該矩形區(qū)域相應(yīng)的柵格單范圍內(nèi)，按中心點法的規(guī)則，該矩形區(qū)域相應(yīng)的柵格單元代碼為元代碼為C，中心點法常用于具有連續(xù)分布特性的地理要，中心點法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。素，如降雨量分布、人口密度圖等。p面積占優(yōu)法面積占優(yōu)法以占矩形區(qū)域面積最大的地物類型或現(xiàn)象特性決定柵格以占矩形區(qū)域面積最大的地物類型或現(xiàn)象特性決定柵格單元的代

26、碼，在圖單元的代碼，在圖7-5所示的例子中，顯見所示的例子中，顯見B類地物所占類地物所占面積最大，故相應(yīng)柵格代碼定為面積最大，故相應(yīng)柵格代碼定為B。面積占優(yōu)法常用于分。面積占優(yōu)法常用于分類較細，地物類別斑塊較小的情況。類較細，地物類別斑塊較小的情況。 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.2決定柵格單元代碼的方法決定柵格單元代碼的方法p重要性法重要性法根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型決定相應(yīng)的柵格單元代碼，假設(shè)圖類型決定相應(yīng)的柵格單元代碼，假設(shè)圖7-5中中A類最類最重要的地物類型，即重要的地物類型，即A比比B和和C類更為

27、重要，則柵類更為重要，則柵格單元的代碼應(yīng)為格單元的代碼應(yīng)為A。重要性法常用于具有特殊意。重要性法常用于具有特殊意義而面積較小的地理要素，特別是點、線狀地理要義而面積較小的地理要素，特別是點、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在柵格中代碼應(yīng)盡量表示這些重要地物。柵格中代碼應(yīng)盡量表示這些重要地物。p百分比法百分比法(長度占優(yōu)法長度占優(yōu)法)根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的代碼，如可記面積最大的兩類定柵格單元的代碼，如可記面積最大的兩類BA，也可以根據(jù)也可以根據(jù)B類和類和A

28、類所占面積百分比數(shù)在代碼中類所占面積百分比數(shù)在代碼中加入數(shù)字加入數(shù)字 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法(一一)直接柵格編碼直接柵格編碼這是最簡單直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種這是最簡單直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼的圖像文件為網(wǎng)格文件或柵格文件，柵格結(jié)構(gòu)不論采用何種壓縮編碼的圖像文件為網(wǎng)格文件或柵格文件，柵格結(jié)構(gòu)不論采用何種壓縮編碼方法，其邏輯原型都是直接編碼網(wǎng)格文件。直接編碼就是將柵格編碼方法，其邏輯原型都是直接編碼網(wǎng)格文件。直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行（或逐列）逐個記錄代碼，可以每行都數(shù)據(jù)看作

29、一個數(shù)據(jù)矩陣，逐行（或逐列）逐個記錄代碼，可以每行都從左到右逐個象元記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向從左到右逐個象元記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序。左記錄，為了特定目的還可采用其他特殊的順序。 AAAAABBBAABBAABB.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法(二二)壓縮編碼方法壓縮編碼方法 目前有一系列柵格數(shù)據(jù)壓縮編碼方法，如目前有一系列柵格數(shù)據(jù)壓縮編碼方法，如鏈碼、游程長度鏈碼、游程長度編碼、塊碼和四叉樹編碼編碼、塊碼

30、和四叉樹編碼等。其目的，就是用盡可能少的等。其目的，就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類型又有信息無損編碼和數(shù)據(jù)量記錄盡可能多的信息，其類型又有信息無損編碼和信息有損編碼之分。信息無損編碼是指編碼過程中沒有任信息有損編碼之分。信息無損編碼是指編碼過程中沒有任何信息損失，通過解碼操作可以完全恢復原來的信息，信何信息損失，通過解碼操作可以完全恢復原來的信息，信息有損編碼是指為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，息有損編碼是指為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損失一部分相對不太重要的信息，解碼時這在壓縮過程中損失一部分相對不太重要的信息，解碼時這部分難以恢復。在地理信息系統(tǒng)

31、中多采用信息無損編碼，部分難以恢復。在地理信息系統(tǒng)中多采用信息無損編碼，而對原始遙感影像進行壓縮編碼時，有時也采取有損壓縮而對原始遙感影像進行壓縮編碼時，有時也采取有損壓縮編碼方法。編碼方法。 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法p鏈碼鏈碼鏈碼又稱為弗里曼鏈碼鏈碼又稱為弗里曼鏈碼Freeman或邊界鏈碼，鏈碼可以有或邊界鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向的凹凸度等運算十分方便，比較適合于存儲圖形數(shù)據(jù)。缺的凹凸度等運算十分方便，比較適合于存儲圖形數(shù)據(jù)。缺點是對邊界進行合并和插入等修

32、改編輯工作比較困難，對點是對邊界進行合并和插入等修改編輯工作比較困難，對局部的修改將改變整體結(jié)構(gòu)，效率較低局部的修改將改變整體結(jié)構(gòu)，效率較低 37650p412(a)(b)012345(3,0)21100066567.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法p游程長度編碼游程長度編碼地理數(shù)據(jù)往往有較強的相關(guān)性，也就是說相鄰像元的值地理數(shù)據(jù)往往有較強的相關(guān)性，也就是說相鄰像元的值往往是相同的。游程長度編碼的基本思想是：按行或列往往是相同的。游程長度編碼的基本思想是：按行或列掃描，將相鄰等值的像元合并，并記錄代碼的重復個數(shù)。掃描，將相鄰等值的像元合并，并記錄代碼的重復個

33、數(shù)。其方法有兩種方案：其方法有兩種方案：一種編碼方案是，只在各行（或列）數(shù)據(jù)的代碼發(fā)一種編碼方案是，只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及相同的代碼重復的個生變化時依次記錄該代碼以及相同的代碼重復的個數(shù)。數(shù)。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法對下圖沿行方向：（對下圖沿行方向：（0，1），（），（4，2），（），（7，5）；（）；（4，5），（），（7，3）；（）；（4，4），（），（8，2），（），（7，2）；（）；（0，2），（），（4，1），（），（8，3），（），（7，2）；（）；（0，2），（），（8，4），（），（7，1），（），（

34、8，1）；）；(0，3)，(8，5)；(0，4)，(8，4)；(0，5)，(8，3)。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0

35、0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法另一種游程長度編碼方案就是逐個記錄各行（或列）另一種游程長度編碼方案就是逐個記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼。代碼發(fā)生變化的位置和相應(yīng)代碼。沿列方向：（沿列方向：（1，0），（），（2，4），（），（4，0），（），（1，4），（），（4，0）；（）；（1，4）

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

37、 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 .2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法游程長度編碼在柵格壓縮時，數(shù)據(jù)量沒有明顯游程長度編碼在柵格壓縮時，數(shù)據(jù)量沒有

38、明顯增加，壓縮效率較高，且易于檢索，疊加合并增加，壓縮效率較高，且易于檢索，疊加合并等操作，運算簡單，適用于機器存儲容量小，等操作，運算簡單，適用于機器存儲容量小，數(shù)據(jù)需大量壓縮，而又要避免復雜的編碼解碼數(shù)據(jù)需大量壓縮，而又要避免復雜的編碼解碼運算增加處理和操作時間的情況。運算增加處理和操作時間的情況。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法p塊狀編碼塊狀編碼塊碼是游程長度編碼擴展到塊碼是游程長度編碼擴展到二維的情況，采用方形區(qū)域二維的情況，采用方形區(qū)域作為記錄單元，每個記錄單作為記錄單元，每個記錄單元包括相鄰的若干柵格，數(shù)元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置

39、據(jù)結(jié)構(gòu)由初始位置(行、列號行、列號)和半徑，再加上記錄單元的和半徑，再加上記錄單元的代碼組成。代碼組成。(1,1,2,9),(1,3,1,9),(1,4,1,9),(1,5,2,0),(1,7,2,0),(2,3,1,9),(2,4,1,0),(3,1,1,0),(3,2,1,9),(3,3,1,9),(3,4,1,0), (3,5,2,7), (3,7,2,0), (4,1,4,0),(5,5,4,7), (8,1,1,0), (8,2,1,0), (8,3,1,0), (8,4,1,0).2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法 0 4 4 4 4 4 4 4

40、0 0 0 0 0 0 0 0 0 0 0 0 0 8 4 4 4 8 8 8 8 8 7 7 4 4 7 7 7 7 7 7 7 7 7 7 8 8 8 8 0 8 0 0 8 7 8 8 8 8 8 8 8 8 8 8 0 4 4 7 7 7 7 7 4 4 4 4 4 7 7 7 4 4 4 4 8 8 7 7 0 0 4 8 8 8 7 7 0 0 8 8 8 8 7 8 0 0 0 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）塊碼分割）塊碼分割 （b）四叉樹分割）四叉樹分割.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼

41、方法p四叉樹四叉樹基本思想：四叉樹將整個圖像區(qū)逐步分解為一系列被基本思想：四叉樹將整個圖像區(qū)逐步分解為一系列被單一類型區(qū)域內(nèi)含的方形區(qū)域，最小的方形區(qū)域為一個單一類型區(qū)域內(nèi)含的方形區(qū)域，最小的方形區(qū)域為一個柵格象元，分割的原則是，將圖像區(qū)域劃分為四個大小柵格象元，分割的原則是，將圖像區(qū)域劃分為四個大小相同的象限，而每個象限又可根據(jù)一定規(guī)則判斷是否繼相同的象限，而每個象限又可根據(jù)一定規(guī)則判斷是否繼續(xù)等分為次一層的四個象限，其終止判據(jù)是，不管是哪續(xù)等分為次一層的四個象限，其終止判據(jù)是，不管是哪一層上的象限，只要劃分到僅代表一種地物或符合既定一層上的象限，只要劃分到僅代表一種地物或符合既定要求的少數(shù)

42、幾種地物時，則不再繼續(xù)劃分，否則一直劃要求的少數(shù)幾種地物時，則不再繼續(xù)劃分，否則一直劃分到單個柵格象元為止。分到單個柵格象元為止。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法定義：定義：將將2n 2n像元陣列連續(xù)地進行像元陣列連續(xù)地進行4象限等分，一象限等分，一直分到子象限中像素值單調(diào)為止，這查即形成一顆直分到子象限中像素值單調(diào)為止，這查即形成一顆四分叉的倒向樹。四分叉的倒向樹。根：根：整個區(qū)域；整個區(qū)域；高：高：深度、分幾深度、分幾級，幾次分割；級，幾次分割；葉：葉：不能再分割的塊；不能再分割的塊；樹叉：樹叉：還需還需分割的塊；分割的塊； 每個樹叉均有每個樹叉均有4

43、個分叉，叫四叉樹。個分叉，叫四叉樹。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法編碼方法編碼方法1)常規(guī)四叉樹常規(guī)四叉樹記錄這棵樹的葉結(jié)點外，中間結(jié)點，結(jié)點之間的聯(lián)系記錄這棵樹的葉結(jié)點外，中間結(jié)點，結(jié)點之間的聯(lián)系用指針聯(lián)系，每個結(jié)點需要用指針聯(lián)系，每個結(jié)點需要6個變量：個變量：父結(jié)點指針、四個子結(jié)點的指針和本結(jié)點的屬性值父結(jié)點指針、四個子結(jié)點的指針和本結(jié)點的屬性值。指針不僅指針不僅增加了數(shù)據(jù)的存儲量增加了數(shù)據(jù)的存儲量，還增加了操作的還增加了操作的復雜復雜性性：如層次數(shù)（分割次數(shù)）由從父結(jié)點移到根結(jié)點的如層次數(shù)（分割次數(shù)）由從父結(jié)點移到根結(jié)點的次數(shù)來確定，結(jié)點所代表的圖

44、像塊的位置需要從根節(jié)次數(shù)來確定，結(jié)點所代表的圖像塊的位置需要從根節(jié)點開始逐步推算下來。所以，點開始逐步推算下來。所以，常規(guī)四叉樹并不廣泛用常規(guī)四叉樹并不廣泛用于存儲數(shù)據(jù)于存儲數(shù)據(jù)，其價值在于建立索引文件，進行數(shù)據(jù)檢其價值在于建立索引文件，進行數(shù)據(jù)檢索。索。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法2)線性四叉樹線性四叉樹記錄葉結(jié)點的位置，深度（幾次分割）和屬性。記錄葉結(jié)點的位置，深度（幾次分割）和屬性。地址碼：定位碼、地址碼：定位碼、Morton碼（加拿大學者碼（加拿大學者Morton于于1966年提出）年提出） 四進制、十進制。其具有以下優(yōu)點：四進制、十進制。其具

45、有以下優(yōu)點：p存貯量小，只對葉結(jié)點編碼，節(jié)省了大量中間結(jié)存貯量小，只對葉結(jié)點編碼，節(jié)省了大量中間結(jié)點的存儲，地址碼隱含著結(jié)點的分割路徑和分割次點的存儲，地址碼隱含著結(jié)點的分割路徑和分割次數(shù)。數(shù)。p線性四叉樹可直接尋址，通過其坐標值直接計算線性四叉樹可直接尋址，通過其坐標值直接計算其其Morton碼，而不用建立四叉樹。碼，而不用建立四叉樹。p定位碼容易存儲和執(zhí)行實現(xiàn)集合相加等組合操作。定位碼容易存儲和執(zhí)行實現(xiàn)集合相加等組合操作。.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法四進制的四進制的Morton碼碼1、 方法方法1：四叉樹從上而下（形成）四叉樹從上而下（形成）（從整

46、體開始）由葉結(jié)點（從整體開始）由葉結(jié)點找找Morton碼。碼。 A、分割一次，增加一、分割一次，增加一位數(shù)字，大分割在前，小位數(shù)字，大分割在前，小分割在后。所以，分割在后。所以，碼的位碼的位數(shù)表示分割的次數(shù)數(shù)表示分割的次數(shù)。 B、每一個位均是不大于每一個位均是不大于3的四進制數(shù)，表達位置。的四進制數(shù)，表達位置。由由Morton找出四叉樹葉結(jié)找出四叉樹葉結(jié)點的具體位置。點的具體位置。 02AAA BAAA A AA0303B BA A.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法 1）計算每個柵格對應(yīng)的）計算每個柵格對應(yīng)的MQ MQ=2*Ib+Jb I,J化為二進制化為二

47、進制Ib,Jb 看最大的看最大的I,J,不足在前補零。不足在前補零。 其其始行列號從始行列號從0計。計。2) 按碼的升序排成線性表，放按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。在連續(xù)的內(nèi)存塊中。3）依次檢查每四個相鄰的）依次檢查每四個相鄰的MQ對應(yīng)的屬性值，相同合并（不同對應(yīng)的屬性值，相同合并（不同碼位去掉），不同則存盤碼位去掉），不同則存盤,直到直到?jīng)]有能夠合并的子塊為止。沒有能夠合并的子塊為止。A000A001A010A011A002 B003B012B013A020A021B030B031A022A023B032B03300011011.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.

48、3編碼方法編碼方法A000A001A010A011A002 B003B012B013A020A021B030B031A022A023B032B033000001002003010011012013020021022023030031032033AAABAABBAAAABBBB000001002003010011012013020030AAABAABBAB.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法十進制的十進制的MortonMorton碼碼-MD-MD四進制四進制MortonMorton碼直觀上切合四叉樹分割，但許多語言碼直觀上切合四叉樹分割，但許多語言不支持四進制變

49、量，需用十進制表示不支持四進制變量，需用十進制表示MortonMorton碼碼. .1 1、一種按位操作的方法：、一種按位操作的方法：如行為如行為2 2、列為、列為3 3的柵格的的柵格的MDMD步驟：步驟： (1)(1)行、列號為二進制行、列號為二進制 Ib= 1 0 Jb= 1 1Ib= 1 0 Jb= 1 1(2)I(2)I行行J J列交叉列交叉 1 1 0 1 = 131 1 0 1 = 13(3)(3)再化為十進制再化為十進制. . 實質(zhì)上是按左上、右上、左下、右下的順序，從零開始對實質(zhì)上是按左上、右上、左下、右下的順序，從零開始對每個柵格進行自然編碼。每個柵格進行自然編碼。 A 0A

50、 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法4.把一幅把一幅2n2n的圖像壓縮成線的圖像壓縮成線性四叉樹的過程性四叉樹的過程 1、按、按Morton碼把圖象讀入一碼把圖象讀入一維數(shù)組。維數(shù)組。 2、相鄰的四個象元比較，一、相鄰的四個象元比較，一致的合并，只記錄第一個象元的致的合并，只記錄第一個象元的Morton碼。循環(huán)比較所形成的大碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合塊，相同的再合并，直到不能合并為止。并為止。 3、進一步用游程長度編碼壓、進一步用游程長

51、度編碼壓縮。壓縮時只記錄第一個象元的縮。壓縮時只記錄第一個象元的Morton碼。碼。A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法右圖的壓縮處理過程為：右圖的壓縮處理過程為：1、按、按Morton碼讀入一維數(shù)組。碼讀入一維數(shù)組。Morton碼：碼：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15象象 元元 值：值： A A A B A B B B A A A A B B B B2、四相鄰象元合并，只記錄第一個象元的、四相鄰象元合并，只記

52、錄第一個象元的Morton碼。碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3、由于不能進一步合并，則用游程長度編碼壓縮。、由于不能進一步合并，則用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B B 15B 14A 11A 10B 13B 12A 9A 8B 7B 6 B 3A 2A 5A 4A 1A 0.2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法采用四叉樹編碼時，為了保證四叉樹分解能不斷地進行下采用四叉樹編碼時，為了保證四叉樹分解能不斷地進行下去，要求圖像必須為去，要求圖像必須為2n2n的柵格陣列，的柵格

53、陣列，n為極限分割數(shù)，為極限分割數(shù)，n+1為四叉樹的最大高度或最大層數(shù)，圖為四叉樹的最大高度或最大層數(shù)，圖7-4（c）為）為2323的柵格，因此最多劃分三次，最大層數(shù)為的柵格，因此最多劃分三次，最大層數(shù)為4，對于非標準尺，對于非標準尺寸的圖像需首先通過增加背景的方法將圖像擴充為寸的圖像需首先通過增加背景的方法將圖像擴充為2n2n的圖像。的圖像。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

54、0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）點）點 （b）線）線 （c）面）面圖圖7-4：點、線、區(qū)域的格網(wǎng)：點、線、區(qū)域

55、的格網(wǎng).2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼柵格數(shù)據(jù)結(jié)構(gòu)及其編碼 2.3編碼方法編碼方法四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運算可以在編碼數(shù)據(jù)上直接實現(xiàn)，大大地提據(jù)靈活，許多運算可以在編碼數(shù)據(jù)上直接實現(xiàn)，大大地提高了運算效率，是優(yōu)秀的柵格壓縮編碼之一。高了運算效率，是優(yōu)秀的柵格壓縮編碼之一。好的壓縮編碼方法就是要在盡可能減少運算時間的基礎(chǔ)上好的壓縮編碼方法就是要在盡可能減少運算時間的基礎(chǔ)上達到最大的數(shù)據(jù)壓縮效率，并且是算法適應(yīng)性強，易于實達到最大的數(shù)據(jù)壓縮效率，并且是算法適應(yīng)性強，易于實現(xiàn)。現(xiàn)。p鏈碼的壓縮效率較高，已經(jīng)近矢量結(jié)構(gòu)

56、，對邊界的運算鏈碼的壓縮效率較高，已經(jīng)近矢量結(jié)構(gòu)，對邊界的運算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域運算困難；比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域運算困難；p游程長度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限游程長度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易；度地保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易；p塊碼和四叉樹碼具有區(qū)域性質(zhì)，又具有可變的分辨率，塊碼和四叉樹碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，四叉樹編碼可以直接進行大量圖形圖有較高的壓縮效率，四叉樹編碼可以直接進行大量圖形圖像運算，效率較高，是很有前途的方法。像運算，效率較高，是很有前途的方法

57、。.3.矢量數(shù)據(jù)結(jié)構(gòu)及其編碼矢量數(shù)據(jù)結(jié)構(gòu)及其編碼 3.1矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)是最常見的圖形數(shù)據(jù)結(jié)構(gòu)，是一種面向目標矢量數(shù)據(jù)結(jié)構(gòu)是最常見的圖形數(shù)據(jù)結(jié)構(gòu)，是一種面向目標的數(shù)據(jù)組織方式。矢量方法強調(diào)離散現(xiàn)象的存在，將線離的數(shù)據(jù)組織方式。矢量方法強調(diào)離散現(xiàn)象的存在，將線離散為一串采樣點的坐標串，面狀區(qū)域由邊界線確定。由于散為一串采樣點的坐標串，面狀區(qū)域由邊界線確定。由于矢量數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)緊湊，冗余度低，利于網(wǎng)絡(luò)、檢索矢量數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)緊湊，冗余度低，利于網(wǎng)絡(luò)、檢索分析等優(yōu)點，是分析等優(yōu)點，是GIS主要的數(shù)據(jù)存儲結(jié)構(gòu)之一。主要的數(shù)據(jù)存儲結(jié)構(gòu)之一。(一一)定義定義p點實體：記錄點坐標和

58、屬性代碼；點實體：記錄點坐標和屬性代碼；p線實體：記錄兩個或一系列采樣點的坐標，并加屬性代線實體：記錄兩個或一系列采樣點的坐標，并加屬性代碼；碼；p面實體：記錄邊界上一系列采樣點的坐標，由于多邊形面實體：記錄邊界上一系列采樣點的坐標，由于多邊形封閉，邊界為閉合環(huán)，加面域?qū)傩源a。封閉，邊界為閉合環(huán)，加面域?qū)傩源a。.3.矢量數(shù)據(jù)結(jié)構(gòu)及其編碼矢量數(shù)據(jù)結(jié)構(gòu)及其編碼 3.1矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)(二二)特點特點矢量結(jié)構(gòu)的特點是：矢量結(jié)構(gòu)的特點是：定位明顯、屬性隱含定位明顯、屬性隱含，其定，其定位是根據(jù)坐標直接存儲的，而屬性則一般存于文位是根據(jù)坐標直接存儲的，而屬性則一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特

59、定的位置上，這種特點件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上，這種特點使得其圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復使得其圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復雜的多，有些甚至難以實現(xiàn)，當然有些地方也有雜的多，有些甚至難以實現(xiàn)，當然有些地方也有所便利和獨到之處，在計算長度、面積、形狀和所便利和獨到之處，在計算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度，而在疊加運算、鄰域搜索等操作時效率和精度，而在疊加運算、鄰域搜索等操作時則比較困難。則比較困難。.3.矢量數(shù)據(jù)結(jié)構(gòu)及其編碼矢量數(shù)據(jù)結(jié)構(gòu)及其編碼 3.2編碼方法編碼方法(一一) 點實體點實體對

60、于點實體和線實體的矢量編碼比較直接，只要能將空間信息對于點實體和線實體的矢量編碼比較直接，只要能將空間信息和屬性信息記錄完全就可以了。點是空間上不能再分的地理實和屬性信息記錄完全就可以了。點是空間上不能再分的地理實體，可以是具體的或抽象的，如地物點、文本位置點或線段網(wǎng)體，可以是具體的或抽象的，如地物點、文本位置點或線段網(wǎng)絡(luò)的結(jié)點等，絡(luò)的結(jié)點等，由一對由一對x、y坐標表示坐標表示。(二二)線實體線實體線實體主要用來表示線狀地物（如公路、水系、山脊線等）符線實體主要用來表示線狀地物（如公路、水系、山脊線等）符號線和多邊形邊界，有時也稱為號線和多邊形邊界，有時也稱為“弧弧”、“鏈鏈”、“串串”等，等