拓?fù)潢P(guān)系和九交模型

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

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

3、間的等級(jí)關(guān)系。如國(guó)家包含省、省包含市等。拓?fù)鋽?shù)據(jù)結(jié)構(gòu)中弧段和鏈具有方向性， 通常以順、逆時(shí)針作為方向基準(zhǔn)，或 將坐標(biāo)以順序方式存儲(chǔ)。拓?fù)湓刂g的各種拓?fù)潢P(guān)系構(gòu)成了對(duì)地理空間實(shí)體的 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)表達(dá)，如圖2所示。PjPsP:圖2拓?fù)潢P(guān)系空間數(shù)據(jù)模型示例不同拓?fù)湓氐耐負(fù)潢P(guān)系可在空間實(shí)體幾何表示的同時(shí)來(lái)建立， 也可單獨(dú)建 立不同的關(guān)系表。若在實(shí)體進(jìn)行幾何表達(dá)的同時(shí)建立拓?fù)潢P(guān)系，可在關(guān)系數(shù)據(jù)庫(kù) 中存儲(chǔ)各類型幾何元素?cái)?shù)據(jù)的同時(shí)存儲(chǔ)對(duì)應(yīng)的拓?fù)潢P(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ù)和拓?fù)潢P(guān)系數(shù)據(jù)同表存儲(chǔ)LireJD StartPoinMD EndPoinMD AllPDints* D(2)(2)二、四交模型、九交模型表達(dá)拓?fù)潢P(guān)系4交模型以點(diǎn)集拓?fù)鋵W(xué)為基礎(chǔ)，通過(guò)邊界和內(nèi)部?jī)蓚€(gè)點(diǎn)集的交進(jìn)行定義，并 根據(jù)其內(nèi)容進(jìn)行關(guān)系劃分

5、，由于它只通過(guò)點(diǎn)集交的“空”與“非空”來(lái)進(jìn)行關(guān)系 判別，方法簡(jiǎn)練，所以在一些商用數(shù)據(jù)庫(kù)系統(tǒng)、GIs軟件設(shè)計(jì)中應(yīng)用廣泛。設(shè)有空間實(shí)體A、B, B（A）、B（B）表示A、B的邊界，J（A）、J（B）表示A、B的內(nèi)部， 二者之間的關(guān)系可用式（1）來(lái)表示：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)中的元素或者為“空”，或?yàn)椤胺强铡?，總共?/p>

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

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

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

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

10、樣任意兩個(gè)n維元素的空間關(guān)系可通過(guò)這三部分相互組合來(lái)詳細(xì)描述，設(shè)地理空間中有兩個(gè)地理元素 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)成了拓?fù)潢P(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、達(dá)方便，九交模型可用3X3的矩陣來(lái)描述，由于9種交集中的每一個(gè)交 集有空（9 ）與非空（？ B ）兩種取值，9種情況可產(chǎn)生29=512種不同的空間關(guān) 系，如地理元素A、B相互分離，則用矩陣可表示為：簡(jiǎn)記為：丨r e oHHrG4,b）= e e-.<9iII拓?fù)潢P(guān)系表達(dá)時(shí)側(cè)重于多邊形間的關(guān)系描述，尤其是在 2維拓?fù)淇臻g中， 九交模型中多邊形（有空多邊形和無(wú)孔多邊形）間拓?fù)潢P(guān)系的存在需滿足一定的 條件，9-交模型中任意多邊形之間拓?fù)潢P(guān)系存在的基本條件有 9個(gè)，而在地圖表 達(dá)時(shí)常常遇到無(wú)孔多邊形間拓?fù)潢P(guān)系的描述， 相對(duì)于有空多邊形，無(wú)孔多邊形的 邊界是連續(xù)的，且多邊形間的拓?fù)潢P(guān)系在滿足 9個(gè)

12、基本條件的同時(shí)，還需更多限 制條件，如：若兩多邊形的邊界都與對(duì)方的內(nèi)部相交，則兩邊界也相交等（Ege nhofer and Herri ng, 1994）。根據(jù)這些條件，得出任意兩多邊形（有空或無(wú)孔）在 2維拓?fù)淇臻g中只存 在18種拓?fù)潢P(guān)系，對(duì)于無(wú)孔多邊形則只存在8中拓?fù)潢P(guān)系，其它拓?fù)潢P(guān)系并無(wú) 實(shí)際意義或不存在。通過(guò)對(duì)大量空間關(guān)系進(jì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平面中多邊形之間基本的拓?fù)潢P(guān)系九交模型描述的拓?fù)潢P(guān)系只是拓?fù)潢P(guān)系的類別，每一類別又有多種情形，如兩個(gè)面邊界相交，交點(diǎn)可能是一個(gè)點(diǎn)，也可能是一條線，這種關(guān)系用九交模型模 型表示是一致的，但其拓?fù)潢P(guān)系并不同，而且這幾種基本空間關(guān)系被定義為空間 關(guān)系的最小集，并具有如下特點(diǎn)：(1) 相互之間不能轉(zhuǎn)化；(2) 能表達(dá)所有的復(fù)雜空間關(guān)系；(3) 能應(yīng)用于不同維幾何目標(biāo)；(4) 每一種拓?fù)潢P(guān)系對(duì)應(yīng)唯一的9-交模型矩陣。由于地理對(duì)象分點(diǎn)、線、面三類，而且其中任意兩者的交集又有 6種取值， 因而9-父模型的空間關(guān)系又可拓展成 6種非常復(fù)雜的空間關(guān)系，形成9-交擴(kuò)展 模型?；诖耍簧賹W(xué)者研究了更為復(fù)雜、細(xì)致的空間關(guān)系，如Cleme ntini首先