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

1、媽媽說(shuō)：“生活就像是一盒巧克力，你永遠(yuǎn)不知道下一塊的味道。”Forrest Gump第七章 空間數(shù)據(jù)管理導(dǎo)讀：本章首先介紹空間數(shù)據(jù)庫(kù)、與一般數(shù)據(jù)庫(kù)的比較，以及空間數(shù)據(jù)庫(kù)的存儲(chǔ)方式。然后介紹了GIS中兩種重要的數(shù)據(jù)結(jié)構(gòu)：柵格結(jié)構(gòu)和矢量結(jié)構(gòu)，以及其具體的存儲(chǔ)方式，然后比較了兩種結(jié)構(gòu)的特點(diǎn)，并給出了其相互轉(zhuǎn)換算法。最后介紹了空間檢索中常用的技術(shù)空間索引，介紹了一些常用的空間索引方式，如BSP樹(shù)、R樹(shù)、CELL樹(shù)等；以及空間數(shù)據(jù)的查詢功能。1空間數(shù)據(jù)庫(kù)一個(gè)信息系統(tǒng)及其數(shù)據(jù)庫(kù)的組成，決定于系統(tǒng)的應(yīng)用目的、數(shù)據(jù)類型和系統(tǒng)的工作方式。關(guān)于地理信息系統(tǒng)的內(nèi)容及其功能，以及地理信息系統(tǒng)的一個(gè)重要特點(diǎn)，或者說(shuō)是與

2、一般管理信息系統(tǒng)的區(qū)別，是數(shù)據(jù)具有空間分布的性質(zhì)。對(duì)地理信息系統(tǒng)來(lái)講，不僅數(shù)據(jù)本身具有空間屬性，系統(tǒng)的分析和應(yīng)用也無(wú)不與地理環(huán)境直接關(guān)聯(lián)。系統(tǒng)的這一基本特征，深刻地影響著數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)庫(kù)的設(shè)計(jì)、分析算法和軟件，以及系統(tǒng)的輸入和輸出。11地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較從數(shù)據(jù)源的角度來(lái)看，圖形和圖像數(shù)據(jù)是地理信息系統(tǒng)數(shù)據(jù)的一個(gè)主要來(lái)源，分析處理的結(jié)果也常用圖形的方式來(lái)表示。而一般的管理信息系統(tǒng)，則多以統(tǒng)計(jì)數(shù)據(jù)、表格數(shù)據(jù)為主。這一點(diǎn)也使地理信息系統(tǒng)在硬件和軟件上與一般的管理信息系統(tǒng)有所區(qū)別。111兩者的區(qū)別1）在硬件上，為了處理圖形和圖像數(shù)據(jù)，系統(tǒng)需要配置專門(mén)的輸入和輸出設(shè)備，如數(shù)字化儀、繪

3、圖機(jī)、圖形圖像的顯示設(shè)備等；許多野外實(shí)地采集和臺(tái)站的觀測(cè)所得到的資源信息是模擬量形式，系統(tǒng)還需要配置模數(shù)轉(zhuǎn)換設(shè)備，這些設(shè)備往往超過(guò)中央處理機(jī)的價(jià)格，體積也比較大。2）在軟件上，則要求研制專門(mén)的圖形和圖像數(shù)據(jù)的分析算法和處理軟件，這些算法和軟件又直接和數(shù)據(jù)的結(jié)構(gòu)及數(shù)據(jù)庫(kù)的管理方法有關(guān)。3）在信息處理的內(nèi)容和采用目的方面，一般的管理信息系統(tǒng)，主要是查詢檢索和統(tǒng)計(jì)分析，處理的結(jié)果，大多是制成某種規(guī)定格式的表格數(shù)據(jù)，而地理信息系統(tǒng)，除了基本的信息檢索和統(tǒng)計(jì)分析外，主要用于分析研究資源的合理開(kāi)發(fā)利用，制定區(qū)域發(fā)展規(guī)劃，地區(qū)的綜合治理方案，對(duì)環(huán)境進(jìn)行動(dòng)態(tài)的監(jiān)視和預(yù)測(cè)預(yù)報(bào)，為國(guó)民經(jīng)濟(jì)建設(shè)中的決策提供科學(xué)依據(jù)

4、，為生產(chǎn)實(shí)踐提供信息和指導(dǎo)。由于地理信息系統(tǒng)是一個(gè)復(fù)雜的自然和社會(huì)的綜合體，所以信息的處理必然是多因素的綜合分析。系統(tǒng)分析是基本的方法，例如，研究某種地理信息系統(tǒng)中各組成部分間的相互關(guān)系，利用統(tǒng)計(jì)數(shù)據(jù)建立系統(tǒng)的數(shù)學(xué)模型，根據(jù)給定的目標(biāo)函數(shù)，進(jìn)行數(shù)學(xué)規(guī)劃，尋求最優(yōu)方案，使該系統(tǒng)的經(jīng)濟(jì)效益為最佳；或者分析系統(tǒng)中各部分之間反饋聯(lián)系，建立系統(tǒng)的結(jié)構(gòu)模型，采用系統(tǒng)動(dòng)力學(xué)的方法，進(jìn)行動(dòng)態(tài)分析，研究系統(tǒng)狀態(tài)的變化和預(yù)測(cè)發(fā)展趨勢(shì)等。計(jì)算機(jī)仿真是一種有效而經(jīng)濟(jì)的分析方法，便于分析各種因素的影響和進(jìn)行方案的比較，在自然環(huán)境和社會(huì)經(jīng)濟(jì)的許多應(yīng)用研究中常被采用。此外，地理信息系統(tǒng)還有分析量算的功能，如計(jì)算面積、長(zhǎng)度、

5、密度、分布特征等以及地理實(shí)體之間的關(guān)系運(yùn)算。112兩者共同之處地理信息系統(tǒng)和一般的信息管理系統(tǒng)，也有許多共同之處。兩者都是以計(jì)算機(jī)為核心的信息處理系統(tǒng)，都具有數(shù)據(jù)量大和數(shù)據(jù)之間關(guān)系復(fù)雜的特點(diǎn)，也都隨著數(shù)據(jù)庫(kù)技術(shù)的發(fā)展在不斷的改進(jìn)和完善。比較起來(lái)，商用的管理信息系統(tǒng)發(fā)展快，用戶數(shù)量大，而且已有定型的軟件產(chǎn)品可供選用，這也促進(jìn)了軟件系統(tǒng)的標(biāo)準(zhǔn)化。地理信息系統(tǒng)，由于上述一些特點(diǎn)，多是根據(jù)具體的應(yīng)用要求專門(mén)設(shè)計(jì)，數(shù)據(jù)格式和組織管理方法各不相同。目前國(guó)外已有幾百個(gè)空間數(shù)據(jù)處理系統(tǒng)和軟件包，幾乎沒(méi)有兩個(gè)系統(tǒng)是一樣的，盡管大家都認(rèn)為標(biāo)準(zhǔn)化是很重要的，也作了許多努力（例如建立計(jì)算機(jī)制圖的標(biāo)準(zhǔn)和規(guī)范），但分析的

6、算法和軟件系統(tǒng)還談不上標(biāo)準(zhǔn)化的問(wèn)題。事實(shí)上，地理信息系統(tǒng)正作為一種空間信息的處理系統(tǒng)，成為一個(gè)單獨(dú)的研究和發(fā)展領(lǐng)域。12空間數(shù)據(jù)庫(kù)121數(shù)據(jù)庫(kù)的概念數(shù)據(jù)庫(kù)就是為一定目的服務(wù)，以特定的數(shù)據(jù)存儲(chǔ)的相關(guān)聯(lián)的數(shù)據(jù)集合，它是數(shù)據(jù)管理的高級(jí)階段，是從文件管理系統(tǒng)發(fā)展而來(lái)的。地理信息系統(tǒng)的數(shù)據(jù)庫(kù)（簡(jiǎn)稱空間數(shù)據(jù)庫(kù)或地理數(shù)據(jù)庫(kù)）是某一區(qū)域內(nèi)關(guān)于一定地理要素特征的數(shù)據(jù)集合。為了直觀地理解數(shù)據(jù)庫(kù)，可以把數(shù)據(jù)庫(kù)作如下比較：表7-1：數(shù)據(jù)庫(kù)與圖書(shū)館比較數(shù)據(jù)庫(kù)圖書(shū)館數(shù)據(jù)圖書(shū)數(shù)據(jù)模型書(shū)卡編目數(shù)據(jù)的物理組織圖書(shū)存放規(guī)則、書(shū)架數(shù)據(jù)庫(kù)管理系統(tǒng)圖書(shū)管理員外存書(shū)庫(kù)用戶讀者數(shù)據(jù)存取圖書(shū)閱覽122空間數(shù)據(jù)庫(kù)特點(diǎn)空間數(shù)據(jù)庫(kù)與一般數(shù)據(jù)庫(kù)相比

7、，具有以下特點(diǎn)：1）數(shù)據(jù)量特別大，地理系統(tǒng)是一個(gè)復(fù)雜的綜合體，要用數(shù)據(jù)來(lái)描述各種地理要素，尤其是要素的空間位置，其數(shù)據(jù)量往往很大。2）不僅有地理要素的屬性數(shù)據(jù)（與一般數(shù)據(jù)庫(kù)中的數(shù)據(jù)性質(zhì)相似），還有大量的空間數(shù)據(jù)，即描述地理要素空間分布位置的數(shù)據(jù)，并且這兩種數(shù)據(jù)之間具有不可分割的聯(lián)系。3）數(shù)據(jù)應(yīng)用廣泛，例如地理研究、環(huán)境保護(hù)、土地利用與規(guī)劃、資源開(kāi)發(fā)、生態(tài)環(huán)境、市政管理、道路建設(shè)等。123數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)是關(guān)于事物及其關(guān)系的信息組合，早期的數(shù)據(jù)庫(kù)物體本身與其屬性是分開(kāi)存儲(chǔ)的，只能滿足簡(jiǎn)單的數(shù)據(jù)恢復(fù)和使用。數(shù)據(jù)定義使用特定的數(shù)據(jù)結(jié)構(gòu)定義，利用文件形式存儲(chǔ)，稱之為文件處理系統(tǒng)。文件處理系統(tǒng)是數(shù)據(jù)

8、庫(kù)管理最普遍的方法，但是有很多缺點(diǎn)：首先每個(gè)應(yīng)用程序都必須直接訪問(wèn)所使用的數(shù)據(jù)文件，應(yīng)用程序完全依賴于數(shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)文件修改時(shí)應(yīng)用程序也隨之修改；另外的問(wèn)題是數(shù)據(jù)文件的共享。由于若干用戶或應(yīng)用程序共享一個(gè)數(shù)據(jù)文件，要修改數(shù)據(jù)文件必須征得所有用戶的認(rèn)可。由于缺乏集中控制也會(huì)帶來(lái)一系列數(shù)據(jù)庫(kù)的安全問(wèn)題。數(shù)據(jù)庫(kù)的完整性是嚴(yán)格的，信息質(zhì)量很差比沒(méi)有信息更糟。數(shù)據(jù)庫(kù)管理系統(tǒng)（Database Management System，DBMS）是在文件處理系統(tǒng)的基礎(chǔ)上進(jìn)一步發(fā)展的系統(tǒng)。DBMS在用戶應(yīng)用程序和數(shù)據(jù)文件之間起到了橋梁作用。DBMS的最大優(yōu)點(diǎn)是提供了兩者之間的數(shù)據(jù)獨(dú)立性，即應(yīng)用程序訪問(wèn)數(shù)

9、據(jù)文件時(shí)，不必知道數(shù)據(jù)文件的物理存儲(chǔ)結(jié)構(gòu)。當(dāng)數(shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)改變時(shí)，不必改變應(yīng)用程序。1）采用標(biāo)準(zhǔn)DBMS存儲(chǔ)空間數(shù)據(jù)的主要問(wèn)題* 在“地理信息系統(tǒng)軟件工程技術(shù)”一章中“數(shù)據(jù)管理設(shè)計(jì)”中詳細(xì)描述了各種不同的數(shù)據(jù)管理方案。用標(biāo)準(zhǔn)的DBMS來(lái)存儲(chǔ)空間數(shù)據(jù)，不如存儲(chǔ)表格數(shù)據(jù)那樣好，其主要問(wèn)題包括：（11）在GIS中，空間數(shù)據(jù)記錄是變長(zhǎng)的，因?yàn)樾枰鎯?chǔ)的坐標(biāo)點(diǎn)的數(shù)目是變化的，而一般數(shù)據(jù)庫(kù)都只允許把記錄的長(zhǎng)度設(shè)定為固定長(zhǎng)度。不僅如此，在存儲(chǔ)和維護(hù)空間數(shù)據(jù)拓?fù)潢P(guān)系方面，DBMS也存在著嚴(yán)重的缺陷。因而，一般要對(duì)標(biāo)準(zhǔn)的DBMS增加附加的軟件功能。（12）DBMS一般都難以實(shí)現(xiàn)對(duì)空間數(shù)據(jù)的關(guān)聯(lián)、連通、包含、

10、疊加等基本操作。（13）GIS需要一些復(fù)雜的圖形功能，一般的DBMS不能支持。（14）地理信息是復(fù)雜的，單個(gè)地理實(shí)體的表達(dá)需要多個(gè)文件、多條記錄、或許包括大地網(wǎng)、特征坐標(biāo)、拓?fù)潢P(guān)系、空間特征量測(cè)值、屬性數(shù)據(jù)的關(guān)鍵字以及非空間專題屬性等，一般的DBMS也難以支持。（15）具有高度內(nèi)部聯(lián)系的GIS數(shù)據(jù)記錄需要更復(fù)雜的安全性維護(hù)系統(tǒng)，為了保證空間數(shù)據(jù)庫(kù)的完整性，保護(hù)數(shù)據(jù)文件的完整性，保護(hù)系列必須與空間數(shù)據(jù)一起存儲(chǔ)，否則一條記錄的改變就會(huì)使其他數(shù)據(jù)文件產(chǎn)生錯(cuò)誤。一般的DBMS都難以保證這些。2）GIS數(shù)據(jù)管理方法主要4種類型（21）對(duì)不同的應(yīng)用模型開(kāi)發(fā)獨(dú)立的數(shù)據(jù)管理服務(wù)，這是一種基于文件管理的處理方法

11、。（22）在商業(yè)化的DBMS基礎(chǔ)上開(kāi)發(fā)附加系統(tǒng)。開(kāi)發(fā)一個(gè)附加軟件用于存儲(chǔ)和管理空間數(shù)據(jù)和空間分析，使用DBMS管理屬性數(shù)據(jù)。（23）使用現(xiàn)有的DBMS，通常是以DBMS為核心，對(duì)系統(tǒng)的功能進(jìn)行必要擴(kuò)充，空間數(shù)據(jù)和屬性數(shù)據(jù)在同一個(gè)DBMS管理之下。需要增加足夠數(shù)量的軟件和功能來(lái)提供空間功能和圖形顯示功能。（24）重新設(shè)計(jì)一個(gè)具有空間數(shù)據(jù)和屬性數(shù)據(jù)管理和分析功能的數(shù)據(jù)庫(kù)系統(tǒng)。13數(shù)據(jù)與文件組織數(shù)據(jù)是現(xiàn)實(shí)世界中信息的載體，是信息的具體表達(dá)形式，為了表達(dá)有意義的信息內(nèi)容，數(shù)據(jù)必須按照一定的方式進(jìn)行組織和存儲(chǔ)。131數(shù)據(jù)組織的分級(jí)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織一般可以分為四級(jí)：數(shù)據(jù)項(xiàng)、記錄、文件和數(shù)據(jù)庫(kù)。1）數(shù)據(jù)項(xiàng)

12、數(shù)據(jù)項(xiàng)是可以定義數(shù)據(jù)的最小單位，也叫元素、基本項(xiàng)、字段等，數(shù)據(jù)項(xiàng)與現(xiàn)實(shí)世界實(shí)體的屬性相對(duì)應(yīng)，數(shù)據(jù)項(xiàng)有一定的取值范圍，稱為域，域以外的任何值對(duì)該數(shù)據(jù)項(xiàng)都是無(wú)意義的。每個(gè)數(shù)據(jù)項(xiàng)都有一個(gè)名稱，稱為數(shù)據(jù)項(xiàng)目。數(shù)據(jù)項(xiàng)的值可以是數(shù)值的、字母的、字母數(shù)字的、漢字的等形式。數(shù)據(jù)項(xiàng)的物理特點(diǎn)在于它具有確定的物理長(zhǎng)度，可以作為整體看待。2）記錄記錄是由若干相關(guān)聯(lián)的數(shù)據(jù)項(xiàng)組成，是處理和存儲(chǔ)信息的基本單位，是關(guān)于一個(gè)實(shí)體的數(shù)據(jù)總和，構(gòu)成該記錄的數(shù)據(jù)項(xiàng)表示實(shí)體的若干屬性。記錄有“型”和“值”的區(qū)別，“型”是同類記錄的框架，它定義記錄；而“值”是記錄反映實(shí)體的內(nèi)容。為了唯一標(biāo)識(shí)每個(gè)記錄，就必須有記錄標(biāo)識(shí)符，也叫關(guān)鍵字。記

13、錄標(biāo)識(shí)符一般由記錄中的第一個(gè)數(shù)據(jù)項(xiàng)擔(dān)任，唯一標(biāo)識(shí)記錄的關(guān)鍵字稱主關(guān)鍵字，其它標(biāo)識(shí)記錄的關(guān)鍵字稱為輔關(guān)鍵字。記錄可以分為邏輯記錄與物理記錄，邏輯記錄是文件中按信息在邏輯上的獨(dú)立意義來(lái)劃分的數(shù)據(jù)單位；而物理記錄是單個(gè)輸入輸出命令進(jìn)行數(shù)據(jù)存取的基本單元。物理記錄和邏輯記錄之間的對(duì)應(yīng)關(guān)系有一個(gè)物理記錄一對(duì)應(yīng)一個(gè)邏輯記錄；一個(gè)物理記錄含有若干個(gè)邏輯記錄；若干個(gè)物理記錄存放一個(gè)邏輯記錄。3）文件文件是一給定類型的（邏輯）記錄的全部具體值的集合，文件用文件名稱標(biāo)識(shí)，文件根據(jù)記錄的組織方式和存取方法可以分為：順序文件、索引文件、直接文件和倒排文件等。4）數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)是比文件更大的數(shù)據(jù)組織，數(shù)據(jù)庫(kù)是具有特定聯(lián)系

14、的數(shù)據(jù)的集合，也可以看成是具有特定聯(lián)系的多種類型的記錄的集合。數(shù)據(jù)庫(kù)的內(nèi)部構(gòu)造是文件的集合，這些文件之間存在某種聯(lián)系，不能孤立存在。132數(shù)據(jù)間的邏輯聯(lián)系數(shù)據(jù)間的邏輯聯(lián)系主要是指記錄與記錄之間的聯(lián)系。記錄是表示現(xiàn)實(shí)世界中的實(shí)體的。實(shí)體之間存在著一種或多種聯(lián)系，這樣的聯(lián)系必然要反映到記錄之間的聯(lián)系上來(lái)。數(shù)據(jù)之間的邏輯聯(lián)系主要有三種：一對(duì)一的聯(lián)系；一對(duì)多的聯(lián)系；多對(duì)多的聯(lián)系。133常用數(shù)據(jù)文件圖7-1：非順序文件文件組織是數(shù)據(jù)組織的一部分，數(shù)據(jù)組織既指數(shù)據(jù)在內(nèi)存中的組織，又指數(shù)據(jù)在外存中的組織，而文件組織則主要指數(shù)據(jù)記錄在外存設(shè)備上的組織，它由操作系統(tǒng)OS進(jìn)行管理，具體講在外存設(shè)備上如何安排數(shù)據(jù)和

15、組織數(shù)據(jù)，以及實(shí)施對(duì)數(shù)據(jù)的訪問(wèn)方式等問(wèn)題。操作系統(tǒng)實(shí)現(xiàn)的文件組織方式，可以分為順序文件、索引文件、直接文件和倒排文件。1）順序文件順序文件（圖7-2）是最簡(jiǎn)單的文件組織形式，對(duì)記錄按照主關(guān)鍵字的順序進(jìn)行組織。當(dāng)主關(guān)鍵字是數(shù)字型時(shí)，以其數(shù)值的大小為序；若主關(guān)鍵字是文字型的，則以字母的排列為序。一切存于磁帶上的記錄，都只能是順序的，而存于磁盤(pán)上的記錄，既可以是順序的，也可以是隨機(jī)的。順序文件的記錄，邏輯上是按主關(guān)鍵字排序的，而在物理存儲(chǔ)上可以有不同的方式，包括向量方式：被存儲(chǔ)的文件按地址連續(xù)存放，物理結(jié)構(gòu)與邏輯結(jié)構(gòu)一致；鏈方式：文件不按地址連續(xù)存放，文件的邏輯順序靠鏈來(lái)實(shí)現(xiàn)，文件中的每個(gè)記錄中都含

16、有一個(gè)指針，用以指明下一個(gè)記錄的存放地址；塊鏈方式：把文件分成若干數(shù)據(jù)塊，塊之間用指針連接，而塊內(nèi)則是連續(xù)存儲(chǔ)。圖7-2：順序文件2）索引文件索引文件除了存儲(chǔ)記錄本身（主文件）以外，還建立了若干索引表，這種帶有索引表的文件叫索引文件。索引表中列出記錄關(guān)鍵字和記錄在文件中的位置（地址）。讀取記錄時(shí)，只要提供記錄的關(guān)鍵字值，系統(tǒng)通過(guò)查找索引表獲得記錄的位置，然后取出該記錄。索引表一般都是經(jīng)過(guò)排序的，既可以是有順序的，也可以是非順序的，可以是單級(jí)索引，也可以是多級(jí)索引，多級(jí)索引可以提高查找速度，但占用的存儲(chǔ)空間較大。3）直接文件直接文件又稱隨機(jī)文件，其存儲(chǔ)是根據(jù)記錄關(guān)鍵字的值，通過(guò)某種轉(zhuǎn)換方法得到一

17、個(gè)物理存儲(chǔ)位置，然后把記錄存儲(chǔ)在該位置上。查找時(shí)，通過(guò)同樣的轉(zhuǎn)換方法，可以直接得到所需要的記錄。4）倒排文件倒排文件是帶有輔索引的文件，其中輔索引是按照一些輔關(guān)鍵字來(lái)組織索引的（注意：索引文件是按照記錄的主關(guān)鍵字來(lái)構(gòu)造索引的，也叫主索引）。倒排文件是一種多關(guān)鍵字的索引文件，其中的索引不能唯一標(biāo)識(shí)記錄，往往同一索引指向若干記錄。因而，索引往往帶有一個(gè)指針表，指向所有該索引標(biāo)識(shí)的記錄。通過(guò)輔索引不能直接讀取記錄，而要通過(guò)主關(guān)鍵字才能查到記錄的位置。倒排文件的主要優(yōu)點(diǎn)是在處理多索引檢索時(shí)，可以在輔檢索中先完成查詢的交、并等邏輯運(yùn)算，得到結(jié)果后再對(duì)記錄進(jìn)行存取，從而提高查找速度。14 GIS的內(nèi)部數(shù)據(jù)

18、結(jié)構(gòu)矢量結(jié)構(gòu)和柵格結(jié)構(gòu)描述地理實(shí)體的數(shù)據(jù)本身的組織方法，稱為內(nèi)部數(shù)據(jù)結(jié)構(gòu)?？臻g數(shù)據(jù)結(jié)構(gòu)是指適合于計(jì)算機(jī)系統(tǒng)存儲(chǔ)、管理和處理的地學(xué)圖形的邏輯結(jié)構(gòu)，是地理實(shí)體的空間排列方式和相互關(guān)系的抽象描述。它是對(duì)數(shù)據(jù)的一種理解和解釋，不說(shuō)明數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)是毫無(wú)用處的，不僅用戶無(wú)法理解，計(jì)算機(jī)程序也不能正確的處理。對(duì)同樣的一組數(shù)據(jù)，按不同的數(shù)據(jù)結(jié)構(gòu)去處理，得到的可能是截然不同的內(nèi)容?？臻g數(shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)溝通信息的橋梁，只有充分理解地理信息系統(tǒng)所采用的特定數(shù)據(jù)結(jié)構(gòu)，才能正確地使用系統(tǒng)。內(nèi)部數(shù)據(jù)結(jié)構(gòu)基本上可分為兩大類：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)（也可以稱為矢量模型和柵格模型）（圖7-3）。兩類結(jié)構(gòu)都可用來(lái)描述地理實(shí)體

19、的點(diǎn)、線、面三種基本類型。空間數(shù)據(jù)編碼是空間數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，即將根據(jù)地理信息系統(tǒng)的目的和任務(wù)所搜集的、經(jīng)過(guò)審核了的地形圖、專題地圖和遙感影像等資料按特定的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適合于計(jì)算機(jī)存儲(chǔ)和處理的數(shù)據(jù)的過(guò)程。由于地理信息系統(tǒng)數(shù)據(jù)量極大，一般采用壓縮數(shù)據(jù)的編碼方式以減少數(shù)據(jù)冗余。在地理信息系統(tǒng)的空間數(shù)據(jù)結(jié)構(gòu)中，柵格結(jié)構(gòu)的編碼方式主要有直接?xùn)鸥窬幋a、鏈碼、游程長(zhǎng)度編碼、塊碼、四叉樹(shù)碼等；矢量結(jié)構(gòu)主要有坐標(biāo)序列編碼、樹(shù)狀索引編碼和二元拓?fù)渚幋a等編碼方法。圖7-3：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)141矢量模型在矢量模型中，現(xiàn)實(shí)世界的要素位置和范圍可以采用點(diǎn)、線或面表達(dá)，與它們?cè)诘貓D上表示相似，每一個(gè)實(shí)體的位置是用它們

20、在坐標(biāo)參考系統(tǒng)中的空間位置（坐標(biāo)）定義。地圖空間中的每一位置都有唯一的坐標(biāo)值。點(diǎn)、線和多邊形用于表達(dá)不規(guī)則的地理實(shí)體在現(xiàn)實(shí)世界的狀態(tài)（多邊形是由若干直線圍成的封閉區(qū)域的邊界）。一條線可能表達(dá)一條道路，一個(gè)多邊形可能表達(dá)一塊林地等。矢量模型中的空間實(shí)體與要表達(dá)的現(xiàn)實(shí)世界中的空間實(shí)體具有一定的對(duì)應(yīng)關(guān)系。142柵格模型在柵格模型中，空間被規(guī)則地劃分為柵格（通常為正方形）。地理實(shí)體的位置和狀態(tài)是用它們占據(jù)的柵格的行、列來(lái)定義的。每個(gè)柵格的大小代表了定義的空間分辨率。由于位置是由柵格行列號(hào)定義的，所以特定的位置由距它最近的柵格記錄決定。例如，某個(gè)區(qū)域被劃分成10*10個(gè)柵格，那么僅能記錄位于這10*10

21、個(gè)柵格附近的物體的位置。柵格的值表達(dá)了這個(gè)位置上物體的類型或狀態(tài)。采用柵格方法，空間被劃分成大量規(guī)則格網(wǎng)，而且每個(gè)柵格取值可能不一樣。空間單元是柵格，每一個(gè)柵格對(duì)應(yīng)于一個(gè)特定的空間位置，如地表的一個(gè)區(qū)域，柵格的值表達(dá)了這個(gè)位置的狀態(tài)。與矢量模型不一樣，柵格模型最小單元與它表達(dá)的真實(shí)世界空間實(shí)體沒(méi)有直接的對(duì)應(yīng)關(guān)系。柵格數(shù)據(jù)模型中的空間實(shí)體單元不是通常概念上理解的物體，它們只是彼此分離的柵格。例如，道路作為明晰的柵格是不存在的，柵格的值才表達(dá)了路是一個(gè)實(shí)體。道路是被具有道路屬性值的一組柵格表達(dá)的，這條路不可能通過(guò)某一柵格實(shí)體被識(shí)別出來(lái)。在這兩種數(shù)據(jù)結(jié)構(gòu)中，空間信息都是使用統(tǒng)一的單位表達(dá)。在柵格方法

22、中，統(tǒng)一的單位是柵格（柵格是不可再分的，其屬性用于表達(dá)對(duì)應(yīng)位置物體的性質(zhì)），表達(dá)一個(gè)區(qū)域所用柵格的數(shù)量很大，但其柵格單元的大小一樣。柵格數(shù)據(jù)文件包含有上百萬(wàn)個(gè)柵格，每個(gè)柵格的位置都被嚴(yán)格定義。在矢量方法中，統(tǒng)一的單元是點(diǎn)、線和多邊形，與柵格方法相比，在數(shù)量上所用的表達(dá)單元較少，但大小可變。在矢量文件中，元素的個(gè)數(shù)或許數(shù)千個(gè)，但畢竟沒(méi)有柵格數(shù)據(jù)那么多。同一類型的矢量單元的位置是用連續(xù)坐標(biāo)值定義。矢量數(shù)據(jù)提供的坐標(biāo)位置比柵格數(shù)據(jù)用行、列號(hào)所表達(dá)位置更精確。這兩種方法各有優(yōu)缺點(diǎn)，究竟采用何種數(shù)據(jù)結(jié)構(gòu)，取決于利用數(shù)據(jù)的目的。有些地理現(xiàn)象用柵格數(shù)據(jù)表達(dá)更合適；有些地理現(xiàn)象則用矢量數(shù)據(jù)更有利，以便表達(dá)它們

23、之間的空間關(guān)系。2柵格數(shù)據(jù)結(jié)構(gòu)及其編碼21柵格數(shù)據(jù)結(jié)構(gòu)211定義柵格結(jié)構(gòu)是最簡(jiǎn)單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個(gè)網(wǎng)格作為一個(gè)象元或象素由行、列定義，并包含一個(gè)代碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。因此，柵格結(jié)構(gòu)是以規(guī)則的陣列來(lái)表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個(gè)數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。如圖7-4所示，在柵格結(jié)構(gòu)中，點(diǎn)用一個(gè)柵格單元表示；線狀地物沿線走向的一組相鄰柵格單元表示，每個(gè)柵格單元最多只有兩個(gè)相鄰單元在線上；面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募媳硎?，每個(gè)柵格單元可有多于兩個(gè)的相鄰單元同屬一個(gè)區(qū)

24、域。遙感影像屬于典型的柵格結(jié)構(gòu)，每個(gè)象元的數(shù)字表示影像的灰度等級(jí)。（a）點(diǎn) （b）線 （c）面圖7-4：點(diǎn)、線、區(qū)域的格網(wǎng)212特點(diǎn)柵格結(jié)構(gòu)的顯著特點(diǎn)是：屬性明顯，定位隱含，即數(shù)據(jù)直接記錄屬性的指針或?qū)傩员旧恚谖恢脛t根據(jù)行列號(hào)轉(zhuǎn)換為相應(yīng)的坐標(biāo)，也就是說(shuō)定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。如圖7-4-（a）所示，數(shù)據(jù)2表示屬性或編碼為2的一個(gè)點(diǎn)，其位置由其所在的第3行、第4列交叉得到的。由于柵格結(jié)構(gòu)是按一定的規(guī)則排列的，所表示的實(shí)體的位置很容易隱含在格網(wǎng)文件的存儲(chǔ)結(jié)構(gòu)中，在后面講述柵格結(jié)構(gòu)編碼時(shí)可以看到，每個(gè)存儲(chǔ)單元的行列位置可以方便地根據(jù)其在文件中的記錄位置得到，且行列坐標(biāo)可以很容易地

25、轉(zhuǎn)為其他坐標(biāo)系下的坐標(biāo)。在格網(wǎng)文件中每個(gè)代碼本身明確地代表了實(shí)體的屬性或?qū)傩缘木幋a，如果為屬性的編碼，則該編碼可作為指向?qū)嶓w屬性表的指針。圖7-4-（a）表示了代碼為2的點(diǎn)實(shí)體，圖7-4-（b）表示了一條代碼為6的線實(shí)體，而圖7-4-（c）則表示了三個(gè)面實(shí)體或稱為區(qū)域?qū)嶓w，代碼分別為4、7和8。由于柵格行列陣列容易為計(jì)算機(jī)存儲(chǔ)、操作和顯示，因此這種結(jié)構(gòu)容易實(shí)現(xiàn)，算法簡(jiǎn)單，且易于擴(kuò)充、修改，也很直觀，特別是易于同遙感影像的結(jié)合處理，給地理空間數(shù)據(jù)處理帶來(lái)了極大的方便。柵格結(jié)構(gòu)表示的地表是不連續(xù)的，是量化和近似離散的數(shù)據(jù)。在柵格結(jié)構(gòu)中，地表被分成相互鄰接、規(guī)則排列的矩形方塊（特殊的情況下也可以是三

26、角形或菱形、六邊形等），每個(gè)地塊與一個(gè)柵格單元相對(duì)應(yīng)。柵格數(shù)據(jù)的比例尺就是柵格大小與地表相應(yīng)單元大小之比。在許多柵格數(shù)據(jù)處理時(shí)，常假設(shè)柵格所表示的量化表面是連續(xù)的，以便使用某些連續(xù)函數(shù)。由于柵格結(jié)構(gòu)對(duì)地表的量化，在計(jì)算面積、長(zhǎng)度、距離、形狀等空間指標(biāo)時(shí)，若柵格尺寸較大，則造成較大的誤差，由于在一個(gè)柵格的地表范圍內(nèi)，可能存在多于一種的地物，而表示在相應(yīng)的柵格結(jié)構(gòu)中常常是一個(gè)代碼。也類似于遙感影像的混合象元問(wèn)題，如Landsat的MSS衛(wèi)星影像單個(gè)象元對(duì)應(yīng)地表79米*79米的矩形區(qū)域，影像上記錄的光譜數(shù)據(jù)是每個(gè)象元所對(duì)應(yīng)的地表區(qū)域內(nèi)所有地物類型的光譜輻射的總和效果。因而，這種誤差不僅有形態(tài)上的畸形

27、，還可能包括屬性方面的偏差。22決定柵格單元代碼的方式在決定柵格代碼時(shí)盡量保持地表的真實(shí)性，保證最大的信息容量。圖7-5所示的一塊矩形地表區(qū)域，內(nèi)部含有A、B、C三種地物類型，O點(diǎn)為中心點(diǎn)，將這個(gè)矩形區(qū)域近似地表示為柵格結(jié)構(gòu)中的一個(gè)柵格單元時(shí)，可根據(jù)需要，采取如下的方式之一來(lái)決定柵格單元的代碼。圖7-5：柵格單元代碼的確定221中心點(diǎn)法用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼，在圖7-5所示的矩形區(qū)域中，中心點(diǎn)O落在代碼為C的地物范圍內(nèi)，按中心點(diǎn)法的規(guī)則，該矩形區(qū)域相應(yīng)的柵格單元代碼為C，中心點(diǎn)法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。222面積占優(yōu)法以占矩形區(qū)域

28、面積最大的地物類型或現(xiàn)象特性決定柵格單元的代碼，在圖7-5所示的例子中，顯見(jiàn)B類地物所占面積最大，故相應(yīng)柵格代碼定為B。面積占優(yōu)法常用于分類較細(xì)，地物類別斑塊較小的情況。223重要性法根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型決定相應(yīng)的柵格單元代碼，假設(shè)圖7-5中A類最重要的地物類型，即A比B和C類更為重要，則柵格單元的代碼應(yīng)為A。重要性法常用于具有特殊意義而面積較小的地理要素，特別是點(diǎn)、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在柵格中代碼應(yīng)盡量表示這些重要地物。224百分比法根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的代碼，如可記面積最大的兩類BA，也可以根據(jù)B

29、類和A類所占面積百分比數(shù)在代碼中加入數(shù)字。23編碼方法231直接?xùn)鸥窬幋a這是最簡(jiǎn)單直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼的圖像文件為網(wǎng)格文件或柵格文件，柵格結(jié)構(gòu)不論采用何種壓縮編碼方法，其邏輯原型都是直接編碼網(wǎng)格文件。直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼，可以每行都從左到右逐個(gè)象元記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序（圖7-6）。圖7-6：一些常用的柵格排列順序232壓縮編碼方法目前有一系列柵格數(shù)據(jù)壓縮編碼方法，如鍵碼、游程長(zhǎng)度編碼、塊碼和四叉樹(shù)編碼等。其目的，就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信

30、息，其類型又有信息無(wú)損編碼和信息有損編碼之分。信息無(wú)損編碼是指編碼過(guò)程中沒(méi)有任何信息損失，通過(guò)解碼操作可以完全恢復(fù)原來(lái)的信息，信息有損編碼是指為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過(guò)程中損失一部分相對(duì)不太重要的信息，解碼時(shí)這部分難以恢復(fù)。在地理信息系統(tǒng)中多采用信息無(wú)損編碼，而對(duì)原始遙感影像進(jìn)行壓縮編碼時(shí)，有時(shí)也采取有損壓縮編碼方法。1）鏈碼（Chain Codes）鏈碼又稱為弗里曼鏈碼Freeman或邊界鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對(duì)于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形數(shù)據(jù)。缺點(diǎn)是對(duì)邊界進(jìn)行合并和插入等修改編輯工作比較困難，對(duì)局部的修改將改變整體

31、結(jié)構(gòu)，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界將被重復(fù)存儲(chǔ)而產(chǎn)生冗余。2）游程長(zhǎng)度編碼（Run-Length Codes）游程長(zhǎng)度編碼是柵格數(shù)據(jù)壓縮的重要編碼方法，它的基本思路是：對(duì)于一幅柵格圖像，常常有行（或列）方向上相鄰的若干點(diǎn)具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。其方法有兩種方案：一種編碼方案是，只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄該代碼以及相同的代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。例如對(duì)圖7-4（c）所示柵格數(shù)據(jù)，可沿行方向進(jìn)行如下游程長(zhǎng)度編碼：（0，1），（4，2），（7，5）；（4，5），（7，3）；（4，4），（8，2），（7

32、，2）；（0，2），（4，1），（8，3），（7，2）；（0，2），（8，4），（7，1），（8，1）；(0，3)，(8，5)；(0，4)，(8，4)；(0，5)，(8，3)。只用了44個(gè)整數(shù)就可以表示，而在前述的直接編碼中卻須要64個(gè)整數(shù)表示，可見(jiàn)游程長(zhǎng)度編碼壓縮數(shù)據(jù)是十分有效又簡(jiǎn)便的。事實(shí)上，壓縮比的大小是與圖的復(fù)雜程度成反比的，在變化多的部分，游程數(shù)就多，變化少的部分游程數(shù)就少，圖件越簡(jiǎn)單，壓縮效率就越高。另一種游程長(zhǎng)度編碼方案就是逐個(gè)記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼，如對(duì)圖7-4（c）所示柵格數(shù)據(jù)的另一種游程長(zhǎng)度編碼如下（沿列方向）：（1，0），（2，4），（4，0），（1

33、，4），（4，0）；（1，4），（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）。游程長(zhǎng)度編碼在柵格壓縮時(shí)，數(shù)據(jù)量沒(méi)有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運(yùn)算簡(jiǎn)單，適用于機(jī)器存儲(chǔ)容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況。3）塊碼塊碼是游程長(zhǎng)度編碼擴(kuò)展到二維的情況，采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置（行、列號(hào)）和半徑，再加上記錄單位的代碼組成。對(duì)圖7-4（c）所示

34、圖像的塊碼編碼如下：(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),

35、(8,5,1,0)。該例中塊碼用了120個(gè)整數(shù)，比直接編碼還多，這是因?yàn)槔袨槊枋龇奖?，柵格劃分很粗糙，在?shí)際應(yīng)用中，柵格劃分細(xì)，數(shù)據(jù)冗余多的多，才能顯出壓縮編碼的效果，而且還可以作一些技術(shù)處理，如行號(hào)可以通過(guò)行間標(biāo)記而省去記錄，行號(hào)和半徑等也不必用雙字節(jié)整數(shù)來(lái)記錄，可進(jìn)一步減少數(shù)據(jù)冗余。塊碼具有可變的分辨率，即當(dāng)代碼變化小時(shí)圖塊大，就是說(shuō)在區(qū)域圖斑內(nèi)部分辨率低；反之，分辨率高以小塊記錄區(qū)域邊界地段，以此達(dá)到壓縮的目的。因此塊碼與游程長(zhǎng)度編碼相似，隨著圖形復(fù)雜程度的提高而降低效率，就是說(shuō)圖斑越大，壓縮比越高；圖斑越碎，壓縮比越低。塊碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。然

36、而在某些操作時(shí)，則必須把游程長(zhǎng)度編碼和塊碼解碼，轉(zhuǎn)換為基本柵格結(jié)構(gòu)進(jìn)行。4）四叉樹(shù)四叉樹(shù)又稱四元樹(shù)或四分樹(shù)，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，絕大部分圖形操作和運(yùn)算都可以直接在四叉樹(shù)結(jié)構(gòu)上實(shí)現(xiàn)，因此四叉樹(shù)編碼既壓縮了數(shù)據(jù)量，又可大大提高圖形操作的效率。四叉樹(shù)將整個(gè)圖像區(qū)逐步分解為一系列被單一類型區(qū)域內(nèi)含的方形區(qū)域，最小的方形區(qū)域?yàn)橐粋€(gè)柵格象元，分割的原則是，將圖像區(qū)域劃分為四個(gè)大小相同的象限，而每個(gè)象限又可根據(jù)一定規(guī)則判斷是否繼續(xù)等分為次一層的四個(gè)象限，其終止判據(jù)是，不管是哪一層上的象限，只要?jiǎng)澐值絻H代表一種地物或符合既定要求的少數(shù)幾種地物時(shí)，則不再繼續(xù)劃分，否則一直劃分到單個(gè)柵格象元為止。

37、四叉樹(shù)通過(guò)樹(shù)狀結(jié)構(gòu)記錄這種劃分，并通過(guò)這種四叉樹(shù)狀結(jié)構(gòu)實(shí)現(xiàn)查詢、修改、量算等操作。圖7-7（b）為圖7-4（c）圖形的四叉樹(shù)分解，各子象限尺度大小不完全一樣，但都是同代碼柵格單元，其四叉樹(shù)如圖7-7-（c）所示。（a）塊碼分割 （b）四叉樹(shù)分割（c）b的四叉樹(shù)編碼圖7-7：四叉樹(shù)編碼其中最上面的那個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)整個(gè)圖形。總共有4層結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)象限，如2層4個(gè)結(jié)點(diǎn)分別對(duì)應(yīng)于整個(gè)圖形的四個(gè)象限，排列次序依次為南西（SW）、南東（SE）、北西（NW）和北東（NE），不能再分的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)（又稱葉子結(jié)點(diǎn)），可能落在不同的層上，該結(jié)點(diǎn)代表的子象限具有單一的代碼，所有終止結(jié)點(diǎn)所代表

38、的方形區(qū)域覆蓋了整個(gè)圖形。從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)如圖7-7(c)所示，共有40個(gè)葉子結(jié)點(diǎn)，也就是原圖被劃分為40個(gè)大小不等的方形子區(qū)，圖7-7(c)的最下面的一排數(shù)字表示各子區(qū)的代碼。由上面圖形的四叉樹(shù)分解可見(jiàn)，四叉樹(shù)中象限的尺寸是大小不一的，位于較高層次的象限較大，深度小即分解次數(shù)少，而低層次上的象限較小，深度大即分解次數(shù)多，這反映了圖上某些位置單一地物分布較廣而另一些位置上的地物比較復(fù)雜，變化較大。正是由于四叉樹(shù)編碼能夠自動(dòng)地依照?qǐng)D形變化而調(diào)整象限尺寸，因此它具有極高的壓縮效率。采用四叉樹(shù)編碼時(shí)，為了保證四叉樹(shù)分解能不斷地進(jìn)行下去，要求圖像必須為2n×2n的柵格陣列，n

39、為極限分割數(shù)，n+1為四叉樹(shù)的最大高度或最大層數(shù)，圖7-4（c）為23×23的柵格，因此最多劃分三次，最大層數(shù)為4，對(duì)于非標(biāo)準(zhǔn)尺寸的圖像需首先通過(guò)增加背景的方法將圖像擴(kuò)充為2n×2n的圖像。為了使計(jì)算機(jī)既能以最小的冗余存儲(chǔ)圖像對(duì)應(yīng)的四叉樹(shù)，又能方便地完成各種圖形圖像操作，專家們已提出了多種編碼方式，下面介紹美國(guó)馬里蘭大學(xué)地理信息系統(tǒng)中采用的編碼方式，該方法記錄了終止結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）的地址和值，值就是子區(qū)的代碼，其中地址包括兩個(gè)部分，共32位（二進(jìn)制），最右邊4位記錄該葉子結(jié)點(diǎn)的深度，即處于四叉樹(shù)的第幾層上，有了深度可以推知子區(qū)的大??；地址由從根結(jié)點(diǎn)到該葉子結(jié)點(diǎn)的路徑表示，

40、0，1，2，3分別表示SW、SE、NW、NE，從右邊第5位開(kāi)始2n字節(jié)記錄這些方向。如圖7-7-（c）表示的第六個(gè)結(jié)點(diǎn)深度為3，第一層處于SW象限，記為0；第二層處于NE象限，記為3，第三層處于NW象限，記為2，表示為二進(jìn)制為：0000 000(22位)；001110（6位）；0011（4位）每層象限位置由兩位二進(jìn)制數(shù)表示，共6位，十進(jìn)制整數(shù)為227。這樣，記錄了各個(gè)葉子的地址，再記上相應(yīng)代碼值，就記錄了這個(gè)圖像，并可在此編碼基礎(chǔ)上進(jìn)行多種圖像操作。事實(shí)上，葉結(jié)點(diǎn)的地址可以直接由子區(qū)左下角的行列坐標(biāo)，按二進(jìn)制按位交錯(cuò)得到。如對(duì)于6號(hào)葉子結(jié)點(diǎn)，在以圖像左下角為原點(diǎn)的行列坐標(biāo)系中，其左下角行、列坐

41、標(biāo)為（3，2），表示為二進(jìn)制分別為011和010，按位交錯(cuò)就是001110，正是6號(hào)地塊。對(duì)于只有點(diǎn)狀地物或只有線狀地物的圖件，為了提高效率，設(shè)計(jì)了略有不同的劃分終止條件和記錄方法，稱為點(diǎn)四叉樹(shù)和線四叉樹(shù)。點(diǎn)四叉樹(shù)對(duì)子象限的劃分直到每個(gè)子象限不含有點(diǎn)或只含有一個(gè)點(diǎn)為止，葉子的值則記錄是否有點(diǎn)和點(diǎn)在子象限的位置；線四叉樹(shù)劃分子象限直到子象限不含線段或只含有單個(gè)線段，對(duì)線的結(jié)點(diǎn)則劃分到單個(gè)象素，其葉子值記錄更為復(fù)雜。四叉樹(shù)編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運(yùn)算可以在編碼數(shù)據(jù)上直接實(shí)現(xiàn)，大大地提高了運(yùn)算效率，是優(yōu)秀的柵格壓縮編碼之一。一般說(shuō)來(lái)，對(duì)數(shù)據(jù)的壓縮是以增加運(yùn)算時(shí)間為代價(jià)

42、的。在這里時(shí)間與空間是一對(duì)矛盾，為了更有效地利用空間資源，減少數(shù)據(jù)冗余，不得不花費(fèi)更多的運(yùn)算時(shí)間進(jìn)行編碼，好的壓縮編碼方法就是要在盡可能減少運(yùn)算時(shí)間的基礎(chǔ)上達(dá)到最大的數(shù)據(jù)壓縮效率，并且是算法適應(yīng)性強(qiáng)，易于實(shí)現(xiàn)。鏈碼的壓縮效率較高，已經(jīng)近矢量結(jié)構(gòu)，對(duì)邊界的運(yùn)算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域運(yùn)算困難；游程長(zhǎng)度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易；塊碼和四叉樹(shù)碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，四叉樹(shù)編碼可以直接進(jìn)行大量圖形圖像運(yùn)算，效率較高，是很有前途的方法。在此基礎(chǔ)上已經(jīng)開(kāi)始發(fā)展了用于三維數(shù)據(jù)的八叉樹(shù)編碼等。3矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

43、31矢量數(shù)據(jù)結(jié)構(gòu)311定義地理信息系統(tǒng)中另一種最常見(jiàn)的圖形數(shù)據(jù)結(jié)構(gòu)為矢量結(jié)構(gòu)，即通過(guò)記錄坐標(biāo)的方式盡可能精確地表示點(diǎn)、線、多邊形等地理實(shí)體，坐標(biāo)空間設(shè)為連續(xù)，允許任意位置、長(zhǎng)度和面積的精確定義，事實(shí)上，其精度僅受數(shù)字化設(shè)備的精度和數(shù)值記錄字長(zhǎng)的限制，在一般情況下，比柵格結(jié)構(gòu)精度高得多。對(duì)于點(diǎn)實(shí)體，矢量結(jié)構(gòu)中只記錄其在特定坐標(biāo)系下的坐標(biāo)和屬性代碼；對(duì)于線實(shí)體，在數(shù)字化時(shí)即進(jìn)行量化，就是用一系列足夠短的直線首尾相接表示一條曲線，當(dāng)曲線被分割成多而短的線段后，這些小線段可以近似地看成直線段，而這條曲線也可以足夠精確地由這些小直線段序列表示，矢量結(jié)構(gòu)中只記錄這些小線段的端點(diǎn)坐標(biāo)，將曲線表示為一個(gè)坐標(biāo)序

44、列，坐標(biāo)之間認(rèn)為是以直線段相連，在一定精度范圍內(nèi)可以逼真地表示各種形狀的線狀地物；“多邊形”在地理信息系統(tǒng)中是指一個(gè)任意形狀、邊界完全閉合的空間區(qū)域。其邊界將整個(gè)空間劃分為兩個(gè)部分：包含無(wú)窮遠(yuǎn)點(diǎn)的部分稱為外部，另一部分稱為多邊形內(nèi)部。把這樣的閉合區(qū)域稱為多邊形是由于區(qū)域的邊界線同前面介紹的線實(shí)體一樣，可以被看作是由一系列多而短的直線段組成，每個(gè)小線段作為這個(gè)區(qū)域的一條邊，因此這種區(qū)域就可以看作是由這些邊組成的多邊形了。跟蹤式數(shù)字化儀對(duì)地圖數(shù)字化產(chǎn)生矢量結(jié)構(gòu)的數(shù)字地圖，適合于矢量繪圖儀繪出。矢量結(jié)構(gòu)允許最復(fù)雜的數(shù)據(jù)以最小的數(shù)據(jù)冗余進(jìn)行存儲(chǔ)，相對(duì)柵格結(jié)構(gòu)來(lái)說(shuō)，數(shù)據(jù)精度高，所占空間小，是高效的空間數(shù)

45、據(jù)結(jié)構(gòu)。312特點(diǎn)矢量結(jié)構(gòu)的特點(diǎn)是：定位明顯、屬性隱含，其定位是根據(jù)坐標(biāo)直接存儲(chǔ)的，而屬性則一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上，這種特點(diǎn)使得其圖形運(yùn)算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，有些甚至難以實(shí)現(xiàn)，當(dāng)然有些地方也有所便利和獨(dú)到之處，在計(jì)算長(zhǎng)度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度，而在疊加運(yùn)算、鄰域搜索等操作時(shí)則比較困難。32編碼方法321點(diǎn)實(shí)體對(duì)于點(diǎn)實(shí)體和線實(shí)體的矢量編碼比較直接，只要能將空間信息和屬性信息記錄完全就可以了。點(diǎn)是空間上不能再分的地理實(shí)體，可以是具體的或抽象的，如地物點(diǎn)、文本位置點(diǎn)或線段網(wǎng)絡(luò)的結(jié)點(diǎn)等，由一對(duì)x、y坐標(biāo)表示。圖7-8-a表

46、示了點(diǎn)的矢量編碼的基本內(nèi)容。322線實(shí)體線實(shí)體主要用來(lái)表示線狀地物（如公路、水系、山脊線等）符號(hào)線和多邊形邊界，有時(shí)也稱為“弧”、“鏈”、“串”等，其矢量編碼一般包括以下內(nèi)容，圖7-8-b為線實(shí)體矢量編碼的基本內(nèi)容。其中唯一標(biāo)識(shí)碼是系統(tǒng)排列序號(hào)；線標(biāo)識(shí)碼可以標(biāo)識(shí)線的類型；起始點(diǎn)和終止點(diǎn)號(hào)可直接用坐標(biāo)表示；顯示信息是顯示時(shí)的文本或符號(hào)等；與線相聯(lián)系的非幾何屬性可以直接存儲(chǔ)于線文件中，也可單獨(dú)存儲(chǔ)，而由標(biāo)識(shí)碼聯(lián)接查找。圖7-8：（a）點(diǎn)實(shí)體的編碼，（b）線實(shí)體的編碼323多邊形多邊形數(shù)據(jù)是描述地理信息的最重要的一類數(shù)據(jù)。在區(qū)域?qū)嶓w中，具有名稱屬性和分類屬性的，多用多邊形表示，如行政區(qū)、土地類型、植

47、被分布等；具有標(biāo)量屬性的，有時(shí)也用等值線描述（如地形、降雨量等）。多邊形矢量編碼不但要表示位置和屬性，更為重要的是要能表達(dá)區(qū)域的拓?fù)湫再|(zhì)，如形狀、鄰域和層次等，以便使這些基本的空間單元可以作為專題圖資料進(jìn)行顯示和操作，由于要表達(dá)的信息十分豐富，基于多邊形的運(yùn)算多而復(fù)雜，因此多邊形矢量編碼比點(diǎn)和線實(shí)體的矢量編碼要復(fù)雜得多，也更為重要。多邊形矢量編碼除有存儲(chǔ)效率的要求外，一般還要求所表示的各多邊形有各自獨(dú)立的形狀，可以計(jì)算各自的周長(zhǎng)和面積等幾何指標(biāo)；各多邊形拓?fù)潢P(guān)系的記錄方式要一致，以便進(jìn)行空間分析；要明確表示區(qū)域的層次，如島-湖-島的關(guān)系等。因此，它與機(jī)助制圖系統(tǒng)僅為顯示和制圖目的而設(shè)計(jì)的編碼有

48、很大不同。1）坐標(biāo)序列法（Spaghetti方式）圖7-9：坐標(biāo)序列法表示的多邊形由多邊形邊界的x、y坐標(biāo)對(duì)集合及說(shuō)明信息組成，是最簡(jiǎn)單的一種多邊形矢量編碼，如圖7-9記為以下坐標(biāo)文件：10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；3

49、0：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；坐標(biāo)序列法文件結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)以多邊形為單位的運(yùn)算和顯示。這種方法的缺點(diǎn)是：（11）多邊形之間的公共邊界被數(shù)字化和存儲(chǔ)兩次，由此產(chǎn)生冗余和碎屑多邊形；（12）每個(gè)

50、多邊形自成體系而缺少鄰域信息，難以進(jìn)行鄰域處理，如消除某兩個(gè)多邊形之間的共同邊界；（13）島只作為一個(gè)單個(gè)的圖形建造，沒(méi)有與外包多邊形的聯(lián)系；（14）不易檢查拓?fù)溴e(cuò)誤。這種方法可用于簡(jiǎn)單的粗精度制圖系統(tǒng)中。2）樹(shù)狀索引編碼法該法采用樹(shù)狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，方法是對(duì)所有邊界點(diǎn)進(jìn)行數(shù)字化，將坐標(biāo)對(duì)以順序方式存儲(chǔ)，由點(diǎn)索引與邊界線號(hào)相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹(shù)狀索引結(jié)構(gòu)。圖7-10和圖7-11分別為圖7-9的多邊形文件和線文件樹(shù)狀索引示意圖。其文件結(jié)構(gòu)如下：圖7-10：線與多邊形之間的樹(shù)狀索引圖7-11：點(diǎn)與邊界線之間的樹(shù)狀索引采用上述的樹(shù)狀結(jié)構(gòu)，圖7-9的多邊形數(shù)據(jù)記

51、錄如下：1）點(diǎn)文件：點(diǎn)號(hào)坐標(biāo)1x1,y12x2,y240x40,y402）線文件線號(hào)起點(diǎn)終點(diǎn)點(diǎn)號(hào)I161,2,3,4,5,6II686,7,8X333333,34,35,36,37,38,39,40,333）多邊形文件多邊形編號(hào)多邊形邊界10I,II,IX20III,VII,VIII,IX,X30X40IV,VI,VII50II,III,IV,V樹(shù)狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問(wèn)題，在簡(jiǎn)化過(guò)于復(fù)雜的邊界線或合并相鄰多邊形時(shí)可不必改造索引表，鄰域信息和島狀信息可以通過(guò)對(duì)多邊形文件的線索引處理得到，但是比較繁瑣，因而給相鄰函數(shù)運(yùn)算，消除無(wú)用邊，處理島狀信息以及檢查拓?fù)潢P(guān)系帶來(lái)一

52、定的困難，而且兩個(gè)編碼表都需要以人工方式建立，工作量大且容易出錯(cuò)。3）拓?fù)浣Y(jié)構(gòu)編碼法要徹底解決鄰域和島狀信息處理問(wèn)題必須建立一個(gè)完整的拓?fù)潢P(guān)系結(jié)構(gòu)，這種結(jié)構(gòu)應(yīng)包括以下內(nèi)容：唯一標(biāo)識(shí)，多邊形標(biāo)識(shí)，外包多邊形指針，鄰接多邊形指針，邊界鏈接，范圍（最大和最小x、y坐標(biāo)值）。采用拓?fù)浣Y(jié)構(gòu)編碼可以較好地解決空間關(guān)系查詢等問(wèn)題，但增加了算法的復(fù)雜性和數(shù)據(jù)庫(kù)的大小。矢量編碼最重要的是信息的完整性和運(yùn)算的靈活性，這是由矢量結(jié)構(gòu)自身的特點(diǎn)所決定的，目前并無(wú)統(tǒng)一的最佳的矢量結(jié)構(gòu)編碼方法，在具體工作中應(yīng)根據(jù)數(shù)據(jù)的特點(diǎn)和任務(wù)的要求而靈活設(shè)計(jì)。DIME(雙重獨(dú)立坐標(biāo)地圖編碼，Dual Independent Map E

53、ncoding)編碼系統(tǒng)DIME是美國(guó)人口調(diào)查局在人口調(diào)查的基礎(chǔ)上發(fā)展起來(lái)的，它通過(guò)有向編碼建立了多邊形、邊界、節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，DIME編碼成為其它拓?fù)渚幋a結(jié)構(gòu)的基礎(chǔ)。4矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法41柵格結(jié)構(gòu)與矢量結(jié)構(gòu)的比較柵格結(jié)構(gòu)與矢量結(jié)構(gòu)似乎是兩種截然不同的空間數(shù)據(jù)結(jié)構(gòu)，柵格結(jié)構(gòu)“屬性明顯、位置隱含”，而矢量結(jié)構(gòu)“位置明顯、屬性隱含”，柵格數(shù)據(jù)操作總的來(lái)說(shuō)比較容易實(shí)現(xiàn)，尤其是作為斑塊圖件的表示更易于為人們接受；而矢量數(shù)據(jù)操作則比較復(fù)雜，許多分析操作（如兩張地圖的覆蓋操作，點(diǎn)或線狀地物的鄰域搜索等）用矢量結(jié)構(gòu)實(shí)現(xiàn)十分困難，矢量結(jié)構(gòu)表達(dá)線狀地物是比較直觀的，而面狀地物則是通過(guò)對(duì)邊界的描述而表

54、達(dá)。無(wú)論哪種結(jié)構(gòu)，數(shù)據(jù)精度和數(shù)據(jù)量都是一對(duì)矛盾，要提高精度，柵格結(jié)構(gòu)需要更多的柵格單元，而矢量結(jié)構(gòu)則需記錄更多的線段結(jié)點(diǎn)。一般來(lái)說(shuō)，柵格結(jié)構(gòu)只是矢量結(jié)構(gòu)在某種程度上的一種近似，如果要使柵格結(jié)構(gòu)描述的圖件取得與矢量結(jié)構(gòu)同樣的精度，甚至僅僅在量值上接近，則數(shù)據(jù)也要比后者大得多。柵格結(jié)構(gòu)在某些操作上比矢量結(jié)構(gòu)更有效更易于實(shí)現(xiàn)，如按空間坐標(biāo)位置的搜索，對(duì)于柵格結(jié)構(gòu)是極為方便的，而對(duì)矢量結(jié)構(gòu)則搜索時(shí)間要長(zhǎng)得多；在給定區(qū)域內(nèi)的統(tǒng)計(jì)指標(biāo)運(yùn)算，包括計(jì)算多邊形形狀、面積、線密度、點(diǎn)密度，柵格結(jié)構(gòu)可以很快算得結(jié)果，而采用矢量結(jié)構(gòu)則由于所在區(qū)域邊界限制條件難以提取而降低效率，對(duì)于給定范圍的開(kāi)窗、縮放柵格結(jié)構(gòu)也比矢量

55、結(jié)構(gòu)優(yōu)越；另一方面，矢量結(jié)構(gòu)用于拓?fù)潢P(guān)系的搜索則更為高效，即諸如計(jì)算多邊形形狀搜索鄰域、層次信息等；對(duì)于網(wǎng)絡(luò)信息只有矢量結(jié)構(gòu)才能完全描述；矢量結(jié)構(gòu)在計(jì)算精度與數(shù)據(jù)量方面的優(yōu)勢(shì)也是矢量結(jié)構(gòu)比柵格結(jié)構(gòu)受到歡迎的原因之一，對(duì)圖7-10而言，假設(shè)坐標(biāo)精度要求為萬(wàn)分之一，即5位數(shù)字，采用矢量結(jié)構(gòu)需記錄40個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)用兩個(gè)雙字節(jié)整數(shù)記錄x、y坐標(biāo)，加上對(duì)其他說(shuō)明信息的描述，200個(gè)字節(jié)足夠了，而若用基本柵格記錄，則需10000*10000=108個(gè)字節(jié)，即使采用單字節(jié)記錄柵格代碼（不超過(guò)255），也需約五百萬(wàn)個(gè)字節(jié)，當(dāng)然實(shí)際圖形的矢量結(jié)構(gòu)記錄采點(diǎn)一般要比圖7-10密得多，但數(shù)據(jù)量仍大大少于柵格結(jié)構(gòu)的

56、數(shù)據(jù)量。柵格結(jié)構(gòu)除了可使大量的空間分析模型得以容易實(shí)現(xiàn)之外，還具有以下兩個(gè)特點(diǎn)：（1）易于與遙感相結(jié)合。遙感影像是以象元為單位的柵格結(jié)構(gòu)，可以直接將原始數(shù)據(jù)或經(jīng)過(guò)處理的影像數(shù)據(jù)納入柵格結(jié)構(gòu)的地理信息系統(tǒng)。（2）易于信息共享。目前還沒(méi)有一種公認(rèn)的矢量結(jié)構(gòu)地圖數(shù)據(jù)記錄格式，而不經(jīng)壓縮編碼的柵格格式即整數(shù)型數(shù)據(jù)庫(kù)陣列則易于為大多數(shù)程序設(shè)計(jì)人員和用戶理解和使用，因此以柵格數(shù)據(jù)為基礎(chǔ)進(jìn)行信息共享的數(shù)據(jù)交流較為實(shí)用。許多實(shí)踐證明，柵格結(jié)構(gòu)和矢量結(jié)構(gòu)在表示空間數(shù)據(jù)上可以是同樣有效的，對(duì)于一個(gè)GIS軟件，較為理想的方案是采用兩種數(shù)據(jù)結(jié)構(gòu)，即柵格結(jié)構(gòu)與矢量結(jié)構(gòu)并存，對(duì)于提高地理信息系統(tǒng)的空間分辨率、數(shù)據(jù)壓縮率和

57、增強(qiáng)系統(tǒng)分析、輸入輸出的靈活性十分重要。兩種格式的比較見(jiàn)表7-2。表7-2：矢量格式與柵格格式的比較優(yōu)點(diǎn)缺點(diǎn)矢量數(shù)據(jù)1數(shù)據(jù)結(jié)構(gòu)緊湊、冗余度低2有利于網(wǎng)絡(luò)和檢索分析3圖形顯示質(zhì)量好、精度高1數(shù)據(jù)結(jié)構(gòu)復(fù)雜2多邊形疊加分析比較困難柵格數(shù)據(jù)1數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單2便于空間分析和地表模擬3現(xiàn)勢(shì)性較強(qiáng)1數(shù)據(jù)量大2投影轉(zhuǎn)換比較復(fù)雜42相互轉(zhuǎn)換算法矢量結(jié)構(gòu)與網(wǎng)格結(jié)構(gòu)的相互轉(zhuǎn)換，是地理信息系統(tǒng)的基本功能之一，目前已經(jīng)發(fā)展了許多高效的轉(zhuǎn)換算法；但是，從柵格數(shù)據(jù)到矢量數(shù)據(jù)的轉(zhuǎn)換，特別是掃描圖像的自動(dòng)識(shí)別，仍然是目前研究的重點(diǎn)。對(duì)于點(diǎn)狀實(shí)體，每個(gè)實(shí)體僅由一個(gè)坐標(biāo)對(duì)表示，其矢量結(jié)構(gòu)和柵格結(jié)構(gòu)的相互轉(zhuǎn)換基本上只是坐標(biāo)精度變換問(wèn)題，不存在太大的技術(shù)問(wèn)題。線實(shí)體的矢量結(jié)構(gòu)由一系列坐標(biāo)對(duì)表示，在變?yōu)闁鸥窠Y(jié)構(gòu)時(shí)，除把序列中坐標(biāo)對(duì)變?yōu)闁鸥裥辛凶鴺?biāo)外，還需根據(jù)柵格精度要求，在坐標(biāo)點(diǎn)之間插滿一系列柵格點(diǎn)，這也容易由兩點(diǎn)式直線方程得到。線實(shí)體由柵格結(jié)構(gòu)變?yōu)槭噶拷Y(jié)構(gòu)與將多邊形邊界表示為矢量結(jié)構(gòu)相似，因此以下重點(diǎn)討論多邊形（面實(shí)體）的矢量結(jié)構(gòu)與柵格結(jié)構(gòu)相互轉(zhuǎn)換。421矢量格式向柵格格式的轉(zhuǎn)換矢量格式向柵格格式轉(zhuǎn)換又稱為多邊形填充，就是在矢