GIS教案：第4章空間數(shù)據(jù)結(jié)構(gòu)

1、第4章 空間數(shù)據(jù)結(jié)構(gòu)空間數(shù)據(jù)結(jié)構(gòu)是指對空間數(shù)據(jù)邏輯模型描述的數(shù)據(jù)組織關(guān)系和編排方式，對地理信息系統(tǒng)中數(shù)據(jù)存儲、查詢檢索和應(yīng)用分析等操作處理的效率有著至關(guān)重要的影響。同一空間數(shù)據(jù)邏輯模型往往采用多種空間數(shù)據(jù)結(jié)構(gòu)，例如游程長度編碼結(jié)構(gòu)、四叉樹結(jié)構(gòu)都是柵格數(shù)據(jù)模型的具體實現(xiàn)?？臻g數(shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)溝通信息的橋梁，只有充分理解地理信息系統(tǒng)所采用的特定數(shù)據(jù)結(jié)構(gòu)，才能正確有效地使用系統(tǒng)。在地理信息系統(tǒng)中，較常用的有柵格數(shù)據(jù)結(jié)構(gòu)和矢量數(shù)據(jù)結(jié)構(gòu)，除此之外還有混合數(shù)據(jù)結(jié)構(gòu)、鑲嵌數(shù)據(jù)結(jié)構(gòu)和超圖數(shù)據(jù)結(jié)構(gòu)等。空間數(shù)據(jù)結(jié)構(gòu)的選擇取決于數(shù)據(jù)的類型、性質(zhì)和使用的方式，應(yīng)根據(jù)不同的任務(wù)目標，選擇最有效和最合適的數(shù)據(jù)結(jié)構(gòu)。

2、 4.1矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)對矢量數(shù)據(jù)模型進行數(shù)據(jù)的組織。它通過記錄實體坐標及其關(guān)系，盡可能精確地表示點、線、多邊形等地理實體，坐標空間設(shè)為連續(xù)，允許任意位置、長度和面積的精確定義。矢量數(shù)據(jù)結(jié)構(gòu)直接以幾何空間坐標為基礎(chǔ)，記錄取樣點坐標。按照這種數(shù)據(jù)組織方式，可以得到精美的地圖。另外，該結(jié)構(gòu)還可以對復(fù)雜數(shù)據(jù)以最小的數(shù)據(jù)冗余進行存貯，它還具有數(shù)據(jù)精度高，存儲空間小等特點，是一種高效的圖形數(shù)據(jù)結(jié)構(gòu)。矢量數(shù)據(jù)結(jié)構(gòu)中，傳統(tǒng)的方法是幾何圖形及其關(guān)系用文件方式組織，而屬性數(shù)據(jù)通常采用關(guān)系型表文件記錄，兩者通過實體標識符連接。由于這一特點使得在某些方面有便利和獨到之處，例如在計算長度、面積、形狀和圖形編輯

3、、幾何變換操作中，有很高的效率和精度。矢量數(shù)據(jù)結(jié)構(gòu)按其是否明確表示地理實體間的空間關(guān)系分為實體數(shù)據(jù)結(jié)構(gòu)和拓撲數(shù)據(jù)結(jié)構(gòu)兩大類。4.1.1實體數(shù)據(jù)結(jié)構(gòu)實體數(shù)據(jù)結(jié)構(gòu)也稱spaghetti數(shù)據(jù)結(jié)構(gòu)，是指構(gòu)成多邊形邊界的各個線段，以多邊形為單元進行組織。按照這種數(shù)據(jù)結(jié)構(gòu)，邊界坐標數(shù)據(jù)和多邊形單元實體一一對應(yīng)，各個多邊形邊界點都單獨編碼并記錄坐標。例如對圖4-1所示的多邊形A、B、C、D，可以采用兩種結(jié)構(gòu)分別組織。圖4.1 原始多邊形數(shù)據(jù)表4.1 多邊形數(shù)據(jù)文件多邊形ID坐標類別碼A（x1，y1），（x2，y2），（x3，y3），（x4，y4），（x5，y5），（x6，y6），（x7，y7），（x8，y8

4、），（x1，y1）A102B（x1，y1），（x8，y8），（x7，y7），（x13，y13），（x12，y12），（x11，y11），（x10，y10），（x9，y9），（x1，y1）B203C（x20，y20），（x25，y25），（x24，y24），（x23，y23），（x22，y22），（x21，y21），（x20，y20）A178D（x5，y5），（x19，y19），（x18，y18），（x17，y17），（x16，y16），（x15，y15），（x14，y14），（x7，y7），（x6，y6），（x5，y5）C523點號坐標1x1，y12x2，y23x3，y34x4，y425x25

5、，y25表4.2 點坐標文件表4.3 多邊形文件多邊形ID點號串類別碼A1,2,3,4,5,6,7,8,1A102B7,8,1,9,10,11,12,13,7B203C20,21,22,23,24,25,20A178D7,13,15,16,17,18,19,5,6,7C523 第一種結(jié)構(gòu)采用表4.1組織，第二種結(jié)構(gòu)同時采用表4.2組織多邊形頂點坐標，在表4.3中記錄多邊形與點的關(guān)系。這種數(shù)據(jù)結(jié)構(gòu)具有編碼容易、數(shù)字化操作簡單和數(shù)據(jù)編排直觀等優(yōu)點；但這種方法有以下明顯缺點： 相鄰多邊形的公共邊界要數(shù)字化兩遍，造成數(shù)據(jù)冗余存儲，可能導(dǎo)致輸出的公共邊界出現(xiàn)間隙或重疊； 缺少多邊形的鄰域信息和圖形的拓撲

6、關(guān)系； 島只作為一個單個圖形，沒有建立與外界多邊形的聯(lián)系。因此，實體式數(shù)據(jù)結(jié)構(gòu)只適用于簡單的系統(tǒng)，如計算機地圖制圖系統(tǒng)。4.1.2拓撲數(shù)據(jù)結(jié)構(gòu)拓撲關(guān)系是一種對空間結(jié)構(gòu)關(guān)系進行明確定義的數(shù)學(xué)方法。具有拓撲關(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓撲數(shù)據(jù)結(jié)構(gòu)。拓撲數(shù)據(jù)結(jié)構(gòu)是GIS分析和應(yīng)用功能所必需的。拓撲數(shù)據(jù)結(jié)構(gòu)沒有固定的格式，還沒有形成標準，但基本原理相同的。它們的共同的特點是：點是相互獨立的，點連成線，線構(gòu)成面。每條線始于起始結(jié)點，止于終止結(jié)點，并與左右多邊形相鄰接。拓撲數(shù)據(jù)結(jié)構(gòu)最重要的特征是具有拓撲編輯功能；這種拓撲編輯功能，不但保證數(shù)字化原始數(shù)據(jù)的自動差錯編輯，而且可以自動形成封閉的多邊形邊界，為由各個單

7、獨存儲的弧段組成所需要的各類多邊形及建立空間數(shù)據(jù)庫奠定基礎(chǔ)。拓撲數(shù)據(jù)結(jié)構(gòu)包括索引式、雙重獨立編碼結(jié)構(gòu)、鏈狀雙重獨立編碼結(jié)構(gòu)等。1. 索引式結(jié)構(gòu)索引式數(shù)據(jù)結(jié)構(gòu)采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，具體方法是對所有邊界點進行數(shù)字化，將坐標對以順序方式存儲，由點索引與邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu)。圖4.2和圖4.3分別為圖4.1的多邊形文件和線文件樹狀索引圖。組織這個圖需要3個表文件，第一個記錄多邊形和邊界弧段的關(guān)系，第二個記錄邊界弧段由哪些點組成；第三個文件記錄每個頂點的坐標，具體的結(jié)構(gòu)見表4.4、表4.5和表4.6。樹狀索引結(jié)構(gòu)消除了相鄰多邊形邊界的數(shù)據(jù)冗余

8、和不一致的問題，在簡化過于復(fù)雜的邊界線或合并多邊形時可不必改造索引表，鄰域信息和島狀信息可以通過對多邊形文件的線索引處理得到（如多邊形A、B之間通過公共邊b相鄰接），但是比較繁瑣，因而給鄰域函數(shù)運算、消除無用邊、處理島狀信息以及檢查拓撲關(guān)系等帶來一定的困難，而且兩個編碼表都要以人工方式建立，工作量大且容易出錯。fedgdcbebaDCBA圖4.2 多邊形與線之間索引20212223242513141516171819567137191011121312345abcdefg187圖4.3 點與線之間的樹狀索引表4.4 點坐標文件點ID坐標1x1,y1表4.5 邊文件邊ID組成的點IDa1,2,3

9、,4,5表4.6 多邊形文件多邊形ID組成的邊IDAa,b,c2. 雙重獨立編碼結(jié)構(gòu)這種數(shù)據(jù)結(jié)構(gòu)最早是由美國人口統(tǒng)計系統(tǒng)采用的一種編碼方式，簡稱DIME（Dual Independent Map Encoding）編碼系統(tǒng)，它是以城市街道為編碼主體，它的特點是采用了拓撲編碼結(jié)構(gòu)，這種結(jié)構(gòu)最適合于城市信息系統(tǒng)。雙重獨立編碼結(jié)構(gòu)是對圖上網(wǎng)狀或面狀要素的任何一條線段，用順序的兩點定義以及相鄰多邊形來予以定義。例如對圖4.4所示的多邊形數(shù)據(jù)，利用雙重獨立編碼可得到以線段為中心的拓撲關(guān)系表，如表4.7所示。圖4.4 多邊形原始數(shù)據(jù)表4.7 雙重獨立式編碼線文件結(jié)構(gòu)線號起點終點左多邊形右多邊形a16QAb

10、21QAc32QAd43BAe54CAf65CAg67QCh78QCi89QCj94BCk910QBl103QBm1113ADn1312ADo1211AD表中第一行表示線段a的方向是從結(jié)點1到結(jié)點6，其左側(cè)面域的多邊形是Q，右側(cè)面域多邊形是A。在雙重獨立式數(shù)據(jù)結(jié)構(gòu)中，結(jié)點與結(jié)點或者多邊形與多邊形之間為鄰接關(guān)系，結(jié)點與線段或者多邊形與線段之間為關(guān)聯(lián)關(guān)系。利用這種拓撲關(guān)系可以來組織數(shù)據(jù)，可以有效地進行數(shù)據(jù)存儲正確性檢查（如多邊形是否封閉），同時便于對數(shù)據(jù)進行更新和檢索。因為通過這種數(shù)據(jù)結(jié)構(gòu)的格式繪制圖形，當多邊形的起始結(jié)點與終止結(jié)點相一致，并且按照左側(cè)面域或右側(cè)面域自動建立一個指定的區(qū)域單元時，則

11、空間點的左邊應(yīng)當自行閉合。如果不閉合，或者出現(xiàn)多余線段，則表示數(shù)據(jù)存儲或編碼有誤，這樣就可以達到數(shù)據(jù)自動編輯的目的。同樣利用該結(jié)構(gòu)可以自動形成多邊形，并可以檢查線文件數(shù)據(jù)的正確性。除線段拓撲關(guān)系文件外，雙重獨立編碼結(jié)構(gòu)還需要點文件和面文件，其結(jié)構(gòu)同表4.4和表4.5。DIME編碼結(jié)構(gòu)尤其適用于城市地籍宗地的管理，在宗地管理中，界址點對應(yīng)于點、界址邊對應(yīng)于線段，面對應(yīng)于多邊形，各種要素都有惟一的標識符。3. 鏈狀雙重獨立編碼結(jié)構(gòu)鏈狀雙重獨立式數(shù)據(jù)結(jié)構(gòu)是DIME數(shù)據(jù)結(jié)構(gòu)的一種改進。在DIME中，一條邊只能用直線兩端點的序號及相鄰的多邊形來表示，而在鏈狀數(shù)據(jù)結(jié)構(gòu)中，將若干直線段合為一個弧段（或鏈段）

12、，每個弧段可以有許多中間點。在鏈狀雙重獨立數(shù)據(jù)結(jié)構(gòu)中，主要有四個文件：多邊形文件、弧段文件、弧段點文件、點坐標文件。多邊形文件主要由多邊形記錄組成，包括多邊形號、組成多邊形的弧段號以及周長、面積、中心點坐標及有關(guān)“洞”的信息等，多邊形文件也可以通過軟件自動檢索各有關(guān)弧段生成，并同時計算出多邊形的周長和面積以及中心點的坐標，當多邊形中含有“洞”時則此“洞”的面積為負，并在總面積中減去，其組成的弧段號前也冠以負號；弧段文件主要有弧記錄組成，存儲弧段的起止結(jié)點號和弧段左右多邊形號；弧段坐標文件由一系列點的位置坐標組成，一般從數(shù)字化過程獲取，數(shù)字化的順序確定了這條鏈段的方向。結(jié)點文件由結(jié)點記錄組成，存

13、儲每個結(jié)點的結(jié)點號、結(jié)點坐標及與該結(jié)點連接的弧段。結(jié)點文件一般通過軟件自動生成，因為在數(shù)字化的過程中，由于數(shù)字化操作的誤差，各弧段在同一結(jié)點處的坐標不可能完全一致，需要進行匹配處理。當其偏差在允許范圍內(nèi)時，可取同名結(jié)點的坐標平均值。如果偏差過大，則弧段需要重新數(shù)字化。對圖4.1所示的矢量數(shù)據(jù)，其鏈狀雙重獨立式數(shù)據(jù)結(jié)構(gòu)需要多邊形文件、弧段文件、弧點文件、點坐標文件，見表4.8、表4.9、表4.10和表4.11。表4.8 多邊形文件多邊形ID弧段號屬性（如周長、面積等）Aa,b,eBc,d,bCgDf,e,d,-g表4.9 弧段文件弧段ID起始點終結(jié)點左多邊形右多邊形a51QAb71ABc113Q

14、Bd137DBe75DAf135QDg2525DC表4.10 弧段點文件弧段ID點號弧段ID點號a5,4,3,2,1e7,6,5b7,8,1f13,14,15,16,17,18,19,5c1,9,10,11,12,13g25,20,21,22,23,24,25d13,7表4.11 點坐標文件點號坐標點號坐標1（x1，y1）14（x14，y14）2（x2，y2）15（x15，y15）12（x12，y12）25（x25，y25）13（x13，y13）國際著名GIS軟件平臺開發(fā)商美國ESRI公司的ARCGIS產(chǎn)品中的COVERAGE數(shù)據(jù)模型就是采用鏈狀雙重獨立編碼數(shù)據(jù)結(jié)構(gòu)的。4.2 柵格數(shù)據(jù)結(jié)構(gòu)以規(guī)

15、則柵格陣列表示空間對象的數(shù)據(jù)結(jié)構(gòu)稱為柵格數(shù)據(jù)結(jié)構(gòu)。陣列中每個柵格單元上的數(shù)值表示空間對象的屬性特征。即柵格陣列中每個單元的行列號確定位置，屬性值表示空間對象的類型、等級等特征。每個柵格單元只能存在一個值。點線面圖4.5 實體在柵格數(shù)據(jù)結(jié)構(gòu)中的表示柵格數(shù)據(jù)結(jié)構(gòu)表示的地表是不連續(xù)的，是量化和近似離散的數(shù)據(jù)。在柵格數(shù)據(jù)結(jié)構(gòu)中，地理空間被分成相互鄰接、規(guī)則排列的柵格單元，一個柵格單元對應(yīng)于小塊地理范圍。在柵格數(shù)據(jù)結(jié)構(gòu)中，點用一個柵格單元表示；線狀地物則用沿線走向的一組相鄰柵格單元表示，每個柵格單元最多只有兩個相鄰單元在線上；面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募媳硎?，每個柵格單元可有多于兩個的相鄰

16、單元同屬一個區(qū)域，如圖4.5所示。柵格數(shù)據(jù)結(jié)構(gòu)的顯著特點是：屬性明顯，定位隱含，即數(shù)據(jù)直接記錄屬性的指針或?qū)傩员旧?，而所在位置則根據(jù)行列號轉(zhuǎn)換為相應(yīng)的坐標給出，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。同時具有數(shù)據(jù)結(jié)構(gòu)簡單、數(shù)學(xué)模擬方便的優(yōu)點；但也存在著缺點：數(shù)據(jù)量大、難以建立實體間的拓撲關(guān)系、通過改變分辨率而減少數(shù)據(jù)量時精度和信息量同時受損等。4.2.1柵格單元的確定1. 柵格數(shù)據(jù)的參數(shù)一個完整的柵格數(shù)據(jù)通常由以下幾個參數(shù)決定：（1）柵格形狀。柵格單元通常為矩形或正方形。特殊的情況下也可以按經(jīng)緯網(wǎng)劃分柵格單元。列行西南角格網(wǎng)坐標（XWS，YWS）格網(wǎng)分辨率格網(wǎng)方向圖4.6 柵格數(shù)據(jù)的坐標

17、系及描述參數(shù)柵格形狀BACO圖4.7 柵格單元屬性值的選取（2）柵格單元大小。也就是柵格單元的尺寸，即分辨率。柵格單元的合理尺寸應(yīng)能有效地逼近空間對象的分布特征，以保證空間數(shù)據(jù)的精度。但是用柵格來逼近空間實體，不論采用多細小的柵格，與原實體比都會有誤差。通常以保證最小圖斑不丟失為原則來確定合理的柵格尺寸。設(shè)研究區(qū)域某要素的最小圖斑面積為S，柵格單元的邊長L用如下公式計算： （4.1）就可以保證最小的圖斑能夠得到反映。（3）柵格原點。柵格系統(tǒng)的起始坐標應(yīng)將和國家基本比例尺地形圖公里網(wǎng)的交點相一致，或者和已有的柵格系統(tǒng)數(shù)據(jù)相一致。并同時使用公里網(wǎng)的縱橫坐標軸作為柵格系統(tǒng)的坐標軸。這樣在使用柵格數(shù)據(jù)

18、時，就容易和矢量數(shù)據(jù)或已有的柵格數(shù)據(jù)相配準。（4）柵格的傾角。通常情況下，柵格的坐標系統(tǒng)與國家坐標系統(tǒng)平行。但有時候，根據(jù)應(yīng)用的需要，可以將柵格系統(tǒng)傾斜某一個角度，以方便應(yīng)用。圖4.6 給出了柵格數(shù)據(jù)結(jié)構(gòu)中柵格數(shù)據(jù)的描述參數(shù)示意圖。2. 柵格單元值的選取柵格單元取值是惟一的，但由于受到柵格大小的限制，柵格單元中可能會出現(xiàn)多個地物，那么在決定柵格單元值時應(yīng)盡量保持其真實性，對于圖4.7所示的柵格單元，要確定該單元的屬性取值，可根據(jù)需要選用如下方法。（1）中心點法。用位于柵格中心處的地物類型決定其取值。由于中心點位于代碼為C的地物范圍內(nèi)，故其取值為C。這種方法常用于有連續(xù)分布特性的地理現(xiàn)象。（2）

19、面積占優(yōu)法。以占矩形區(qū)域面積最大的地物類型作為柵格單元的代碼。從圖上看，B類地物所占面積最大，故相應(yīng)柵格單元代碼為B。（3）重要性法。根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型作為相應(yīng)的柵格單元代碼。設(shè)圖中A類地物為最重要的地物類型，則柵格代碼為A。這種方法常用于有特殊意義而面積較小的地理要素，特別是點狀和線狀地理要素。如城鎮(zhèn)、交通線、水系等。在柵格代碼中應(yīng)盡量表示這些重要地物。（4）百分比法。根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的取值，如可記面積最大的兩類BA，也可根據(jù)B類和A類所占面積百分比數(shù)在代碼中加入數(shù)字。由于采用的取值方法不同，得到的結(jié)果也不盡相同。逼近原始精

20、度的第二種方法是縮小單個柵格單元的面積，即增加?xùn)鸥駟卧目倲?shù)，行列數(shù)也相應(yīng)地增加。這樣，每個柵格單元可代表更為精細的地面矩形單元，混合單元減少?；旌项悇e和混合的面積都大大減小，可以大大提高量算的精度；接近真實的形態(tài)，表現(xiàn)更細小的地物類型。然而增加?xùn)鸥駛€數(shù)、提高數(shù)據(jù)精度的同時也帶來了一個嚴重的問題，那就是數(shù)據(jù)量的大幅度增加，數(shù)據(jù)冗余嚴重。4.2.2完全柵格數(shù)據(jù)結(jié)構(gòu)完全柵格數(shù)據(jù)結(jié)構(gòu)（也稱編碼）將柵格看作一個數(shù)據(jù)矩陣，逐行逐個記錄柵格單元的值?？梢悦啃卸紡淖蟮接遥部善鏀?shù)行從左到右而偶數(shù)行從右到左，或者采用其他特殊的方法。這是最簡單最直接的一種柵格編碼方法。通常這種編碼為柵格文件或格網(wǎng)文件。它不采用

21、任何壓縮數(shù)據(jù)的處理，因此是最直觀最基本的柵格數(shù)據(jù)組織方式。完全柵格數(shù)據(jù)的組織有三種基本方式：基于象元、基于層和基于面域，如圖4.8所示。（1）基于像元。以像元為獨立存儲單元，每一個象元對應(yīng)一條記錄，每條記錄中的記錄內(nèi)容包括象元坐標及其各層屬性值的編碼；節(jié)省了許多存儲坐標的空間，因為各層對應(yīng)象元的坐標只需存儲一次。數(shù)據(jù)文件像元1x坐標y坐標層1屬性值層2屬性值層N屬性值像元2像元N數(shù)據(jù)文件層1層2層N像元1像元2像元Nx坐標y坐標屬性值數(shù)據(jù)文件層1層2層N多邊形1多邊形2多邊形N屬性值像元1坐標像元2坐標像元N坐標（c） 基于面域方式圖4.8 柵格數(shù)據(jù)組織方式（b） 基于層方式（a）基于象元方式

22、（2）基于層。以層為存儲基礎(chǔ)，層中又以象元為序記錄其坐標和對應(yīng)該層的屬性值編碼。（3）基于面域。也以層作為存儲基礎(chǔ)，層中再以面域為單元進行記錄，記錄的內(nèi)容包括：面域編號、面域?qū)?yīng)該層的屬性值編碼、面域中所有柵格單元的坐標；同一屬性的多個相鄰象元只需記錄一次屬性值?；谙笤臄?shù)據(jù)組織方式簡單明了，便于數(shù)據(jù)擴充和修改，但進行屬性查詢和面域邊界提取時速度較慢；基于層的數(shù)據(jù)組織方式便于進行屬性查詢，但每個象元的坐標均要重復(fù)存儲，浪費了存儲空間；基于面域的數(shù)據(jù)組織方式雖然便于面域邊界提取，但在不同層中象元的坐標還是要多次存儲。4.2.4壓縮柵格數(shù)據(jù)結(jié)構(gòu)1. 游程長度編碼結(jié)構(gòu)游程長度（run-length

23、）編碼，也稱行程編碼，不僅是一種柵格數(shù)據(jù)無損壓縮的重要方法，也是一種柵格數(shù)據(jù)結(jié)構(gòu)。它的基本思想是：對于一幅柵格數(shù)據(jù)（或影像），常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。其編碼方案是，只在各行（或列）數(shù)據(jù)值發(fā)生變化時依次記錄該值以及相同值重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮，并實現(xiàn)數(shù)據(jù)的組織。經(jīng)編碼后，原始柵格數(shù)據(jù)陣列轉(zhuǎn)換為（si，li）數(shù)據(jù)對，其中si為屬性值，li為行程。圖4.9給出了柵格數(shù)據(jù)沿行方向進行游程長度編碼的結(jié)果。0000044400044444004444880044488822448888222488882222888822228

24、888(0,5),(4,3)(0,3),(4,5)(0,2),(4,4),(8,2)(0,2),(4,3),(8,3)(2,2),(4,2),(8,4)(2,3),(8,1),(8,4)(2,4),(8,4)(2,4),(8,4)圖4.9 柵格數(shù)據(jù)的游程長度編碼及其數(shù)據(jù)結(jié)構(gòu)顯然游程長度編碼只用了40個整數(shù)就可以表示，而如果用前述的直接編碼卻需要64個整數(shù)表示，可見游程長度編碼壓縮數(shù)據(jù)是十分有效又簡便的。事實上，壓縮比的大小是與圖的復(fù)雜程度成反比的，在變化多的部分，游程數(shù)就多，變化少的部分游程數(shù)就少，原始柵格類型越簡單，壓縮效率就越高。因此這種數(shù)據(jù)結(jié)構(gòu)最適宜于類型面積較大的專題要素、遙感圖像的分

25、類結(jié)構(gòu)，而不適合于類型連續(xù)變化或類型分散的分類圖。游程長度編碼在柵格加密時，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運算簡單，適用于機器存貯容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運算增加處理和操作時間的情況。 2. 四叉樹數(shù)據(jù)結(jié)構(gòu)四叉樹（quadtree）數(shù)據(jù)結(jié)構(gòu)也是一種對柵格數(shù)據(jù)的壓縮編碼方法。其基本思想是將一幅柵格數(shù)據(jù)層或圖像等分為四部分，逐塊檢查其格網(wǎng)屬性值（或灰度）；如果某個子區(qū)的所有格網(wǎng)值都具有相同的值，則這個子區(qū)就不再繼續(xù)分割，否則還要把這個子區(qū)再分割成四個子區(qū)；這樣依次地分割，直到每個子塊都只含有相同的屬性值或灰度為止。圖4.10表示了對柵格數(shù)據(jù)四

26、叉樹的分割過程及其關(guān)系。這四個等分區(qū)稱為四個子象限，按順序為左上（NW）、右上（NE）、左下（SW），右下（SE），其結(jié)果是一棵倒立的樹。生成四叉樹0102440022002200葉結(jié)點圖4.10 柵格數(shù)據(jù)的四叉樹分割0011444400114444002244440022444422224444000044440000444400004444這種從上而下的分割需要大量的運算，因為大量數(shù)據(jù)需要重復(fù)檢查才能確定劃分。當nn的柵格單元數(shù)比較大，且區(qū)域內(nèi)容要素又比較復(fù)雜時，建立這種四叉樹的速度比較慢。另一種是采用從下而上的方法建立。對柵格數(shù)據(jù)按如下的順序進行檢測。如果每相鄰四個網(wǎng)格值相同則進行合并，

27、逐次往上遞歸合并，直到符合四叉樹的原則為止。這種方法重復(fù)計算較少，運算速度較快。從圖4.10中可以看出，為了保證四叉樹能不斷的分解下去，要求柵格數(shù)據(jù)的柵格單元數(shù)必須滿足2n2n，n為極限分割次數(shù)，n+1是四叉樹的最大高度或最大層數(shù)。對于非標準尺寸的圖像需首先通過增加背景的方法將柵格數(shù)據(jù)擴充為2n2n個單元，對不足的部分以0補足（在建樹時，對于補足部分生成的葉結(jié)點不存儲，這樣存儲量并不會增加。四叉樹結(jié)構(gòu)按其編碼的方法不同又分為常規(guī)四叉樹和線性四叉樹。常規(guī)四叉樹除了記錄葉結(jié)點之外，還要記錄中間結(jié)點。結(jié)點之間借助指針聯(lián)系，每個結(jié)點需要用六個量表達：四個葉結(jié)點指針，一個父結(jié)點指針和一個結(jié)點的屬性或灰度

28、值。這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復(fù)雜性。常規(guī)四叉樹主要在數(shù)據(jù)索引和圖幅索引等方面應(yīng)用。線性四叉樹則只存貯最后葉結(jié)點的信息，包括葉結(jié)點的位置、深度和本結(jié)點的屬性或灰度值。所謂深度是指處于四叉樹的第幾層上，由深度可推知子區(qū)的大小。線性四叉樹葉結(jié)點的編號需要遵循一定的規(guī)則，這種編號稱為地址碼，它隱含了葉結(jié)點的位置和深度信息。最便于應(yīng)用的地址碼是十進制Morton碼（簡稱MD碼）。十進制mortan碼可以使用柵格單元的行列號計算（遵循C語言規(guī)范，矩陣的第一行為“0”行、第一列為“0”列），先將十進制的行列號轉(zhuǎn)換成二進制數(shù)，進行“位”運算操作，如圖4.11 所示，即行號和列號的二進制數(shù)

29、兩兩交叉，得到以二進制數(shù)表示的MD碼，再將其轉(zhuǎn)換為十進制數(shù)。圖4.11 MD碼的“位”運算生成In In-1 In-2 . I3 I2 I1Jn Jn-1 Jn-2 . J3 J2 J1In Jn In-1 Jn-1 In-2 Jn-2 . I3 J3 I2 J2 I1 J1MD=行號I=列號 J=例如下圖第二行和第三列對應(yīng)的柵格單元，其二進制的行列號分別為：I=0010，J=0011 ；得到的MD碼為：MD=(00001101)2=(13)10 ；用類似的方法，也可以由MD碼反求柵格單元的行列號。對于88柵格單元，MD碼的排列順序如圖4.12 所示。 01234567800145161720

30、21641236718192223662891213242528297231011141526273031744323336374849525396534353839505154559864041444556576061104742434647585962631068128129132133144145148149192YX圖4.12 柵格單元的MD碼順序行方向列方向按以上MD順序，對圖4.10所示的柵格數(shù)據(jù)按線性四叉樹進行編碼，可得到線性四叉樹數(shù)據(jù)文件，其結(jié)構(gòu)如圖4.13所示。0140222224000000MD碼屬性值004180122164322332340350362372380390

31、400440484圖4.13 按MD碼建立的線性四叉樹結(jié)構(gòu)3. 二維行程編碼結(jié)構(gòu)在生成線性四叉樹之后，仍然存在前后葉結(jié)點的值相同的情況，因而可以進一步壓縮數(shù)據(jù)，將前后值相同的葉結(jié)點合并，形成一個新的線性表列。如圖4. 14（a）所示的線性四叉樹的線性表，是按Morton碼的大小順序排列的，可以看出，在這個表中還有屬性值相同而又相鄰排列的情況，將值相同的葉結(jié)點合并后的編碼表見圖4. 14（b）。這種記錄方式類似游程編碼，但是所合并的不是柵格單元，而是合并了代表范圍大小不一的葉結(jié)點，所以稱它為二維行程編碼。比較兩個表可以看出，二維行程編碼又進一步壓縮了數(shù)據(jù)。MD碼屬性值00418012216432

32、2332340350362372380390400440484二維行程碼屬性值004180122164322340362380484（a）（b）圖4.14 二維行程編碼結(jié)構(gòu)及其生成二維行程編碼采用了線性四叉樹的地址碼（Morton碼），并按照碼的順序完成編碼，但卻是沒有結(jié)構(gòu)規(guī)律的四叉樹。二維行程編碼比規(guī)則的四叉樹更節(jié)省存貯空間，而且有利于以后的插入、刪除和修改等操作。它與線性四叉樹之間的相互轉(zhuǎn)換也非常容易和快速，因此可將它們視為相同的結(jié)構(gòu)概念。4.2.4鏈碼結(jié)構(gòu)32140567圖4.15 Freeman方向碼 起始點起始點65656774556701222圖4.16 線、面的鏈式編碼鏈碼數(shù)據(jù)結(jié)

33、構(gòu)首先采用弗里曼（Freeman）碼對柵格中的線或多邊形邊界進行編碼，然后再組織為鏈碼結(jié)構(gòu)的文件。鏈式編碼將線狀地物或區(qū)域邊界表示為：由某一起始點和在某些基本方向上的單位矢量鏈組成。單位矢量的長度為一個柵格單元，每個后續(xù)點可能位于其前繼點的8個基本方向之一（如圖4.15）。圖4.16所示的線實體和面實體可編碼為表4.12所示的方式。具體編碼過程是：起始點的尋找一般遵從從上到下、從左到右的原則。當發(fā)現(xiàn)沒有記錄過的點，而且數(shù)值也不為零時，就是一條線或邊界線的起點。記下該地物的特征碼及起點的行列數(shù)；然后按順時針方向?qū)ほE，找到相鄰的等值點，并按八個方向編碼。如遇不能閉合的線段，結(jié)束后可以返回到起始點再

34、開始尋找下一個線段。已經(jīng)記錄過的柵格單元，可將屬性代碼置零，以免重復(fù)編碼。表4.12 鏈碼結(jié)構(gòu)文件特征碼起點行起點列鏈碼2146,5,6,5,6,7,77284,5,5,6,7,0,1,2,2,2鏈碼結(jié)構(gòu)可以有效地壓縮柵格數(shù)據(jù)，特別是對計算面積、長度、轉(zhuǎn)折方向和凹凸度等運算十分方便。缺點是對邊界做合并和插入等修改，編輯比較困難。這種結(jié)構(gòu)有些類似矢量結(jié)構(gòu)，但不具有區(qū)域的性質(zhì)，因此對區(qū)域空間分析運算比較困難。圖4.17 金字塔數(shù)據(jù)結(jié)構(gòu)X0X1X2Xn4.2.5影像金字塔結(jié)構(gòu)影像金字塔是指在統(tǒng)一的空間參照下，根據(jù)用戶需要以不同分辨率進行存儲與顯示，形成分辨率由粗到細、數(shù)據(jù)量由小到大的金字塔結(jié)構(gòu)。影像

35、金字塔結(jié)構(gòu)用于圖像編碼和漸進式圖像傳輸，是一種典型的分層數(shù)據(jù)結(jié)構(gòu)形式，適合于柵格數(shù)據(jù)和影像數(shù)據(jù)的多分辨率組織，也是一種柵格數(shù)據(jù)或影像數(shù)據(jù)的有損壓縮方式。在金字塔結(jié)構(gòu)里，圖像被分層表示。在金字塔結(jié)構(gòu)的最頂層，存儲最低分辨率的數(shù)據(jù)；隨著金字塔層數(shù)的增加，數(shù)據(jù)的分辨率依次降低；在金字塔結(jié)構(gòu)的底層，則存儲能滿足用戶需要的最高分辨率的數(shù)據(jù)。每一層相當于降低分辨率的圖像估計。影像金字塔有多種結(jié)構(gòu)，其中最簡單的是M-金字塔結(jié)構(gòu),如圖4.17所示。4.3 矢柵一體化數(shù)據(jù)結(jié)構(gòu)4.3.1 柵格結(jié)構(gòu)與矢量數(shù)據(jù)結(jié)構(gòu)的比較柵格數(shù)據(jù)結(jié)構(gòu)類型具有“屬性明顯、位置隱含”的特點，它易于實現(xiàn)，且操作簡單，有利于基于柵格的空間信息

36、模型的分析，如在給定區(qū)域內(nèi)計算多邊形面積、線密度，柵格結(jié)構(gòu)可以很快算得結(jié)果，而采用矢量數(shù)據(jù)結(jié)構(gòu)則麻煩的多；但柵格數(shù)據(jù)表達精度不高，數(shù)據(jù)存儲量大，工作效率較低。如要提高一倍的表達精度（柵格單元減小一半），數(shù)據(jù)量就需增加三倍，同時也增加了數(shù)據(jù)的冗余。因此，對于基于柵格數(shù)據(jù)結(jié)構(gòu)的應(yīng)用來說，需要根據(jù)應(yīng)用項目的自身特點及其精度要求來恰當?shù)仄胶鈻鸥駭?shù)據(jù)的表達精度和工作效率兩者之間的關(guān)系。另外，因為柵格數(shù)據(jù)結(jié)構(gòu)的簡單性（不經(jīng)過壓縮編碼），其數(shù)據(jù)格式容易為大多數(shù)程序設(shè)計人員和用戶所理解，基于柵格數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之上的信息共享也較矢量數(shù)據(jù)容易。最后，遙感影像本身就是以象元為單位的柵格結(jié)構(gòu)，所以，可以直接把遙感影像應(yīng)

37、用于柵格結(jié)構(gòu)的地理信息系統(tǒng)中，也就是說柵格數(shù)據(jù)結(jié)構(gòu)比較容易和遙感相結(jié)合。矢量數(shù)據(jù)結(jié)構(gòu)類型具有“位置明顯、屬性隱含”的特點，它操作起來比較復(fù)雜，許多分析操作（如疊置分析等）用矢量數(shù)據(jù)結(jié)構(gòu)難于實現(xiàn)；但它的數(shù)據(jù)表達精度較高，數(shù)據(jù)存儲量小，輸出圖形美觀且工作效率較高。兩者的比較如表4.13所示。表4.13 柵格、矢量數(shù)據(jù)結(jié)構(gòu)的對比優(yōu)點缺點矢量數(shù)據(jù)結(jié)構(gòu)1. 數(shù)據(jù)結(jié)構(gòu)嚴密，冗余度小，數(shù)據(jù)量??；2. 空間拓撲關(guān)系清晰，易于網(wǎng)絡(luò)分析；3. 面向?qū)ο竽繕说模粌H能表達屬性編碼，而 且能方便地記錄每個目標的具體的屬性描述 信息；4. 能夠?qū)崿F(xiàn)圖形數(shù)據(jù)的恢復(fù)、更新和綜合；圖形顯示質(zhì)量好、精度高。1. 數(shù)據(jù)結(jié)構(gòu)處理算

38、法復(fù)雜2. 疊置分析與柵格圖組合比較難；3. 數(shù)學(xué)模擬比較困難；4. 空間分析技術(shù)上比較復(fù)雜，需要更復(fù)雜的軟、硬件條件；5. 顯示與繪圖成本比較高。柵格數(shù)據(jù)結(jié)構(gòu)1. 數(shù)據(jù)結(jié)構(gòu)簡單，易于算法實現(xiàn)；2. 空間數(shù)據(jù)的疊置和組合容易，有利于與遙感數(shù)據(jù)的匹配應(yīng)用和分析；3. 各類空間分析，地理現(xiàn)象模擬均較為容易；4. 輸出方法快速建議，成本低廉。5. 圖形數(shù)據(jù)量大，用大像元減小數(shù)據(jù)量時，精度和信息量受損失；6. 難以建立空間網(wǎng)絡(luò)連接關(guān)系；7. 投影變化實現(xiàn)困難；8. 圖形數(shù)據(jù)質(zhì)量低，地圖輸出不精美。目前，大多數(shù)地理信息系統(tǒng)平臺都支持這兩種數(shù)據(jù)結(jié)構(gòu)，而在應(yīng)用過程中，應(yīng)該根據(jù)具體的目的，選用不同的數(shù)據(jù)結(jié)構(gòu)。

39、例如，在集成遙感數(shù)據(jù)以及進行空間模擬運算（如污染擴散）等應(yīng)用中，一般采用柵格數(shù)據(jù)為主要數(shù)據(jù)結(jié)構(gòu)；而在網(wǎng)絡(luò)分析、規(guī)劃選址等應(yīng)用中，通常采用矢量數(shù)據(jù)結(jié)構(gòu)。4.3.2 矢柵一體化數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)矢量和柵格數(shù)據(jù)結(jié)構(gòu)各有優(yōu)缺點，如何充分利用兩者的優(yōu)點，在同一個系統(tǒng)中將兩者結(jié)合起來，是GIS中的一個重要理論與技術(shù)問題。為將矢量與柵格數(shù)據(jù)更加有效地結(jié)合與處理，龔建雅（1993）研究提出了矢柵一體化結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)中，同時具有矢量實體的概念，又具有柵格覆蓋的思想。其理論基礎(chǔ)是：多級格網(wǎng)方法、三個基本約定和線性四叉樹編碼。圖4.18 一體化數(shù)據(jù)結(jié)構(gòu)細分格網(wǎng)多級格網(wǎng)的方法是將柵格劃分成多級格網(wǎng)：粗格網(wǎng)、基本格網(wǎng)

40、和細分格網(wǎng)（圖4.18）。粗格網(wǎng)用于建立空間索引，基本格網(wǎng)的大小與通常柵格劃分的原則基本一致，即基本柵格的大小。由于基本柵格的分辨率較低，難以滿足精度要求，所以在基本格網(wǎng)的基礎(chǔ)上又細分為256256或1616個格網(wǎng)，以增加?xùn)鸥竦目臻g分辨率，從而提高點、線的表達精度。粗格網(wǎng)、基本格網(wǎng)和細分格網(wǎng)都采用線性四叉樹編碼的方法，用三個Morton碼（M0、M1、M2）表示，其中M0表示點或線所通過的粗格網(wǎng)的Morton碼，是研究區(qū)的整體編碼；M1表示點或線所通過的基本格網(wǎng)的Morton碼，也是研究區(qū)的整體編碼；M2表示點或線所通過的細分格網(wǎng)的Morton碼，是基本柵格內(nèi)的局部編碼。以上編碼是基于柵格的，

41、因而據(jù)此設(shè)計的數(shù)據(jù)結(jié)構(gòu)必定具有柵格的性質(zhì)。為了使之具有矢量的特點，對點狀地物、線狀地物、和面狀地物的作三個約定：（1）點狀地物僅有空間位置而無形狀和面積，在計算機中僅有一個坐標數(shù)據(jù)；（2）線狀地物有形狀但無面積，在計算機中需要組織一組元子（即柵格單元）填滿的路徑表達；（3）面狀地物有形狀和面積，在計算機中有一組元子表達的填滿路徑的邊界線和內(nèi)部（空洞外均填滿）的區(qū)域組成。據(jù)此，點狀地物、線狀地物、面狀地物的數(shù)據(jù)組織方式如下：點狀地物：用（M1，M2）代替矢量數(shù)據(jù)結(jié)構(gòu)中的（x，y）；點標識號M1M2屬性值線狀地物：用Morton碼代替（x，y）記錄原始采樣的中間點的位置；必要時，還可記錄線目標所穿

42、過的基本網(wǎng)格的交線位置：弧ID起點ID終點ID左域ID右域ID中間點坐標（M1，M2）序列面狀地物：除用Morton碼代替（x，y）記錄面狀地物邊界原始采樣的中間點位置，以及它們所穿過的所有基本網(wǎng)格的交線位置之外，還要用鏈指針記錄多邊形的內(nèi)部柵格。必要時，還可以記錄邊界所穿過的所有基本網(wǎng)格的交線位置：面域ID邊界ID序列面域內(nèi)點指針面域內(nèi)點指針面域內(nèi)點坐標（M1，M2）序列因此，點狀地物、線狀地物和面狀地物不僅具有如同矢量數(shù)據(jù)結(jié)構(gòu)的位置“坐標”，而且還可以有類型編碼、屬性值和拓撲關(guān)系，因而具有完全的矢量特性。與此同時，由于用柵格元子表達了點、填充了線性目標、多邊形邊界及其內(nèi)部（空洞除外），實際

43、是進行了柵格化，因而可以進行各種柵格操作。 4.4 鑲嵌數(shù)據(jù)結(jié)構(gòu)針對以正方形和矩形單元進行地理空間劃分的規(guī)則鑲嵌數(shù)據(jù)模型，完全可以采用柵格數(shù)據(jù)結(jié)構(gòu)進行數(shù)據(jù)的組織。本節(jié)重點討論以Voronoi多邊形和TIN三角網(wǎng)進行空間劃分的不規(guī)則鑲嵌數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)。4.4.1 Voronoi數(shù)據(jù)結(jié)構(gòu)以Voronoi 面塊單元來組織Voronoi多邊形數(shù)據(jù)。如圖4.19 所示，節(jié)點p1p8 將平面凸多邊形ABCDE區(qū)域劃分為8個Voronoi 單元，定義相鄰Voronoi 單元之間的垂直平分線的交點為頂點，且各頂點分別賦予頂點ID號。對于每個樣點及其Voronoi 單元，其數(shù)據(jù)結(jié)構(gòu)包括一組文件，在這些文件中

44、分別記錄：（1） 樣點序號（與Voronoi 單元的ID號相同）、樣點的坐標及其屬性；（2） 各樣點所對應(yīng)的相鄰樣點的序號；（3） 生成的Voronoi 單元的頂點坐標；（4） Voronoi單元的頂點組成。則其數(shù)據(jù)結(jié)構(gòu)如表4.14 表4.15 所示。在記錄相鄰Vorinoi單元序號時, 統(tǒng)一采用逆時針方向。當某樣點的Voronoi 單元的邊界就是地理區(qū)域的邊界時，將Vorinoi邊與地理區(qū)域邊界的交點也作為頂點，但使用特殊標識符予以區(qū)分。這種數(shù)據(jù)結(jié)構(gòu)對Voronoi多邊形的生成過程以及基于Voronoi的空間分析將起到重要的作用。表4.15 Voronoi單元鄰接關(guān)系表Voronoi單元ID

45、相鄰Voronoi單元號12，3，4，5，6，7，821，8，331，2，441，3，551，4，661，5，771，6，881，7，2表4.16 Voronoi頂點信息表Voronoi頂點IDVoronoi頂點坐標Voronoi頂點標識v1x1,y1v2x2,y2v3x3,y3v4x4,y4x5,y5AxA,yA邊界點BxB,yB邊界點X8,y8圖4.19 Voronoi多邊形樣點ID樣點坐標樣點屬性值1x1,y1A12x2,y2A23x3,y3A34x4,y4A45x5,y5A56x6,y6A67x7,y7A78X8,y8A8表4.14 樣點數(shù)據(jù)AEDB54136278C4.4.2 TIN數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)上，TIN可以采用類似于多邊形的矢量拓撲結(jié)構(gòu)，但不必要描述一般多邊形中的“島嶼”或“洞”的拓撲關(guān)系?？梢圆捎枚喾N方式來組織TIN數(shù)據(jù)模型，對圖4.20所示的TIN三角網(wǎng)，可以三角形作為基本的空間對象進行數(shù)據(jù)組織，見圖4.21。數(shù)據(jù)組織需要兩個