《空間數(shù)據(jù)管理》復(fù)習(xí)資料

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

導(dǎo)讀：本章首先介紹空間數(shù)據(jù)庫、與一般數(shù)據(jù)庫的比較，以及空間數(shù)據(jù)庫的存儲(chǔ)方

式。

然后介紹了GIS中兩種重要的數(shù)據(jù)結(jié)構(gòu)：柵格結(jié)構(gòu)和矢量結(jié)構(gòu)，以及其具體的存儲(chǔ)

方式，然后比較了兩種結(jié)構(gòu)的特點(diǎn)，并給出了其相互轉(zhuǎn)換算法。

最后介紹了空間檢索中常用的技術(shù)——空間索引，介紹了一些常用的空間索引方式，

如BSP樹、R樹、CELL樹等；以及空間數(shù)據(jù)的查詢功能。

1.空間數(shù)據(jù)庫

一個(gè)信息系統(tǒng)及其數(shù)據(jù)庫的組成，決定于系統(tǒng)的應(yīng)用目的、數(shù)據(jù)類型和系統(tǒng)的工作方式。

關(guān)于地理信息系統(tǒng)的內(nèi)容及其功能，以及地理信息系統(tǒng)的一個(gè)重要特點(diǎn)，或者說是與一般管

理信息系統(tǒng)的區(qū)別，是數(shù)據(jù)具有空間分布的性質(zhì)。對(duì)地理信息系統(tǒng)來講，不僅數(shù)據(jù)本身具有

空間屬性，系統(tǒng)的分析和應(yīng)用也無不與地理環(huán)境直接關(guān)聯(lián)。系統(tǒng)的這一基本特征，深刻地影

響著數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)庫的設(shè)計(jì)、分析算法和軟件，以及系統(tǒng)的輸入和輸出。

1.1地理信息系統(tǒng)與一般管理信息系統(tǒng)的比較

從數(shù)據(jù)源的角度來看，圖形和圖像數(shù)據(jù)是地理信息系統(tǒng)數(shù)據(jù)的一個(gè)主要來源，分析處理

的結(jié)果也常用圖形的方式來表示。而一般的管理信息系統(tǒng)，則多以統(tǒng)計(jì)數(shù)據(jù)、表格數(shù)據(jù)為主。

這一點(diǎn)也使地理信息系統(tǒng)在硬件和軟件上與一般的管理信息系統(tǒng)有所區(qū)別。

1.1.1兩者的區(qū)別

1）在硬件上，為了處理圖形和圖像數(shù)據(jù)，系統(tǒng)需要配置專門的輸入和輸出設(shè)備，如數(shù)

字化儀、繪圖機(jī)、圖形圖像的顯示設(shè)備等；許多野外實(shí)地采集和臺(tái)站的觀測(cè)所得到的資源信

息是模擬量形式，系統(tǒng)還需要配置模一一數(shù)轉(zhuǎn)換設(shè)備，這些設(shè)備往往超過中央處理機(jī)的價(jià)格,

體積也比較大。

2）在軟件上，則要求研制專門的圖形和圖像數(shù)據(jù)的分析算法和處理軟件，這些算法和

軟件又直接和數(shù)據(jù)的結(jié)構(gòu)及數(shù)據(jù)庫的管理方法有關(guān)。

3）在信息處理的內(nèi)容和采用目的方面，一般的管理信息系統(tǒng)，主要是查詢檢索和統(tǒng)計(jì)

分析，處理的結(jié)果，大多是制成某種規(guī)定格式的表格數(shù)據(jù)，而地理信息系統(tǒng)，除了基本的信

息檢索和統(tǒng)計(jì)分析外，主要用于分析研究資源的合理開發(fā)利用，制定區(qū)域發(fā)展規(guī)劃，地區(qū)的

綜合治理方案，對(duì)環(huán)境進(jìn)行動(dòng)態(tài)的監(jiān)視和預(yù)測(cè)預(yù)報(bào),為國民經(jīng)濟(jì)建設(shè)中的決策提供科學(xué)依據(jù),

為生產(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)度、密度、分布特征等以及地理實(shí)體之間的關(guān)系運(yùn)算。

1.1.2兩者共同之處

地理信息系統(tǒng)和一般的信息管理系統(tǒng)，也有許多共同之處。兩者都是以計(jì)算機(jī)為核心的

信息處理系統(tǒng)，都具有數(shù)據(jù)量大和數(shù)據(jù)之間關(guān)系復(fù)雜的特點(diǎn)，也都隨著數(shù)據(jù)庫技術(shù)的發(fā)展在

不斷的改進(jìn)和完善。比較起來，商用的管理信息系統(tǒng)發(fā)展快，用戶數(shù)量大，而且已有定型的

軟件產(chǎn)品可供選用，這也促進(jìn)了軟件系統(tǒng)的標(biāo)準(zhǔn)化。地理信息系統(tǒng)，由于上述一些特點(diǎn)，多

是根據(jù)具體的應(yīng)用要求專門設(shè)計(jì)，數(shù)據(jù)格式和組織管理方法各不相同。目前國外已有幾百個(gè)

空間數(shù)據(jù)處理系統(tǒng)和軟件包，幾乎沒有兩個(gè)系統(tǒng)是一樣的，盡管大家都認(rèn)為標(biāo)準(zhǔn)化是很重要

的，也作了許多努力（例如建立計(jì)算機(jī)制圖的標(biāo)準(zhǔn)和規(guī)范），但分析的算法和軟件系統(tǒng)還談

不上標(biāo)準(zhǔn)化的問題。事實(shí)上，地理信息系統(tǒng)正作為一種空間信息的處理系統(tǒng)，成為一個(gè)單獨(dú)

的研究和發(fā)展領(lǐng)域。

1.2空間數(shù)據(jù)庫

1.2.1數(shù)據(jù)庫的概念

數(shù)據(jù)庫就是為一定目的服務(wù)，以特定的數(shù)據(jù)存儲(chǔ)的相關(guān)聯(lián)的數(shù)據(jù)集合，它是數(shù)據(jù)管理的

高級(jí)階段，是從文件管理系統(tǒng)發(fā)展而來的。地理信息系統(tǒng)的數(shù)據(jù)庫（簡(jiǎn)稱空間數(shù)據(jù)庫或地理

數(shù)據(jù)庫）是某一區(qū)域內(nèi)關(guān)于一定地理要素特征的數(shù)據(jù)集合。為了直觀地理解數(shù)據(jù)庫，可以把

數(shù)據(jù)庫作如下比較：

表7-1：數(shù)據(jù)庫與圖書館比較

數(shù)據(jù)庫圖書館

數(shù)據(jù)圖書

數(shù)據(jù)模型書卡編目

數(shù)據(jù)的物理組織圖書存放規(guī)則、書架

數(shù)據(jù)庫管理系統(tǒng)圖書管理員

外存書庫

用戶讀者

數(shù)據(jù)存取圖書閱覽

1.2.2空間數(shù)據(jù)庫特點(diǎn)

空間數(shù)據(jù)庫與一般數(shù)據(jù)庫相比，具有以下特點(diǎn)：

1）數(shù)據(jù)量特別大，地理系統(tǒng)是一個(gè)復(fù)雜的綜合體，要用數(shù)據(jù)來描述各種地理要素，尤

其是要素的空間位置，其數(shù)據(jù)量往往很大.

2）不僅有地理要素的屬性數(shù)據(jù)（與一般數(shù)據(jù)庫中的數(shù)據(jù)性質(zhì)相似），還有大量的空間數(shù)

據(jù)，即描述地理要素空間分布位置的數(shù)據(jù)，并且這兩種數(shù)據(jù)之間具有不可分割的聯(lián)系。

3）數(shù)據(jù)應(yīng)用廣泛，例如地理研究、環(huán)境保護(hù)、土地利用與規(guī)劃、資源開發(fā)、生態(tài)環(huán)境、

市政管理、道路建設(shè)等。

1.2.3數(shù)據(jù)庫管理系統(tǒng)

數(shù)據(jù)庫是關(guān)于事物及其關(guān)系的信息組合，早期的數(shù)據(jù)庫物體本身與其屬性是分開存儲(chǔ)

的，只能滿足簡(jiǎn)單的數(shù)據(jù)恢復(fù)和使用。數(shù)據(jù)定義使用特定的數(shù)據(jù)結(jié)構(gòu)定義，利用文件形式存

儲(chǔ)，稱之為文件處理系統(tǒng)。

文件處理系統(tǒng)是數(shù)據(jù)庫管理最普遍的方法，但是有很多缺點(diǎn)：首先每個(gè)應(yīng)用程序都必須

直接訪問所使用的數(shù)據(jù)文件，應(yīng)用程序完全依賴于數(shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)文件修改時(shí)應(yīng)

用程序也隨之修改；另外的問題是數(shù)據(jù)文件的共享。由于若干用戶或應(yīng)用程序共享一個(gè)數(shù)據(jù)

文件，要修改數(shù)據(jù)文件必須征得所有用戶的認(rèn)可。由于缺乏集中控制也會(huì)帶來一系列數(shù)據(jù)庫

的安全問題。數(shù)據(jù)庫的完整性是嚴(yán)格的，信息質(zhì)量很差比沒有信息更糟。

數(shù)據(jù)庫管理系統(tǒng)(DatabaseManagementSystem,DBMS)是在文件處理系統(tǒng)的基礎(chǔ)上

進(jìn)一步發(fā)展的系統(tǒng)。DBMS在用戶應(yīng)用程序和數(shù)據(jù)文件之間起到了橋梁作用。DBMS的最

大優(yōu)點(diǎn)是提供了兩者之間的數(shù)據(jù)獨(dú)立性，即應(yīng)用程序訪問數(shù)據(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ù)的主要問題*

用標(biāo)準(zhǔn)的DBMS來存儲(chǔ)空間數(shù)據(jù)，不如存儲(chǔ)表格數(shù)據(jù)那樣好，其主要問題包括：

(1.1)在GIS中，空間數(shù)據(jù)記錄是變長(zhǎng)的，因?yàn)樾枰鎯?chǔ)的坐標(biāo)點(diǎn)的數(shù)目是變化的,

而一般數(shù)據(jù)庫都只允許把記錄的長(zhǎng)度設(shè)定為固定長(zhǎng)度。不僅如此，在存儲(chǔ)和維護(hù)空間數(shù)據(jù)拓

撲關(guān)系方面，DBMS也存在著嚴(yán)重的缺陷。因而，一般要對(duì)標(biāo)準(zhǔn)的DBMS增加附加的軟件

功能。

(1.2)DBMS一般都難以實(shí)現(xiàn)對(duì)空間數(shù)據(jù)的關(guān)聯(lián)、連通、包含、疊加等基本操作。

(1.3)GIS需要一些復(fù)雜的圖形功能，一般的DBMS不能支持。

(1.4)地理信息是復(fù)雜的，單個(gè)地理實(shí)體的表達(dá)需要多個(gè)文件、多條記錄、或許包括

大地網(wǎng)、特征坐標(biāo)、拓?fù)潢P(guān)系、空間特征量測(cè)值、屬性數(shù)據(jù)的關(guān)鍵字以及非空間專題屬性等,

一般的DBMS也難以支持。

(1.5)具有高度內(nèi)部聯(lián)系的GIS數(shù)據(jù)記錄需要更復(fù)雜的安全性維護(hù)系統(tǒng)，為了保證

空間數(shù)據(jù)庫的完整性，保護(hù)數(shù)據(jù)文件的完整性，保護(hù)系列必須與空間數(shù)據(jù)一起存儲(chǔ)，否則一

條記錄的改變就會(huì)使其他數(shù)據(jù)文件產(chǎn)生錯(cuò)誤。一般的DBMS都難以保證這些。

2)GIS數(shù)據(jù)管理方法主要4種類型

(2.1)對(duì)不同的應(yīng)用模型開發(fā)獨(dú)立的數(shù)據(jù)管理服務(wù)，這是一種基于文件管理的處理方

法。

(2.2)在商業(yè)化的DBMS基礎(chǔ)上開發(fā)附加系統(tǒng)。開發(fā)一個(gè)附加軟件用于存儲(chǔ)和管理

空間數(shù)據(jù)和空間分析，使用DBMS管理屬性數(shù)據(jù)。

(2.3)使用現(xiàn)有的DBMS,通常是以DBMS為核心，對(duì)系統(tǒng)的功能進(jìn)行必要擴(kuò)充，

空間數(shù)據(jù)和屬性數(shù)據(jù)在同一個(gè)DBMS管理之下。需要增加足夠數(shù)量的軟件和功能來提供空

間功能和圖形顯示功能。

(2.4)重新設(shè)計(jì)一個(gè)具有空間數(shù)據(jù)和屬性數(shù)據(jù)管理和分析功能的數(shù)據(jù)庫系統(tǒng)。

*在“地理信息系統(tǒng)軟件工程技術(shù)”一章中“數(shù)據(jù)管理設(shè)計(jì)”中詳細(xì)描述了各種不同的數(shù)據(jù)管理方案。

1.3數(shù)據(jù)與文件組織

數(shù)據(jù)是現(xiàn)實(shí)世界中信息的載體，是信息的具體表達(dá)形式，為了表達(dá)有意義的信息內(nèi)容，

數(shù)據(jù)必須按照一定的方式進(jìn)行組織和存儲(chǔ)。

1.3.1數(shù)據(jù)組織的分級(jí)

數(shù)據(jù)庫中的數(shù)據(jù)組織一般可以分為四級(jí)：數(shù)據(jù)項(xiàng)、記錄、文件和數(shù)據(jù)庫。

1）數(shù)據(jù)項(xiàng)

數(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)都是無意

義的.每個(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)鍵字。記錄標(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ú)立意義來劃分的數(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ù)庫

數(shù)據(jù)庫是比文件更大的數(shù)據(jù)組織，數(shù)據(jù)庫是具有特定聯(lián)系的數(shù)據(jù)的集合，也可以看成是

具有特定聯(lián)系的多種類型的記錄的集合。數(shù)據(jù)庫的內(nèi)部構(gòu)造是文件的集合，這些文件之間存

在某種聯(lián)系，不能孤立存在。

1.3.2數(shù)據(jù)間的邏輯聯(lián)系

數(shù)據(jù)間的邏輯聯(lián)系主要是指記錄與記錄之間的聯(lián)系。記錄是表示現(xiàn)實(shí)世界中的實(shí)體的。

實(shí)體之間存在著一種或多種聯(lián)系，這樣的聯(lián)系必然要反映到記錄之間的聯(lián)系上來。數(shù)據(jù)之間

的邏輯聯(lián)系主要有三種：一對(duì)一的聯(lián)系；一對(duì)多的聯(lián)系；多對(duì)多的聯(lián)系。

1.3.3常用數(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ù)和組織數(shù)據(jù)，以及實(shí)施對(duì)數(shù)據(jù)的訪問方式等問題。操作系

統(tǒng)實(shí)現(xiàn)的文件組織方式，可以分為順序文件、索引文件、直接文件和倒排文件。

1）順序文件

順序文件（圖7-2）是最簡(jiǎn)單的文件組織形式，對(duì)記錄按照主關(guān)鍵字的順序進(jìn)行組織。

當(dāng)主關(guān)鍵字是數(shù)字型時(shí)，以其數(shù)值的大小為序；若主關(guān)鍵字是文字型的，則以字母的排列為

序。一切存于磁帶上的記錄，都只能是順序的，而存于磁盤上的記錄，既可以是順序的，也

可以是隨機(jī)的。順序文件的記錄，邏輯上是按主關(guān)鍵字排序的，而在物理存儲(chǔ)上可以有不同

的方式，包括向量方式：被存儲(chǔ)的文件按地址連續(xù)存放，物理結(jié)構(gòu)與邏輯結(jié)構(gòu)一致；鏈方式:

文件不按地址連續(xù)存放，文件的邏輯順序靠鏈來實(shí)現(xiàn),文件中的每個(gè)記錄中都含有一個(gè)指針,

用以指明下一個(gè)記錄的存放地址；塊鏈方式：把文件分成若干數(shù)據(jù)塊，塊之間用指針連接,

而塊內(nèi)則是連續(xù)存儲(chǔ)。

圖7-2：順序文件

2）索引文件

索引文件除了存儲(chǔ)記錄本身（主文件）以外，還建立了若干索引表，這種帶有索引表的

文件叫索引文件。索引表中列出記錄關(guān)鍵字和記錄在文件中的位置（地址）。讀取記錄時(shí)，

只要提供記錄的關(guān)鍵字值，系統(tǒng)通過查找索引表獲得記錄的位置，然后取出該記錄。索引表

一般都是經(jīng)過排序的，既可以是有順序的，也可以是非順序的，可以是單級(jí)索引，也可以是

多級(jí)索引，多級(jí)索引可以提高查找速度，但占用的存儲(chǔ)空間較大。

3）直接文件

直接文件又稱隨機(jī)文件，其存儲(chǔ)是根據(jù)記錄關(guān)鍵字的值，通過某種轉(zhuǎn)換方法得到一個(gè)物

理存儲(chǔ)位置，然后把記錄存儲(chǔ)在該位置上。查找時(shí)，通過同樣的轉(zhuǎn)換方法，可以直接得到所

需要的記錄。

4）倒排文件

倒排文件是帶有輔索引的文件，其中輔索引是按照一些輔關(guān)鍵字來組織索引的（注意：

索引文件是按照記錄的主關(guān)鍵字來構(gòu)造索引的，也叫主索引）。倒排文件是一種多關(guān)鍵字的

索引文件，其中的索引不能唯一標(biāo)識(shí)記錄，往往同一索引指向若干記錄。因而，索引往往帶

有一個(gè)指針表，指向所有該索引標(biāo)識(shí)的記錄。通過輔索引不能直接讀取記錄，而要通過主關(guān)

鍵字才能查到記錄的位置。倒排文件的主要優(yōu)點(diǎn)是在處理多索引檢索時(shí)，可以在輔檢索中先

完成查詢的‘交'、'并'等邏輯運(yùn)算，得到結(jié)果后再對(duì)記錄進(jìn)行存取，從而提高查找速度。

1.4GIS的內(nèi)部數(shù)據(jù)結(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ù)的一種理解和解釋，不說明數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)是毫無用處的，不僅用

戶無法理解，計(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)都可用來描述地理實(shí)體的點(diǎn)、線、面三種基本類型。

空間數(shù)據(jù)編碼是空間數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，即將根據(jù)地理信息系統(tǒng)的目的和任務(wù)所搜集的、

經(jīng)過審核了的地形圖、專題地圖和遙感影像等資料按特定的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適合于計(jì)算機(jī)存

儲(chǔ)和處理的數(shù)據(jù)的過程。由于地理信息系統(tǒng)數(shù)據(jù)量極大，一般采用壓縮數(shù)據(jù)的編碼方式以減

少數(shù)據(jù)冗余。

在地理信息系統(tǒng)的空間數(shù)據(jù)結(jié)構(gòu)中，柵格結(jié)構(gòu)的編碼方式主要有直接?xùn)鸥窬幋a、鏈碼、

游程長(zhǎng)度編碼、塊碼、四叉樹碼等；矢量結(jié)構(gòu)主要有坐標(biāo)序列編碼、樹狀索引編碼和二元拓

撲編碼等編碼方法。

卜軸

B?格表示形式C矢量表示形式

圖7-3：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)

1.4.1矢量模型

在矢量模型中，現(xiàn)實(shí)世界的要素位置和范圍可以采用點(diǎn)、線或面表達(dá)，與它們?cè)诘貓D上

表示相似，每一個(gè)實(shí)體的位置是用它們?cè)谧鴺?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)系。

1.4.2柵格模型

在柵格模型中，空間被規(guī)則地劃分為柵格（通常為正方形）。地理實(shí)體的位置和狀態(tài)是

用它們占據(jù)的柵格的行、列來定義的。每個(gè)柵格的大小代表了定義的空間分辨率。由于位置

是由柵格行列號(hào)定義的，所以特定的位置由距它最近的柵格記錄決定。例如，某個(gè)區(qū)域被劃

分成10*10個(gè)柵格，那么僅能記錄位于這10*10個(gè)柵格附近的物體的位置。柵格的值表達(dá)了

這個(gè)位置上物體的類型或狀態(tài)。采用柵格方法，空間被劃分成大量規(guī)則格網(wǎng)，而且每個(gè)柵格

取值可能不一樣?？臻g單元是柵格，每一個(gè)柵格對(duì)應(yīng)于一個(gè)特定的空間位置，如地表的一個(gè)

區(qū)域，柵格的值表達(dá)了這個(gè)位置的狀態(tài)。

與矢量模型不一樣，柵格模型最小單元與它表達(dá)的真實(shí)世界空間實(shí)體沒有直接的對(duì)應(yīng)關(guān)

系。柵格數(shù)據(jù)模型中的空間實(shí)體單元不是通常概念上理解的物體，它們只是彼此分離的柵格。

例如，道路作為明晰的柵格是不存在的，柵格的值才表達(dá)了路是一個(gè)實(shí)體。道路是被具有道

路屬性值的一組柵格表達(dá)的，這條路不可能通過某一柵格實(shí)體被識(shí)別出來。在這兩種數(shù)據(jù)結(jié)

構(gòu)中，空間信息都是使用統(tǒng)一的單位表達(dá)。在柵格方法中，統(tǒng)一的單位是柵格（柵格是不可

再分的，其屬性用于表達(dá)對(duì)應(yīng)位置物體的性質(zhì)），表達(dá)一個(gè)區(qū)域所用柵格的數(shù)量很大，但其

柵格單元的大小一樣。柵格數(shù)據(jù)文件包含有上百萬個(gè)柵格，每個(gè)柵格的位置都被嚴(yán)格定義。

在矢量方法中，統(tǒng)一的單元是點(diǎn)、線和多邊形，與柵格方法相比，在數(shù)量上所用的表達(dá)單元

較少，但大小可變。在矢量文件中，元素的個(gè)數(shù)或許數(shù)千個(gè)，但畢竟沒有柵格數(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á)它們之間的空間關(guān)系。

2.柵格數(shù)據(jù)結(jié)構(gòu)及其編碼

2.1柵格數(shù)據(jù)結(jié)構(gòu)

2.1.1定義

柵格結(jié)構(gòu)是最簡(jiǎn)單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的

網(wǎng)格陣列，每個(gè)網(wǎng)格作為一個(gè)象元或象素由行、列定義，并包含一個(gè)代碼表示該象素的屬性

類型或量值，或僅僅包括指向其屬性記錄的指針。因此，柵格結(jié)構(gòu)是以規(guī)則的陣列來表示空

間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個(gè)數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。如圖

7-4所示，在柵格結(jié)構(gòu)中，點(diǎn)用一個(gè)柵格單元表示；線狀地物沿線走向的一組相鄰柵格單元

表示，每個(gè)柵格單元最多只有兩個(gè)相鄰單元在線上；面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟?/p>

元的集合表示，每個(gè)柵格單元可有多于兩個(gè)的相鄰單元同屬一個(gè)區(qū)域。遙感影像屬于典型的

柵格結(jié)構(gòu)，每個(gè)象元的數(shù)字表示影像的灰度等級(jí)。

000000000000000004477777

000000000006000044444777

000020000660600044448877

000000000000060000488877

000000000000060000888878

000000000000060000088888

000000000000006000008888

000000000000000000000888

(a)點(diǎn)(b)線(c)面

圖7?4：點(diǎn)、線、區(qū)域的格網(wǎng)

2.1.2特點(diǎn)

柵格結(jié)構(gòu)的顯著特點(diǎn)是：屬性明顯，定位隱含，即數(shù)據(jù)直接記錄屬性的指針或?qū)傩员旧?

而所在位置則根據(jù)行列號(hào)轉(zhuǎn)換為相應(yīng)的坐標(biāo)，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得

到的。如圖74-(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)可以很容易地轉(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ū)域

實(shí)體，代碼分別為4、7和8o由于柵格行列陣列容易為計(jì)算機(jī)存儲(chǔ)、操作和顯示，因此這

種結(jié)構(gòu)容易實(shí)現(xiàn)，算法簡(jiǎn)單，且易于擴(kuò)充、修改，也很直觀，特別是易于同遙感影像的結(jié)合

處理，給地理空間數(shù)據(jù)處理帶來了極大的方便。

柵格結(jié)構(gòu)表示的地表是不連續(xù)的，是量化和近似離散的數(shù)據(jù)。在柵格結(jié)構(gòu)中，地表被分

成相互鄰接、規(guī)則排列的矩形方塊(特殊的情況下也可以是三角形或菱形、六邊形等)，每

個(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è)代碼。也類似于遙感影像的混合象元問題，如Landsat的

MSS衛(wèi)星影像單個(gè)象元對(duì)應(yīng)地表79米*79米的矩形區(qū)域，影像上記錄的光譜數(shù)據(jù)是每個(gè)象

元所對(duì)應(yīng)的地表區(qū)域內(nèi)所有地物類型的光譜輻射的總和效果。因而，這種誤差不僅有形態(tài)上

的畸形，還可能包括屬性方面的偏差。

2.2決定柵格單元代碼的方式

在決定柵格代碼時(shí)盡量保持地表的真實(shí)性，保證最大的信息容量。圖7-5所示的一塊矩

形地表區(qū)域，內(nèi)部含有A、B、C三種地物類型，0點(diǎn)為中心點(diǎn)，將這個(gè)矩形區(qū)域近似地表

示為柵格結(jié)構(gòu)中的一個(gè)柵格單元時(shí)，可根據(jù)需要，采取如下的方式之一來決定柵格單元的代

碼。

圖7-5：柵格單元代碼的確定

2.2.1中心點(diǎn)法

用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼，在圖7-5所示的矩形區(qū)域中，

中心點(diǎn)O落在代碼為C的地物范圍內(nèi)，按中心點(diǎn)法的規(guī)則，該矩形區(qū)域相應(yīng)的柵格單元代

碼為C,中心點(diǎn)法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等.

2.2.2面積占優(yōu)法

以占矩形區(qū)域面積最大的地物類型或現(xiàn)象特性決定柵格單元的代碼，在圖7-5所示的例

子中，顯見B類地物所占面積最大，故相應(yīng)柵格代碼定為B。面積占優(yōu)法常用于分類較細(xì),

地物類別斑塊較小的情況。

2.2.3重要性法

根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型決定相應(yīng)的柵格單元代碼，假設(shè)

圖7-5中A類最重要的地物類型，即A比B和C類更為重要，則柵格單元的代碼應(yīng)為A。

重要性法常用于具有特殊意義而面積較小的地理要素，特別是點(diǎn)、線狀地理要素，如城鎮(zhèn)、

交通樞紐、交通線、河流水系等，在柵格中代碼應(yīng)盡量表示這些重要地物。

2.2.4百分比法

根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的代碼，如可記面積最大

的兩類BA,也可以根據(jù)B類和A類所占面積百分比數(shù)在代碼中加入數(shù)字。

2.3編碼方法

2.3.1直接?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：一些常用的柵格排列順序

2.3.2壓縮編碼方法

目前有一系列柵格數(shù)據(jù)壓縮編碼方法，如鍵碼、游程長(zhǎng)度編碼、塊碼和四叉樹編碼等。

其目的，就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類型又有信息無損編碼和信息有

損編碼之分。信息無損編碼是指編碼過程中沒有任何信息損失，通過解碼操作可以完全恢復(fù)

原來的信息，信息有損編碼是指為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損

失一部分相時(shí)不太重要的信息，解碼時(shí)這部分難以恢復(fù)。在地理信息系統(tǒng)中多采用信息無損

編碼，而對(duì)原始遙感影像進(jìn)行壓縮編碼時(shí)，有時(shí)也采取有損壓縮編碼方法。

1)鏈碼(ChainCodes)

鏈碼又稱為弗里曼鏈碼［Freeman］或邊界鏈碼，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對(duì)

于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形數(shù)據(jù)。缺點(diǎn)是

對(duì)邊界進(jìn)行合并和插入等修改編輯工作比較困難,對(duì)局部的修改將改變整體結(jié)構(gòu)，效率較低,

而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界將被重復(fù)存儲(chǔ)而產(chǎn)生冗余。

2)游程長(zhǎng)度編碼(Run-LengthCodes)

游程長(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,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ù)表示，可見游程長(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,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)；(L1),(3,8)；(1,7),

(6,8)；(1,7),(5,8)?

游程長(zhǎng)度編碼在柵格壓縮時(shí)，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加

合并等操作，運(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ì)圖74(c)所示圖像的塊碼編碼如下：

(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,6J,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」,0),(8,5,1,0)。

該例中塊碼用了120個(gè)整數(shù)，比直接編碼還多，這是因?yàn)槔袨槊枋龇奖悖瑬鸥駝澐趾?/p>

粗糙，在實(shí)際應(yīng)用中，柵格劃分細(xì)，數(shù)據(jù)冗余多的多，才能顯出壓縮編碼的效果，而且還可

以作一些技術(shù)處理，如行號(hào)可以通過行間標(biāo)記而省去記錄，行號(hào)和半徑等也不必用雙字節(jié)整

數(shù)來記錄，可進(jìn)一步減少數(shù)據(jù)冗余。

塊碼具有可變的分辨率，即當(dāng)代碼變化小時(shí)圖塊大，就是說在區(qū)域圖斑內(nèi)部分辨率低；

反之，分辨率高以小塊記錄區(qū)域邊界地段，以此達(dá)到壓縮的目的。因此塊碼與游程長(zhǎng)度編碼

相似，隨著圖形復(fù)雜程度的提高而降低效率，就是說圖斑越大，壓縮比越高；圖斑越碎，壓

縮比越低。塊碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。然而在某

些操作時(shí)，則必須把游程長(zhǎng)度編碼和塊碼解碼，轉(zhuǎn)換為基本柵格結(jié)構(gòu)進(jìn)行。

4)四叉樹

四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，絕大部分圖形操

作和運(yùn)算都可以直接在四叉樹結(jié)構(gòu)上實(shí)現(xiàn)，因此四叉樹編碼既壓縮了數(shù)據(jù)量，又可大大提高

圖形操作的效率。四叉樹將整個(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è)柵格象元為止。四叉樹通過樹狀結(jié)構(gòu)記錄這種劃分，并通過

這種四叉樹狀結(jié)構(gòu)實(shí)現(xiàn)查詢、修改、量算等操作。圖7-7(b)為圖74(c)圖形的四叉樹

分解，各子象限尺度大小不完全一樣，但都是同代碼柵格單元，其四叉樹如圖7-7-(c)所

ZjSo

/SE\NW、E

A

00o

④⑤向⑦⑥⑥?而????翹??②合⑤?&②匈匈??您???

08880888887800444844440444474777

（c）b的四叉樹編碼

圖7-7:四叉樹編碼

其中最上面的那個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)整個(gè)圖形?？偣灿?層結(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)所代表的方形區(qū)

域覆蓋了整個(gè)圖形。從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)如圖7-7（c）所示，共有40個(gè)葉子

結(jié)點(diǎn)，也就是原圖被劃分為40個(gè)大小不等的方形子區(qū)，圖7-7（c）的最下面的一排數(shù)字表示

各子區(qū)的代碼。

由上面圖形的四叉樹分解可見，四叉樹中象限的尺寸是大小不一的，位于較高層次的象

限較大，深度小即分解次數(shù)少，而低層次上的象限較小，深度大即分解次數(shù)多，這反映了圖

上某些位置單一地物分布較廣而另一些位置上的地物比較復(fù)雜，變化較大。正是由于四叉樹

編碼能夠自動(dòng)地依照?qǐng)D形變化而調(diào)整象限尺寸，因此它具有極高的壓縮效率。

采用四叉樹編碼時(shí)，為了保證四叉樹分解能不斷地進(jìn)行下去，要求圖像必須為2nx2n

的柵格陣列，n為極限分割數(shù)，n+1為四叉樹的最大高度或最大層數(shù)，圖7-4（c）為23X2?

的柵格，因此最多劃分三次，最大層數(shù)為4,對(duì)于非標(biāo)準(zhǔn)尺寸的圖像需首先通過增加背景的

方法將圖像擴(kuò)充為2nx2n的圖像。

為了使計(jì)算機(jī)既能以最小的冗余存儲(chǔ)圖像對(duì)應(yīng)的四叉樹，又能方便地完成各種圖形圖像

操作，專家們已提出了多種編碼方式，下面介紹美國馬里蘭大學(xué)地理信息系統(tǒng)中采用的編碼

方式，該方法記錄了終止結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）的地址和值，值就是子區(qū)的代碼，其中地址包

括兩個(gè)部分，共32位（二進(jìn)制），最右邊4位記錄該葉子結(jié)點(diǎn)的深度，即處于四叉樹的第幾

層上，有了深度可以推知子區(qū)的大小；地址由從根結(jié)點(diǎn)到該葉子結(jié)點(diǎn)的路徑表示，0,1,2,

3分別表示SW、SE,NW、NE,從右邊第5位開始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)系中，其左下角行、列坐標(biāo)為（3,2）,

表示為二進(jìn)制分別為011和010,按位交錯(cuò)就是001110,正是6號(hào)地塊。

對(duì)于只有點(diǎn)狀地物或只有線狀地物的圖件，為了提高效率，設(shè)計(jì)了略有不同的劃分終止

條件和記錄方法，稱為點(diǎn)四叉樹和線四叉樹。點(diǎn)四叉樹對(duì)子象限的劃分直到每個(gè)子象限不含

有點(diǎn)或只含有一個(gè)點(diǎn)為止，葉子的值則記錄是否有點(diǎn)和點(diǎn)在子象限的位置；線四叉樹劃分子

象限直到子象限不含線段或只含有單個(gè)線段，對(duì)線的結(jié)點(diǎn)則劃分到單個(gè)象素，其葉子值記錄

更為復(fù)雜。

四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運(yùn)算可以在編碼

數(shù)據(jù)上直接實(shí)現(xiàn)，大大地提高了運(yùn)算效率，是優(yōu)秀的柵格壓縮編碼之一。

一般說來，對(duì)數(shù)據(jù)的壓縮是以增加運(yùn)算時(shí)間為代價(jià)的。在這里時(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)，編碼解碼十分容易；塊碼和四叉樹碼具有區(qū)域性質(zhì)，又具有可變的

分辨率，有較高的壓縮效率，四叉樹編碼可以直接進(jìn)行大量圖形圖像運(yùn)算，效率較高，是很

有前途的方法。在此基礎(chǔ)上已經(jīng)開始發(fā)展了用于三維數(shù)據(jù)的八叉樹編碼等。

3.矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

3.1矢量數(shù)據(jù)結(jié)構(gòu)

3.1.1定義

地理信息系統(tǒng)中另一種最常見的圖形數(shù)據(jù)結(jié)構(gòu)為矢量結(jié)構(gòu)，即通過記錄坐標(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)序列，

坐標(biāo)之間認(rèn)為是以直線段相連，在一定精度范圍內(nèi)可以逼真地表示各種形狀的線狀地物；

“多邊形”在地理信息系統(tǒng)中是指一個(gè)任意形狀、邊界完全閉合的空間區(qū)域。其邊界將整個(gè)

空間劃分為兩個(gè)部分：包含無窮遠(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)來說，數(shù)據(jù)精度高，所占

空間小，是高效的空間數(shù)據(jù)結(jié)構(gòu)。

3.1.2特點(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í)則比較困難。

3.2編碼方法

3.2.1點(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表示了點(diǎn)的矢量編碼的基本內(nèi)容。

3.2.2線實(shí)體

線實(shí)體主要用來表示線狀地物（如公路、水系、山脊線等）符號(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)接查找。

'簡(jiǎn)單點(diǎn)

，點(diǎn)類型《文本點(diǎn)

I結(jié)點(diǎn)

統(tǒng)一標(biāo)識(shí)比例

（簡(jiǎn)單點(diǎn)一符號(hào)

類別或序列號(hào)朝向

x,y坐標(biāo)

比例

朝向

用于建立和顯示數(shù)據(jù)庫聯(lián)系的屬性文本點(diǎn)---字符（

文類

、陳述

其他非幾何屬性線指針

I結(jié)點(diǎn)一符號(hào)〈

線交匯角

唯一標(biāo)識(shí)碼

線標(biāo)識(shí)碼

起始點(diǎn)

<終止點(diǎn)

坐標(biāo)對(duì)序列

顯示信息

非幾何屬性

<b）

圖7-8：（a）點(diǎn)實(shí)體的編碼，（b）線實(shí)體的編碼

3.2.3多邊形

多邊形數(shù)據(jù)是描述地理信息的最重要的一類數(shù)據(jù)。在區(qū)域?qū)嶓w中，具有名稱屬性和分類

屬性的，多用多邊形表示，如行政區(qū)、土地類型、植被分布等；具有標(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ì)的編碼有很大不同。

1）坐標(biāo)序列法（Spaghetti方式）

圖7-9：坐標(biāo)序列法表示的多邊形

由多邊形邊界的x、y坐標(biāo)對(duì)集合及說明信息組成，是最簡(jiǎn)單的一種多邊形矢量編碼，

如圖7-9記為以下坐標(biāo)文件：

1°：X|,yi；X2,2；X3?3；X4,y4；X5,y5；X6,y6；X7,y7；X8,y8；X9,y9；Xio,yio；xn.yn；

2°：X|,yi；xi2,y（2；x13,yi3；xi4,yu;xis,yi5；Xi6,yi6；xn.yn;Xi8,yi8；xi9,y19；X2o,y2o;X2i,y2i;

X22,y22；X23,y23；X8j8；X9,y9；X1O,yiO；X||,yn；

3°：X33,y33：X34?34；X35,y35；X36?36；X37,y37：X38,y38；X39?39；X40,y40；

4°:X|9,yi9；X20,y20；X21,y21；X28,y28；X29,y29；X3O，Y3O；X3|,y3|；X32，Y32；

5°：X21,y2l；X22,y22；X23,y23；X8?8；X7,y7；X6,y6；X24，Y24；*25,丫25；X26?26；X27?27；X28,28；

坐標(biāo)序列法文件結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)以多邊形為單位的運(yùn)算和顯示。這種方法的缺點(diǎn)是:

（1.1）多邊形之間的公共邊界被數(shù)字化和存儲(chǔ)兩次，由此產(chǎn)生冗余和碎屑多邊形；

（1.2）每個(gè)多邊形自成體系而缺少鄰域信息，難以進(jìn)行鄰域處理，如消除某兩個(gè)多邊

形之間的共同邊界；

（1.3）島只作為一個(gè)單個(gè)的圖形建造，沒有與外包多邊形的聯(lián)系；

（1.4）不易檢查拓?fù)溴e(cuò)誤。這種方法可用于簡(jiǎn)單的粗精度制圖系統(tǒng)中。

2）樹狀索引編碼法

該法采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息,方法是對(duì)所有邊界點(diǎn)進(jìn)行數(shù)字

化，將坐標(biāo)對(duì)以順序方式存儲(chǔ)，由點(diǎn)索引與邊界線號(hào)相聯(lián)系，以線索引與各多邊形相聯(lián)系，

形成樹狀索引結(jié)構(gòu)。

圖7-10和圖7-11分別為圖7-9的多邊形文件和線文件樹狀索引示意圖。其文件結(jié)構(gòu)如

下:

多邊形線索引文件

圖7-10：線與多邊形之間的樹狀索引

采用上述的樹狀結(jié)構(gòu)，圖7-9的多邊形數(shù)據(jù)記錄如下:

1）點(diǎn)文件：

點(diǎn)號(hào)坐標(biāo)

1Xbyi

2X2,J2

40X40,y40

2）線文件

線號(hào)起點(diǎn)終點(diǎn)點(diǎn)號(hào)

I16123,4,5,6

II686,7,8

X333333,34,35,36,37,38,39,40,33

3）多邊形文件

多邊形編號(hào)多邊形邊界

1°1,11,IX

2°III,VII,VIII,IX,X

3°X

4°IV,VI,VII

5°II,III,IV,V

樹狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問題,在簡(jiǎn)化過于復(fù)雜的邊

界線或合并相鄰多邊形時(shí)可不必改造索引表，鄰域信息和島狀信息可以通過對(duì)多邊形文件的

線索引處理得到，但是比較繁瑣，因而給相鄰函數(shù)運(yùn)算，消除無用邊，處理島狀信息以及檢

查拓?fù)潢P(guān)系帶來一定的困難，而且兩個(gè)編碼表都需要以人工方式建立，工作量大且容易出錯(cuò)。

3）拓?fù)浣Y(jié)構(gòu)編碼法

要徹底解決鄰域和島狀信息處理問題必須建立一個(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)系查詢等問題，但增

加了算法的復(fù)雜性和數(shù)據(jù)庫的大小。

矢量編碼最重要的是信息的完整性和運(yùn)算的靈活性,這是由矢量結(jié)構(gòu)自身的特點(diǎn)所決定

的，目前并無統(tǒng)一的最佳的矢量結(jié)構(gòu)編碼方法，在具體工作中應(yīng)根據(jù)數(shù)據(jù)的特點(diǎn)和任務(wù)的要

求而靈活設(shè)計(jì)。

DIME（雙重獨(dú)立坐標(biāo)地圖編碼，DualIndependentMapEncoding）編碼系統(tǒng)

DIME是美國人口調(diào)查局在人口調(diào)查的基礎(chǔ)上發(fā)展起來的，它通過有向編碼建立了多邊

形、邊界、節(jié)點(diǎn)之間的拓?fù)潢P(guān)系，DIME編碼成為其它拓?fù)渚幋a結(jié)構(gòu)的基礎(chǔ)。

4.矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法

4.1柵格結(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ù)操作總的來說比較容易實(shí)現(xiàn)，尤其是

作為斑塊圖件的表示更易于為人們接受；而矢量數(shù)據(jù)操作則比較復(fù)雜，許多分析操作（如兩

張地圖的覆蓋操作，點(diǎn)或線狀地物的鄰域搜索等）用矢量結(jié)構(gòu)實(shí)現(xiàn)十分困難，矢量結(jié)構(gòu)表達(dá)

線狀地物是比較直觀的，而面狀地物則是通過對(duì)邊界的描述而表達(dá)。無論哪種結(jié)構(gòu)，數(shù)據(jù)精

度和數(shù)據(jù)量都是一對(duì)矛盾，要提高精度，柵格結(jié)構(gòu)需要更多的柵格單元，而矢量結(jié)構(gòu)則需記

錄更多的線段結(jié)點(diǎn)。一般來說，柵格結(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ì)于給定范圍的開窗、縮放柵格結(jié)構(gòu)

也比矢量結(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)精度要求為萬分之一，即5位數(shù)字，采用矢量結(jié)構(gòu)需記錄40個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)用

兩個(gè)雙字節(jié)整數(shù)記錄x、y坐標(biāo)，加上對(duì)其他說明信息的描述，200個(gè)字節(jié)足夠了，而若用

基本柵格記錄，則需10000*100（X）=108個(gè)字節(jié)，即使采用單字節(jié)記錄柵格代碼（不超過255）,

也需約五百萬個(gè)字節(jié)，當(dāng)然實(shí)際圖形的矢量結(jié)構(gòu)記錄采點(diǎn)一般要比圖7-10密得多，但數(shù)據(jù)

量仍大大少于柵格結(jié)構(gòu)的數(shù)據(jù)量。

柵格結(jié)構(gòu)除了可使大量的空間分析模型得以容易實(shí)現(xiàn)之外，還具有以下兩個(gè)特點(diǎn)：（1）

易于與遙感相結(jié)合。遙感影像是以象元為單位的柵格結(jié)構(gòu)，可以直接將原始數(shù)據(jù)或經(jīng)過處理

的影像數(shù)據(jù)納入柵格結(jié)構(gòu)的地理信息系統(tǒng)。（2）易于信息共享。目前還沒有一種公認(rèn)的矢量

結(jié)構(gòu)地圖數(shù)據(jù)記錄格式，而不經(jīng)壓縮編碼的柵格格式即整數(shù)型數(shù)據(jù)庫陣列則易于為大多數(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ù)壓縮率和增強(qiáng)系統(tǒng)分析、輸入輸出的靈活性十分重要。兩種

格式的比較見表7-2?

表7-2：矢量格式與柵格格式的比較

矢量數(shù)據(jù)L數(shù)據(jù)結(jié)構(gòu)緊湊、冗余度低L數(shù)據(jù)結(jié)構(gòu)復(fù)雜

2.有利于網(wǎng)絡(luò)和檢索分析2.多邊形疊加分析比較困難

3.圖形顯示質(zhì)量好、精度高

柵格數(shù)據(jù)1.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單L數(shù)據(jù)量大

2.便于空間分析和地表模擬2.投影轉(zhuǎn)換比較復(fù)雜

3.現(xiàn)勢(shì)性較強(qiáng)

4.2相互轉(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)精度變換問題，不存在太大的技術(shù)問題。線實(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)槭噶?/p>

結(jié)構(gòu)與將多邊形邊界表示為矢量結(jié)構(gòu)相似，因此以下重點(diǎn)討論多邊形（面實(shí)體）的矢量結(jié)構(gòu)

與柵格結(jié)構(gòu)相互轉(zhuǎn)換。

4.2.1矢量格式向柵格格式的轉(zhuǎn)換

矢量格式向柵格格式轉(zhuǎn)換又稱為多邊形填充,就是在矢量表示的多邊形邊界內(nèi)部的所有

柵格點(diǎn)上賦以相應(yīng)的多邊形編碼，從而形成類似圖74的柵格數(shù)據(jù)陣列。幾種主要的算法描

述如下：

1）內(nèi)部點(diǎn)擴(kuò)散算法

該算法由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn)（種子點(diǎn)）開始，向其八個(gè)方向的鄰點(diǎn)擴(kuò)散，判斷各個(gè)

新加入點(diǎn)是否在多邊形邊界上，如果是邊界上，則該新加入點(diǎn)不作為種子點(diǎn)，否則把非邊界

點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算，并將該種子點(diǎn)賦以該多邊形

的編號(hào)。重復(fù)上述過程直到所有種子點(diǎn)填滿該多邊形并遇到邊界停止為止。擴(kuò)散算法程序設(shè)

計(jì)比較復(fù)雜，并且在一定的柵格精度上，如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個(gè)

或相鄰的兩個(gè)柵格內(nèi)，會(huì)造成多邊形不連通，這樣一個(gè)種子點(diǎn)不能完成整個(gè)多邊形的填充。

2）復(fù)數(shù)積分算法

對(duì)全部柵格陣列逐個(gè)柵格單元地判斷該柵格歸屬的多邊形編碼，判別方法是由待判點(diǎn)對(duì)

每個(gè)多邊形的封閉邊界計(jì)算復(fù)數(shù)積分，對(duì)某個(gè)多邊形，如果積分值為2兀r,則該待判點(diǎn)屬于

此多邊形，賦以多邊形編號(hào)，否則在此多邊形外部，不屬于該多邊形。

3）射線算法和掃描算法

射線算法可逐點(diǎn)判斷數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)，由待判點(diǎn)向圖外某點(diǎn)引

射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，則待判點(diǎn)在該多邊形

外部，如為奇數(shù)次，則待判點(diǎn)在該多邊形內(nèi)部（圖7-12）。采用射線算法，要注意的是：射

線與多邊形邊界相交時(shí)，有一些特殊情況會(huì)影響交點(diǎn)的個(gè)數(shù)，必須予以排除（圖7-13）。

掃描算法是射線算法的改進(jìn)，將射線改為沿柵格陣列列或行方向掃描線，判斷與射線算

法相似。掃描算法省去了計(jì)算射線與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效率。

0外部點(diǎn)?內(nèi)部點(diǎn)n交點(diǎn)個(gè)數(shù)

圖7-12：射線算法

（e）不連通

圖7-13：射線算法的特殊情況

4）邊界代數(shù)算法（BAF-BoundaryAlgebraFilling）［任伏虎］

邊界代數(shù)多邊形填充算法是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法,它適合

于記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格結(jié)構(gòu)。圖7-15表示轉(zhuǎn)換單個(gè)多邊形的情況，

多邊形編號(hào)為a,模仿積分求多邊形區(qū)域面積的過程，初始化的柵格陣列各柵格值為零，以

柵格行列為參考坐標(biāo)軸，由多邊形邊界上某點(diǎn)開始順時(shí)針?biāo)阉鬟吔缇€，當(dāng)邊界上行時(shí)（圖

7-15-a）,位于該邊界左側(cè)的具有相同行坐標(biāo)的所有柵格被減去a；當(dāng)邊界下行時(shí)（圖7-15-b）,

該邊界左邊（前進(jìn)方向看為右側(cè)）所有柵格點(diǎn)加一個(gè)值a,邊界搜索完畢則完成了多邊形的

轉(zhuǎn)換。

00000000

00aaaa00

-a-a000000

-a-a000000

-a-a-J]00000

00000000

(a)

圖7-15：?jiǎn)蝹€(gè)多邊形的轉(zhuǎn)換

00000000000000000000

0000000000

-3-3-3-3|000000

-3-3-3-3000000

-3-3-3-3000000

0000000000⑴

0000000000