第二節(jié)　基于RCC的空間拓?fù)潢P(guān)系推理

一、RCC的定義

RCC(Region Connection Calculus，區(qū)域連接演算)是Clarke(1981)提出的拓?fù)潢P(guān)系理論，當(dāng)兩個(gè)區(qū)域擁有相同的部分，或者相互接觸時(shí)，這兩個(gè)區(qū)域是連接的，記為C(x，y);否則，這兩個(gè)區(qū)域是相離的，記為C(x，y)。相應(yīng)的公理如下:

公理1:AxC(x，x)。對(duì)于任意的(表達(dá)式中A可以讀成“任意的”，下同)區(qū)域x，其自身總是連接的，即區(qū)域連接關(guān)系具有自反性。

公理2:AxAy(C(x，y)→C(y，x))。對(duì)于任意的區(qū)域x和y，如果x與y連接，則y與x也必然連接(表達(dá)式中的→符號(hào)可以讀成“推出”，下同)，即區(qū)域連接關(guān)系具有對(duì)稱(chēng)性。

公理3:AxAy(Az(C(z，x)→C(z，y))→x=y)。對(duì)于任意的區(qū)域x、y、z，如果當(dāng)且僅當(dāng)z與y連接時(shí)，z與x連接(表達(dá)式中的→符號(hào)可以讀成“蘊(yùn)涵”，下同)，則x與y相等。

上述三個(gè)公理構(gòu)成了基于邏輯的空間拓?fù)潢P(guān)系描述及推理模型的基石?；谏鲜鋈齻€(gè)關(guān)系的邏輯定義可以衍生出更多的目標(biāo)之間的拓?fù)潢P(guān)系，例如:其中，邏輯定義中的符號(hào)表示“非”;E符號(hào)表示“存在”;∧符號(hào)表示合取，可以讀作“并且”。同時(shí)，根據(jù)上述空間關(guān)系集合算子，還可以對(duì)區(qū)域的并、區(qū)域的補(bǔ)集和區(qū)域相交等進(jìn)行邏輯運(yùn)算。在定義的這些關(guān)系中，集合{DC，EC，PO，EQ，TPP，NTPP，TPP^－1，NTPP^－1}(“－1”表示相對(duì)稱(chēng)的一種拓?fù)潢P(guān)系)中包含了8種關(guān)系，這個(gè)集合在理論上被稱(chēng)為RCC8。它描述了任意兩個(gè)區(qū)域之間可能的拓?fù)潢P(guān)系，即DC(相離)、EC(鄰接)、PO(重疊)、EQ(相等)、TPP(內(nèi)切于)、NTPP(包含于)、TPP^－1(被內(nèi)切)、NTPP^－1(被包含)，其含義分別為分離(DisConnected)、外部聯(lián)系(Externally Connected)、部分重疊(Partial Overlap)、相等(Equal)、內(nèi)相切并全包含(Tangential Proper Part)、不內(nèi)相切但全包含(Non-Tangential Proper Part)以及后兩者的對(duì)稱(chēng)關(guān)系。這些關(guān)系與Egenhofer給出的拓?fù)潢P(guān)系有完全相同的語(yǔ)義，如圖3-7所示。

圖3-7　RCC8的8種基本關(guān)系

RCC5比RCC8更粗糙。在RCC5中，不考慮一個(gè)區(qū)域的邊界，即不能區(qū)分DC和EC、TPP和NTPP。這些關(guān)系分別合并后，分別變成RCC5中的不連續(xù)關(guān)系DR和部分關(guān)系PP。這樣，RCC5包含的5種關(guān)系為:DR、PO、PP、PP^－1和EQ。DR包含了DC(相離)和EC(鄰接)，PP包含了TPP(內(nèi)切于)和NTPP(包含于)，PP^－1包含了TPP^－1(被內(nèi)切)和NTPP^－1(被包含)。

二、基于RCC的不確定區(qū)域之間拓?fù)潢P(guān)系的推理

著名的卵-黃(Egg-Yolk)算法(Cohn和Gotts，1996)就是描述不確定區(qū)域拓?fù)潢P(guān)系的方法。把一個(gè)不確定區(qū)域的各個(gè)部分標(biāo)記為卵(egg)、卵黃(yolk)和卵白(white)，它們分別對(duì)應(yīng)于完整的區(qū)域、區(qū)域明確的部分以及區(qū)域完全不確定的部分。用有4個(gè)元素的一個(gè)矩陣可以確定這些關(guān)系。每一個(gè)元素可以用5個(gè)RCC5基本關(guān)系中的一個(gè)來(lái)代替。這個(gè)矩陣的形式為:

這里的y(A)是區(qū)域A的卵黃，e(A)是區(qū)域A的卵;而F函數(shù)表示所存在的關(guān)系。這種模型提供了5⁴=625種不同關(guān)系。但是，由于在這種演算中有很多限制條件，例如，卵黃必須是卵的一個(gè)完全部分、卵黃不能是非空的，所以只能得到不確定區(qū)域之間的46種關(guān)系，見(jiàn)圖3-8。

圖3-8　基于RCC5推理出的“Egg-Yolk”拓?fù)潢P(guān)系圖(Cohn和Gotts，1996)