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

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

2、L 由 A 、 B 結(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)系包括以下幾種：(1) 鄰接：借助于不同類型拓撲元素描述相同拓撲元素之間的關(guān)系，如多邊 形和多邊形的鄰接關(guān)系。(2) 關(guān)聯(lián)：不同拓撲元素之間的關(guān)系，如結(jié)點與鏈、鏈與多邊形等。(3) 包含：面與其它拓撲元素之間的關(guān)系，如結(jié)點、線、面都位于某一個面， 則稱該面包含這些拓撲元素。(4) 連通關(guān)系：拓撲元素之間的通達關(guān)系，如點連通度、面連通度的各種性 質(zhì)(如距離等)及相互

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

4、集拓撲學為基礎(chǔ)，通過邊界和部兩個點集的交進行定義，并根 據(jù)其容進行關(guān)系劃分， 由于它只通過點集交的 “空”與“非空”來進行關(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的部，二者之間 的關(guān)系可用式 (1) 來表示：1)2)式(2) 中的元素或者為“空”，或為“非空”，總共可產(chǎn)生 16 種情形。排除現(xiàn) 實世界中不具有物理意義的關(guān)系，即可得出 8種面一面關(guān)系， 13 種線一線關(guān)系、 3 種面一點關(guān)系、 16 種線一點關(guān)系、 3 種點一線關(guān)系。這里我們列出它所能描述 的八

5、種面一面關(guān)系，如圖 4。但是由于該方法具有普遍性， 許多通過人眼都可明顯區(qū)分開的一些情形， 利 用該方法卻無能為力， 如圖 5。二者的 4交模型取值完全相同， 都為(- ，- ， - ， - )，但是實際上二者的拓撲關(guān)系并不等價。與部以進一步描述對象間的空間關(guān)系， 而后建立了描述兩個集合對象的拓撲空間 關(guān)系模型，即四交模型（ Egenhofer and Franzosa ，1991），在四交模型的基礎(chǔ) 上，加上兩對象外部的相交關(guān)系來表達實體間更為復(fù)雜的空間關(guān)系即形成了 9- 交模型（ Egenhofer and Herring ， 1994）。九交模型以代數(shù)拓撲空間數(shù)據(jù)模型的 基本幾何對象為基

6、準， 幾何對象被稱作元素， 元素通過維數(shù)進行劃分： 0 維元素 即一個結(jié)點； 1 維元素即鏈，其兩端點為兩個結(jié)點； 2 維元素即面，由一系列互 不相交的鏈構(gòu)成，任何包含在 n 維元素中的元素被稱為子部。九交模型將地理空間中的每個元素都分為部、 邊界和余三部分， 這樣任意兩 個 n 維元素的空間關(guān)系可通過這三部分相互組合來詳細描述，設(shè)地理空間中有 兩個地理元素 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)成了拓撲關(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)為表達方便，九交模型可用 33 的矩陣來描述， 由于 9 種交集中的每一個交 集有空（）與非空（ ?）兩種取值， 9 種情況可產(chǎn)生 29=512 種不同的空間關(guān) 系，如地理元素 A、 B 相互分離，則用矩陣可表示為：簡記為：拓撲關(guān)系表達時側(cè)重于多邊形間的關(guān)系描述，尤其是在 2 維拓撲空間中， 九交模型中多邊形 （有空多邊形和無孔多邊形） 間拓撲關(guān)系的存在需滿足一定的 條件，9-交模型中任意多邊形之間拓撲關(guān)系存在的基本條件有

8、 9 個，而在地圖表 達時常常遇到無孔多邊形間拓撲關(guān)系的描述， 相對于有空多邊形， 無孔多邊形的 邊界是連續(xù)的，且多邊形間的拓撲關(guān)系在滿足 9個基本條件的同時， 還需更多限 制條件，如：若兩多邊形的邊界都與對方的部相交， 則兩邊界也相交等 （Egenhofer and Herring，1994）。根據(jù)這些條件，得出任意兩多邊形（有空或無孔）在 2 維拓撲空間中只存 在 18 種拓撲關(guān)系，對于無孔多邊形則只存在 8 中拓撲關(guān)系， 其它拓撲關(guān)系并無 實際意義或不存在。 通過對大量空間關(guān)系進行歸納和分類， 得出以下幾種基本的 空間關(guān)系：相離、相接、相交、重合、包含、覆蓋，其表示如圖 6 所示。圖 6

9、 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)用于不同維幾何目標；(4) 每一種拓撲關(guān)系對應(yīng)唯一的 9-交模型矩陣。由于地理對象分點、線、面三類，而且其中任意兩者的交集又有 6 種取值， 因而 9-交模型的空間關(guān)系又可拓展成 69 種非常復(fù)雜的空間關(guān)系， 形成 9-交擴展 模型。

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

11、的空間關(guān)系則可表示成 9 種情況， 每一種情況又有空與非空兩種取值，9 種情況可產(chǎn)生 2* * 9=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)系 (Disjoint) 、相接關(guān)系 (Touch) 、相交關(guān)系 (Cross) 、包含于 關(guān)系(In) 、交疊關(guān)系 (Overlap) ?；诖?，不少學者又研究更為復(fù)雜對象之間更 加復(fù)雜、細致的空間關(guān)系，如 Clementini 首先對平面上復(fù)雜幾何對象(不連通 并含有洞的面、 閉曲線和自相交的折線集和多點集) 進行了定義，明確了其邊界、