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

2、一般管理信息系統的區別，是數據具有空間分布的性質。對地理信息系統來講，不僅數據本身具有空間屬性，系統的分析和應用也無不與地理環境直接關聯。系統的這一基本特征，深刻地影響著數據的結構、數據庫的設計、分析算法和軟件，以及系統的輸入和輸出。11地理信息系統與一般管理信息系統的比較從數據源的角度來看，圖形和圖像數據是地理信息系統數據的一個主要來源，分析處理的結果也常用圖形的方式來表示。而一般的管理信息系統，則多以統計數據、表格數據為主。這一點也使地理信息系統在硬件和軟件上與一般的管理信息系統有所區別。111兩者的區別1）在硬件上，為了處理圖形和圖像數據，系統需要配置專門的輸入和輸出設備，如數字化儀、繪

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

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

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

6、算法和軟件系統還談不上標準化的問題。事實上，地理信息系統正作為一種空間信息的處理系統，成為一個單獨的研究和發展領域。12空間數據庫121數據庫的概念數據庫就是為一定目的服務，以特定的數據存儲的相關聯的數據集合，它是數據管理的高級階段，是從文件管理系統發展而來的。地理信息系統的數據庫（簡稱空間數據庫或地理數據庫）是某一區域內關于一定地理要素特征的數據集合。為了直觀地理解數據庫，可以把數據庫作如下比較：表7-1：數據庫與圖書館比較數據庫圖書館數據圖書數據模型書卡編目數據的物理組織圖書存放規則、書架數據庫管理系統圖書管理員外存書庫用戶讀者數據存取圖書閱覽122空間數據庫特點空間數據庫與一般數據庫相比

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

8、庫管理最普遍的方法，但是有很多缺點：首先每個應用程序都必須直接訪問所使用的數據文件，應用程序完全依賴于數據文件的存儲結構，數據文件修改時應用程序也隨之修改；另外的問題是數據文件的共享。由于若干用戶或應用程序共享一個數據文件，要修改數據文件必須征得所有用戶的認可。由于缺乏集中控制也會帶來一系列數據庫的安全問題。數據庫的完整性是嚴格的，信息質量很差比沒有信息更糟。數據庫管理系統（Database Management System，DBMS）是在文件處理系統的基礎上進一步發展的系統。DBMS在用戶應用程序和數據文件之間起到了橋梁作用。DBMS的最大優點是提供了兩者之間的數據獨立性，即應用程序訪問數

9、據文件時，不必知道數據文件的物理存儲結構。當數據文件的存儲結構改變時，不必改變應用程序。1）采用標準DBMS存儲空間數據的主要問題* 在“地理信息系統軟件工程技術”一章中“數據管理設計”中詳細描述了各種不同的數據管理方案。用標準的DBMS來存儲空間數據，不如存儲表格數據那樣好，其主要問題包括：（11）在GIS中，空間數據記錄是變長的，因為需要存儲的坐標點的數目是變化的，而一般數據庫都只允許把記錄的長度設定為固定長度。不僅如此，在存儲和維護空間數據拓撲關系方面，DBMS也存在著嚴重的缺陷。因而，一般要對標準的DBMS增加附加的軟件功能。（12）DBMS一般都難以實現對空間數據的關聯、連通、包含、

10、疊加等基本操作。（13）GIS需要一些復雜的圖形功能，一般的DBMS不能支持。（14）地理信息是復雜的，單個地理實體的表達需要多個文件、多條記錄、或許包括大地網、特征坐標、拓撲關系、空間特征量測值、屬性數據的關鍵字以及非空間專題屬性等，一般的DBMS也難以支持。（15）具有高度內部聯系的GIS數據記錄需要更復雜的安全性維護系統，為了保證空間數據庫的完整性，保護數據文件的完整性，保護系列必須與空間數據一起存儲，否則一條記錄的改變就會使其他數據文件產生錯誤。一般的DBMS都難以保證這些。2）GIS數據管理方法主要4種類型（21）對不同的應用模型開發獨立的數據管理服務，這是一種基于文件管理的處理方法

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

12、數據項是可以定義數據的最小單位，也叫元素、基本項、字段等，數據項與現實世界實體的屬性相對應，數據項有一定的取值范圍，稱為域，域以外的任何值對該數據項都是無意義的。每個數據項都有一個名稱，稱為數據項目。數據項的值可以是數值的、字母的、字母數字的、漢字的等形式。數據項的物理特點在于它具有確定的物理長度，可以作為整體看待。2）記錄記錄是由若干相關聯的數據項組成，是處理和存儲信息的基本單位，是關于一個實體的數據總和，構成該記錄的數據項表示實體的若干屬性。記錄有“型”和“值”的區別，“型”是同類記錄的框架，它定義記錄；而“值”是記錄反映實體的內容。為了唯一標識每個記錄，就必須有記錄標識符，也叫關鍵字。記

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

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

15、組織數據，以及實施對數據的訪問方式等問題。操作系統實現的文件組織方式，可以分為順序文件、索引文件、直接文件和倒排文件。1）順序文件順序文件（圖7-2）是最簡單的文件組織形式，對記錄按照主關鍵字的順序進行組織。當主關鍵字是數字型時，以其數值的大小為序；若主關鍵字是文字型的，則以字母的排列為序。一切存于磁帶上的記錄，都只能是順序的，而存于磁盤上的記錄，既可以是順序的，也可以是隨機的。順序文件的記錄，邏輯上是按主關鍵字排序的，而在物理存儲上可以有不同的方式，包括向量方式：被存儲的文件按地址連續存放，物理結構與邏輯結構一致；鏈方式：文件不按地址連續存放，文件的邏輯順序靠鏈來實現，文件中的每個記錄中都含

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

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

18、結構矢量結構和柵格結構描述地理實體的數據本身的組織方法，稱為內部數據結構。空間數據結構是指適合于計算機系統存儲、管理和處理的地學圖形的邏輯結構，是地理實體的空間排列方式和相互關系的抽象描述。它是對數據的一種理解和解釋，不說明數據結構的數據是毫無用處的，不僅用戶無法理解，計算機程序也不能正確的處理。對同樣的一組數據，按不同的數據結構去處理，得到的可能是截然不同的內容。空間數據結構是地理信息系統溝通信息的橋梁，只有充分理解地理信息系統所采用的特定數據結構，才能正確地使用系統。內部數據結構基本上可分為兩大類：矢量結構和柵格結構（也可以稱為矢量模型和柵格模型）（圖7-3）。兩類結構都可用來描述地理實體

19、的點、線、面三種基本類型。空間數據編碼是空間數據結構的實現，即將根據地理信息系統的目的和任務所搜集的、經過審核了的地形圖、專題地圖和遙感影像等資料按特定的數據結構轉換為適合于計算機存儲和處理的數據的過程。由于地理信息系統數據量極大，一般采用壓縮數據的編碼方式以減少數據冗余。在地理信息系統的空間數據結構中，柵格結構的編碼方式主要有直接柵格編碼、鏈碼、游程長度編碼、塊碼、四叉樹碼等；矢量結構主要有坐標序列編碼、樹狀索引編碼和二元拓撲編碼等編碼方法。圖7-3：矢量結構和柵格結構141矢量模型在矢量模型中，現實世界的要素位置和范圍可以采用點、線或面表達，與它們在地圖上表示相似，每一個實體的位置是用它們

20、在坐標參考系統中的空間位置（坐標）定義。地圖空間中的每一位置都有唯一的坐標值。點、線和多邊形用于表達不規則的地理實體在現實世界的狀態（多邊形是由若干直線圍成的封閉區域的邊界）。一條線可能表達一條道路，一個多邊形可能表達一塊林地等。矢量模型中的空間實體與要表達的現實世界中的空間實體具有一定的對應關系。142柵格模型在柵格模型中，空間被規則地劃分為柵格（通常為正方形）。地理實體的位置和狀態是用它們占據的柵格的行、列來定義的。每個柵格的大小代表了定義的空間分辨率。由于位置是由柵格行列號定義的，所以特定的位置由距它最近的柵格記錄決定。例如，某個區域被劃分成10*10個柵格，那么僅能記錄位于這10*10

21、個柵格附近的物體的位置。柵格的值表達了這個位置上物體的類型或狀態。采用柵格方法，空間被劃分成大量規則格網，而且每個柵格取值可能不一樣。空間單元是柵格，每一個柵格對應于一個特定的空間位置，如地表的一個區域，柵格的值表達了這個位置的狀態。與矢量模型不一樣，柵格模型最小單元與它表達的真實世界空間實體沒有直接的對應關系。柵格數據模型中的空間實體單元不是通常概念上理解的物體，它們只是彼此分離的柵格。例如，道路作為明晰的柵格是不存在的，柵格的值才表達了路是一個實體。道路是被具有道路屬性值的一組柵格表達的，這條路不可能通過某一柵格實體被識別出來。在這兩種數據結構中，空間信息都是使用統一的單位表達。在柵格方法

22、中，統一的單位是柵格（柵格是不可再分的，其屬性用于表達對應位置物體的性質），表達一個區域所用柵格的數量很大，但其柵格單元的大小一樣。柵格數據文件包含有上百萬個柵格，每個柵格的位置都被嚴格定義。在矢量方法中，統一的單元是點、線和多邊形，與柵格方法相比，在數量上所用的表達單元較少，但大小可變。在矢量文件中，元素的個數或許數千個，但畢竟沒有柵格數據那么多。同一類型的矢量單元的位置是用連續坐標值定義。矢量數據提供的坐標位置比柵格數據用行、列號所表達位置更精確。這兩種方法各有優缺點，究竟采用何種數據結構，取決于利用數據的目的。有些地理現象用柵格數據表達更合適；有些地理現象則用矢量數據更有利，以便表達它們

23、之間的空間關系。2柵格數據結構及其編碼21柵格數據結構211定義柵格結構是最簡單最直接的空間數據結構，是指將地球表面劃分為大小均勻緊密相鄰的網格陣列，每個網格作為一個象元或象素由行、列定義，并包含一個代碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。因此，柵格結構是以規則的陣列來表示空間地物或現象分布的數據組織，組織中的每個數據表示地物或現象的非幾何屬性特征。如圖7-4所示，在柵格結構中，點用一個柵格單元表示；線狀地物沿線走向的一組相鄰柵格單元表示，每個柵格單元最多只有兩個相鄰單元在線上；面或區域用記有區域屬性的相鄰柵格單元的集合表示，每個柵格單元可有多于兩個的相鄰單元同屬一個區

24、域。遙感影像屬于典型的柵格結構，每個象元的數字表示影像的灰度等級。（a）點 （b）線 （c）面圖7-4：點、線、區域的格網212特點柵格結構的顯著特點是：屬性明顯，定位隱含，即數據直接記錄屬性的指針或屬性本身，而所在位置則根據行列號轉換為相應的坐標，也就是說定位是根據數據在數據集中的位置得到的。如圖7-4-（a）所示，數據2表示屬性或編碼為2的一個點，其位置由其所在的第3行、第4列交叉得到的。由于柵格結構是按一定的規則排列的，所表示的實體的位置很容易隱含在格網文件的存儲結構中，在后面講述柵格結構編碼時可以看到，每個存儲單元的行列位置可以方便地根據其在文件中的記錄位置得到，且行列坐標可以很容易地

25、轉為其他坐標系下的坐標。在格網文件中每個代碼本身明確地代表了實體的屬性或屬性的編碼，如果為屬性的編碼，則該編碼可作為指向實體屬性表的指針。圖7-4-（a）表示了代碼為2的點實體，圖7-4-（b）表示了一條代碼為6的線實體，而圖7-4-（c）則表示了三個面實體或稱為區域實體，代碼分別為4、7和8。由于柵格行列陣列容易為計算機存儲、操作和顯示，因此這種結構容易實現，算法簡單，且易于擴充、修改，也很直觀，特別是易于同遙感影像的結合處理，給地理空間數據處理帶來了極大的方便。柵格結構表示的地表是不連續的，是量化和近似離散的數據。在柵格結構中，地表被分成相互鄰接、規則排列的矩形方塊（特殊的情況下也可以是三

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

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

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

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

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

31、結構，效率較低，而且由于鏈碼以每個區域為單位存儲邊界，相鄰區域的邊界將被重復存儲而產生冗余。2）游程長度編碼（Run-Length Codes）游程長度編碼是柵格數據壓縮的重要編碼方法，它的基本思路是：對于一幅柵格圖像，常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復的記錄內容。其方法有兩種方案：一種編碼方案是，只在各行（或列）數據的代碼發生變化時依次記錄該代碼以及相同的代碼重復的個數，從而實現數據的壓縮。例如對圖7-4（c）所示柵格數據，可沿行方向進行如下游程長度編碼：（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個整數就可以表示，而在前述的直接編碼中卻須要64個整數表示，可見游程長度編碼壓縮數據是十分有效又簡便的。事實上，壓縮比的大小是與圖的復雜程度成反比的，在變化多的部分，游程數就多，變化少的部分游程數就少，圖件越簡單，壓縮效率就越高。另一種游程長度編碼方案就是逐個記錄各行（或列）代碼發生變化的位置和相應代碼，如對圖7-4（c）所示柵格數據的另一種游程長度編碼如下（沿列方向）：（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）。游程長度編碼在柵格壓縮時，數據量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運算簡單，適用于機器存儲容量小，數據需大量壓縮，而又要避免復雜的編碼解碼運算增加處理和操作時間的情況。3）塊碼塊碼是游程長度編碼擴展到二維的情況，采用方形區域作為記錄單元，每個記錄單元包括相鄰的若干柵格，數據結構由初始位置（行、列號）和半徑，再加上記錄單位的代碼組成。對圖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個整數，比直接編碼還多，這是因為例中為描述方便，柵格劃分很粗糙，在實際應用中，柵格劃分細，數據冗余多的多，才能顯出壓縮編碼的效果，而且還可以作一些技術處理，如行號可以通過行間標記而省去記錄，行號和半徑等也不必用雙字節整數來記錄，可進一步減少數據冗余。塊碼具有可變的分辨率，即當代碼變化小時圖塊大，就是說在區域圖斑內部分辨率低；反之，分辨率高以小塊記錄區域邊界地段，以此達到壓縮的目的。因此塊碼與游程長度編碼相似，隨著圖形復雜程度的提高而降低效率，就是說圖斑越大，壓縮比越高；圖斑越碎，壓縮比越低。塊碼在合并、插入、檢查延伸性、計算面積等操作時有明顯的優越性。然

36、而在某些操作時，則必須把游程長度編碼和塊碼解碼，轉換為基本柵格結構進行。4）四叉樹四叉樹又稱四元樹或四分樹，是最有效的柵格數據壓縮編碼方法之一，絕大部分圖形操作和運算都可以直接在四叉樹結構上實現，因此四叉樹編碼既壓縮了數據量，又可大大提高圖形操作的效率。四叉樹將整個圖像區逐步分解為一系列被單一類型區域內含的方形區域，最小的方形區域為一個柵格象元，分割的原則是，將圖像區域劃分為四個大小相同的象限，而每個象限又可根據一定規則判斷是否繼續等分為次一層的四個象限，其終止判據是，不管是哪一層上的象限，只要劃分到僅代表一種地物或符合既定要求的少數幾種地物時，則不再繼續劃分，否則一直劃分到單個柵格象元為止。

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

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

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

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

41、標為（3，2），表示為二進制分別為011和010，按位交錯就是001110，正是6號地塊。對于只有點狀地物或只有線狀地物的圖件，為了提高效率，設計了略有不同的劃分終止條件和記錄方法，稱為點四叉樹和線四叉樹。點四叉樹對子象限的劃分直到每個子象限不含有點或只含有一個點為止，葉子的值則記錄是否有點和點在子象限的位置；線四叉樹劃分子象限直到子象限不含線段或只含有單個線段，對線的結點則劃分到單個象素，其葉子值記錄更為復雜。四叉樹編碼具有可變的分辨率，并且有區域性質，壓縮數據靈活，許多運算可以在編碼數據上直接實現，大大地提高了運算效率，是優秀的柵格壓縮編碼之一。一般說來，對數據的壓縮是以增加運算時間為代價

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

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

44、列，坐標之間認為是以直線段相連，在一定精度范圍內可以逼真地表示各種形狀的線狀地物；“多邊形”在地理信息系統中是指一個任意形狀、邊界完全閉合的空間區域。其邊界將整個空間劃分為兩個部分：包含無窮遠點的部分稱為外部，另一部分稱為多邊形內部。把這樣的閉合區域稱為多邊形是由于區域的邊界線同前面介紹的線實體一樣，可以被看作是由一系列多而短的直線段組成，每個小線段作為這個區域的一條邊，因此這種區域就可以看作是由這些邊組成的多邊形了。跟蹤式數字化儀對地圖數字化產生矢量結構的數字地圖，適合于矢量繪圖儀繪出。矢量結構允許最復雜的數據以最小的數據冗余進行存儲，相對柵格結構來說，數據精度高，所占空間小，是高效的空間數

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

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

47、被分布等；具有標量屬性的，有時也用等值線描述（如地形、降雨量等）。多邊形矢量編碼不但要表示位置和屬性，更為重要的是要能表達區域的拓撲性質，如形狀、鄰域和層次等，以便使這些基本的空間單元可以作為專題圖資料進行顯示和操作，由于要表達的信息十分豐富，基于多邊形的運算多而復雜，因此多邊形矢量編碼比點和線實體的矢量編碼要復雜得多，也更為重要。多邊形矢量編碼除有存儲效率的要求外，一般還要求所表示的各多邊形有各自獨立的形狀，可以計算各自的周長和面積等幾何指標；各多邊形拓撲關系的記錄方式要一致，以便進行空間分析；要明確表示區域的層次，如島-湖-島的關系等。因此，它與機助制圖系統僅為顯示和制圖目的而設計的編碼有

48、很大不同。1）坐標序列法（Spaghetti方式）圖7-9：坐標序列法表示的多邊形由多邊形邊界的x、y坐標對集合及說明信息組成，是最簡單的一種多邊形矢量編碼，如圖7-9記為以下坐標文件：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；坐標序列法文件結構簡單，易于實現以多邊形為單位的運算和顯示。這種方法的缺點是：（11）多邊形之間的公共邊界被數字化和存儲兩次，由此產生冗余和碎屑多邊形；（12）每個

50、多邊形自成體系而缺少鄰域信息，難以進行鄰域處理，如消除某兩個多邊形之間的共同邊界；（13）島只作為一個單個的圖形建造，沒有與外包多邊形的聯系；（14）不易檢查拓撲錯誤。這種方法可用于簡單的粗精度制圖系統中。2）樹狀索引編碼法該法采用樹狀索引以減少數據冗余并間接增加鄰域信息，方法是對所有邊界點進行數字化，將坐標對以順序方式存儲，由點索引與邊界線號相聯系，以線索引與各多邊形相聯系，形成樹狀索引結構。圖7-10和圖7-11分別為圖7-9的多邊形文件和線文件樹狀索引示意圖。其文件結構如下：圖7-10：線與多邊形之間的樹狀索引圖7-11：點與邊界線之間的樹狀索引采用上述的樹狀結構，圖7-9的多邊形數據記

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

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

53、ncoding)編碼系統DIME是美國人口調查局在人口調查的基礎上發展起來的，它通過有向編碼建立了多邊形、邊界、節點之間的拓撲關系，DIME編碼成為其它拓撲編碼結構的基礎。4矢柵結構的比較及轉換算法41柵格結構與矢量結構的比較柵格結構與矢量結構似乎是兩種截然不同的空間數據結構，柵格結構“屬性明顯、位置隱含”，而矢量結構“位置明顯、屬性隱含”，柵格數據操作總的來說比較容易實現，尤其是作為斑塊圖件的表示更易于為人們接受；而矢量數據操作則比較復雜，許多分析操作（如兩張地圖的覆蓋操作，點或線狀地物的鄰域搜索等）用矢量結構實現十分困難，矢量結構表達線狀地物是比較直觀的，而面狀地物則是通過對邊界的描述而表

54、達。無論哪種結構，數據精度和數據量都是一對矛盾，要提高精度，柵格結構需要更多的柵格單元，而矢量結構則需記錄更多的線段結點。一般來說，柵格結構只是矢量結構在某種程度上的一種近似，如果要使柵格結構描述的圖件取得與矢量結構同樣的精度，甚至僅僅在量值上接近，則數據也要比后者大得多。柵格結構在某些操作上比矢量結構更有效更易于實現，如按空間坐標位置的搜索，對于柵格結構是極為方便的，而對矢量結構則搜索時間要長得多；在給定區域內的統計指標運算，包括計算多邊形形狀、面積、線密度、點密度，柵格結構可以很快算得結果，而采用矢量結構則由于所在區域邊界限制條件難以提取而降低效率，對于給定范圍的開窗、縮放柵格結構也比矢量

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

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

57、增強系統分析、輸入輸出的靈活性十分重要。兩種格式的比較見表7-2。表7-2：矢量格式與柵格格式的比較優點缺點矢量數據1數據結構緊湊、冗余度低2有利于網絡和檢索分析3圖形顯示質量好、精度高1數據結構復雜2多邊形疊加分析比較困難柵格數據1數據結構簡單2便于空間分析和地表模擬3現勢性較強1數據量大2投影轉換比較復雜42相互轉換算法矢量結構與網格結構的相互轉換，是地理信息系統的基本功能之一，目前已經發展了許多高效的轉換算法；但是，從柵格數據到矢量數據的轉換，特別是掃描圖像的自動識別，仍然是目前研究的重點。對于點狀實體，每個實體僅由一個坐標對表示，其矢量結構和柵格結構的相互轉換基本上只是坐標精度變換問題，不存在太大的技術問題。線實體的矢量結構由一系列坐標對表示，在變為柵格結構時，除把序列中坐標對變為柵格行列坐標外，還需根據柵格精度要求，在坐標點之間插滿一系列柵格點，這也容易由兩點式直線方程得到。線實體由柵格結構變為矢量結構與將多邊形邊界表示為矢量結構相似，因此以下重點討論多邊形（面實體）的矢量結構與柵格結構相互轉換。421矢量格式向柵格格式的轉換矢量格式向柵格格式轉換又稱為多邊形填充，就是在矢