1、簡單數據結構和拓撲數據結構【09級測繪工程】梁艷【引言】空間數據結構是指對空間數據邏輯模型描述的數據組織關系和編排方式，對地理信息系統中數據存儲、查詢檢索和應用分析等操作處理的效率有著至關重要的影 響。空間數據結構是地理信息系統溝通信息的橋梁，只有充分理解地理信息系統所 采用的特定數據結構，才能正確有效地使用系統。在地理信息系統中，較常用的有 柵格數據結構和矢量數據結構，除此之外還有混合數據結構、鑲嵌數據結構和超圖 數據結構等。空間數據結構的選擇取決于數據的類型、性質和使用的方式，應根據 不同的任務目標，選擇最有效和最合適的數據結構。矢量數據結構對矢量數據模型進行數據的組織。它通過記錄實體坐標

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

3、的空間關系分為簡單數據結構和拓撲數據結構兩大類。【摘要】矢量數據結構是利用歐幾里得幾何學中的點、線、面及其組合體來表示地理實 體空間分布的一種數據組織方式。矢量數據結構分為無拓撲的矢量數據結構（也稱 簡單數據結構）、拓撲數據結構；拓撲數據結構最重要的技術特征和貢獻是具有拓 撲編輯功能，包括多邊形連接編輯和結點連接編輯。無拓撲的矢量數據結構僅記錄 空間對象的位置坐標和屬性信息，而不記錄其拓撲關系。它有兩種模式它有兩種模式：一種方式是用點 一種方式是用點、線線、面對象 面對象分別記錄其坐標對； 另一種方式是用一個文件記錄點坐標對，而線、面由點號組成。空間拓撲關系是 GIS的重要標志。目前大部分GI

4、S軟件所存儲的拓撲關系僅僅涉及空間對象的拓撲 關聯關系，其它拓撲關系（如拓撲鄰接、拓撲包含拓撲包含）可以從關聯關系中導出，或通過實時空間運算得到。【關鍵字】數據結構、拓撲、空間實體空間數據結構是指適合于計算機存貯、管理、處理的幾何數據的邏輯結構。換句話說，是指幾何數據以什么形式在計算機中存貯和處理。空間數據結構分為矢量數據結構和柵格數據結構兩種（如圖2-4）。h輅表示形式匚矢表示理式圖2-4空間實體的柵格、矢量數據結構表示、矢量數據結構矢量數據結構是通過坐標值來精確地表示點、線、面等地理實體的方法。點由一對 x,y坐標表示。線由一串有序的 x,y坐標對表示。面一一由一串有序的、且首尾坐標相同的

5、 x,y坐標對表示。矢量數據結構可以表示現實世界中各種復雜的實體，當問題可描述成線和邊界時，特別有效。矢量數據冗余度低，結構緊湊，并具有空間 實體的拓撲信息，便于深層次分析。矢量數據的輸出質量好、精度高。矢量數據的獲取方式通常有：(1) 由外業測量獲得。可利用測量儀器自動記錄測量成果(常稱為電子手薄)，然后轉到地理數據庫中(2) 由柵格數據轉換獲得。利用柵格數據矢量化技術，把柵格數據轉換為矢量數據。(3) 跟蹤數字化。用跟蹤數字化的方法，把地圖變成離散的矢量數據。矢量數據結構的表示：矢量數據的表示方法多種多樣，但基本上類似，可觸類旁通。在GIS中，矢量數據表示時應考慮以下問題：矢量數據自身的存

6、貯和處理。與屬性數據的聯系。矢量數據之間的空間關系(拓撲關系)。下面分別介紹矢量數據的簡單數據結構和拓撲數據結構。(1)簡單數據結構矢量數據的簡單數據結構沒有拓撲關系，主要用于矢量數據的顯示、輸出，以及一般的查詢和檢索。可分別按點、線、面三種基本形式來描述。1、點的矢量數據結構可表示為：標識碼X, Y坐標標識碼：按一定的原則編碼，簡單情況下可順序編號。標識碼 具有唯一性，是聯系矢量數據和與其對應的屬性數據的關鍵字。屬 性數據單獨存放在數據庫中。 在點的矢量數據結構中也可包含屬性 碼，這時其數據結構為：標識碼屬性碼X Y坐標屬性碼：通常把與實體有關的基本屬性（如等級、類型、大小等）作為屬性碼。屬

7、性碼可以有一個和多個。X，Y坐標：是點實體的定位點，如果是有向點，貝何以有兩個坐標對。2、線（鏈）的矢量數據結構 線（鏈）的矢量數據結構可表示為：標識碼坐標對數nX, 丫坐標標識碼的含義與點的矢量數據結構相同。同樣，在線的矢量數據結構中也可含有屬性碼，如表示線的類型、等級、是否要加密、坐標對數n：構成該線（鏈）的坐標對的個數。X,Y坐標串：這是構成線（鏈）的矢量坐標，共有n對。也可把所有 線（鏈）的X,Y坐標串單獨存放，這時只要給出指向該鏈 坐標串的首地址指針即可。3、面（多邊形）面的矢量數據結構可以象線的數據結構一樣表示， 只是坐標串的 首尾坐標相同。這里介紹鏈索引編碼的面（多邊形）的矢量數

8、據結構， 可表示為：標識碼璉標識碼集標識碼的含義同點和線的矢量數據結構，在面的矢量數據結構中也可含有屬性碼。鏈數n：指構成該面（多邊形）的鏈的數目。鏈標識碼集：指所有構成該面（多邊形）的鏈的標識碼的集合，共有這樣，一個面（多邊形）就可由多條鏈構成，每條鏈的坐標可由線 （鏈）的矢量數據結構獲取。這種方法可保證多邊形公共邊的唯一性； 但多邊形的分解和合并不易進行；鄰域處理比較復雜，需追蹤出公 共邊；在處理“洞”或“島”之類的多邊形嵌套問題時較麻煩，需計算多 邊形的包含等。（2）拓撲數據結構拓撲關系是一種對空間結構關系進行明確定義的數學方法。具有拓撲關系的矢量數據結構就是拓撲數據結構， 拓撲數據結構

9、是GIS的 分析和應用功能所必需的。拓撲數據結構的表示方式沒有固定的格式， 還沒有形成標準，但基本原理是相同的。1、拓撲元素矢量數據可抽象為點（結點）、線（鏈、弧段、邊）、面（多邊形）三種要素，即稱為拓撲元素。點（結點） 孤立點、線的端點、面的首尾點、鏈的連接點等。線（鏈、弧段、邊）一一兩結點間的有序弧段。面（多邊形）若干條鏈構成的閉合多邊形。2、最基本的拓撲關系最基本的拓撲關系是關聯和鄰接。關聯不同拓撲元素之間的關系。如結點與鏈，鏈與多邊形等。鄰接相同拓撲元素之間的關系。如結點與結點，鏈與鏈，面與面等。鄰接關系是借助于不同類型的拓撲元素描述的，如面通過鏈而鄰接在GIS的分析和應用功能中，還可

10、能用到其它拓撲關系，如：包含關系面與其它拓撲元素之間的關系。如果點、線、面在該 面內，則稱為被該面包含。如某省包含的湖泊、河流等。幾何關系拓撲元素之間的距離關系。 如拓撲元素之間距離不超 過某一半徑的關系。層次關系相同拓撲元素之間的等級關系。如國家由省 （自治區、 直轄市）組成，省（自治區、直轄市）由縣組成等。3、拓撲關系的表示拓撲數據結構包括DIME（對偶獨立地圖編碼法）、POLYVRT（多邊 形轉換器）、TIGER（地理編碼和參照系統的拓撲集成）等。它們共同的 特點是:點是相互獨立的，點連成線，線構成面。每條線始于起始結點 （FN），止于終止結點TN），并與左右多邊形（LP和RP）相鄰接。

11、構成 多邊形的線叉稱為鏈段或弧段，兩條以上的弧段相交的點稱為結點， 由一條弧段組成的多邊形稱為島，多邊形圖中不含島的多邊形稱為簡 單多邊形，表示單連通區域；含島區的多邊形稱為復合多邊形， 表示復 連通區域。在復連通區域中，包括有外邊界和內邊界，島區多邊形看 作是復連通區域的內邊界，復連通區域的內邊界多邊形對應的區域含 有平面上的無窮遠慮。該數據結構的基本元素如圖2-11所示。在這種數據結構中，弧段或鏈段是數據組織的基本對象。弧段文 件由弧段記錄組成，每個弧段記錄包括弧段標識碼、FN、TN、LP和RP。結點文件由結點記錄組成，包括每個結點的結點號、結點坐標及與該結點連接的弧段標識碼等。多邊形文件

12、由多邊形記錄組成，包括多邊形標識碼、組成該多邊形的弧段標識碼以及相關屬性等。現以圖2-11為例，列出拓撲數據結構的弧段文件格式俵2-5):他結點碼C)弧段碼 多邊形o 結點多邊形島圖2-11矢量結構圖形基本元素瓠段號起結點終結點左務還汞右參邊形CN】P2?16旳P】P1N1%申%出叫p*Cg嗎P*C10%拓撲數據結構最重要的技術特征和貢獻是具有拓撲編輯功能。這 種拓撲編輯功能，不但保證數字化原始數據的自動查錯編輯，而且可以自動形成封閉的多邊形邊界，為由各個單獨存儲的弧段組成所需要 的各類多邊形及建立空間數據庫奠定基礎。拓撲編輯功能包括多邊形連接編輯和結點連接編輯，前者指順序連接組成封閉多邊形一

13、組線段的編輯，后者指順序連接環繞某個結點所有多邊形的編輯。具體的編輯算法如下：(1)多邊形連接編輯。例如，設需要對多邊形P1進行編輯，其算法過程為： 從表2-5所示的弧段文件中，檢出與當前編輯的多邊形P1相關的所有記錄：邨段號起豺點左霧過形右當迪形ClNiNtPtPiClNjNtPi融CjNiPi 在檢出的記錄中，計算機檢查當前編輯的多邊形P1所處的位置：如果P1位在左多邊形位置，將之與位于右多邊形位置的多邊 形號相交換，同時也將該記錄的結點號位置作相應的交換；反之，如 果當前編輯的多邊形P1位于右多邊形位置，則該記錄的所有數據 項順序不作改變。按照上述規則，檢出的記錄變為以下形式：卿號起簪點

14、CiHiNi：PtPiCi地NiRPiCiNiKiPi 從經過代碼位置轉換的記錄中，任取一個起結點作為起點，順序連 接各個結點，必要時可對記錄的前后順序作調整，使得連接的結點 能自行封閉，如圖2-12所示。如果依照上述順序連接的結點不能自行閉合， 或者出現記錄缺 損或記錄多余等情況，則表示弧段文件有錯，必須改正出錯的記錄。直到所有多邊形都經過編輯和改正，再轉入結點連接編輯左寥逍誓右零逍形ClCi亠 Ni恥:二PiPiCi皿1K1Pi(2)結點連接編輯。例如，設需要對結點 N2進行編輯，其算法過程為： 從表2-5所示的弧段文件中，檢出與當前編輯的結點N2相關的所有記錄：起統*左寥過形右寥過形Ci

15、NiNtPiGNjNtPi典CsNiNsPs 在檢出的記錄中，計算機檢查當前編輯的結點 N2所處的位置： 如果N2位在起結點位置，將之與位于終結點位置的結點號相交換， 同時也符該記錄的多邊形號位置作相應的交換；反之，如果當前編輯 的結點N2位于終結點位置，則該記錄所有數據項順序不作改變。 按照上述規則，檢出的記錄變為以下形式：飆段號左字過總右審迪薛CiHiNtPiCiNj恥Pi塾CsNjsPtPt 從經過代碼位置轉換的記錄中， 任取一個左多邊形作為起點，順序連接各個多邊形，同樣，必要時可對記錄的前后順序作調整，使得連接的多邊形能首尾呼應，如圖2-13所示：邨段號包結點左棗迪形CLN1N2

16、9;APLC2N3N2P4C5N5N2二T P2如果依照上述序連接的多邊形不能首尾呼應，或者出現記錄缺損 或記錄多余等情況，同樣也表示弧段文件有錯，必須改正出錯的記錄。直到所有結點都經過編輯和改正，才能將該弧段文件用于結點文件和多邊形文件的自動生成以及數據庫的建立。這種拓撲數據結構及其自動編輯功能，已經被許多商品化的GIS 軟件所采用，例如美國的 ARC/INFO GIS軟件等。、GIS中的矢量數據模型在過去20年中，矢量數據模型是GIS中變化最大的方面，例如,ESRI公司所開發每種新軟件包都對應一種新的矢量數據模型，ArcView 對應 Shapefile，Arc/Info 對應 Cover

17、age，ArcGIS 對應 Geodatabase。Shapefile和Coverage是地理關系數據模型，它利 用分離的系統來存儲空間數據和屬性數據，而Geodatabase是基于對象數據模型，它把空間數據和屬性數據存儲在唯一的系統中。Shapefile是非拓撲的，Coverage是拓撲的。Shapefile多邊形對于共享邊界實際上有重復弧段且可彼此重疊， 不同于Coverage所用的多個文件，它用幾何學性質存儲兩個基本文 件：以.shp為擴展名的文件存儲要素幾何學特征；以.shx為擴展名 的文件保留要素幾何特征的空間索引。Coverage支持三種基本拓撲關系：連接性、面定義、鄰接性。Sha

18、pefile: 一種基于文件方式存儲GIS數據的文件格式。至少由.shp,.dbf,.shx三個文件作成，分別存儲空間，屬性和前兩者的關 系。Shapefile是GIS中比較通用的一種數據格式。Coverage: 一種拓撲數據結構，一般的 GIS原理書中都有它的原 理論述。數據結構復雜，屬性缺省存儲在Info表中。目前ArcGIS中 仍然有一些分析操作只能基于這種數據格式進行操作。Geodatabase: Arclnfo 發展到ArcGIS時候推出的一種數據格式， 一種基于RDBMS存儲的數據格式，其有兩大類：1. Personal Geodatabse 用來存儲小數據量數據，存儲在Acces

19、s 的mdb格式中。2. ArcSDE Geodatabse存儲大型數據，存儲在大型數據庫中Oracle,Sql Server,DB2等。可以實現并發操作，不過需要單獨 的用戶許可。Shapefile數據模型Shapefile是ArcView GIS3.X的原生數據格式，屬于簡單要素類， 用點、線、多邊形存儲要素的形狀，卻不能存儲拓撲關系，具有簡單、 快速顯示的優點。一個shapefile是由若干個文件組成的，空間信息 和屬性信息分離存儲，所以稱之為“基于文件”。每個shapefile，都至少由三個文件組成，其中：*shp存儲的是 幾何要素的的空間信息，也就是 XY坐標。*.shx存儲的是有關

20、*.shp 存儲的索引信息，它記錄了在*.shp中，空間數據是如何存儲的，XY 坐標的輸入點在哪里，有多少XY坐標對等信息。*.dbf存儲地理數據 的屬性信息的dBase表。這三個文件是一個shapefile的基本文件， shapefile還可以有其他一些文件，但所有這些文件都與該shapefile同名，并且存儲在同一路徑下。其他一些較為常見的文件：*.prj如果shapefile定義了坐標系統， 那么它的空間參考信息將會存儲在*.prj文件中；*.shp.xml這是對shapefile進行元數據瀏覽后生成的 xml元數據文件；*sbn和*sbx 這兩個存儲的是shapefile的空間索引，它

21、能加速空間數據的讀取， 這兩個文件是在對數據進行操作、瀏覽或連接后才產生的，也可以通 過ArcToolbox->DataMa nageme ntTools->ln dexes->Addspatiallndex 工具生成。當使用ArcCatalog對shapefile進行創建、移動、刪除或重命名 等操作，或使用 ArcMap對shapefile進行編輯時，ArcCatalog將自 動維護數據的完整性，將所有文件同步改變。所以需要使用 ArcCatalog管理shapefile。雖然Shapefile無法存儲拓撲關系，但它 并不是普通用于顯示的圖形文件，作為地理數據，它自身有拓撲

22、的。 比如一個多邊形要素類，shapefile會按順時針方向為它的所有頂點 排序，然后按頂點順序兩兩連接成的邊線向量，在向量右側的為多邊形的內部，在向量左側的是多邊形的外部。由于20世紀90年代地理信息的迅速發展以及ArcViewGIS3.x軟件在世界范圍內的推廣，shapefile格式的數據使用非常廣泛，數據 來源也較多。很多軟件都提供了向shapefile轉換的接口（如Map Info、 MapGIS等）oArcGIS支持對shapefile的編輯操作，也支持shapefile 向第三代數據模型geodatabase的轉換。Coverage數據模型Coverage是一個集合，它可以包含一個

23、或多個要素類。 在第一個 商業化GIS軟件Arc/INFO之前，計算計劃的圖形表示源自通用的 CAD軟件，屬性信息和幾何要素放在一起，不利于空間信息的描述和分析Coverage的優勢：(1) 空間數據與屬性數據關聯。空間數據存儲于建立了索引的二進 制文件中，屬性數據存放在 DBMS表中，二者以公共的標識編碼關 聯。(2) 矢量數據間的拓撲關系得以保存。Geodatabase數據模型Geodatabase作為ArcGIS的原生數據格式，體現了很多第三代 地理數據模型的優勢。隨著IT技術的發展，普通的事務型數據的管 理模式，早已從傳統的基于文件的管理轉向利用基于工業標準建立的 關系型數據庫進行管理

24、，這種基于數據庫的管理方式的優點是不言而 喻的。那么帶有空間信息的地理數據是否也可以利用這種非常成熟的 數據庫技術進行管理呢？于是 ESRI推出了 geodatabase數據模型， 利用數據庫技術高效安全地管理我們的地理數據。Geodatabase 可以分為兩種，一種是基于 Microsoft Access的 personal geodatabase ，另一種是基于 oracle、SQL Server、Informix 或者DB2的enterprise geodatabase ，由于它需要中間件 ArcSDE進 行連接，所以 enterprise geodatabase 又稱為 ArcSDEg

25、eodatabase。 由于 Microsoft Access 自身容量的限制， personal geodatabase 的 容量上限為2GB，這顯然不能滿足企業級的海量地理數據的存儲需 求。于是可以將geodatabase擴展為ArcSDEgeodatabase，底層數 據庫可以使用oracle這樣的大型關系數據庫，能夠存儲近乎“無限”的海量數據(僅受硬盤大小的限制)。雖然底層使用的數據庫各不相同，但是geodatabase給用戶提供的是一個一致的操作環境。在geodatabase中，不僅可以存儲類似shapefile的簡單要素類還可以存儲類似coverage的要素集并且支持一系列的行為規

26、則對其 空間信息和屬性信息進行驗證表格、關聯類、柵格、注記和尺寸都可 以作為 eodatabase 對象存儲。這些在 perasonalgeodatabase 禾口 ArcSDE geodatabase中都是一樣的(柵格的存儲有點小差異，但對 用戶來說都是一樣的)。Geodatabase的模型結構：(1)對象類(Object class)對象類是一種特殊的類，沒有空間特征。其實例是可關聯某特定行為的表記錄。如，某地塊的主人，在“地塊” “主人”間可建立某 種關系。要素類(Feature class)要素類是同類空間要素的集合。如，河流、道路、植被、電纜 等。要素類可以獨立存在，也可以具有某種聯

27、系。當不同的要素 類之間存在關系時，就將其組織到一個要素數據集(Featuredataset ) 中。(3) 要素數據集(Feature dataset)要素數據集由一組具有相同空間參考(Spatial referenee )的 要素類組成。將不同要素類放入要素數據集的原因：a. 專題歸類表示一一當不同的要素類屬于同一范疇。比如，全國范圍內某種比例尺的水系數據，其點線面類型的要素類可組織成 同一個要素數據集。b. 創建幾何網絡一一在同一幾何網絡中充當連接點和邊的各種要素類，須組織到同一要素數據集中。比如，配電網絡中，有各種開 關、變壓器、電纜等，它們分別對應點或線類型的要素類，在配 電網絡建模時，我們要將其全部考慮到配電網絡對應的幾何網絡 模型中。此時這些要素類就要放在統一要素數據集下