復(fù)雜體目標(biāo)之間三維拓?fù)潢P(guān)系描述模型

曹雪峰

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

0 引言

空間關(guān)系是地理信息科學(xué)中的重要理論問題，包括拓?fù)潢P(guān)系、方向關(guān)系、距離關(guān)系3類空間關(guān)系的描述和推理［1］。拓?fù)潢P(guān)系描述方法主要有點(diǎn)集拓?fù)浞椒āEM方法、最小邊界矩形法、區(qū)域連接法、CBM方法、符號(hào)投影法、Voronoi圖法、廣義交模型方法、符號(hào)陣列法等［2，3］，基于點(diǎn)集拓?fù)淅碚摰乃慕荒Ｐ停?IM）和九交模型（9IM）是GIS領(lǐng)域中廣泛使用的拓?fù)潢P(guān)系描述方法。

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

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

以點(diǎn)集拓?fù)淅碚摚?］為基礎(chǔ)，提出點(diǎn)鄰域模型（Point Neighborhood Model，PNM）。給出點(diǎn)鄰域結(jié)構(gòu)的定義，研究所有可能存在的點(diǎn)鄰域結(jié)構(gòu)類型，設(shè)計(jì)了描述兩個(gè)復(fù)雜體目標(biāo)間三維拓?fù)潢P(guān)系的編碼。對(duì)點(diǎn)鄰域模型與9IM模型進(jìn)行比較分析，結(jié)合實(shí)例說明點(diǎn)鄰域模型對(duì)三維拓?fù)潢P(guān)系的描述更精細(xì)。

1 點(diǎn)鄰域模型

點(diǎn)鄰域模型的基本思路是通過三維空間中點(diǎn)鄰域內(nèi)各點(diǎn)的歸屬關(guān)系刻畫體目標(biāo)之間的拓?fù)潢P(guān)系。

基于點(diǎn)集拓?fù)淅碚?，將體目標(biāo)建模為三維歐氏空間中的特定無限點(diǎn)集，研究含有洞或由多個(gè)部分組成的復(fù)雜體之間的三維拓?fù)潢P(guān)系。通過分析點(diǎn)鄰域中各點(diǎn)歸屬關(guān)系的組合，描述兩個(gè)體目標(biāo)之間的三維拓?fù)潢P(guān)系。其中，某一個(gè)點(diǎn)的鄰域結(jié)構(gòu)描述了“靠近”參考點(diǎn)的各點(diǎn)的歸屬關(guān)系，以布爾值表示點(diǎn)鄰域中每個(gè)點(diǎn)的歸屬關(guān)系，對(duì)于點(diǎn)鄰域中的各個(gè)點(diǎn)就形成了一組確定的布爾值集合。

例如，對(duì)于包含體目標(biāo)A和B的場(chǎng)景，若存在一點(diǎn)p，鄰近它的點(diǎn)都既屬于A又屬于B，就將對(duì)應(yīng)的鄰域結(jié)構(gòu)exist nei in overlap（見定義1）標(biāo)記為true，這個(gè)鄰域結(jié)構(gòu)標(biāo)記將用于A與B之間拓?fù)潢P(guān)系的描述。

1.1 點(diǎn)鄰域及其結(jié)構(gòu)

為了描述三維空間拓?fù)潢P(guān)系，首先定義相關(guān)的拓?fù)渑c度量概念，給出點(diǎn)鄰域的形式化描述，然后分析所有可能的點(diǎn)鄰域結(jié)構(gòu)。

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

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

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

1.2 點(diǎn)鄰域結(jié)構(gòu)標(biāo)記

在定義1中，規(guī)定了A和B所處的R3中15種對(duì)應(yīng)的鄰域結(jié)構(gòu)標(biāo)記。

定義1 令A(yù)?R3，B?R3，p∈R3，Nε（p）為p的一個(gè)具有極小半徑ε的鄰域。首先為p定義4種歸屬關(guān)系標(biāo)記：

對(duì)A和B所處的R3中15種鄰域結(jié)構(gòu)標(biāo)記定義為：

上述15種鄰域結(jié)構(gòu)標(biāo)記描述了R3中兩個(gè)體目標(biāo)A與B之間在任意一個(gè)點(diǎn)上所有可能的相交情況，圖1給出了對(duì)應(yīng)的示例。例如，圖1（8）表示的標(biāo)記為true，則存在一個(gè)點(diǎn)，其鄰域僅包含屬于前操作對(duì)象A的點(diǎn)和屬于后操作對(duì)象B的點(diǎn)，進(jìn)一步的，exist＿nei＿contain＿op1＿op2標(biāo)記為true，說明A 與B之間為面拓?fù)湎嗲嘘P(guān)系。

圖1 點(diǎn)p的15種可能的鄰域結(jié)構(gòu)Fig.1 The drawing of the 15 neighborhood structures for point p

1.3 三維拓?fù)潢P(guān)系編碼

前文已為歐氏空間R3中兩個(gè)體目標(biāo)引入了15種鄰域結(jié)構(gòu)標(biāo)記。這些標(biāo)記描述了三維歐氏空間R3中兩個(gè)體目標(biāo)每一個(gè)點(diǎn)的所有拓?fù)淝闆r，也就是說通過一個(gè)點(diǎn)的鄰域結(jié)構(gòu)，就可以在很低的粒度層次上刻畫兩個(gè)體之間的拓?fù)潢P(guān)系。因而，確定兩個(gè)體之間的拓?fù)潢P(guān)系，只需要獲得所有15種鄰域結(jié)構(gòu)標(biāo)記的布爾值。更進(jìn)一步的，假定這些標(biāo)記按定義1中的順序存儲(chǔ)在F中，則定義2規(guī)定了基于點(diǎn)鄰域結(jié)構(gòu)的兩個(gè)體目標(biāo)之間三維拓?fù)潢P(guān)系的編碼。

定義2 令A(yù)與B為R3中的兩個(gè)體目標(biāo)（A?R3，B?R3），令FV代表對(duì)兩個(gè)體之間關(guān)于第i種（1≤i≤15）鄰域結(jié)構(gòu)標(biāo)記值的拓?fù)湎嘟魂P(guān)系進(jìn)行編碼的函數(shù)，則有：

顯然，采用15bit數(shù)組就可以對(duì)A與B之間拓?fù)潢P(guān)系進(jìn)行編碼。拓?fù)潢P(guān)系編碼TRE的形式化描述如下：

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

定義2為兩個(gè)體目標(biāo)之間的拓?fù)潢P(guān)系表達(dá)引入15bit二進(jìn)制表示法。圖2給出3個(gè)編碼示例。圖2a顯示了由A與B組成的場(chǎng)景中9個(gè)拓?fù)潢P(guān)系標(biāo)記為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，并標(biāo)識(shí)了對(duì)應(yīng)的點(diǎn)pi。在圖2b中，另有3個(gè)為true的標(biāo)記，分別對(duì)應(yīng)p8、p11、p14。圖2給出的3種不同拓?fù)潢P(guān)系分別是編碼為111111001100001的overlap、編碼為111111011110011的overlap with meet on face、編碼為111111001110001的overlap with meet on edge。

圖2 拓?fù)潢P(guān)系編碼示例Fig.2 Examples of topological relationship encodings

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

2 PNM與9IM的比較分析

點(diǎn)鄰域模型（PNM）與9IM模型存在共同的理論基礎(chǔ)，即點(diǎn)集拓?fù)淅碚?。因此，點(diǎn)鄰域模型與9IM模型對(duì)拓?fù)潢P(guān)系的建模方法僅依賴于點(diǎn)集和拓?fù)淇臻g，而與空間目標(biāo)的表達(dá)形式無關(guān)。基于空間目標(biāo)某一特定表達(dá)的拓?fù)潢P(guān)系模型對(duì)同一空間目標(biāo)的不同表達(dá)形式，可能得出不同的拓?fù)潢P(guān)系判斷結(jié)果，因而不具有通用性。例如，基于空間目標(biāo)維度元素的維度模型［8］高度依賴空間目標(biāo)的具體表達(dá)形式，對(duì)于邊界光滑的圓和由相連片段組成近似邊界的圓將得出不同的結(jié)果。相比而言，無論空間目標(biāo)采用怎樣的數(shù)據(jù)表達(dá)，基于點(diǎn)集拓?fù)淅碚摰哪Ｐ涂偸沁m用的，所以，基于點(diǎn)集拓?fù)淅碚摰目臻g關(guān)系模型相比其他模型更具有一般性。

由于建立在相同的點(diǎn)集拓?fù)淅碚摶A(chǔ)上，點(diǎn)鄰域模型與9IM模型在拓?fù)潢P(guān)系的描述結(jié)構(gòu)、描述方式上存在對(duì)應(yīng)關(guān)系。點(diǎn)鄰域模型的“點(diǎn)鄰域結(jié)構(gòu)”與9IM模型的“內(nèi)部—邊界—外部”三元組對(duì)應(yīng)，都是作為拓?fù)潢P(guān)系描述結(jié)構(gòu)的基本元素。點(diǎn)鄰域的拓?fù)潢P(guān)系編碼與9IM模型的拓?fù)潢P(guān)系矩陣對(duì)應(yīng)，都被用作拓?fù)潢P(guān)系的描述形式。

以一些典型的三維空間拓?fù)潢P(guān)系為例，對(duì)點(diǎn)鄰域模型與9IM模型進(jìn)行比較分析，以說明點(diǎn)鄰域模型能夠識(shí)別兩個(gè)體目標(biāo)之間的三維拓?fù)潢P(guān)系種類更多。

9IM模型可以區(qū)分8種兩個(gè)簡(jiǎn)單體目標(biāo)之間的三維拓?fù)潢P(guān)系。圖3顯示了這8種拓?fù)浣Y(jié)構(gòu)與對(duì)應(yīng)的9IM矩陣，并對(duì)應(yīng)地給出了基于點(diǎn)鄰域模型的拓?fù)潢P(guān)系編碼。對(duì)應(yīng)于不同的拓?fù)潢P(guān)系，9IM模型和點(diǎn)鄰域模型都給出了唯一的拓?fù)潢P(guān)系描述結(jié)果。

圖3 9IM與PNM均可區(qū)分的8種拓?fù)潢P(guān)系Fig.3 The 8 topological relationships between two volumes that can be distinguished with both 9IM and PNM

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

圖4 9IM無法區(qū)分但PNM可以區(qū)分的4種拓?fù)潢P(guān)系Fig.4 Topological relationships that can be distinguished with PNM but not 9IM

3 結(jié)論

現(xiàn)有拓?fù)潢P(guān)系描述模型對(duì)于三維空間中體目標(biāo)之間拓?fù)潢P(guān)系的刻畫不夠精確?；邳c(diǎn)集拓?fù)淅碚摚岢隽它c(diǎn)鄰域模型，定義了三維空間中點(diǎn)鄰域的空間結(jié)構(gòu)，利用點(diǎn)鄰域結(jié)構(gòu)標(biāo)記實(shí)現(xiàn)對(duì)三維拓?fù)潢P(guān)系的編碼描述。點(diǎn)鄰域模型與9IM模型的比較結(jié)果表明，9IM模型能夠區(qū)分出的三維拓?fù)潢P(guān)系在點(diǎn)鄰域模型中同樣可以區(qū)分描述，9IM模型無法區(qū)分開的三維拓?fù)潢P(guān)系在點(diǎn)鄰域模型中仍然可以區(qū)分描述，因而點(diǎn)鄰域模型所能夠區(qū)分的三維拓?fù)潢P(guān)系的種類更多。理論上，點(diǎn)鄰域模型能夠區(qū)分的三維拓?fù)潢P(guān)系數(shù)量巨大，本文未能對(duì)其進(jìn)行完全分析，這將是今后研究的方向。此外，如何將點(diǎn)鄰域模型推廣到三維空間的曲線、曲面等其他復(fù)雜空間目標(biāo)還需要進(jìn)一步研究。

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

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

［3］ 吳長(zhǎng)彬，閭國(guó)年.空間拓?fù)潢P(guān)系若干問題研究現(xiàn)狀的評(píng)析［J］.地球信息科學(xué)學(xué)報(bào)，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］ 陳軍，郭薇.三維空間實(shí)體間拓?fù)潢P(guān)系的矩陣描述［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，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］ 熊金城.點(diǎn)集拓?fù)渲v義（第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.