GIS教案：第4章空間數(shù)據(jù)結構

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

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

3、、幾何變換操作中，有很高的效率和精度。矢量數(shù)據(jù)結構按其是否明確表示地理實體間的空間關系分為實體數(shù)據(jù)結構和拓撲數(shù)據(jù)結構兩大類。4.1.1實體數(shù)據(jù)結構實體數(shù)據(jù)結構也稱spaghetti數(shù)據(jù)結構，是指構成多邊形邊界的各個線段，以多邊形為單元進行組織。按照這種數(shù)據(jù)結構，邊界坐標數(shù)據(jù)和多邊形單元實體一一對應，各個多邊形邊界點都單獨編碼并記錄坐標。例如對圖4-1所示的多邊形A、B、C、D，可以采用兩種結構分別組織。圖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 第一種結構采用表4.1組織，第二種結構同時采用表4.2組織多邊形頂點坐標，在表4.3中記錄多邊形與點的關系。這種數(shù)據(jù)結構具有編碼容易、數(shù)字化操作簡單和數(shù)據(jù)編排直觀等優(yōu)點；但這種方法有以下明顯缺點： 相鄰多邊形的公共邊界要數(shù)字化兩遍，造成數(shù)據(jù)冗余存儲，可能導致輸出的公共邊界出現(xiàn)間隙或重疊； 缺少多邊形的鄰域信息和圖形的拓撲

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

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

8、和不一致的問題，在簡化過于復雜的邊界線或合并多邊形時可不必改造索引表，鄰域信息和島狀信息可以通過對多邊形文件的線索引處理得到（如多邊形A、B之間通過公共邊b相鄰接），但是比較繁瑣，因而給鄰域函數(shù)運算、消除無用邊、處理島狀信息以及檢查拓撲關系等帶來一定的困難，而且兩個編碼表都要以人工方式建立，工作量大且容易出錯。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. 雙重獨立編碼結構這種數(shù)據(jù)結構最早是由美國人口統(tǒng)計系統(tǒng)采用的一種編碼方式，簡稱DIME（Dual Independent Map Encoding）編碼系統(tǒng)，它是以城市街道為編碼主體，它的特點是采用了拓撲編碼結構，這種結構最適合于城市信息系統(tǒng)。雙重獨立編碼結構是對圖上網(wǎng)狀或面狀要素的任何一條線段，用順序的兩點定義以及相鄰多邊形來予以定義。例如對圖4.4所示的多邊形數(shù)據(jù)，利用雙重獨立編碼可得到以線段為中心的拓撲關系表，如表4.7所示。圖4.4 多邊形原始數(shù)據(jù)表4.7 雙重獨立式編碼線文件結構線號起點終點左多邊形右多邊形a16QAb

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

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

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

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

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

16、單元同屬一個區(qū)域，如圖4.5所示。柵格數(shù)據(jù)結構的顯著特點是：屬性明顯，定位隱含，即數(shù)據(jù)直接記錄屬性的指針或屬性本身，而所在位置則根據(jù)行列號轉換為相應的坐標給出，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。同時具有數(shù)據(jù)結構簡單、數(shù)學模擬方便的優(yōu)點；但也存在著缺點：數(shù)據(jù)量大、難以建立實體間的拓撲關系、通過改變分辨率而減少數(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 柵格單元屬性值的選?。?）柵格單元大小。也就是柵格單元的尺寸，即分辨率。柵格單元的合理尺寸應能有效地逼近空間對象的分布特征，以保證空間數(shù)據(jù)的精度。但是用柵格來逼近空間實體，不論采用多細小的柵格，與原實體比都會有誤差。通常以保證最小圖斑不丟失為原則來確定合理的柵格尺寸。設研究區(qū)域某要素的最小圖斑面積為S，柵格單元的邊長L用如下公式計算： （4.1）就可以保證最小的圖斑能夠得到反映。（3）柵格原點。柵格系統(tǒng)的起始坐標應將和國家基本比例尺地形圖公里網(wǎng)的交點相一致，或者和已有的柵格系統(tǒng)數(shù)據(jù)相一致。并同時使用公里網(wǎng)的縱橫坐標軸作為柵格系統(tǒng)的坐標軸。這樣在使用柵格數(shù)據(jù)

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

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

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

21、任何壓縮數(shù)據(jù)的處理，因此是最直觀最基本的柵格數(shù)據(jù)組織方式。完全柵格數(shù)據(jù)的組織有三種基本方式：基于象元、基于層和基于面域，如圖4.8所示。（1）基于像元。以像元為獨立存儲單元，每一個象元對應一條記錄，每條記錄中的記錄內容包括象元坐標及其各層屬性值的編碼；節(jié)省了許多存儲坐標的空間，因為各層對應象元的坐標只需存儲一次。數(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）基于層。以層為存儲基礎，層中又以象元為序記錄其坐標和對應該層的屬性值編碼。（3）基于面域。也以層作為存儲基礎，層中再以面域為單元進行記錄，記錄的內容包括：面域編號、面域對應該層的屬性值編碼、面域中所有柵格單元的坐標；同一屬性的多個相鄰象元只需記錄一次屬性值。基于象元的數(shù)據(jù)組織方式簡單明了，便于數(shù)據(jù)擴充和修改，但進行屬性查詢和面域邊界提取時速度較慢；基于層的數(shù)據(jù)組織方式便于進行屬性查詢，但每個象元的坐標均要重復存儲，浪費了存儲空間；基于面域的數(shù)據(jù)組織方式雖然便于面域邊界提取，但在不同層中象元的坐標還是要多次存儲。4.2.4壓縮柵格數(shù)據(jù)結構1. 游程長度編碼結構游程長度（run-length

23、）編碼，也稱行程編碼，不僅是一種柵格數(shù)據(jù)無損壓縮的重要方法，也是一種柵格數(shù)據(jù)結構。它的基本思想是：對于一幅柵格數(shù)據(jù)（或影像），常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復的記錄內容。其編碼方案是，只在各行（或列）數(shù)據(jù)值發(fā)生變化時依次記錄該值以及相同值重復的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮，并實現(xiàn)數(shù)據(jù)的組織。經(jīng)編碼后，原始柵格數(shù)據(jù)陣列轉換為（si，li）數(shù)據(jù)對，其中si為屬性值，li為行程。圖4.9給出了柵格數(shù)據(jù)沿行方向進行游程長度編碼的結果。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ù)結構顯然游程長度編碼只用了40個整數(shù)就可以表示，而如果用前述的直接編碼卻需要64個整數(shù)表示，可見游程長度編碼壓縮數(shù)據(jù)是十分有效又簡便的。事實上，壓縮比的大小是與圖的復雜程度成反比的，在變化多的部分，游程數(shù)就多，變化少的部分游程數(shù)就少，原始柵格類型越簡單，壓縮效率就越高。因此這種數(shù)據(jù)結構最適宜于類型面積較大的專題要素、遙感圖像的分

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

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

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

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

29、兩兩交叉，得到以二進制數(shù)表示的MD碼，再將其轉換為十進制數(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=例如下圖第二行和第三列對應的柵格單元，其二進制的行列號分別為：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ù)文件，其結構如圖4.13所示。0140222224000000MD碼屬性值004180122164322332340350362372380390

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

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

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

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

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

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

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

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

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

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

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

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

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

44、分別記錄：（1） 樣點序號（與Voronoi 單元的ID號相同）、樣點的坐標及其屬性；（2） 各樣點所對應的相鄰樣點的序號；（3） 生成的Voronoi 單元的頂點坐標；（4） Voronoi單元的頂點組成。則其數(shù)據(jù)結構如表4.14 表4.15 所示。在記錄相鄰Vorinoi單元序號時, 統(tǒng)一采用逆時針方向。當某樣點的Voronoi 單元的邊界就是地理區(qū)域的邊界時，將Vorinoi邊與地理區(qū)域邊界的交點也作為頂點，但使用特殊標識符予以區(qū)分。這種數(shù)據(jù)結構對Voronoi多邊形的生成過程以及基于Voronoi的空間分析將起到重要的作用。表4.15 Voronoi單元鄰接關系表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ù)結構在數(shù)據(jù)結構上，TIN可以采用類似于多邊形的矢量拓撲結構，但不必要描述一般多邊形中的“島嶼”或“洞”的拓撲關系?？梢圆捎枚喾N方式來組織TIN數(shù)據(jù)模型，對圖4.20所示的TIN三角網(wǎng)，可以三角形作為基本的空間對象進行數(shù)據(jù)組織，見圖4.21。數(shù)據(jù)組織需要兩個