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

1、認(rèn)識(shí)拓?fù)潢P(guān)系和九交模型-03 文 一、拓?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 維空間物體則代表四面體 或其它多面體， 各類(lèi)型的空間物體含有各自的坐標(biāo)序列和屬性值， 并通過(guò)基本的 鄰接、關(guān)聯(lián)、包含、幾何和層次關(guān)系等建立之間的相互聯(lián)系，而不同類(lèi)型的物體 相互組合又構(gòu)成復(fù)雜的地理空間對(duì)象。 除了結(jié)點(diǎn)沒(méi)有方向性， 弧段和多邊形空間 對(duì)象都具有方向性，如弧段

2、L 由 A 、 B 結(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)系包括以下幾種：(1) 鄰接：借助于不同類(lèi)型拓?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è)面， 則稱(chēng)該面包含這些拓?fù)湓亍?4) 連通關(guān)系：拓?fù)湓刂g的通達(dá)關(guān)系，如點(diǎn)連通度、面連通度的各種性 質(zhì)(如距離等)及相互

3、關(guān)系。(5) 層次關(guān)系： 相同拓?fù)湓刂g的等級(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 所示。圖 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ǔ)各類(lèi)型幾何元素?cái)?shù)據(jù)的同時(shí)存儲(chǔ)對(duì)應(yīng)的拓?fù)潢P(guān)系，如圖 3 所示。圖 3 幾何數(shù)據(jù)和拓?fù)潢P(guān)系數(shù)據(jù)同表存儲(chǔ)二、四交模型、九交模型表達(dá)拓?fù)潢P(guān)系4 交模型以點(diǎn)

4、集拓?fù)鋵W(xué)為基礎(chǔ)，通過(guò)邊界和部?jī)蓚€(gè)點(diǎn)集的交進(jìn)行定義，并根 據(jù)其容進(jìn)行關(guān)系劃分， 由于它只通過(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的部，二者之間 的關(guān)系可用式 (1) 來(lái)表示：1)2)式(2) 中的元素或者為“空”，或?yàn)椤胺强铡?，總共可產(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)系。這里我們列出它所能描述 的八

5、種面一面關(guān)系，如圖 4。但是由于該方法具有普遍性， 許多通過(guò)人眼都可明顯區(qū)分開(kāi)的一些情形， 利 用該方法卻無(wú)能為力， 如圖 5。二者的 4交模型取值完全相同， 都為(- ，- ， - ， - )，但是實(shí)際上二者的拓?fù)潢P(guān)系并不等價(jià)。與部以進(jìn)一步描述對(duì)象間的空間關(guān)系， 而后建立了描述兩個(gè)集合對(duì)象的拓?fù)淇臻g 關(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ì)象為基

6、準(zhǔn)， 幾何對(duì)象被稱(chēng)作元素， 元素通過(guò)維數(shù)進(jìn)行劃分： 0 維元素 即一個(gè)結(jié)點(diǎn)； 1 維元素即鏈，其兩端點(diǎn)為兩個(gè)結(jié)點(diǎn)； 2 維元素即面，由一系列互 不相交的鏈構(gòu)成，任何包含在 n 維元素中的元素被稱(chēng)為子部。九交模型將地理空間中的每個(gè)元素都分為部、 邊界和余三部分， 這樣任意兩 個(gè) n 維元素的空間關(guān)系可通過(guò)這三部分相互組合來(lái)詳細(xì)描述，設(shè)地理空間中有 兩個(gè)地理元素 A、B， I （A）、I （B）表示 A、B 部， B（A）、B（B）表示 A、B 邊 界，E（A）、E（B）表示 A、B 的余，那么這六部分相互組合求交可形成 3 3=9 種 交集，并構(gòu)成了拓?fù)潢P(guān)系描述的基本框架，即九交模型，如表 1。

7、表 1 九交模型I(A) I(B)I(A) B(B)I(A) E(B)B(A) I(B)B(A) B(B)B(A) E(B)E(A)I(B)E(A) B(B)E(A)E(B)為表達(dá)方便，九交模型可用 33 的矩陣來(lái)描述， 由于 9 種交集中的每一個(gè)交 集有空（）與非空（ ?）兩種取值， 9 種情況可產(chǎn)生 29=512 種不同的空間關(guān) 系，如地理元素 A、 B 相互分離，則用矩陣可表示為：簡(jiǎn)記為：拓?fù)潢P(guān)系表達(dá)時(shí)側(cè)重于多邊形間的關(guān)系描述，尤其是在 2 維拓?fù)淇臻g中， 九交模型中多邊形 （有空多邊形和無(wú)孔多邊形） 間拓?fù)潢P(guān)系的存在需滿足一定的 條件，9-交模型中任意多邊形之間拓?fù)潢P(guān)系存在的基本條件有

8、 9 個(gè)，而在地圖表 達(dá)時(shí)常常遇到無(wú)孔多邊形間拓?fù)潢P(guān)系的描述， 相對(duì)于有空多邊形， 無(wú)孔多邊形的 邊界是連續(xù)的，且多邊形間的拓?fù)潢P(guān)系在滿足 9個(gè)基本條件的同時(shí)， 還需更多限 制條件，如：若兩多邊形的邊界都與對(duì)方的部相交， 則兩邊界也相交等 （Egenhofer and Herring，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)行歸納和分類(lèi)， 得出以下幾種基本的 空間關(guān)系：相離、相接、相交、重合、包含、覆蓋，其表示如圖 6 所示。圖 6

9、 2 平面中多邊形之間基本的拓?fù)潢P(guān)系 九交模型描述的拓?fù)潢P(guān)系只是拓?fù)潢P(guān)系的類(lèi)別， 每一類(lèi)別又有多種情形， 如 兩個(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)、線、面三類(lèi)，而且其中任意兩者的交集又有 6 種取值， 因而 9-交模型的空間關(guān)系又可拓展成 69 種非常復(fù)雜的空間關(guān)系， 形成 9-交擴(kuò)展 模型。

10、基于此，不少學(xué)者研究了更為復(fù)雜、細(xì)致的空間關(guān)系，如 Clementini 首先對(duì)平面上復(fù)雜 幾何對(duì)象 (不連通并含有空的面、 閉曲線和自相交的折線集和多點(diǎn)集) 進(jìn)行了定 義，明確了邊界、部等的含義，然后用 CBM(Calculated Based Method)對(duì)這些 對(duì)象間的拓?fù)潢P(guān)系進(jìn)行了描述，并證明了基本空間關(guān)系的互斥性 ( Clementini,1996)；還有學(xué)者提出基于 Voronoi 圖的混合方法，它利用空間對(duì) 象的 Voronoi 區(qū)域作為其外部對(duì)原 9-交擴(kuò)展模型進(jìn)行了改進(jìn)( Chen， 1997)。九交模型則將現(xiàn)實(shí)世界的每一對(duì)象都分成邊界、 部和余三部分， 這樣任意兩對(duì)象之間

11、的空間關(guān)系則可表示成 9 種情況， 每一種情況又有空與非空兩種取值，9 種情況可產(chǎn)生 2* * 9=512 種不同的空間關(guān)系情形，但其中有些關(guān)系并不存在。 9-交模型形式化的描述了離散空間對(duì)象之間的拓?fù)潢P(guān)系，雖然理論上可表達(dá) 512種關(guān)系，但大部分關(guān)系無(wú)實(shí)際意義或是不存在，可以說(shuō) 9- 交模型所描述的拓?fù)?關(guān)系只是拓?fù)潢P(guān)系的類(lèi)別， 每一類(lèi)別又可能有多種情形。 由于地理對(duì)象又可分為 點(diǎn)、線、面三類(lèi)，而且其中任意兩者的交集又有 T、F、* 、0、1、2 六種取值， 因而 9-交模型的空間關(guān)系又可拓展成 69=10077696 種非常復(fù)雜的空間情形，形 成 9- 交擴(kuò)展模型，并通過(guò)對(duì)大量的空間關(guān)系進(jìn)行歸納和分類(lèi)，得出5 種基本的 空間關(guān)系：相離關(guān)系 (Disjoint) 、相接關(guān)系 (Touch) 、相交關(guān)系 (Cross) 、包含于 關(guān)系(In) 、交疊關(guān)系 (Overlap) ?；诖?，不少學(xué)者又研究更為復(fù)雜對(duì)象之間更 加復(fù)雜、細(xì)致的空間關(guān)系，如 Clementini 首先對(duì)平面上復(fù)雜幾何對(duì)象(不連通 并含有洞的面、 閉曲線和自相交的折線集和多點(diǎn)集) 進(jìn)行了定義，明確了其邊界、