曹雪峰

（信息工程大學地理空間信息學院，河南 鄭州 450052）

0 引言

空間關系是地理信息科學中的重要理論問題，包括拓撲關系、方向關系、距離關系3類空間關系的描述和推理［1］。拓撲關系描述方法主要有點集拓撲方法、DEM方法、最小邊界矩形法、區(qū)域連接法、CBM方法、符號投影法、Voronoi圖法、廣義交模型方法、符號陣列法等［2，3］，基于點集拓撲理論的四交模型（4IM）和九交模型（9IM）是GIS領域中廣泛使用的拓撲關系描述方法。

9IM模型［4］是Egenhofer等研究二維空間實體拓撲關系提出的。陳軍等用DE＋9IM方法［5］研究三維空間中單純形間的拓撲關系，可以區(qū)分59中拓撲關系，其中有意義且可實現(xiàn)的拓撲關系分為6種：相鄰（touch）、包含（in）、相交（cross）、部分覆蓋（overlap）、相離（disjoint）和相等（equal）。采用 Open－GIS的數(shù)據(jù)模型，使用9IM方法能夠區(qū)分并實現(xiàn)的體－體拓撲關系有8種［6］。劉新等［2］使用9IM方法研究三維空間中單純形間的拓撲關系，其中兩個四面體之間的拓撲關系有8種。

目前對拓撲關系描述的研究主要集中在二維拓撲關系。關于三維拓撲關系描述的研究，主要是基于9IM模型圍繞三維空間中的折線段、表面（不含島）、體（不含洞）等簡單空間目標展開。9IM模型用兩個物體的內(nèi)部、邊界和外部間的交所組成的3×3矩陣來描述兩物體間的拓撲關系。但是，三維空間中物體的邊界也具有自身的結構，可能由多個部分組成，因而，兩個體目標邊界間的相交等價于兩個復雜面目標的相交，有可能存在的接觸于一點、相交于一個面、相互交錯或者接觸、相交、交叉等交的情況共存于一處或多處。由于9IM模型的基本元素難以分辨這些相交細節(jié)，大量復雜體目標之間的拓撲關系就得不到區(qū)分。關于復雜體目標三維拓撲關系的研究還不夠全面和系統(tǒng)，

以點集拓撲理論［7］為基礎，提出點鄰域模型（Point Neighborhood Model，PNM）。給出點鄰域結構的定義，研究所有可能存在的點鄰域結構類型，設計了描述兩個復雜體目標間三維拓撲關系的編碼。對點鄰域模型與9IM模型進行比較分析，結合實例說明點鄰域模型對三維拓撲關系的描述更精細。

1 點鄰域模型

點鄰域模型的基本思路是通過三維空間中點鄰域內(nèi)各點的歸屬關系刻畫體目標之間的拓撲關系。

基于點集拓撲理論，將體目標建模為三維歐氏空間中的特定無限點集，研究含有洞或由多個部分組成的復雜體之間的三維拓撲關系。通過分析點鄰域中各點歸屬關系的組合，描述兩個體目標之間的三維拓撲關系。其中，某一個點的鄰域結構描述了“靠近”參考點的各點的歸屬關系，以布爾值表示點鄰域中每個點的歸屬關系，對于點鄰域中的各個點就形成了一組確定的布爾值集合。

例如，對于包含體目標A和B的場景，若存在一點p，鄰近它的點都既屬于A又屬于B，就將對應的鄰域結構exist nei in overlap（見定義1）標記為true，這個鄰域結構標記將用于A與B之間拓撲關系的描述。

1.1 點鄰域及其結構

為了描述三維空間拓撲關系，首先定義相關的拓撲與度量概念，給出點鄰域的形式化描述，然后分析所有可能的點鄰域結構。

首先引入必需的拓撲與度量概念和點鄰域定義。令R代表自然數(shù)集合，R＋＝｛x∈R｜x＞0｝。令R3代表三維歐氏空間，存在歐氏距離函數(shù)：

對于任意一點p∈R3和r∈R＋，集合Nr（p）＝｛q∈R3｜d（p，q）≤r｝稱為以p為中心、半徑為r閉包球。令ε代表一個小的正數(shù)值（ε→0），稱閉包球Nε（p）為（包圍）p的鄰域。這樣，可以將p的鄰域認為是一個極小的封閉的包圍球，其中包含了R3中所有距離p最近的點。

本文研究含有兩個體目標的三維場景中各點可能存在的鄰域結構。假定體目標A和B為R3中的點集（即A?R3，B?R3），則對于給定點p∈R3，其鄰域Nε（p）中任一點q（即q∈Nε（p））可能的歸屬關系為以下4種之一：q∈A∧q?B；q?A∧q∈B；q∈A∧q∈B；q?A∧q?B。因此，可以通過某個鄰域中所有點的歸屬關系的組合，來描述該鄰域的歸屬。將這種鄰域歸屬關系的描述結果稱為點鄰域結構。利用某個點所有可能的4種歸屬關系，可以獲得一個鄰域的24－1＝15種可能的歸屬關系組合，組合數(shù)量為15而不是16的原因是一個鄰域中歸屬關系為空（即不屬于這4種關系的任意一種）的情況不存在。換言之，15種鄰域結構涵蓋A和B所處的R3中任意一點的所有可能的歸屬關系。

1.2 點鄰域結構標記

在定義1中，規(guī)定了A和B所處的R3中15種對應的鄰域結構標記。

定義1 令A?R3，B?R3，p∈R3，Nε（p）為p的一個具有極小半徑ε的鄰域。首先為p定義4種歸屬關系標記：

對A和B所處的R3中15種鄰域結構標記定義為：

上述15種鄰域結構標記描述了R3中兩個體目標A與B之間在任意一個點上所有可能的相交情況，圖1給出了對應的示例。例如，圖1（8）表示的標記為true，則存在一個點，其鄰域僅包含屬于前操作對象A的點和屬于后操作對象B的點，進一步的，exist＿nei＿contain＿op1＿op2標記為true，說明A 與B之間為面拓撲相切關系。

圖1 點p的15種可能的鄰域結構Fig.1 The drawing of the 15 neighborhood structures for point p

1.3 三維拓撲關系編碼

前文已為歐氏空間R3中兩個體目標引入了15種鄰域結構標記。這些標記描述了三維歐氏空間R3中兩個體目標每一個點的所有拓撲情況，也就是說通過一個點的鄰域結構，就可以在很低的粒度層次上刻畫兩個體之間的拓撲關系。因而，確定兩個體之間的拓撲關系，只需要獲得所有15種鄰域結構標記的布爾值。更進一步的，假定這些標記按定義1中的順序存儲在F中，則定義2規(guī)定了基于點鄰域結構的兩個體目標之間三維拓撲關系的編碼。

定義2 令A與B為R3中的兩個體目標（A?R3，B?R3），令FV代表對兩個體之間關于第i種（1≤i≤15）鄰域結構標記值的拓撲相交關系進行編碼的函數(shù)，則有：

顯然，采用15bit數(shù)組就可以對A與B之間拓撲關系進行編碼。拓撲關系編碼TRE的形式化描述如下：

TRE（A，B）＝（FV（A，B，0）FV（A，B，1）…FV（A，B，14））

定義2為兩個體目標之間的拓撲關系表達引入15bit二進制表示法。圖2給出3個編碼示例。圖2a顯示了由A與B組成的場景中9個拓撲關系標記為true，分別是exist nei in overlap、exist nei in op1、exist nei in op2、exist nei in ext、exist nei contain overlap op1、exist nei contain overlap op2、exist nei contain op1 ext、exist nei contain op2 ext、exist nei contain op1 op2 overlap ext，并標識了對應的點pi。在圖2b中，另有3個為true的標記，分別對應p8、p11、p14。圖2給出的3種不同拓撲關系分別是編碼為111111001100001的overlap、編碼為111111011110011的overlap with meet on face、編碼為111111001110001的overlap with meet on edge。

圖2 拓撲關系編碼示例Fig.2 Examples of topological relationship encodings

理論上，基于點鄰域模型的三維拓撲關系編碼可以獲得總計215＝32 768種可能的拓撲關系編碼值，即隱含在兩個體目標之間的拓撲關系編碼存在總計32 768種可能。但并非所有編碼表示的拓撲關系都是真實存在的。顯然，當且僅當該拓撲關系可以從含有兩個體目標的現(xiàn)實世界場景中抽象出來時，對應的拓撲編碼才有效。例如，在現(xiàn)實世界中不存在編碼為000000000000000的拓撲關系。由此引發(fā)一些問題：對于兩個復雜體目標的拓撲關系，究竟哪些編碼是有效的？對于兩個簡單體目標的拓撲關系，究竟哪些編碼是有效的？這些有效的拓撲關系編碼數(shù)量有多少？在此，本文僅僅提出了基本的建模思想，這些問題還需更深入的研究。

2 PNM與9IM的比較分析

點鄰域模型（PNM）與9IM模型存在共同的理論基礎，即點集拓撲理論。因此，點鄰域模型與9IM模型對拓撲關系的建模方法僅依賴于點集和拓撲空間，而與空間目標的表達形式無關?；诳臻g目標某一特定表達的拓撲關系模型對同一空間目標的不同表達形式，可能得出不同的拓撲關系判斷結果，因而不具有通用性。例如，基于空間目標維度元素的維度模型［8］高度依賴空間目標的具體表達形式，對于邊界光滑的圓和由相連片段組成近似邊界的圓將得出不同的結果。相比而言，無論空間目標采用怎樣的數(shù)據(jù)表達，基于點集拓撲理論的模型總是適用的，所以，基于點集拓撲理論的空間關系模型相比其他模型更具有一般性。

由于建立在相同的點集拓撲理論基礎上，點鄰域模型與9IM模型在拓撲關系的描述結構、描述方式上存在對應關系。點鄰域模型的“點鄰域結構”與9IM模型的“內(nèi)部—邊界—外部”三元組對應，都是作為拓撲關系描述結構的基本元素。點鄰域的拓撲關系編碼與9IM模型的拓撲關系矩陣對應，都被用作拓撲關系的描述形式。

以一些典型的三維空間拓撲關系為例，對點鄰域模型與9IM模型進行比較分析，以說明點鄰域模型能夠識別兩個體目標之間的三維拓撲關系種類更多。

9IM模型可以區(qū)分8種兩個簡單體目標之間的三維拓撲關系。圖3顯示了這8種拓撲結構與對應的9IM矩陣，并對應地給出了基于點鄰域模型的拓撲關系編碼。對應于不同的拓撲關系，9IM模型和點鄰域模型都給出了唯一的拓撲關系描述結果。

圖3 9IM與PNM均可區(qū)分的8種拓撲關系Fig.3 The 8 topological relationships between two volumes that can be distinguished with both 9IM and PNM

但是，9IM模型只能識別出overlap等主要的拓撲關系，無法區(qū)分相切于一面等同時存在的其他拓撲關系，而點鄰域模型能夠?qū)@些拓撲關系進行正確的描述。對于圖4給出的4種拓撲關系，9IM模型給出的描述矩陣與overlap的描述矩陣相同，而在點鄰域模型中，這4種拓撲關系的編碼是不同的，它們被清晰地區(qū)分開。除了A、B之間的overlap關系，類似于A在外側切于B、A相切于B的內(nèi)側、A與B部分相交同時A與B重合于一面（分別對應圖4所示的第2、3、4種情況）等，點鄰域模型均能夠給以唯一的編碼描述結果將其區(qū)分開。這些實例表明，相比9IM模型，點鄰域模型能夠區(qū)分出兩個復雜體目標之間的三維拓撲關系種類更多。

圖4 9IM無法區(qū)分但PNM可以區(qū)分的4種拓撲關系Fig.4 Topological relationships that can be distinguished with PNM but not 9IM

3 結論

現(xiàn)有拓撲關系描述模型對于三維空間中體目標之間拓撲關系的刻畫不夠精確。基于點集拓撲理論，提出了點鄰域模型，定義了三維空間中點鄰域的空間結構，利用點鄰域結構標記實現(xiàn)對三維拓撲關系的編碼描述。點鄰域模型與9IM模型的比較結果表明，9IM模型能夠區(qū)分出的三維拓撲關系在點鄰域模型中同樣可以區(qū)分描述，9IM模型無法區(qū)分開的三維拓撲關系在點鄰域模型中仍然可以區(qū)分描述，因而點鄰域模型所能夠區(qū)分的三維拓撲關系的種類更多。理論上，點鄰域模型能夠區(qū)分的三維拓撲關系數(shù)量巨大，本文未能對其進行完全分析，這將是今后研究的方向。此外，如何將點鄰域模型推廣到三維空間的曲線、曲面等其他復雜空間目標還需要進一步研究。

［1］ 劉瑜，龔詠喜，張晶，等.地理空間中的空間關系表達和推理［J］.地理與地理信息科學，2007，23（5）：1－7.

［2］ 劉新，劉文寶，李成明.三維空間關系的描述及其定性推理［M］.北京：測繪出版社，2010.

［3］ 吳長彬，閭國年.空間拓撲關系若干問題研究現(xiàn)狀的評析［J］.地球信息科學學報，2010，12（4）：524－531.

［4］ EGENHOFER M J，HERRING J R.A mathematical framework for the definition of topological relationships［A］.BRASSEL K，KISHIMOTO H.Proceedings of 4th International Symposium on Spatial Data Handling［C］.Zurich，Switzerland，1990.803－813.

［5］ 陳軍，郭薇.三維空間實體間拓撲關系的矩陣描述［J］.武漢測繪科技大學學報，1998，23（4）：359－363.

［6］ ZLATANOVA S.On 3Dtopological relationships［A］.Proc.ofthe 11th International Workshop on Database and Expert System Applications［C／OL］.［2008－02－01］.http：／／www.gdmc.nl／alatanova／thesis／html／refer／ps／sz＿asdm.pdf.2011－12－31.

［7］ 熊金城.點集拓撲講義（第4版）［M］.北京：高等教育出版社，2011.

［8］ BILLEN R，ZLATANOVA S，MATHONET P，et al.The dimensional model：A framework to distinguish spatial relationships［A］.Int.Symp.on Advances in Spatial Databases［C］.2002.285－298.