1、三、 空間數(shù)據(jù)結(jié)構(gòu)與GIS數(shù)據(jù)模型 地理信息系統(tǒng)所處理的數(shù)據(jù)與一般事務(wù)性信息系統(tǒng)如銀行管理系統(tǒng)、圖書檢索系統(tǒng)不同。GIS的數(shù)據(jù)處理不僅包括所研究對象的屬性關(guān)系，還包括研究對象的空間位置以及空間拓?fù)潢P(guān)系等信息，數(shù)據(jù)量大，結(jié)構(gòu)復(fù)雜。因此，人們對GIS中的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)模型進(jìn)行了大量的研究，并發(fā)展了一整套空間數(shù)據(jù)處理的算法。 一、空間數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的組織形式，可以分為抽象數(shù)據(jù)結(jié)構(gòu)(或稱邏輯結(jié)構(gòu))和數(shù)據(jù)存貯結(jié)構(gòu)(或稱物理結(jié)構(gòu))來進(jìn)行研究。所謂抽象數(shù)據(jù)結(jié)構(gòu)是指人們僅從概念上描繪數(shù)據(jù)之間的排列和聯(lián)系，而并不涉及數(shù)據(jù)和具體程序管理細(xì)節(jié)。數(shù)據(jù)存貯結(jié)構(gòu)則是為實(shí)現(xiàn)某一抽象數(shù)據(jù)結(jié)構(gòu)而具體設(shè)計(jì)的數(shù)據(jù)存

2、貯管理方式.是依照任務(wù)的不同，軟件系統(tǒng)和設(shè)計(jì)者的不同而改變的，具有一定的特殊性，是前者的一個(gè)具體實(shí)現(xiàn)。地理空間數(shù)據(jù)在GIS中的流向可以認(rèn)為經(jīng)歷了四個(gè)階段。用戶認(rèn)知的數(shù)據(jù)結(jié)構(gòu)輸入GIS系統(tǒng)后轉(zhuǎn)換成為GIS空間數(shù)據(jù)結(jié)構(gòu)，然后，為有效地進(jìn)行數(shù)據(jù)管理，將其轉(zhuǎn)化為數(shù)據(jù)庫結(jié)構(gòu)，最后按某種特定程式以硬件結(jié)構(gòu)寫入存貯介質(zhì)。上述流程即為數(shù)據(jù)的輸入過程。地理空間實(shí)體可以抽象為點(diǎn)、線、面三種基本地形要素來表示它的位置、形狀、大小、高低等。 -點(diǎn)(零維)：又稱為元素或像元，是一個(gè)數(shù)據(jù)點(diǎn)，具有一對(x，y)坐標(biāo)相至少個(gè)屬性，邏輯上不能再分。這里所謂邏輯上不能再分是指抽象的點(diǎn)而不是幾何點(diǎn)，因?yàn)槭聦?shí)上抽象的點(diǎn)可以是實(shí)體線段

3、或面塊，對某個(gè)比例尺或圖像分辨率而言，它們可以被抽象為以一對坐標(biāo)表示的數(shù)據(jù)點(diǎn)。 -線：是由一個(gè)(x,y)坐標(biāo)對序列表示的具有相同屬性的點(diǎn)的軌跡。線的形狀決定坐標(biāo)對序列的排列順序，線上每個(gè)點(diǎn)有不多于二個(gè)鄰點(diǎn)。地理實(shí)體，如河流、道路、地形線、公共設(shè)施走廊、區(qū)域邊界、地質(zhì)界線等均屬線狀地物，其特點(diǎn)是線上各點(diǎn)有相同的公共屬性并至少存在一個(gè)屬性。-面：是以(x,y)坐標(biāo)對的集合表示的具有相同屬性的點(diǎn)的軌跡。面的形狀不受各點(diǎn)坐標(biāo)對排列順序的影響。凡是面的內(nèi)部點(diǎn)可以有多于三個(gè)的鄰點(diǎn)，面內(nèi)每個(gè)點(diǎn)應(yīng)至少具有一個(gè)相同屬性。土壤、植被、行政區(qū)劃、巖石分類等地理實(shí)體屬面狀地物。如果顧及平面位置與高程位置結(jié)合起來所構(gòu)成

4、的空間數(shù)據(jù)模型則還應(yīng)考慮三維的體元素，作為點(diǎn)、線、面三個(gè)基本地形要素的個(gè)外延?？傊?，從幾何上講，人們正是通過上述這些基本要素構(gòu)成了對各種地理實(shí)體的認(rèn)識(shí)結(jié)構(gòu)。地理信息系統(tǒng)空間數(shù)據(jù)結(jié)構(gòu)就是指空間數(shù)據(jù)的編排方式和組織關(guān)系?？臻g數(shù)據(jù)編碼是空間數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。目的是將圖形數(shù)據(jù)、影像數(shù)據(jù)、統(tǒng)計(jì)數(shù)據(jù)等資料，按一定的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適用于計(jì)算機(jī)存儲(chǔ)和處理的過程，不同的數(shù)據(jù)源，其數(shù)據(jù)結(jié)構(gòu)相差很大，同一數(shù)據(jù)源，也可以用許多方式來組織數(shù)據(jù)，按不同的數(shù)據(jù)結(jié)構(gòu)去處理，得到的截然不同的內(nèi)容。如下圖所示為用這兩種數(shù)據(jù)結(jié)構(gòu)來表示同一塊由不同土壤結(jié)構(gòu)構(gòu)成的土地。圖中(a)的土壤結(jié)構(gòu)是由一組具有起終點(diǎn)坐標(biāo)的線段和必要的連接指針構(gòu)成

5、。因?yàn)楸硎疚锛木€段有方向性，所以稱之為矢量結(jié)構(gòu)。線段端點(diǎn)的指針表明了這些線段應(yīng)如何連接在一起才能形成相應(yīng)地塊。這種結(jié)構(gòu)可以表述為:地塊矢量組連通性圖中(b)的土壤結(jié)構(gòu)是由格網(wǎng)中某一部分的像元或稱柵格集合所構(gòu)成，所以稱之為柵格結(jié)構(gòu)。在同一集合中的像元都具有同樣的編碼“a”或“b”或“c”等。實(shí)際上這些值本身并不一定顯示出來，通常它們可能只代表某一符弓或是某種顏色或是影像灰度,這種結(jié)構(gòu)可以表述為：地塊符號(hào)顏色像元圖: 用矢量結(jié)構(gòu)或柵格結(jié)構(gòu)表示同一地塊的例子從上所述, 空間數(shù)據(jù)的結(jié)構(gòu)有矢量數(shù)據(jù)結(jié)構(gòu)和柵格數(shù)據(jù)結(jié)構(gòu)兩種形式。目前大多數(shù)GIS軟件均結(jié)合了這兩種數(shù)據(jù)結(jié)構(gòu)，或采用混合數(shù)據(jù)結(jié)構(gòu)或采用矢柵一體化

6、結(jié)構(gòu)。GIS的空間數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)系統(tǒng)中的實(shí)現(xiàn)通常是通過空間數(shù)據(jù)編碼的方法進(jìn)行的。由于GIS數(shù)據(jù)量極大,一般需要采用壓縮數(shù)據(jù)的編碼方式以減少數(shù)據(jù)冗余。一些常用的編碼方式有:矢量數(shù)據(jù)結(jié)構(gòu)編碼方式:坐標(biāo)系列編碼、層次索引編碼、拓?fù)浣Y(jié)構(gòu)編碼等柵格數(shù)據(jù)結(jié)構(gòu)編碼方式：鏈碼、直接?xùn)鸥窬幋a、游程長度編碼、塊碼、四叉樹碼等計(jì)算機(jī)存儲(chǔ)和處理數(shù)據(jù)的效率，在很大程度上取決于數(shù)據(jù)組織方式的優(yōu)劣。數(shù)據(jù)結(jié)構(gòu)在GIS中對于數(shù)據(jù)采集、存儲(chǔ)、查詢、檢索和應(yīng)用分析等操作方式有著重要的影響。一種高效率的數(shù)據(jù)結(jié)構(gòu)，應(yīng)具備幾方面的要求： 組織的數(shù)據(jù)能夠表示要素之間的層次關(guān)系，便于不同數(shù)據(jù)聯(lián)接和覆蓋。 正確反映地理實(shí)體的空間排列方式和各

7、實(shí)體間相互關(guān)系。 便于存取和檢索。 節(jié)省存貯空間，減少數(shù)據(jù)冗余。 存取速度快，在運(yùn)算速度較慢的微機(jī)上要達(dá)到快速響應(yīng)。 足夠靈活性，數(shù)據(jù)組織應(yīng)具有插入新的數(shù)據(jù)、刪除或修改部分?jǐn)?shù)據(jù)的基本功能。空間數(shù)據(jù)結(jié)構(gòu)選擇對于GIS設(shè)計(jì)和建立起著十分關(guān)鍵的作用，只有充分理解了GIS的特定的數(shù)據(jù)結(jié)構(gòu)，才能正確有效地使用系統(tǒng)。 A 柵格數(shù)據(jù)結(jié)構(gòu) 一、柵格數(shù)據(jù)的基本概念柵格數(shù)據(jù)是最簡單、最直觀的一種空間數(shù)據(jù)結(jié)構(gòu)，它是將地面按一定分辨率劃分為均勻的網(wǎng)格，每個(gè)網(wǎng)格作為一個(gè)像元，像元的位置由所在行、列號(hào)確定，像元所含有的代碼表示其屬性類型或僅是與其屬性記錄相聯(lián)系的指針。在地理信息系統(tǒng)中，掃描數(shù)字化數(shù)據(jù)、遙感數(shù)據(jù)、數(shù)字地面高

8、程數(shù)據(jù)(DTM)網(wǎng)格化后的物化探數(shù)據(jù)以及矢量柵格轉(zhuǎn)換數(shù)據(jù)等都屬于柵格數(shù)據(jù)。在柵格結(jié)構(gòu)中：l 點(diǎn)用一個(gè)像元來表示；l 線狀地物用沿線走向的一組相鄰像元來表示。由線的定義可知，每個(gè)線上的像元最多只有兩個(gè)相鄰像元在線上。l 面狀地物或區(qū)域則用具有相同屬性的相鄰像元集合表示。由面的定義可知，每個(gè)像元可以有兩個(gè)以上的相鄰像元屬于同一區(qū)域。來自遙感、數(shù)字?jǐn)z影測量的數(shù)據(jù)屑于典型的柵格結(jié)構(gòu)。如遙感影像像元的數(shù)值表示該影像的灰度等級。因?yàn)樵跂鸥窠Y(jié)構(gòu)中，是將地面分劃成相互鄰接的大小均勻格網(wǎng)方塊，然后使每地塊與一個(gè)柵格像元相對應(yīng)。因此，由柵格結(jié)構(gòu)所表示的地表數(shù)據(jù)是不連續(xù)的，是經(jīng)過量化的離散值，而每一個(gè)像元大小與它所

9、代表的實(shí)地地塊大小之比就是柵格數(shù)據(jù)的比例尺。這樣，在使用柵格數(shù)據(jù)計(jì)算面積、長度、距離、形狀等空間指標(biāo)時(shí)，若像元所代表的實(shí)地地塊尺寸較大，則會(huì)造成較大的計(jì)算誤差，誤差隨像元的增大而增加。 二、柵格數(shù)據(jù)層的概念地理信息系統(tǒng)對現(xiàn)實(shí)世界的描述可以以地理空間位置為基礎(chǔ)，按道路、行政區(qū)域、土地使用、土壤、房屋、地下管線、自然地形等不同專題屬性來組織地理信息。地理數(shù)據(jù)在柵格數(shù)據(jù)結(jié)構(gòu)中必須分層組織存儲(chǔ)：在柵格數(shù)據(jù)結(jié)構(gòu)中，物體的空間位置就用其在笛卡爾平面網(wǎng)格中的行號(hào)和列號(hào)坐標(biāo)表示，物體的屬性用像元的取值表示，每個(gè)象元在一個(gè)網(wǎng)格中只能取值一次，同一像元要表示多重屬性的事物就要用多個(gè)笛卡爾平面網(wǎng)格，每個(gè)笛卡爾平面網(wǎng)

10、格表示一種屬性或同一屬性的不同特征，這種平面稱為層。每一層構(gòu)成單一的屬性數(shù)據(jù)層或?qū)ｎ}信息層：例如同樣以線性特征表示的地理要素，河流可以組織為一個(gè)層，道路可以作為另一層，同樣以多邊形特征表示的地理要素，湖泊可以作為一個(gè)層，房屋可以作為另一層，根據(jù)使用目的不同，可以確定需要建立哪些層及需要建立哪些描述性屬性。在下圖中，左邊是現(xiàn)實(shí)世界按專題內(nèi)容的分層表示，第三層為植被，第二層為土壤，第一層為地形，中間是現(xiàn)實(shí)世界各專題層所對應(yīng)的柵格數(shù)據(jù)層。右圖是對不同柵格數(shù)據(jù)層進(jìn)行疊加分析，并得出分析結(jié)論。圖: 柵格數(shù)據(jù)的分層與疊合分析三、柵格數(shù)據(jù)取值柵格數(shù)據(jù)通常有下述幾種途徑的得到1） 格網(wǎng)法取值2） 矢量結(jié)構(gòu)轉(zhuǎn)化

11、為柵格數(shù)據(jù)3） 掃描法4） 遙感影象數(shù)據(jù)格網(wǎng)法是是在專題地圖上均勻地劃分網(wǎng)格，每一網(wǎng)格覆蓋部分的屬性數(shù)據(jù)，即為該網(wǎng)格柵格數(shù)據(jù)的取值。但是常常會(huì)遇到一些特殊的情況，同一網(wǎng)格可能對應(yīng)地圖上多種專題屬性，而每一個(gè)單元只允許取一個(gè)值，目前對于這種多重屬性的網(wǎng)格，有不同的取值方法：圖: 柵格數(shù)據(jù)取值方法l 中心歸屬法：每個(gè)柵格單元的值以網(wǎng)格中心點(diǎn)對應(yīng)的面域?qū)傩灾祦泶_定，如圖中 (a)所示。l 長度占優(yōu)法：每個(gè)柵格單元的值以網(wǎng)格中線（水平或垂直）的大部分長度所對應(yīng)的面域的屬性值來確定，如圖中（b）所示。l 面積占優(yōu)法：每個(gè)柵格單元的值以在該網(wǎng)格單元中占據(jù)最大面積的屬性值來確定，如圖中（c）所示l 重要性法

12、：根據(jù)柵格內(nèi)不同地物的重要性程度，選取特別重要的空間實(shí)體決定對應(yīng)的柵格單元值，如稀有金屬礦產(chǎn)區(qū)，其所在區(qū)域盡管面積很小或不位于中心，也應(yīng)采取保留的原則，如圖中（d）所示。四、柵格數(shù)據(jù)文件的組織方法 假定基于笛卡爾坐標(biāo)系上的一系列疊置層的柵格地圖文件已建立起來，那么如何在計(jì)算機(jī)內(nèi)組織這些數(shù)據(jù)才能達(dá)到最優(yōu)數(shù)據(jù)存取、最少的存儲(chǔ)空間、最短處理過程呢？如果每一層中每一個(gè)象元在數(shù)據(jù)庫中都是獨(dú)立單元即數(shù)據(jù)值、象元和位置之間存在著一對一的關(guān)系，按上述要求組織數(shù)據(jù)的可能方式有三種:l l）以象元為記錄的序列。不同層上同一象元位置上的各屬性值表示為一個(gè)列數(shù)組（圖a）。l 2）以層為基礎(chǔ)。每一層又以象元為序記錄它的

13、坐標(biāo)和屬性值，一層記錄完后再記錄第二層（圖b）。這種方法較為簡單，但需要的存儲(chǔ)空間最大。l 3）以層為基礎(chǔ)，但每一層內(nèi)則以多邊形（也稱制圖單元）為序記錄多邊形的屬性值和充滿多邊形的各象元的坐標(biāo)（圖C）。三種方式的優(yōu)缺點(diǎn)： 方法（1）節(jié)省了許多存儲(chǔ)空間，因?yàn)镹層中實(shí)際只存儲(chǔ)了一層的象元坐標(biāo)：方法（3）則節(jié)省了許多用于存儲(chǔ)屬性的空間，同一屬性的制圖單元的n個(gè)像元只記錄一次屬性值。它實(shí)際上是地圖分析軟件包中所使用的分級結(jié)構(gòu)。這種多像元對應(yīng)一種屬性值的多對一的關(guān)系，相當(dāng)于把相同屬性的像元排列在一起，使地圖分析和制圖處理較為方便；這種方法很適合應(yīng)用壓縮編碼的方法來存貯數(shù)據(jù)，通常多采用鏈碼、行程編碼、塊碼

14、和四叉樹碼等方法。方法（2）則是每層每個(gè)像元一一記錄，它的形式最為簡單。圖: 柵格數(shù)據(jù)文件的組織方式五、柵格數(shù)據(jù)存儲(chǔ)的壓縮編碼1直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a是最簡單最直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼的圖像文件或柵格文件。直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼，可以每行都從左到右逐象元記錄，也可奇數(shù)據(jù)行從左到右，而偶數(shù)行由右向左記錄，為了特定目的還可采用其它特殊的順序。如右圖所示的柵格結(jié)構(gòu)就可以記錄成：7，7，7，6，6，6，6，6，7，7，7，7，7，6，6，6，7，7，7，7，7，7，6，6，4，4，4，76，6，6，6，4，4，4，4，4，6，

15、6，6，4，4，4，6，5，5，6，6，0，O，4，4，6，6，6，6，0，0，1，0，6，6，0，0。2鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（Freeman，1961）或邊界鏈碼。它用一個(gè)起點(diǎn)和一系列在基本方向上的單位矢量描述出線狀地物或區(qū)域邊界。所采用的基本方向可以事先定義。例如我們可以定義基本方向?yàn)椋簴|0，北1，西2，南3，則如右圖所示的屬性代碼為6的線狀地物，其位置可以表示為：1，4，3，2，3，2，32，02，3，0，3，03。其中前二個(gè)數(shù)字1和4表示起點(diǎn)為第1行第4列，從第3個(gè)數(shù)字起每個(gè)數(shù)字表示單位矢量的方向。數(shù)字的上標(biāo)表示單位矢量的前進(jìn)量。這里將單位矢量的長度默認(rèn)為一個(gè)柵格像元。當(dāng)然

16、,我們也可以采用8個(gè)基本方向碼進(jìn)行編碼.鏈碼可以有效地壓縮柵格數(shù)據(jù)，尤其是對于計(jì)算面積或長度或轉(zhuǎn)折方向的凸凹度等運(yùn)算較為方便，比較適合存貯圖形數(shù)據(jù)。缺點(diǎn)是在進(jìn)行疊加操作時(shí)，對邊界的合并和插入等修改編輯工作比較困難。對局部的修改要涉及改變整體結(jié)構(gòu)。因此效率較低。另外，由于鏈碼是以每個(gè)區(qū)域?yàn)閱挝淮尜A邊界，所以相鄰邊界將被存貯兩次而產(chǎn)生數(shù)據(jù)冗余，這些問題使鏈碼的應(yīng)用受到一定限制。 3行程編碼我們知道,在同一面元區(qū)域內(nèi)，相鄰像元的屬性代碼值是相同的，這樣就非常適合于用壓縮的編碼方式. 將相鄰等值的像元合并，記錄下行程長度和代碼值，這種方法稱為行程編碼。通常有兩種行程編碼方案可實(shí)現(xiàn)對數(shù)據(jù)的壓縮:一種編碼

17、方案是行程長度編碼，即在進(jìn)行行列掃描過程中只在各行(或列)數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄該代碼以相同代碼出現(xiàn)的個(gè)數(shù)(長度)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。例如對右圖所示的柵格數(shù)據(jù)，可進(jìn)行如下行程編碼：(7，3)，(6，5),(7，5)，(6，3)，(7，6)，(6，2)，(4，3)，(7，1)， (6，4)，(4，5)，(6，3)，(4， 3)，(6，5)，(0，2)，(4， 2)，(6，4)，（0，4），(6，2)，(0，2)。這些只用了38個(gè)整數(shù)就可以表示右圖所示的柵格數(shù)據(jù)而前述的柵格矩陣法中直接編碼記錄需要64個(gè)整數(shù)表示，可見行程編碼壓縮數(shù)據(jù)是十分有效且簡便的。實(shí)際上，柵格圖像的復(fù)雜程度直接影響到行

18、程編碼的壓縮比，圖形變化少則行程數(shù)就少，壓縮效率就高，反之壓縮比就低。另一種編碼方案是行程起始編碼(或行程終止編碼),即在逐行(或列)記錄屬性代碼時(shí)，僅記錄下發(fā)生變化的位置和相應(yīng)代碼，可得到行程起始編碼為：(1，7)，（4，6），(1，7)，(6，6)，(1，7)，(7，6)，(1，4)，(4，7)，(5，6)，(1，4)，(6，6)，(1，4)，(6，6)，(1，4)，(4，6)，(1，0)，(3，4)，(5，6)，(1，0)，(5，6)，(7，0)。行程編碼具有壓縮效率高、易于檢索、運(yùn)算簡單等優(yōu)點(diǎn)，區(qū)域越大、數(shù)據(jù)相關(guān)性越強(qiáng)則該法節(jié)省存貯空間越多。這適用于計(jì)算機(jī)存貯容量小，且數(shù)據(jù)需大量壓縮，

19、而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況。這種編碼方法減少了柵格數(shù)據(jù)庫的數(shù)據(jù)輸入量，但計(jì)算期間的處理和制圖輸出處理工作量都有所增加。 4塊式編碼塊式編碼是將行程編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由象元組成的正方形，然后以正方形為單元對各個(gè)正方形進(jìn)行編碼。圖右圖所示對多邊形進(jìn)行分塊和編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)中包括3個(gè)數(shù)字：塊的原點(diǎn)坐標(biāo)（可以是塊的中心或塊的左下角象元的行、列號(hào)）和塊的大小（塊包括的象元數(shù)或塊的半徑），再加上記錄單元的代碼組成。這種變換過程稱為中軸變換。(1，1，3，7)，(1，4，1，6)，(1，5，1，6)，(1，6，2，6)，(1，8，l，6)；(2，4，2

20、，7)，(2，8，l，6),(3，6，1，7)， 一個(gè)多邊形所能包含的正方形越大，多邊形的邊界越簡單，塊式編碼的效果就越好。行程和塊式編碼都對大而簡單的多邊形更有效，而對那些碎部僅比象元大幾倍的復(fù)雜多邊形效果并不好。塊式編碼即中軸變換的優(yōu)點(diǎn)是多邊形之間求并及求交都方便；探測多邊形的延伸特征也較容易。但對某些運(yùn)算不適應(yīng)，必須再轉(zhuǎn)換成簡單柵格數(shù)據(jù)形式才能順利進(jìn)行。 5四叉樹編碼四叉樹編碼是以柵格數(shù)據(jù)二維空間分布的特點(diǎn)，將整個(gè)圖像區(qū)域按照四個(gè)象限進(jìn)行遞歸分割(2n X2n)最后逐步分解為一系列被單一類型區(qū)域內(nèi)含的方形區(qū)域，所分解的最小方形區(qū)域?yàn)橐粋€(gè)柵格像元。按照象限遞歸分割的原則，所分圖像區(qū)域的柵格

21、陣列應(yīng)為2n X2n(n為分割的層次數(shù)n1)的形式，無論分割到哪一層的象限，只要子象限上僅含一種屬性代碼或符合既定要求的少數(shù)幾種屬性時(shí)，則停止繼續(xù)分割，否則就一直分割到單個(gè)像元為止。這樣最后可得到一棵四分叉的倒向樹。四叉樹編碼正是通過這種樹狀結(jié)構(gòu)來記錄和壓縮柵格數(shù)據(jù)，并通過這種結(jié)構(gòu)實(shí)現(xiàn)查詢、修改和量算等操作。因此，四叉樹編碼法不僅能壓縮數(shù)據(jù)，還可提高圖形操作的效率。右圖是對前述柵格數(shù)據(jù)經(jīng)過四叉樹編碼得到的四叉樹。在圖(a)中各子象限的大小不同，它們是由組成該子象限的具有相同代碼的柵格像元構(gòu)成的子塊而決定的。圖(b)中最上面的結(jié)點(diǎn)稱作根結(jié)點(diǎn)。它對應(yīng)于整個(gè)圖形區(qū)域。在這個(gè)例子中，總共劃分出四層結(jié)點(diǎn)

22、。每層結(jié)點(diǎn)對應(yīng)于不同尺寸的子象限。如第二層的4個(gè)結(jié)點(diǎn)對應(yīng)于整個(gè)圖形區(qū)域的四個(gè)象限: 西北(NW)象限2 東北(NE)象限 =3 西南(SW)象限0 東南(SE)象限1若某子象限僅含一種屬性代碼時(shí)，就不冉繼續(xù)劃分，即被記為葉結(jié)點(diǎn)或終止結(jié)點(diǎn)。葉結(jié)點(diǎn)可以落在任意層上,它表示的區(qū)域僅具有某一類型的地物或符合既定要求的少數(shù)幾種地物。圖(b)所示的四叉樹結(jié)構(gòu)中，共有43個(gè)葉結(jié)點(diǎn)這說明原柵格數(shù)據(jù)圖被劃分為43個(gè)大小不等的子象限。每個(gè)葉結(jié)點(diǎn)下的數(shù)字表爾該子象限代表區(qū)域的屬性代碼。每個(gè)結(jié)點(diǎn)上方的數(shù)字表示該子象限的地址編號(hào)。上圖中,共分割層次數(shù)n3所得到四叉樹的最大層數(shù)為n十l4。也就是說，若象限遞歸分割層次數(shù)為

23、n，則可得到結(jié)點(diǎn)的最大層次數(shù)為n十1。從對上述圖形的四叉樹編碼過程中可見，位于結(jié)點(diǎn)層次較高的子象限尺寸也較大，說明其分解深度小，也即分割次數(shù)少；而低層次上的象限尺寸就較小，反映其分解深度大即分割次數(shù)多。這樣編碼后，可反映出整個(gè)圖形區(qū)域的空間地物分布情況，在某些位置上單一地物分布較廣，則采用較少的分割次數(shù)；在地物較復(fù)雜，變化較大的區(qū)域，則用加深分解深度，增加分割次數(shù)的方式編碼。所以，采用四叉樹編碼方法能夠自動(dòng)地依照實(shí)際圖形區(qū)域的地物分布情況而調(diào)整象限分割的尺寸和疏密，從而產(chǎn)生較高的數(shù)據(jù)壓縮效率。一種四叉樹編碼的方式被稱為指針?biāo)牟鏄?或常規(guī)四叉樹)，即通過在子結(jié)點(diǎn)和父結(jié)點(diǎn)之間設(shè)立指針的方式建立起整

24、個(gè)結(jié)構(gòu)。按這種方式,四叉樹的每個(gè)結(jié)點(diǎn)通常存儲(chǔ)6個(gè)量即四個(gè)子結(jié)點(diǎn)指針、一個(gè)父結(jié)點(diǎn)指針相該結(jié)點(diǎn)的屬性代碼。這種方法除了要記錄葉結(jié)點(diǎn)外還要記錄中間結(jié)點(diǎn)，一般要占用較大存儲(chǔ)空間。但是另一方面，指針?biāo)牟鏄潆m然增加了些存儲(chǔ)量，卻換取了處理上的簡便和靈活，例如，要將相鄰的四塊四叉樹合并成一棵新樹，對指針?biāo)牟鏄鋪碚f就十分容易，只要將這四塊四叉樹作為新樹的子樹，使它們的根結(jié)點(diǎn)指針指向一個(gè)共同的根結(jié)點(diǎn)就行了。因此，指針?biāo)牟鏄鋵τ跀?shù)據(jù)檢索、多要素疊置分析和求實(shí)體間的空間關(guān)系等操作都很方便。在GIS中還經(jīng)常采用一種能以較小數(shù)據(jù)冗余存貯圖形圖像，而且又能方便地完成各種圖形圖像操作的編碼方式,即所謂線性四又樹方法，該方法

25、記錄從根結(jié)點(diǎn)至葉結(jié)點(diǎn)的路徑以及葉結(jié)點(diǎn)的屬性代碼，即僅記錄每個(gè)結(jié)點(diǎn)的地址、深度和屬性代碼三個(gè)量。這種方法較指針?biāo)牟鏄涔?jié)省存儲(chǔ)量，并且由于記錄了結(jié)點(diǎn)地址,就能夠直接找到其在四叉樹中的走向路徑，也可以換算出柵格區(qū)域中的行列位置。通常定義從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑可以按照象限遞歸分割的順序編號(hào)進(jìn)行。無論分割到哪一層，總是用0、1、2、3分別表示SW、SE、NW、NE四個(gè)象限的編號(hào)，只是每個(gè)子象限子結(jié)點(diǎn)編號(hào)的前綴必須為其父象限(父結(jié)點(diǎn))的編號(hào)，如右圖所示。通常每個(gè)葉結(jié)點(diǎn)的地址編號(hào)在計(jì)算機(jī)中是用二進(jìn)制數(shù)來表示的，在每一層上的象限位置(0、1、2、3)均可用兩位二進(jìn)制數(shù)寫出。例如，0記作二進(jìn)制數(shù)00，1記作二進(jìn)

26、制數(shù)01,2和3分別記作二進(jìn)制10和11。則編號(hào)為213的子象限(葉結(jié)占)的地址可用二進(jìn)制表示為； 編號(hào)213這樣，記錄了各個(gè)葉結(jié)點(diǎn)的地址，再記上各自相應(yīng)的屬性代碼值就記錄了整個(gè)圖像,并可在此基礎(chǔ)上進(jìn)行多種圖像操作。實(shí)際上，為了得到四叉樹葉結(jié)點(diǎn)的地址碼還可以來用一種被稱為Morton碼的方法直接得到。四叉樹編碼法有許多有趣的優(yōu)點(diǎn)： 容易而有效地計(jì)算多邊形的數(shù)量特征： 陣列各部分的分辨率是可變的，邊界復(fù)雜部分四叉樹較高，即分級多，分辨率也高，而不需要表示許多細(xì)節(jié)的部分則分級少，分辨率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存儲(chǔ)量； 柵格到四叉樹及到四叉樹到簡單柵格結(jié)構(gòu)的轉(zhuǎn)換比其他壓縮方法容易； 多邊

27、形中嵌套異類多邊形的表示較方便。四叉樹編碼的不足之處是轉(zhuǎn)換的不定性，同一形狀和大小的多邊形可能得出多種不同的四叉樹結(jié)構(gòu)，故不利于形狀分析和模式識(shí)別。但因它允許多邊形中嵌套多邊形即所謂“洞”的結(jié)構(gòu)存在，使越來越多的GIS工作者對四叉樹結(jié)構(gòu)很感興趣。上述這些壓縮數(shù)據(jù)的方法應(yīng)視圖形的復(fù)雜情況合理選用，同時(shí)應(yīng)在系統(tǒng)中備有相應(yīng)的程序。另外，用戶的分析目的和分析方法也決定著壓縮方法的選取 前面討論了5種柵格數(shù)據(jù)編碼方法。一般說來，對數(shù)據(jù)的壓縮是以增加運(yùn)算時(shí)間為代價(jià)的。在這里時(shí)間與空間是一對矛盾。為了更有效地利用空間資源，減少數(shù)據(jù)冗余，有時(shí)不得不多費(fèi)一些機(jī)器運(yùn)算時(shí)間進(jìn)行編碼以及進(jìn)行較為復(fù)雜的圖形運(yùn)算。一個(gè)好

28、的壓縮編碼方法就是要在盡可能減少運(yùn)算時(shí)間的基礎(chǔ)上達(dá)到最大的數(shù)據(jù)壓縮效率，并且使算法適應(yīng)性強(qiáng)，易于實(shí)現(xiàn)。柵格矩陣法簡單明了可直觀地反映柵格圖像數(shù)據(jù)，但是數(shù)據(jù)冗余太大；鏈碼的壓縮放率較高，已接近矢量結(jié)構(gòu)，對邊界的運(yùn)算比較方便，但是不具備區(qū)域的性質(zhì)，區(qū)域運(yùn)算較困難；行程編碼既可在很大程度上壓縮數(shù)據(jù)，又可較大限度地保留原始柵格結(jié)構(gòu)、而且編碼解碼也較為容易；塊碼和四叉樹編碼部具有區(qū)域性質(zhì)，而且有可變的分辨率，壓縮效率比較高。四叉樹編碼可以直接進(jìn)行大量的圖形圖像運(yùn)算，效率高，使用也日益廣泛。當(dāng)前，在四叉樹編碼的基礎(chǔ)上，對三維柵格數(shù)據(jù)己開始發(fā)展所謂八叉樹編碼方法。B 矢量數(shù)據(jù)結(jié)構(gòu)一、矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)

29、是通過記錄坐標(biāo)的方式，用點(diǎn)、線、面等基本要素盡可能精確地來表示各種地理實(shí)體。矢量數(shù)據(jù)表示的坐標(biāo)空間是連續(xù)的，因此可以精確定義地理實(shí)體的任意位置、長度、面積等。如前所述，其顯示精度較柵格結(jié)構(gòu)高。事實(shí)上，它主要受數(shù)字化設(shè)備的精度和數(shù)值記錄字長的限制。 在矢量結(jié)構(gòu)中對于點(diǎn)實(shí)體只是記錄其在某特定坐標(biāo)系下的坐標(biāo)和屬性代碼,可以將其空間數(shù)據(jù)和屬性數(shù)據(jù)結(jié)合在一起，將點(diǎn)的坐標(biāo)直接作為點(diǎn)實(shí)體的兩個(gè)屬性值對待。在對線實(shí)體進(jìn)行數(shù)字化時(shí)，就是用一系列足夠短的直線段首尾相接表示一條曲線，當(dāng)曲線被分割成多而短的線段后,這些小線段可以近似地看成直線段，而這條曲線也可以足夠精確地由這些小直線段序列表示。在矢量結(jié)構(gòu)中，只記錄這

30、些小線段的端點(diǎn)坐標(biāo)，將曲線表示為一個(gè)坐標(biāo)序列，坐標(biāo)之間認(rèn)為是以直線段相接，在某一精度范圍內(nèi)可以逼真地表示出各種形狀的線狀地物。對于面實(shí)體而言，在GIS中常用所謂“多邊形”的概念來表述一個(gè)任意形狀，并且邊界完全閉合的空間區(qū)域。該閉合區(qū)域的邊界線同前面介紹的線實(shí)體一樣,也可以被看作是由一系列多而短的直線段組成，每個(gè)小線段作為這個(gè)區(qū)域的一條邊，因此該區(qū)域也可看成是由這些邊組成的多邊形了。 矢量數(shù)據(jù)結(jié)構(gòu)直接以幾何空間坐標(biāo)為基礎(chǔ)，記錄取樣點(diǎn)坐標(biāo)，可以將目標(biāo)表示得精確無誤。對于一個(gè)數(shù)字制圖系統(tǒng)而言，按照這種簡單的記錄方式，再適當(dāng)增加目標(biāo)的注記名稱、輸出的線型和符號(hào)等，在矢量繪圖儀上就可以得到精美的地圖。另

31、外，該結(jié)構(gòu)還可以對復(fù)雜數(shù)據(jù)以最小的數(shù)據(jù)冗余進(jìn)行存貯，相對于柵格結(jié)構(gòu)來說，它還具有數(shù)據(jù)精度高，存貯空間小等特點(diǎn)，是一種高效的圖形數(shù)據(jù)結(jié)構(gòu)。 因?yàn)槭噶拷Y(jié)構(gòu)的空間定位是根據(jù)坐標(biāo)直接存貯的，而屬性數(shù)據(jù)現(xiàn)在通常是建立表結(jié)構(gòu)文件，用關(guān)系數(shù)據(jù)庫管理。因此，矢量數(shù)據(jù)結(jié)構(gòu)具有定位明顯、屬性隱含的特點(diǎn)。由于這一特點(diǎn)點(diǎn)使其在某些方面有便利和獨(dú)到之處，例如在計(jì)算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度。但是同樣由于這一特點(diǎn)，也使其圖形運(yùn)算的算法要較柵格結(jié)構(gòu)復(fù)雜；在涉及疊加運(yùn)算、鄰域搜索等操作方面也不及柵格結(jié)構(gòu)簡單.二、矢量數(shù)據(jù)結(jié)構(gòu)編碼的基本內(nèi)容1點(diǎn)實(shí)體 點(diǎn)實(shí)體包括由單獨(dú)一對x，y坐標(biāo)定位

32、的一切地理或制圖實(shí)體。在矢量數(shù)據(jù)結(jié)構(gòu)中，除點(diǎn)實(shí)體的x，y坐標(biāo)外還應(yīng)存儲(chǔ)其它一些與點(diǎn)實(shí)體有關(guān)的數(shù)據(jù)來描述點(diǎn)實(shí)體的類型、制圖符號(hào)和顯示要求等。 點(diǎn)是空間上不可再分的地理實(shí)體，可以是具體的, 也可以是抽象的，如地物點(diǎn)、文本位置點(diǎn)或線段網(wǎng)絡(luò)的結(jié)點(diǎn)等，如果點(diǎn)是一個(gè)與其它信息無關(guān)的符號(hào)，則記錄時(shí)應(yīng)包括符號(hào)類型、大小、方向等到有關(guān)信息；如果點(diǎn)是文本實(shí)體，記錄的數(shù)據(jù)應(yīng)包括字符大小、字體、排列方式、比例、方向以及與其它非圖形屬性的聯(lián)系方式等信息。對其它類型的點(diǎn)實(shí)體也應(yīng)做相應(yīng)的處理。右圖說明點(diǎn)實(shí)體的矢量數(shù)據(jù)結(jié)構(gòu)的一種組織方式。2線實(shí)體 線實(shí)體可以定義為直線元素組成的各種線性要素，直線元素由兩對x ，y坐標(biāo)定義。最

33、簡單的線實(shí)體只存儲(chǔ)它的起止點(diǎn)坐標(biāo)、屬性、顯示等有關(guān)數(shù)據(jù)。例如，線實(shí)體輸出時(shí)可能用實(shí)線或虛線描繪，這類信息屬符號(hào)信息，它說明線實(shí)體的輸出方式。雖然線實(shí)體并不是以虛線存儲(chǔ)，仍可用虛線輸出。 弧、鏈?zhǔn)莕個(gè)坐標(biāo)對的集合。這些坐標(biāo)可以描述任何連續(xù)而又復(fù)雜的曲線。組成曲線的線元素越短，x，y坐標(biāo)數(shù)量越多，就越逼近于一條復(fù)雜的曲線。既要節(jié)省存儲(chǔ)空間，又要求較為精確地描繪曲線，唯一的辦法是增加數(shù)據(jù)處理工作量。亦即在線實(shí)體的紀(jì)錄中加入一個(gè)指示字，當(dāng)起動(dòng)顯示程序時(shí)，這個(gè)指示字告訴程序：需要數(shù)學(xué)內(nèi)插函數(shù)（例如樣條函數(shù)）加密數(shù)據(jù)點(diǎn)且與原來的點(diǎn)匹配, 于是在輸出設(shè)備上得到較精確的曲線。不過，數(shù)據(jù)內(nèi)插工作卻增加了?；『玩?/p>

34、的存儲(chǔ)記錄中也要加人線的符號(hào)類型等信息。 線的網(wǎng)絡(luò)結(jié)構(gòu)：線或鏈攜帶彼此互相連接的空間信息，而這種連接信息又是供排水網(wǎng)和道路網(wǎng)分析中必不可少的信息。因此要在數(shù)據(jù)結(jié)構(gòu)中建立指針系統(tǒng)才能讓計(jì)算機(jī)在復(fù)雜的線網(wǎng)結(jié)構(gòu)中逐線路綜每一條線。指針的建立要以結(jié)點(diǎn)為基礎(chǔ)。如建立水網(wǎng)中每條支流之間連接關(guān)系時(shí)必須使用這種指針系統(tǒng)指針系統(tǒng)包括結(jié)點(diǎn)指向線的指針。每條從結(jié)支流之間連接關(guān)系時(shí)必須使用這種指針系統(tǒng)指針系統(tǒng)包括結(jié)點(diǎn)指向線的指針。每條從結(jié)點(diǎn)出發(fā)的線匯于結(jié)點(diǎn)處的角度等，從而完整地定義線網(wǎng)絡(luò)的拓樸關(guān)系。 如上所述。線實(shí)體主要用來表示線狀地物（公路、水系、山脊線）、符號(hào)線和多邊形邊界，有時(shí)也稱為“弧”、“鏈”、“串”等，其

35、矢量編碼的內(nèi)容如右圖所示。其中:唯一標(biāo)識(shí)是系統(tǒng)排列序號(hào)；線標(biāo)識(shí)碼可以標(biāo)識(shí)線的類型；起始點(diǎn)和終止點(diǎn)可以用點(diǎn)號(hào)或直接用坐標(biāo)表示；顯示信息是顯示時(shí)的文本或符號(hào)等；與線相聯(lián)的非幾何屬性可以直接存儲(chǔ)于線文件中。也可單獨(dú)存儲(chǔ)，而由標(biāo)識(shí)碼聯(lián)接查找。3。面實(shí)體 多邊形（有時(shí)稱為區(qū)域）數(shù)據(jù)是描述地理空間信息的最重要的一類數(shù)據(jù)。在區(qū)域?qū)嶓w中，具有名稱屬性和分類屬性的，多用多邊形表示，如行政區(qū)、土地類型、植被分布等；具有標(biāo)量屬性的有時(shí)也用等值線描述（如地形、降雨量等）。 多邊形的矢量編碼，不但要表示位置和屬性，更重要的是能表達(dá)區(qū)域的拓?fù)涮卣鳎缧螤?、領(lǐng)域和層次結(jié)構(gòu)等，以便恢復(fù)這些基本的空間單元可以作為專題圖的資料進(jìn)

36、行顯示和操作，由于要表示的信息十分豐富，基于多邊形的運(yùn)算多而復(fù)雜，因此多邊形矢量編碼比點(diǎn)和線實(shí)體的矢量編碼要復(fù)雜得多，也更為重要。 在討論多邊形數(shù)據(jù)結(jié)構(gòu)編碼的時(shí)候，需注意到多邊形網(wǎng)有如下特點(diǎn)： （1）組成地圖的每個(gè)多邊形有不同的形狀、周長和面積。 （2）地理分析要求的數(shù)據(jù)結(jié)構(gòu)應(yīng)能夠記錄每個(gè)多邊形的鄰域關(guān)系，其方法與水系網(wǎng)中記錄連接關(guān)系一樣。 （3）專題地圖上的多邊形并不都是同一等級的多邊形，而可能是多邊形內(nèi)嵌套小的多邊形（次一級）。例如，湖泊的水域線在土地用圖上可算是個(gè)島狀多邊形，而湖中的島嶼為“島中之島”這種所謂“島”或“洞”的結(jié)構(gòu)是多邊形關(guān)系中較難處理的問題。 三、矢量數(shù)據(jù)的編碼 矢量數(shù)據(jù)

37、的編碼包括坐標(biāo)編碼和拓?fù)渚幋a兩個(gè)方面。 （一）坐標(biāo)編碼矢量數(shù)據(jù)的坐標(biāo)位置即地圖上任何點(diǎn)、線、面（多邊形）的坐標(biāo)位置，可以用直角坐標(biāo)系中的坐標(biāo)點(diǎn)X，y表示。X，y可以對應(yīng)于地面的經(jīng)、緯度，也可以對應(yīng)于數(shù)字化時(shí)所建立的平面坐標(biāo)系x和y。如前所述：點(diǎn)用一對x，y表示；線用一組有序的x，y坐標(biāo)對表示；多邊形用一組坐標(biāo)首尾相接的有序X，y坐標(biāo)對表示。這些點(diǎn)是在光滑的曲線上間隔采樣獲得的。同一曲線長度取點(diǎn)越多，以后恢復(fù)圖形時(shí)越接近原曲線形狀；取點(diǎn)過少，則恢復(fù)時(shí)就會(huì)出現(xiàn)失真，曲線很可能畸變成為折線。下圖為點(diǎn)、線、面的坐標(biāo)表示和坐標(biāo)點(diǎn)的編碼文件。 圖中的點(diǎn)、線、面坐標(biāo)各具特征，因此編碼時(shí)需要對每一種特征給定一

38、個(gè)序號(hào)，或叫做特征碼。每一特征的坐標(biāo)可以用每一特征點(diǎn)的坐標(biāo)對和有關(guān)的序號(hào)來記錄。（二）拓?fù)渚幋a（ToPological Encoding）為了真實(shí)地表現(xiàn)空間實(shí)體，不僅要反映實(shí)體的坐標(biāo)位置，而且要反映出實(shí)體之間的相互關(guān)系。拓?fù)渚幋a主要是用來反映點(diǎn)、線和面在真實(shí)空間中的相互關(guān)系和屬性聯(lián)系。所以拓?fù)渚幋a是坐標(biāo)編碼的一種補(bǔ)充，它使數(shù)據(jù)庫對存儲(chǔ)的空間實(shí)體的描述更加完整。所謂拓?fù)浣Y(jié)構(gòu)是指確定各地理實(shí)體空間關(guān)系的數(shù)學(xué)方法。為了準(zhǔn)確描述空間目標(biāo)的位置和空間關(guān)系，在幾何上主要從兩個(gè)方面進(jìn)行： 在幾何形態(tài)方面，常采用解析幾何方法來分析，這主要是以幾何坐標(biāo)為基礎(chǔ)，涉及空間目標(biāo)的角度、周長、方向、距離離和面積等； 在

39、空間關(guān)系方面，則采用拓?fù)鋷缀畏椒▉砻枋?，主要涉及的是空間目標(biāo)之間的“相鄰”、“相連”、“包容”、“在里面”和“在外面”等關(guān)系。這樣，就可能發(fā)生幾何結(jié)構(gòu)相差很大的圖形，它們的拓?fù)浣Y(jié)構(gòu)卻可能相同。所以說，若從幾何形態(tài)的觀點(diǎn)出發(fā)，主要研究的是圖形的位置形狀；而從拓?fù)溆^點(diǎn)看，則重視的是點(diǎn)、線和多邊形之間的相互關(guān)系。 空間數(shù)據(jù)的拓?fù)潢P(guān)系主要表現(xiàn)為下列三種關(guān)系： 拓?fù)溧徑樱褐复嬖谟诳臻g圖形的同類元素之間的拓?fù)潢P(guān)系。如上圖中，結(jié)點(diǎn)鄰接關(guān)系有N1N4；N1N2，等；多邊形鄰接關(guān)系有P1P3，P2P3，等。 拓?fù)潢P(guān)聯(lián)：指存在空間圖形的不同類元素之間的拓?fù)潢P(guān)系。如圖1-2-2中結(jié)點(diǎn)與線段的關(guān)聯(lián)關(guān)系有N1C1、C3

40、、C6，N2C1、C2、C5，等。多邊形與線段的關(guān)聯(lián)關(guān)系有PlC1、C5、C6，P2C2、C4、C5、C7，等。拓?fù)浒褐复嬖谟诳臻g圖形的同類但不同級的元素之間的拓?fù)潢P(guān)系。如上圖中設(shè)ID表示當(dāng)前多邊形，IW表示等價(jià)包含數(shù)，IP表示ID是否為島。若為島則以IP0表示，若不是島則以IP=0表示。于是圖上所示的關(guān)系為：空間數(shù)據(jù)的拓?fù)潢P(guān)系對地理信息系統(tǒng)的數(shù)據(jù)處理和空間分析具有重要意義?？臻g拓?fù)涞淖饔茫?）根據(jù)拓?fù)潢P(guān)系，不需要利用坐標(biāo)或距離，可以確定一種地理實(shí)體相對于另一種地理實(shí)體的位置關(guān)系。2）拓?fù)鋽?shù)據(jù)也有利于空間要素的查詢，如查詢某條河流能為哪些行政區(qū)提供飲用水源；某一開發(fā)區(qū)與哪些道路鄰接等。3）

41、拓?fù)鋽?shù)據(jù)也可用做重建地理實(shí)體的工具。例如建立封閉多邊形、實(shí)現(xiàn)道路的選取、進(jìn)行最佳路徑的計(jì)算等。拓?fù)潢P(guān)系的表示方法是拓?fù)渚幋a中的一個(gè)重要問題。我們將在下一節(jié)弧段一結(jié)點(diǎn)結(jié)構(gòu)和相關(guān)數(shù)據(jù)結(jié)構(gòu)中再做介紹。四、幾種典型的矢量數(shù)據(jù)結(jié)構(gòu) 目前用于GIS編碼的矢量數(shù)據(jù)結(jié)構(gòu)種類很多，比較典型的有全多邊形結(jié)構(gòu)，DIME結(jié)構(gòu)、弧段一節(jié)點(diǎn)結(jié)構(gòu)，DLG結(jié)構(gòu)等。簡要介紹如下：（一） 全多邊形結(jié)構(gòu)（Whole Polygon Structure）全多邊形結(jié)構(gòu)主要用于表示空間圖形為多邊形的面狀要素。一個(gè)區(qū)域或一幅地圖可以劃分成許多多邊形（如右圖）。每個(gè)多邊形由一條或若干條線段或弧段組成，每條線段或弧段包含二個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)連接

42、二條以上的弧段。全多邊形結(jié)構(gòu)中，每個(gè)多邊形在數(shù)據(jù)庫中是相互獨(dú)立、分開存儲(chǔ)的。多邊形的屬性例如土地類型、土壤類型等可以用坐標(biāo)表的方式存儲(chǔ)。 缺點(diǎn)是：1）不考慮多邊形的拓?fù)潢P(guān)系。2）全多邊形結(jié)構(gòu)由于一些多邊形的公共弧段和結(jié)點(diǎn)在數(shù)據(jù)庫中被多次記錄，因此不僅數(shù)據(jù)的冗余度很大，而且很容易造成數(shù)據(jù)結(jié)構(gòu)的破壞；3）“島”只作為一個(gè)單個(gè)圖形構(gòu)造，沒有與其外包多邊形的聯(lián)系；4)不易對邊界的拓?fù)潢P(guān)系進(jìn)行檢查。（二) DIME結(jié)構(gòu) DIME（Dual Independent Map Encoding）稱為“雙重獨(dú)立地圖編碼”，這是由美國人口局發(fā)展起來的、為在城區(qū)進(jìn)行人口統(tǒng)計(jì)分析時(shí)設(shè)計(jì)的一種拓?fù)渚庉嫹椒?。它是GIS發(fā)

43、展早期使用的一種拓?fù)渚幋a方式。 DIME文件由線段記錄組成，線段即指兩個(gè)端點(diǎn)或結(jié)點(diǎn)之間的一條直線段。例如街道、鐵路、機(jī)場跑道等。在這種結(jié)構(gòu)中，線段通常被認(rèn)為是直線型的。如果出現(xiàn)弧段，可以將其看作是一系列有序直線的合成。DIME文件中每條線段均單獨(dú)進(jìn)行編碼。文件編輯存儲(chǔ)的基本要素包括線段名（如街道名）、描述線段兩端結(jié)點(diǎn)的“始”結(jié)點(diǎn)號(hào)和“終”結(jié)點(diǎn)號(hào)以及描述該線段兩側(cè)區(qū)域的“左”區(qū)號(hào)和“右”區(qū)號(hào)。此外，許多輔助的屬性信息在DIME文件中也可以給予編碼。這些信息包括如街道兩側(cè)的地址范圍、地區(qū)碼、人口統(tǒng)計(jì)地段碼、非街道要素的代碼、郵政代碼和選舉分區(qū)代碼等。下圖簡要地表明了DIME文件的拓?fù)浣Y(jié)構(gòu)編碼方式。

44、（三）弧段一結(jié)點(diǎn)結(jié)構(gòu)（ArcNode Structure） 在弧段一結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素在數(shù)據(jù)庫中是分層次組織的。其中，點(diǎn)是最基本的元素，弧段由一組X，y坐標(biāo)對來定義，而多邊形則由一組閉合的弧段限定的區(qū)域構(gòu)成。這種結(jié)構(gòu)中的結(jié)點(diǎn)是由弧段的端點(diǎn)或幾條弧段相交的交點(diǎn)組成。許多結(jié)點(diǎn)為一些弧段和鄰接的多邊形共有，但是一些與線段無關(guān)的點(diǎn)不能作為結(jié)點(diǎn)?；《我唤Y(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)與全多邊形結(jié)構(gòu)不同，它在對數(shù)據(jù)進(jìn)行幾何位置編碼時(shí)沒有冗余。點(diǎn)在編碼中僅僅記錄一次，但可以反復(fù)調(diào)出來使用。各種類型的屬性數(shù)據(jù)利用這種結(jié)構(gòu)很容易編入數(shù)據(jù)庫，而且屬性數(shù)據(jù)和數(shù)據(jù)元素的幾何位置是相互聯(lián)系的。下圖是弧段一結(jié)點(diǎn)結(jié)構(gòu)的直觀表示，表達(dá)了“

45、面弧”、“結(jié)點(diǎn)弧”等一系列空間拓?fù)潢P(guān)系。在數(shù)字化輸入完成以后建立矢量拓?fù)浣Y(jié)構(gòu)的過程可以分為五個(gè)階段來完成。1） 首先，在所涉及的范圍內(nèi)對所有邊界線進(jìn)行分類，通過自相交或兩兩相交使各邊界線都分割成兩結(jié)點(diǎn)之間的具有單一拓?fù)湫再|(zhì)的弧段，建立連接指針，構(gòu)成圖形外邊界；2） 然后，檢查該外邊界構(gòu)成的多邊形是否閉合，即應(yīng)保證連接指針的正確，只有在單弧段組成的“孤島”情況下，弧段指針才可能指向該弧本身；3） 第三步從外邊界連接各弧段構(gòu)成各個(gè)內(nèi)多邊形，并給以順序編導(dǎo)；4） 第四步按梯形規(guī)則計(jì)算各多邊形面積，井將其作為附加屬性記錄，5） 最后，向建立的多邊形連接其同性數(shù)據(jù)，建正與屬性庫的聯(lián)系。自動(dòng)建立拓?fù)浣Y(jié)構(gòu)編

46、碼可以簡化數(shù)據(jù)錄入流程，減少工作量，生成的拓?fù)潢P(guān)系的可靠性和一致性較好，此外，該法還具有如下優(yōu)點(diǎn)：(1)可將多邊形生成完好的網(wǎng)絡(luò)，減少數(shù)據(jù)冗余和公共邊界不重合的矛盾，(2)因?yàn)樯傻亩噙呅巍⑦吔缂捌鋵傩远即嬖谥ハ嗦?lián)系，從而可以實(shí)現(xiàn)鄰域分析，(3)多邊形與生成“島”的層次關(guān)系不受限制；(4)其精度僅受數(shù)字化儀本身精度和計(jì)算機(jī)字長的限制。多邊形編碼與拓?fù)潢P(guān)系自動(dòng)生成的具體算法原理可參見地理信息系統(tǒng)使用教程一書。總之，矢量結(jié)構(gòu)自身的待點(diǎn)決定于矢量編碼具有信息的完整性和運(yùn)算的靈活性。但是從目前來說，尚無統(tǒng)一的最佳矢量結(jié)構(gòu)編碼方法。所以在具體工作中應(yīng)根據(jù)任務(wù)的性質(zhì)、要求和數(shù)據(jù)特點(diǎn)靈活地應(yīng)用與設(shè)計(jì)。 C

47、 矢量與柵格數(shù)據(jù)結(jié)構(gòu)的比較 在計(jì)算機(jī)輔助制圖和地理信息系統(tǒng)發(fā)展早期，最初引用的是矢量處理技術(shù)，柵格數(shù)據(jù)處理始于70年代中期。幾年以前，這兩種數(shù)據(jù)結(jié)構(gòu)勢不兩立，很難兼容，因此給數(shù)據(jù)利用帶來許多不便。近年來，人們越來越清楚地認(rèn)識(shí)到：原先把柵格和矢量數(shù)據(jù)結(jié)構(gòu)的差別當(dāng)成重要的概念差別，事實(shí)上都是技術(shù)問題。計(jì)算機(jī)技術(shù)的發(fā)展使運(yùn)算速度、存儲(chǔ)能力、地理數(shù)據(jù)的空間分辨率等大大提高。為了更有效地利用GIS，人們面臨的問題之一是柵格和矢量數(shù)據(jù)結(jié)構(gòu)的選擇。 一、矢量與柵格數(shù)據(jù)結(jié)構(gòu)的比較 地理信息系統(tǒng)的數(shù)據(jù)范圍十分廣泛，數(shù)據(jù)保存方式多種多樣，數(shù)據(jù)結(jié)構(gòu)類型復(fù)雜?？臻g數(shù)據(jù)的矢量結(jié)構(gòu)和柵格結(jié)構(gòu)是模擬地理信息系統(tǒng)的截然不同的

48、兩種方法，它們各有千秋，相互補(bǔ)充、相互促進(jìn)。矢量數(shù)據(jù)與柵格數(shù)據(jù)結(jié)構(gòu)詳細(xì)比較見下表。 表：矢量與柵格數(shù)據(jù)的比較 二、矢量數(shù)據(jù)和柵格數(shù)據(jù)的選擇 根據(jù)上述比較，在GIS建立過程中，應(yīng)根據(jù)應(yīng)用目的要求、實(shí)際應(yīng)用特點(diǎn)、可能獲得的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件配制情況，在矢量和柵格數(shù)據(jù)結(jié)構(gòu)中選擇合適的數(shù)據(jù)結(jié)構(gòu)。 矢量數(shù)據(jù)結(jié)構(gòu)是人們最熟悉的圖形表達(dá)形式，對于線劃地圖來說，用矢量數(shù)據(jù)來記錄往往比用柵格數(shù)據(jù)節(jié)省存貯空間。相互連接的線網(wǎng)絡(luò)或多邊形網(wǎng)絡(luò)則只有矢量數(shù)據(jù)結(jié)構(gòu)模式才能做到，因此矢量結(jié)構(gòu)更有利于網(wǎng)絡(luò)分析（交通網(wǎng)，供、排水網(wǎng)，煤氣管道，電纜等）和制圖應(yīng)用。矢量數(shù)據(jù)表示的數(shù)據(jù)精度高，并易于附加上對制圖物體的

49、屬性所作的分門別類的描述。目前解析幾何被頻繁地應(yīng)用于矢量數(shù)據(jù)的處理中，對于一些直接與點(diǎn)位有關(guān)的處理以及有現(xiàn)成數(shù)學(xué)公式可循的針對個(gè)別符號(hào)的操作計(jì)算，用矢量數(shù)據(jù)有其獨(dú)到的便利之處。矢量數(shù)據(jù)便于產(chǎn)生各個(gè)獨(dú)立的制圖物體，并便于存貯備圖形元素間的關(guān)系信息。 柵格數(shù)據(jù)結(jié)構(gòu)是一種影像數(shù)據(jù)結(jié)構(gòu)，適用于遙感圖像的處理。它與制圖物體的空間分布特征有著簡單、直觀而嚴(yán)格的對應(yīng)關(guān)系，對于制圖物體空間位置的可探性強(qiáng)，并為應(yīng)用機(jī)器視覺提供了可能性，對于探測物體之間的位置關(guān)系，柵格數(shù)據(jù)最為便捷。多邊形數(shù)據(jù)結(jié)構(gòu)的計(jì)算方法中常常采用柵格選擇方案，而且在許多情況下，柵格方案還更有效。例如，多邊形周長、面積、總和、平均值的計(jì)算、從一

50、點(diǎn)出發(fā)的半徑等在柵格數(shù)據(jù)結(jié)構(gòu)中都減化為簡單的計(jì)數(shù)操作。又因?yàn)闁鸥褡鴺?biāo)是規(guī)則的，刪除和提取數(shù)據(jù)都可按位置確定窗口來實(shí)現(xiàn)，比矢量數(shù)據(jù)結(jié)構(gòu)方便得多。最近以矢量數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)發(fā)展起來的柵格算法表明存在著一種比以前想象中更為有效的方法去解決某些柵格結(jié)構(gòu)曾經(jīng)存在的問題。例如，柵格結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)量過大的問題可用前面提出的壓縮方法使其減少。 柵格結(jié)構(gòu)和矢量結(jié)構(gòu)都有一定的局限性。一般來說，大范圍小比例的自然資源、環(huán)境、農(nóng)業(yè)、林業(yè)、地質(zhì)等區(qū)域問題的研究，城市總體規(guī)劃階段的戰(zhàn)略性布局研究等，使用柵格模型比較合適。城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公用事業(yè)管理等方面的應(yīng)用，矢量模型比較合適。當(dāng)然也可以把兩種模型混合起來使

51、用，在同一屏幕上同時(shí)顯示兩種方式的地圖。目前GIS的開發(fā)者和使用者都積極研究這兩類數(shù)據(jù)結(jié)構(gòu)的相互轉(zhuǎn)換技術(shù)，而且己開發(fā)出柵格數(shù)據(jù)結(jié)構(gòu)和矢量數(shù)據(jù)結(jié)構(gòu)相互轉(zhuǎn)換的軟件。 D 兩種數(shù)據(jù)結(jié)構(gòu)的相互轉(zhuǎn)換 對地圖數(shù)字化主要是采用兩種方式，即手扶跟蹤數(shù)字化產(chǎn)生矢量結(jié)構(gòu)數(shù)據(jù)和圖像掃描產(chǎn)生柵格結(jié)構(gòu)數(shù)據(jù)。在GIS中，這兩種數(shù)據(jù)結(jié)構(gòu)是最基本的。因此矢量數(shù)據(jù)與柵格數(shù)據(jù)的相互轉(zhuǎn)換的方法也就必然要成為在不同GIS之間進(jìn)行數(shù)據(jù)傳輸、信息共享所不可缺少的手段；即使在同一GIS系統(tǒng)中，在實(shí)現(xiàn)其空間分析和數(shù)據(jù)操作的過程中，為使系統(tǒng)運(yùn)行的總體效率和功能得以圓滿完成，這種數(shù)據(jù)格式的相互轉(zhuǎn)換也是不可避免的，并且也是GIS的重要功能之一。

52、一般地，GIS中的數(shù)據(jù)格式轉(zhuǎn)換基本上可分為矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換和柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換兩種方式。這種互相轉(zhuǎn)換是通過各種算法編制的轉(zhuǎn)換程序得以實(shí)現(xiàn)的。近年來已發(fā)展了許多高效的轉(zhuǎn)換算法以適應(yīng)不同的環(huán)境需要。 一、矢量數(shù)據(jù)向柵格數(shù)據(jù)的轉(zhuǎn)換 對于以矢量結(jié)構(gòu)表述的點(diǎn)狀實(shí)體而言，每個(gè)實(shí)體僅由一個(gè)坐標(biāo)對表示其空間位置，而在概格結(jié)構(gòu)中的點(diǎn)實(shí)體（像元）的位置，則是由該點(diǎn)所處的行列位置所確定。因此對于點(diǎn)實(shí)體的兩種結(jié)構(gòu)轉(zhuǎn)換基本上只是一個(gè)坐標(biāo)精度變換的問題，在技術(shù)上并不難解決。 用矢量結(jié)構(gòu)表示的線實(shí)體是由一系列點(diǎn)的坐標(biāo)對來表述其位置的，在變換為柵格結(jié)構(gòu)時(shí)，按解析幾何中的兩點(diǎn)式直線方程，根據(jù)柵格精度要求，在每兩坐標(biāo)點(diǎn)

53、之間插入一系列柵格像元，每個(gè)坐標(biāo)點(diǎn)變換為柵格結(jié)構(gòu)的行列坐標(biāo)，可見在線實(shí)體上實(shí)現(xiàn)這種結(jié)構(gòu)轉(zhuǎn)換也是不難實(shí)現(xiàn)的。因此，通常對轉(zhuǎn)換算法的研究主要放在對面實(shí)體或稱多邊形的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換上。為便于敘述，這里對所謂多邊形及其矢量格式和柵格格式給予具體定義。 多邊形：指由折線段組成的封閉曲線圍成的多邊形區(qū)域，具有可唯一標(biāo)識(shí)的多邊形編號(hào)。該編號(hào)可作為多邊形屬性代碼也可是指向?qū)傩詳?shù)據(jù)記錄地址的指針。 所謂矢量格式向柵格格式的數(shù)據(jù)轉(zhuǎn)換，就是在矢量格式的多邊形內(nèi)部給所有柵格像元上賦以相應(yīng)的多邊形編號(hào)，故又可稱為多邊形填充?，F(xiàn)將幾種主要的轉(zhuǎn)換算法描述如下： （l）內(nèi)部點(diǎn)擴(kuò)散算法 該算法由每個(gè)多邊形的一個(gè)內(nèi)部點(diǎn)（種子點(diǎn)）開

54、始，向周圍8個(gè)方向的鄰點(diǎn)擴(kuò)散，然后判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上。若新點(diǎn)在邊界上，則該點(diǎn)不作為種子點(diǎn)，停止擴(kuò)散；如果該點(diǎn)不在多邊形邊界上，則該點(diǎn)作為新的種子點(diǎn)與原有的種子點(diǎn)一起繼續(xù)向外擴(kuò)散，并將新的種子點(diǎn)賦以該多邊形編號(hào)。重復(fù)上述過程直到所有的種子點(diǎn)填滿該多邊形并遇到多邊形邊界停止為止。 擴(kuò)散算法程序設(shè)計(jì)比較復(fù)雜，需要在柵格陣列中進(jìn)行搜索，占用內(nèi)存較大。當(dāng)計(jì)算機(jī)內(nèi)存容量受限制時(shí)，由于搜索過程中讀寫磁盤文件需花費(fèi)大量的時(shí)間，故該法難于采用。另外，由于柵格精度的限制，在一定的柵格精度下，如果復(fù)雜圖形中某個(gè)多邊形兩側(cè)的邊界落入同一個(gè)或相鄰的兩個(gè)柵格像元之內(nèi)，就會(huì)造成該多邊形不連通，如圖322（e

55、）所示，此時(shí)，僅用一個(gè)種子點(diǎn)就不能完成整個(gè)多邊形的填充。 （2）射線算法 射線算法是逐點(diǎn)判斷各柵格點(diǎn)是位于多邊形內(nèi)或在多邊形之外。通過從待判點(diǎn)向外引射線，然后判斷該射線與多邊形的邊界相交的次數(shù)。如果相交偶數(shù)次，則該點(diǎn)在多邊形外部；若為奇數(shù)次，則該點(diǎn)為多邊形內(nèi)部點(diǎn)。如圖323所示，當(dāng)n一奇數(shù)時(shí)，可給該點(diǎn)賦值該多邊形編號(hào)。 射線算法要計(jì)算射線與多邊形邊界的交點(diǎn)，計(jì)算量較大。此外，判斷射線與多邊形邊界相交時(shí)，有一些特殊情況會(huì)影響判斷的正確性，如圖322所示的幾種特例情況，必須予以排除。而這又會(huì)造成算法的不完善并增加編程的復(fù)雜性。 （3）掃描算法 掃描算法是射線算法的改進(jìn)。通常情況下，沿柵格陣列的行（

56、或列）方向進(jìn)行逐行（列）掃描，對掃描線每兩次遇到多邊形邊界的交點(diǎn)之間的柵格，判別為屬于多邊形內(nèi)部點(diǎn)給予賦值該多邊形編號(hào)。掃描算法較射線算法大大提高了計(jì)算效率。但是，射線算法中的一些特殊情況，如圖322所示，在掃描算法中仍然存在，仍需給予特殊處理。 （4）邊界代數(shù)算法 邊界代數(shù)法是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換的方法。在平面直角坐標(biāo)系下，沿多邊形邊界對坐標(biāo)軸積分，可以得到閉合多邊形的面積。模仿積分求多邊形面積的過程，首先以單個(gè)多邊形的簡單情況為例，說明邊界代數(shù)法的轉(zhuǎn)換原理，然后再推廣到由多個(gè)多邊形組成的區(qū)域轉(zhuǎn)換方法。圖324表示轉(zhuǎn)換單個(gè)多邊形的情況。設(shè)該多邊形編號(hào)為a，對初始化的柵格陣列各像元賦值為零，欲完成轉(zhuǎn)換，就是要將該多邊形區(qū)域內(nèi)的所有柵格像元均賦值為a，而多邊形區(qū)域以外的像元仍保持原值零。因此，轉(zhuǎn)換時(shí)以柵格行列為參考坐標(biāo)軸，從多邊形邊界上某點(diǎn)開始順時(shí)針?biāo)阉鬟吔缇€。當(dāng)邊界上行時(shí)，如圖324（a），位于該邊界線段左側(cè)的具有相同行號(hào)的所有柵格像元被減去a值；當(dāng)邊界下行時(shí)，如圖324（b），該邊界左側(cè)（或?yàn)檫吔缧羞M(jìn)方向的右側(cè)）的所有柵格像元加上一個(gè)值a，當(dāng)沿邊界搜索一周重新回到起點(diǎn)后，所有多邊形內(nèi)部像元點(diǎn)都已被賦值a，而多邊形外部的柵格像元值不變，從而完成多邊形填充的轉(zhuǎn)換.二、柵格數(shù)據(jù)向矢量數(shù)據(jù)的轉(zhuǎn)換 柵格數(shù)據(jù)向矢量數(shù)據(jù)的轉(zhuǎn)換實(shí)際上就是將具有相同屬性代碼的