拓撲關(guān)系和九交模型

1、認識拓撲關(guān)系和九交模型-2008301130103 楊文一、拓撲關(guān)系拓撲關(guān)系模型主要以結(jié)點、弧段、三角形和多邊形作為描述空間物體的最簡 化元素，運用數(shù)學(xué)領(lǐng)域中的組合拓撲學(xué)來實現(xiàn)對空間簡單與復(fù)雜物體幾何位置和 屬性信息的完整描述。在該模型中，0維空間物體代表結(jié)點，1維空間物體代表 弧段或邊，2維空間物體代表三角形或其它多邊形，3維空間物體則代表四面體 或其它多面體，各類型的空間物體含有各自的坐標(biāo)序列和屬性值，并通過基本的 鄰接、關(guān)聯(lián)、包含、幾何和層次關(guān)系等建立之間的相互聯(lián)系，而不同類型的物體 相互組合又構(gòu)成復(fù)雜的地理空間對象。除了結(jié)點沒有方向性，弧段和多邊形空間對象都具有方向性，如弧段L由A、B

2、結(jié)點組成，其方向性可表示為由 A-B或 由B-A，多邊形則可用順、逆時針來表示其方向性。如下圖：圖1拓撲關(guān)系數(shù)據(jù)模型描述拓撲關(guān)系數(shù)據(jù)模型中建立拓撲數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵是對元素間拓撲關(guān)系的描述， 最基本的拓撲關(guān)系包括以下幾種：鄰接：借助于不同類型拓撲元素描述相同拓撲元素之間的關(guān)系，如多邊 形和多邊形的鄰接關(guān)系。(2) 關(guān)聯(lián)：不同拓撲元素之間的關(guān)系，如結(jié)點與鏈、鏈與多邊形等。(3) 包含：面與其它拓撲元素之間的關(guān)系，如結(jié)點、線、面都位于某一個面 內(nèi)，則稱該面包含這些拓撲元素。(4) 連通關(guān)系：拓撲元素之間的通達關(guān)系，如點連通度、面連通度的各種性 質(zhì)(如距離等)及相互關(guān)系。(5) 層次關(guān)系：相同拓撲元素之

3、間的等級關(guān)系。如國家包含省、省包含市等。拓撲數(shù)據(jù)結(jié)構(gòu)中弧段和鏈具有方向性， 通常以順、逆時針作為方向基準(zhǔn)，或 將坐標(biāo)以順序方式存儲。拓撲元素之間的各種拓撲關(guān)系構(gòu)成了對地理空間實體的 拓撲數(shù)據(jù)結(jié)構(gòu)表達，如圖2所示。PjPsP:圖2拓撲關(guān)系空間數(shù)據(jù)模型示例不同拓撲元素的拓撲關(guān)系可在空間實體幾何表示的同時來建立， 也可單獨建 立不同的關(guān)系表。若在實體進行幾何表達的同時建立拓撲關(guān)系，可在關(guān)系數(shù)據(jù)庫 中存儲各類型幾何元素數(shù)據(jù)的同時存儲對應(yīng)的拓撲關(guān)系，如圖 3所示。Points litbkGeonietiT DntaPoinMD 仇巧Tapalogical Rehrioii jhip Data Gecme

4、tiv BataArtiibiite Dara Points-IDInformationlines-iDInf erm at ionPolygons-ID InformationPolygons Tablei*Tapalcigica K elation ship Datai Pol'/iCn-IDLtlPlDAttributes Tabk圖3幾何數(shù)據(jù)和拓撲關(guān)系數(shù)據(jù)同表存儲LireJD StartPoinMD EndPoinMD AllPDints* D(2)(2)二、四交模型、九交模型表達拓撲關(guān)系4交模型以點集拓撲學(xué)為基礎(chǔ)，通過邊界和內(nèi)部兩個點集的交進行定義，并 根據(jù)其內(nèi)容進行關(guān)系劃分

5、，由于它只通過點集交的“空”與“非空”來進行關(guān)系 判別，方法簡練，所以在一些商用數(shù)據(jù)庫系統(tǒng)、GIs軟件設(shè)計中應(yīng)用廣泛。設(shè)有空間實體A、B, B（A）、B（B）表示A、B的邊界，J（A）、J（B）表示A、B的內(nèi)部， 二者之間的關(guān)系可用式（1）來表示：BOTT衣厲衣石行了（3）i L i（A）n b（b） i（A）n /</?）:（1）(2)r/(A)n i(b)I b<a> n KB)Le(a)n /(B)KA) n B(B)B(A) n B(B)E D1(A) n E(B)1B(A) n E(B)E(A) n E(B)J(2)式(2)中的元素或者為“空”，或為“非空”，總共可

6、產(chǎn)生16種情形。排除現(xiàn) 實世界中不具有物理意義的關(guān)系，即可得出 8種面一面關(guān)系，13種線一線關(guān)系、 3種面一點關(guān)系、16種線一點關(guān)系、3種點一線關(guān)系。這里我們列出它所能描述 的八種面一面關(guān)系，如圖4。但是由于該方法具有普遍性，許多通過人眼都可明顯區(qū)分開的一些情形， 利 用該方法卻無能為力，如圖5。二者的4交模型取值完全相同，都為(-，-, -，-)，但是實際上二者的拓撲關(guān)系并不等價。:ffiS 4交模殂可區(qū)分的八種區(qū)域間空間關(guān)系| 這樣任意九交模型則將現(xiàn)實世界的每一對象都分成邊界、內(nèi)部和余三部分, 兩對象之間的空間關(guān)系則可表示成 9種情況，每一種情況又有空與非空兩種取 值，9種情況可產(chǎn)生29=

7、512種不同的空間關(guān)系情形，但其中有些關(guān)系并不存在。9-交模型形式化的描述了離散空間對象之間的拓撲關(guān)系，雖然理論上可表達512種關(guān)系，但大部分關(guān)系無實際意義或是不存在，可以說9-交模型所描述的拓撲關(guān)系只是拓撲關(guān)系的類別，每一類別又可能有多種情形。由于地理對象又可分為 點、線、面三類，而且其中任意兩者的交集又有T、F、*、0、1、2六種取值，因而9-交模型的空間關(guān)系又可拓展成 69=10077696種非常復(fù)雜的空間情形，形 成9-交擴展模型，并通過對大量的空間關(guān)系進行歸納和分類，得出5種基本的空間關(guān)系：相離關(guān)系(Disjoi nt)、相接關(guān)系(Touch)、相交關(guān)系(Cross)、包含于 關(guān)系(

8、In)、交疊關(guān)系(Overlap)?；诖耍簧賹W(xué)者又研究更為復(fù)雜對象之間更 加復(fù)雜、細致的空間關(guān)系，如 Cleme nti ni首先對平面上復(fù)雜幾何對象(不連通 并含有洞的面、閉曲線和自相交的折線集和多點集) 進行了定義，明確了其邊界、 內(nèi)部等的含義，然后用 CBM( Calculated Based Method )對這些對象之間的拓 撲關(guān)系進行了描述，并證明了這 5種關(guān)系的互斥性20;還有學(xué)者提出基于 Voronoi圖的混合方法，它利用控件對象的 Voronoi區(qū)域作為其外部對原9-交 擴展模型進行了修改。在基于拓撲關(guān)系思想的基礎(chǔ)上，Egenhofer在點集關(guān)系中引入了對象的邊界與內(nèi)部以

9、進一步描述對象間的空間關(guān)系，而后建立了描述兩個集合對象的拓撲空 間關(guān)系模型，即四交模型（Egenhofer and Franzosa ， 1991），在四交模型的基 礎(chǔ)上，加上兩對象外部的相交關(guān)系來表達實體間更為復(fù)雜的空間關(guān)系即形成了9-交模型（Egenhofer and Herring ， 1994）。九交模型以代數(shù)拓撲空間數(shù)據(jù)模型 的基本幾何對象為基準(zhǔn)，幾何對象被稱作元素，元素通過維數(shù)進行劃分：0維元 素即一個結(jié)點；1維元素即鏈，其兩端點為兩個結(jié)點；2維元素即面，由一系列 互不相交的鏈構(gòu)成，任何包含在 n維元素中的元素被稱為子部。九交模型將地理空間中的每個元素都分為內(nèi)部、邊界和余三部分，這

10、樣任意兩個n維元素的空間關(guān)系可通過這三部分相互組合來詳細描述，設(shè)地理空間中有兩個地理元素 AB,I（A）、I（B）表示 A B內(nèi)部，B（A）、B（B）表示A、B邊界，E（A）、E（B）表示A、B的余，那么這六部分相互組合求交可形成 3 X 3=9種交集，并構(gòu)成了拓撲關(guān)系描述的基本框架，即九交模型，如表 1。IR(A9B) =I- 5(4) c 1(B) 0B(A) c B(B) = 0表1九交模型i（a）n i（b）I(A) n B(B)I(A) n E(B)B(A) n I(B)B(A) n B(B)B(A) n E(B)E(A) n I(B)E(A) n B(B)E(A) n E(B)為表

11、達方便，九交模型可用3X3的矩陣來描述，由于9種交集中的每一個交 集有空（9 ）與非空（？ B ）兩種取值，9種情況可產(chǎn)生29=512種不同的空間關(guān) 系，如地理元素A、B相互分離，則用矩陣可表示為：簡記為：丨r e oHHrG4,b）= e e-.<9iII拓撲關(guān)系表達時側(cè)重于多邊形間的關(guān)系描述，尤其是在 2維拓撲空間中， 九交模型中多邊形（有空多邊形和無孔多邊形）間拓撲關(guān)系的存在需滿足一定的 條件，9-交模型中任意多邊形之間拓撲關(guān)系存在的基本條件有 9個，而在地圖表 達時常常遇到無孔多邊形間拓撲關(guān)系的描述， 相對于有空多邊形，無孔多邊形的 邊界是連續(xù)的，且多邊形間的拓撲關(guān)系在滿足 9個

12、基本條件的同時，還需更多限 制條件，如：若兩多邊形的邊界都與對方的內(nèi)部相交，則兩邊界也相交等（Ege nhofer and Herri ng, 1994）。根據(jù)這些條件，得出任意兩多邊形（有空或無孔）在 2維拓撲空間中只存 在18種拓撲關(guān)系，對于無孔多邊形則只存在8中拓撲關(guān)系，其它拓撲關(guān)系并無 實際意義或不存在。通過對大量空間關(guān)系進行歸納和分類， 得出以下幾種基本的 空間關(guān)系：相離、相接、相交、重合、包含、覆蓋，其表示如圖 6所示。8 8e e -ee e& w& -d e卡七七.A iiiiE ct?a= si± :tl;?i' A sni 3 :?aid.

13、?A GhiE tcu:h-eV d 0凡倒=e e -e-e e eA4?二e -e -e-e_e e -e_-6-e e_ie Q -e_-e -e 一Aec-ntsin; 33 icntuis AE cjvsrs AA sie E圖6 2平面中多邊形之間基本的拓撲關(guān)系九交模型描述的拓撲關(guān)系只是拓撲關(guān)系的類別，每一類別又有多種情形，如兩個面邊界相交，交點可能是一個點，也可能是一條線，這種關(guān)系用九交模型模 型表示是一致的，但其拓撲關(guān)系并不同，而且這幾種基本空間關(guān)系被定義為空間 關(guān)系的最小集，并具有如下特點：(1) 相互之間不能轉(zhuǎn)化；(2) 能表達所有的復(fù)雜空間關(guān)系；(3) 能應(yīng)用于不同維幾何目標(biāo)；(4) 每一種拓撲關(guān)系對應(yīng)唯一的9-交模型矩陣。由于地理對象分點、線、面三類，而且其中任意兩者的交集又有 6種取值， 因而9-父模型的空間關(guān)系又可拓展成 6種非常復(fù)雜的空間關(guān)系，形成9-交擴展 模型?；诖?，不少學(xué)者研究了更為復(fù)雜、細致的空間關(guān)系，如Cleme ntini首先