王占剛，屈紅剛，王想紅

1. 中國礦業(yè)大學(xué)地球科學(xué)與測繪工程學(xué)院，北京 100083； 2. 中國地質(zhì)調(diào)查局發(fā)展研究中心,北京 100037

描述復(fù)雜對象間的拓撲關(guān)系是地理信息科學(xué)中的一個基礎(chǔ)性研究問題。面域?qū)ο笫亲钪匾目臻g對象之一，結(jié)構(gòu)構(gòu)成上可表現(xiàn)為多部分構(gòu)成，可以帶洞以及島[1-6]。目前描述面域?qū)ο箝g拓撲關(guān)系的模型主要有針對簡單面域的4交，9交模型[7-8]和區(qū)域鏈接法(region connection calculus,RCC)[9-10]等方法，擴展9交模型的方法如9+交集模型[11]、V9I模型[12-13]，以及直接針對存在帶洞、多部分構(gòu)成復(fù)雜面域的方法如關(guān)系矩陣表[2,6]、擴展9-交集模型[14-15]、16交模型[5]及25交模型[5,16]等。

以上拓撲關(guān)系描述模型的一般特點是，基于點集拓撲理論根據(jù)復(fù)雜對象的結(jié)構(gòu)構(gòu)成進行對象或者點集分解，用已知對象或者點集間的關(guān)系描述拓撲關(guān)系。對比傳統(tǒng)的Egenhofer 9交模型[7-8]，采用拓撲點集或者對象分解的方法分辨拓撲關(guān)系的能力普遍提高，并廣泛用于空間數(shù)據(jù)推理[6,17]、多尺度空間數(shù)據(jù)庫或復(fù)雜對象的拓撲變化識別[18]、不同分辨率拓撲一致性評價[19]等。然而，拓撲關(guān)系分辨能力高的描述模型也使得推導(dǎo)或者推理拓撲關(guān)系變得更加復(fù)雜，比如如何推導(dǎo)出兩個復(fù)雜面域間所有可能的拓撲關(guān)系。相關(guān)的研究主要針對具有簡單結(jié)構(gòu)的面域進行分析，如帶洞區(qū)域和簡單區(qū)域拓撲關(guān)系[20]、凹形區(qū)域和帶單洞區(qū)域間拓撲關(guān)系的表示[21]。文獻[22]提出的關(guān)系矩陣表方法可以處理任意復(fù)雜面域的情況，可精細表達拓撲關(guān)系，但是關(guān)系矩陣表結(jié)構(gòu)復(fù)雜，不便于實現(xiàn)空間查詢和分析，這就需要將其轉(zhuǎn)換為其他模型或者拓撲關(guān)系謂詞。文獻[23]和[24]利用推理組合表推導(dǎo)多部分構(gòu)成以及帶洞面域間的拓撲關(guān)系，但這種方法只限于處理簡單面域，推導(dǎo)結(jié)果只能屬于8種基本謂詞之一，不能給出所有可能的拓撲關(guān)系。同時，不同拓撲關(guān)系描述模型之間的關(guān)系以及轉(zhuǎn)換也缺少系統(tǒng)研究。

本文分析了6種描述帶洞面域拓撲關(guān)系的模型以及之間的聯(lián)系，基于25交模型提出了一種利用簡單面域間拓撲關(guān)系推導(dǎo)復(fù)雜面域間拓撲關(guān)系的方法，實現(xiàn)了拓撲關(guān)系描述模型之間的轉(zhuǎn)換，應(yīng)用于推導(dǎo)和推理具有特定結(jié)構(gòu)復(fù)雜面域間的所有拓撲關(guān)系。

1 帶洞面域定義

1.1 帶洞面域的構(gòu)成結(jié)構(gòu)

一個帶洞面域?qū)⒍S空間R2從內(nèi)向外可劃分為5個拓撲子集(如圖1)：Ao是面域的內(nèi)部，內(nèi)外部A-1由所有洞的內(nèi)部構(gòu)成，外外部A+1是除去A-1的面域外部點集，內(nèi)邊界?A-1由分割A(yù)o和A-1的邊界構(gòu)成，外邊界?A+1是除去?A-1的面域邊界部分，分割外外部空間。其中，A+1，?A+1和Ao均不能為空，?A-1和A-1可能為空且滿足(?A-1≠?∧A-1≠?)∨(?A-1=?∧A-1=?)。復(fù)雜面域的邊界?A=?A+1∪?A-1，所有的洞Ah=A-1∪?A-1。

圖1 復(fù)雜面域的5個拓撲子集 Fig.1 Five topologically distinct and mutually exclusive parts

1.2 復(fù)雜面域分解與正則表達式

參考文獻[3]和OpenGIS[25]相關(guān)定義，復(fù)雜面域既可以是簡單面域，也可以是帶洞簡單面域或者多部分面域及其組合[26]。對于洞內(nèi)不帶洞的復(fù)雜面域?qū)ο?，其面域分解和表達定義如下：

通過定義1和定義2，利用“+”和“-”形成一個正則表達式表示復(fù)雜面域的分解過程，且正則表達式可進一步采用語法樹進行先序遍歷[26]。比如，帶洞簡單面域可表示為A=A1-A2，多部分面域可記為A=A1+…+An。正則表達式反映了各個簡單對象之間的包含關(guān)系以及相離關(guān)系。

2 帶洞面域的拓撲關(guān)系描述模型

本文主要分析基于對象分解和點集拓撲理論的帶洞面域間拓撲關(guān)系描述模型，下文分別介紹6種主要模型以及其聯(lián)系。

2.1 主要模型

2.1.1 經(jīng)典9交模型

Egenhofer 9交模型[7-8](本文稱為經(jīng)典9交模型，簡稱9I)采用對象的內(nèi)部(o)、邊界(?)和外部(+)三個子集間的交集描述拓撲關(guān)系，其定義為

2.1.2 寬邊界擴展9交模型[4]

該模型(簡稱E9I)主要針對邊界不確定性區(qū)域，邊界采用寬邊界(Δ)描述。其定義為

2.1.3 關(guān)系矩陣表

該方法將帶洞面域分解為簡單面域，利用簡單面域間的拓撲關(guān)系描述整體對象間的拓撲關(guān)系。帶洞面域A的簡單面域集合為WA={A1,A2,…，Ai，…,Am}；B的簡單面域集合為WB={B1,B2,…，Bi，…,Bn}，其中m≥1,n≥1。其定義為

R(A,B)=Tijm×n

式中，Tij=R9(Ai,Bj)，i=1,2,…，m;j=1,2,…，n。表中每個元素是簡單面域間的拓撲關(guān)系，采用8種基本拓撲關(guān)系，能描述的拓撲關(guān)系個數(shù)為8m×n。

2.1.4 擴展9交集模型[14-15]

該方法(簡稱D9I)利用A、B分解后簡單面域間的內(nèi)部、邊界和外部交集構(gòu)建一個mn+1位的二進制編碼代替經(jīng)典9交模型中的相應(yīng)交集。其定義為

2.1.5 4元組模型[18,27]

該方法(簡稱4-Tuple)是對關(guān)系矩陣表的簡化，將面域?qū)ο蟮膹V義面域和洞進行了合并，通過合并后的面域構(gòu)建關(guān)系矩陣表，此表中僅有4個元素。其定義為

R(A,B)=(T1,T2,T3,T4)

2.1.6 25交模型[5,16]

25交模型是通過兩個面域A、B的5個拓撲子集的交集來描述拓撲關(guān)系，表示為一個5×5的0/1型25交矩陣R25(A,B)

2.2 對比分析

根據(jù)上文不同帶洞面域間拓撲關(guān)系描述模型的定義，本文從模型構(gòu)建方式、對洞的表達、存儲方式推理分析及拓撲關(guān)系分辨能力5個方面進行了對比分析，如表1所示。模型構(gòu)建方式主要分為基于點集拓撲構(gòu)建交集矩陣和利用對象分解構(gòu)建對象交集矩陣。不同模型對洞的表達以及對象構(gòu)成細節(jié)描述不一樣，也使得它們對拓撲關(guān)系的分辨能力不同，當(dāng)然描述的細節(jié)信息越多，所需存儲空間相對也越多。對于關(guān)系矩陣表模型，其表內(nèi)每個元素僅需要描述簡單面域間的拓撲關(guān)系，即8種可能性，因此二進制編碼的存儲位數(shù)最多是3mn。分辨能力高的模型，一般只能給出所能描述拓撲關(guān)系可能性的理論數(shù)字，目前研究只是給出了經(jīng)典9交模型所能描述復(fù)雜面域間的所有33種拓撲關(guān)系。其他模型由于自身復(fù)雜性還沒有給出描述面域間拓撲關(guān)系個數(shù)的準確數(shù)值。在拓撲關(guān)系推理方面，分辨能力低的模型由于無法表達面域的細節(jié)構(gòu)成，一般只能給出簡單對象之間的推理組合表，而關(guān)系矩陣表則可適用于任意復(fù)雜面域間的拓撲關(guān)系推理，相關(guān)內(nèi)容在4.1節(jié)闡述。

表1 不同模型對比

2.3 不同模型之間的轉(zhuǎn)換

根據(jù)以上6種模型的定義，盡管可以采用基于點集拓撲和對象分解的方法構(gòu)建拓撲關(guān)系描述模型，但是當(dāng)所表達的面域細節(jié)信息相同時，不同模型對拓撲關(guān)系的描述是等價的，比如關(guān)系矩陣表和擴展9交模型、25交模型和4元組模型對拓撲關(guān)系的分辨能力相同，描述是等價的(第3部分給出等價證明)。同時，不同模型之間可以轉(zhuǎn)換：相同分辨能力的模型之間可以轉(zhuǎn)換，分辨能力高的模型可以轉(zhuǎn)換為分辨能力低的模型。這種轉(zhuǎn)換可直接實現(xiàn)也可以間接實現(xiàn)，如圖2。直接轉(zhuǎn)換是根據(jù)定義無須進行復(fù)雜的推理計算即可實現(xiàn)，比如25交模型轉(zhuǎn)換為寬邊界9交模型以及25交模型轉(zhuǎn)換為4元組模型等；間接轉(zhuǎn)換則需要進行推理計算一些未知信息，比如關(guān)系矩陣表和4元組模型都無法直接給出整體面域的內(nèi)部交集Ao∩Bo信息，所以無法直接轉(zhuǎn)換為25交模型。本文第3部分基于25交模型給出了實現(xiàn)間接轉(zhuǎn)換的方法。

圖2 不同模型之間的轉(zhuǎn)換Fig.2 Conversion of different models

3 不同拓撲關(guān)系模型間的轉(zhuǎn)換推導(dǎo)

參考文獻[26]對復(fù)雜區(qū)域?qū)ο笸負潢P(guān)系分解與計算的思路，比如給定兩個面域A和B，其中B=B1+B2B，對象分解為B1和B2，拓撲關(guān)系R(A,B)可由R(A,B1)和R(A,B2)計算得到。這就需要研究給出基于25交模型的拓撲關(guān)系分解計算方法，然后利用拓撲關(guān)系分解計算方法推導(dǎo)不同拓撲關(guān)系描述模型之間的轉(zhuǎn)換。

3.1 基于25交模型的拓撲關(guān)系分解計算

從上述復(fù)雜面域的分解可知，當(dāng)給定兩個面域A和B，就可以將其分解為簡單面域表達的形式。當(dāng)推導(dǎo)其25交關(guān)系矩陣R25(A,B)時，根據(jù)面域?qū)ο蟮姆纸?，將拓撲關(guān)系的推導(dǎo)也相應(yīng)分解，進而將復(fù)雜對象拓撲關(guān)系的推導(dǎo)轉(zhuǎn)化為對簡單面域間拓撲關(guān)系的處理。這其中最主要的問題是如何根據(jù)分解后對象間的已知拓撲關(guān)系推導(dǎo)計算出A和B的拓撲關(guān)系。為此，本文提出兩個主要25交關(guān)系矩操作算子。

若復(fù)雜面域B=B1+B2，B1與B2相離，則復(fù)雜面域A和B的25交關(guān)系矩陣加布爾操作公式為

R25(A,B1+B2)=R25(A,B1)R25(A,B2)=

證明：由于B=B1+B2，可得

B+1= R2-(B-1∪?B-1∪Bo∪?B+1)=

設(shè)Ma={A-1，?A-1，Ao，?A+1，A+1}，?a∈Ma可得

R25(A,B)是0/1布爾型矩陣，需要將上述集合的并和交操作直接轉(zhuǎn)化為邏輯或和邏輯與。顯然，集合的并和邏輯或?qū)?yīng)，且運算不會產(chǎn)生歧義，故

證明：由于B=B1-B2，可得

設(shè)Ma={A-1，?A-1，Ao，?A+1，A+1}，?a∈Ma可得：

將上述集合的并和交操作直接轉(zhuǎn)化為邏輯或和邏輯與，形成R25(A,B)的0/1布爾型矩陣形式

參考文獻[26]，根據(jù)25交模型的特點以及轉(zhuǎn)置矩陣RT的性質(zhì)，可知R25(A,B)=[R25(B,A)]T。因此，當(dāng)公式發(fā)生歧義時，分別計算R25(A,B)和R25(B,A)，存在R25(A,B)≠[R25(B,A)]T的情況。根據(jù)這一特性消除25交關(guān)系矩操作算子的歧義性。

3.2 不同模型的轉(zhuǎn)換證明

當(dāng)給定兩個面域A和B將其分解為簡單面域表達的形式，并采用關(guān)系矩陣表描述其拓撲關(guān)系，則利用上述兩個25交關(guān)系矩操作算子，即可將關(guān)系矩陣表轉(zhuǎn)換為25交模型。這樣可實現(xiàn)分辨能力高的模型向分辨能力低的模型進行轉(zhuǎn)換。下面重點討論不同模型的等價性。

證明25交模型和4元組模型是等價的。

首先，25交模型可以直接轉(zhuǎn)換為4元組模型。

4元組模型由整體廣義面域和洞構(gòu)成，表示為A=AE-AH，B=BE-BH。與5個拓撲子集的關(guān)系為

AE=AH∪Ao∪?A+1AH=A-1∪?A-1，

BE=BH∪Bo∪?B+1BH=B-1∪?B-1

采用9交模型表示每一個元組T1=R9(AE,BE)，T2=R9(AE,BH)，T3=R9(AH,BE)，T4=R9(AH,BH)。則面域的內(nèi)部、邊界和外部與5個拓撲子集的關(guān)系為

以T2=R9(AE,BH)為例

(?A+1∩Bo)∪(?A+1∩?B+1)∪(?A+1∩B+1)

可見，利用25交模型可以得到4元組模型中的各個交集值，而且一個25交矩陣只能轉(zhuǎn)換為一個對應(yīng)的4元組模型。因此，25交模型可以直接轉(zhuǎn)換為4元組模型。

其次，4元組模型可間接轉(zhuǎn)換為25交模型。

R25(AE-AH,BE-BH)=

由于AE、AH、BE、BH都不帶洞，此時可利用9交矩陣可以構(gòu)建出25交模型(內(nèi)外部和內(nèi)邊界為空集合)，進而得到R25(A,B)=R25(AE-AH,BE-BH)。而且，一個對應(yīng)的4元組模型只能轉(zhuǎn)換為一個25交矩陣。因此，4元組模型可通過一定計算間接得到25交模型。

最后，通過以上分析，4元組模型和25交模型可相互轉(zhuǎn)換，而且轉(zhuǎn)換是唯一的，因此，對特定拓撲關(guān)系，其描述是等價的。證明關(guān)系矩陣表模型和擴展9交集模型是等價的。

從關(guān)系矩陣表模型和擴展9交集模型的定義看，兩種模型都是利用了帶洞面域?qū)ο蠓纸夂蟮乃泻唵蚊嬗虻膬?nèi)部、邊界和外部交集信息，所以所能描述拓撲關(guān)系的信息量是一致的，這些信息只是存儲在了不同的二進制編碼位置上。兩種模型的差異在于，擴展9交集模型外加了一個整體面域的9交拓撲關(guān)系?；?5交模型的拓撲關(guān)系分解計算可知，通過關(guān)系矩陣表模型可以轉(zhuǎn)換為唯一一個25交模型以及進一步得到9交模型，這也說明整體面域的9交模型不是獨立信息，可由其他信息推導(dǎo)出來的。因此，擴展9交集模型外加的9交拓撲關(guān)系在于方便獲知整體面域間的拓撲關(guān)系，并沒有增加模型的拓撲關(guān)系分辨能力。由于兩個模型所記錄的細節(jié)信息一致，故其對拓撲關(guān)系的描述是等價的。

4 基于25交模型的拓撲關(guān)系分析實例

4.1 具有特定結(jié)構(gòu)的帶洞面域拓撲關(guān)系推導(dǎo)

利用25交模型在模型轉(zhuǎn)換過程中的“橋梁”作用，則可推導(dǎo)出采用不同模型的所有可能拓撲關(guān)系以及拓撲關(guān)系推理。

利用關(guān)系矩陣表描述復(fù)雜面域間的精細拓撲關(guān)系。通過A、B與B、C的關(guān)系矩陣表推理A、C關(guān)系矩陣表的公式[6,29]為

R25(Ai,Cj)∈M(Ai,Cj)=∩Bk∈WBR25(Ai,Bk)·R25(Bk,Cj)，其中，R25取值為基本拓撲關(guān)系,Cj∈WC,Ai∈WA。根據(jù)復(fù)雜面域的定義，25交模型推理中剔除不合理拓撲關(guān)系的條件為[26]

R25(Ai,Aj)=contain∈M(Ai,Aj)=

∩Bk∈WBR25(Ai,Bk)·R25(Bk,Aj)

R25(Ai,Aj)=disjoint∈M(Ai,Aj)=

∩Bk∈WBR25(Ai,Bk)·R25(Bk,Aj)

R25(Bi,Bj)=contain∈M(Bi,Bj)=

∩Ak∈WAR25(Bi,Ak)·R25(Ak,Bj)

R25(Bi,Bj)=disjoint∈M(Bi,Bj)=

∩Ak∈WAR25(Bi,Ak)·R25(Ak,Bj)

在以上限定條件下，利用關(guān)系矩陣表描述精細拓撲關(guān)系以及拓撲關(guān)系推理，基于25交模型的拓撲關(guān)系分解計算得到不同分辨能力的拓撲關(guān)系模型。

比如，給定4個已知構(gòu)成的面域?qū)ο驛=A1-A2，B=B1+(B2-B3)，C=C1+(C2-C3)和D=D1-D2，如圖3所示。利用關(guān)系矩陣表，25交模型和經(jīng)典9交模型推導(dǎo)的所有拓撲關(guān)系見表2。

當(dāng)A、B與B、C的具體拓撲關(guān)系如圖4所示，則采用關(guān)系矩陣表推理得到A、C的可能拓撲關(guān)系為15種，如表3所示，將這些關(guān)系轉(zhuǎn)換為25交模型，可得到5種拓撲關(guān)系，如圖5所示。其中8種基本拓撲關(guān)系disjoint，meet，contain，cover，inside，coverby，equal和overlap的縮寫為d,m,cn,cv,i,cb,e,o。

圖3 4個面域?qū)ο螅篈,B,C和DFig.3 Four regions:A,B,C and D

表2 A,B,C和D間的所有拓撲關(guān)系

圖4 A,B與B,C的拓撲關(guān)系Fig.4 Topological relations of A and B，and B and C

表3 A,C推理結(jié)果

圖5 A、C推理結(jié)果：5種25交拓撲關(guān)系Fig.5 Reasoning results：5 relations based on 25I

4.2 實例分析

中國行政區(qū)化上存在大量“飛地”現(xiàn)象。如圖6所示，天津市寧河區(qū)，其行政區(qū)域表現(xiàn)為帶洞復(fù)雜區(qū)域?qū)ο蟆Ｔ谝恍?yīng)用中需要區(qū)分洞內(nèi)外空間關(guān)系，例如利用行政區(qū)和礦權(quán)界線的25交拓撲關(guān)系可以使得礦權(quán)隸屬分類更加詳細。行政單元邊界和單一礦權(quán)區(qū)用簡單區(qū)域表示，采用正則表達式構(gòu)成各行政區(qū)和復(fù)合礦權(quán)區(qū)。礦權(quán)分析系統(tǒng)只記錄行政單元邊界和單一礦權(quán)邊界簡單區(qū)域間的拓撲關(guān)系。復(fù)雜區(qū)域間拓撲關(guān)系通過計算得到。寧河區(qū)A=A1-A2,礦權(quán)區(qū)B=B1+B2,則A和B的拓撲關(guān)系為

R25(A,B)=R25(A1-A2,B1+B2)=

R25(A1-A2,B1)R25(A1-A2,B2)=

[R25(B1,A1-A2)]T[R25(B2,A1-A2)]T=

圖6 帶洞區(qū)域?qū)ο蟮耐負潢P(guān)系描述實例Fig.6 An example of the topological relations between regions with holes

相對于9交模型，25交模型更好地描述了該礦區(qū)與寧河區(qū)及飛地之間的關(guān)系。此外，當(dāng)單一礦權(quán)區(qū)域的所有人發(fā)生變化，由于簡單區(qū)域之間的拓撲關(guān)系并沒有變化，礦權(quán)區(qū)與行政區(qū)間的拓撲關(guān)系按本文方法實時計算得到。

5 結(jié) 論

本文將帶洞復(fù)雜面域分解為有限個簡單面域并采用正則表達式進行結(jié)構(gòu)說明，分析了6種不同表達帶洞面域的拓撲關(guān)系描述模型。分析證明，關(guān)系矩陣表和擴展9交模型、25交模型和4元組模型實質(zhì)上對拓撲關(guān)系的分辨能力相同?；?5交模型實現(xiàn)了拓撲關(guān)系分辨能力高的模型向分辨能力低的模型的轉(zhuǎn)換，這樣可方便實現(xiàn)對具有特定結(jié)構(gòu)的復(fù)雜面域間拓撲關(guān)系的推導(dǎo)。

同時，文獻[2]提出的關(guān)系矩陣表可用于任意復(fù)雜面域?qū)ο箝g拓撲關(guān)系的精細表達，并可進行拓撲關(guān)系的有效推導(dǎo)和推理。25交模型和4元組模型是對該方法的一種概化，主要是對洞整體信息進行描述，不關(guān)注洞的細節(jié)構(gòu)成。通過對比分析也發(fā)現(xiàn)，一方面25交模型比4元組模型存儲空間更少；另一方面利用本文定義的25交矩陣操作算子可直接基于矩陣計算實現(xiàn)復(fù)雜面域間拓撲關(guān)系的分析，而基于4元組模型尚不能實現(xiàn)該功能。