復(fù)雜區(qū)域?qū)ο笸負(fù)潢P(guān)系分解與計算

王占剛，杜群樂，王想紅

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

復(fù)雜區(qū)域?qū)ο笸負(fù)潢P(guān)系分解與計算

王占剛1，杜群樂1，王想紅2

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

本文提出了基于9交矩陣的拓?fù)潢P(guān)系計算方法，將復(fù)雜區(qū)域分解有限個簡單區(qū)域，采用正則表達(dá)式描述其多部分和洞構(gòu)成，通過定義兩個9交關(guān)系矩陣操作算子，利用分解區(qū)域間的拓?fù)潢P(guān)系直接計算復(fù)雜區(qū)域間的9交關(guān)系矩陣。詳細(xì)證明和分析了兩個操作算子的不成立條件以及消除不成立條件的方法。結(jié)合關(guān)系矩陣表法拓?fù)潢P(guān)系的推導(dǎo)和推理過程，操作算子可用于推導(dǎo)已知結(jié)構(gòu)復(fù)雜區(qū)域間的所有可能9交拓?fù)潢P(guān)系。同時，9交關(guān)系矩陣操作算子依賴復(fù)雜區(qū)域的定義，不適用于所有區(qū)域?qū)ο蟆?/p>

地理信息系統(tǒng);復(fù)雜區(qū)域;拓?fù)潢P(guān)系;9-交模型

空間關(guān)系是空間數(shù)據(jù)組織、查詢、分析和推理的基礎(chǔ)，一直受到國內(nèi)外地理信息系統(tǒng)(GIS)研究方面的廣泛關(guān)注[1-3]。拓?fù)潢P(guān)系是其中最重要的一種空間關(guān)系，描述兩個空間對象在連續(xù)空間變換(旋轉(zhuǎn)、縮放、平移等)下的拓?fù)洳蛔冃訹3-5]。許多方法被用來描述空間對象之間的拓?fù)潢P(guān)系，比如9交模型[5-6]和區(qū)域鏈接法(region connection calculus，RCC)[7-8]。這些方法最初只是描述簡單點、簡單線和簡單區(qū)域等空間對象之間的拓?fù)潢P(guān)系。隨著空間信息獲取與更新能力的飛速發(fā)展，空間數(shù)據(jù)的復(fù)雜程度也在增加。復(fù)雜區(qū)域?qū)ο蠖x已有大量研究[9-13]，主要包括有確定邊界的區(qū)域?qū)ο蠛蛶Р淮_定邊界的區(qū)域?qū)ο?模糊對象)。本文主要討論有確定邊界區(qū)域?qū)ο箝g的拓?fù)潢P(guān)系計算問題。

針對復(fù)雜區(qū)域拓?fù)潢P(guān)系的描述，9交模型仍是廣泛使用的一種方法，并被OpenGIS采用[12]。文獻(xiàn)[13—14]給出了確定邊界復(fù)雜區(qū)域間的33種9交拓?fù)潢P(guān)系。同時，研究人員也提出了大量擴(kuò)展9交模型的方法，比如9+交集模型[15]，V9I模型[16-17]、擴(kuò)展9交模型[18-20]、25交模型[21]等。這些方法根據(jù)復(fù)雜對象的特點改變9交矩陣中各個元素的含義進(jìn)而形成新矩陣。文獻(xiàn)[4，22]采用關(guān)系矩陣表精細(xì)描述復(fù)雜區(qū)域間的拓?fù)潢P(guān)系，主要將復(fù)雜區(qū)域分解為有限個簡單區(qū)域，這些簡單區(qū)域按一定關(guān)系組合構(gòu)成復(fù)雜區(qū)域的表達(dá)形式，例如帶一個洞區(qū)域，可以分解為兩個簡單區(qū)域，一是洞區(qū)域，另一個是包含洞的廣義區(qū)域。關(guān)系矩陣表詳細(xì)描述了分解后兩兩簡單區(qū)域間的拓?fù)潢P(guān)系，簡單區(qū)域間僅存在8種基本拓?fù)潢P(guān)系。然而，在空間查詢中，關(guān)系矩陣表不能像其他拓?fù)潢P(guān)系描述模型一樣方便使用，需要將其轉(zhuǎn)化為目前GIS領(lǐng)域熟知的拓?fù)洳樵冎^詞或者其他交集模型[23]。如OpenGIS中提供了兩種查詢方法[12]，一種是面向語義的查詢謂詞，比如Overlap等；另一種是基于9交矩陣的查詢。其核心問題是如何利用簡單區(qū)域間的8種基本拓?fù)潢P(guān)系計算出復(fù)雜區(qū)域間的拓?fù)潢P(guān)系。文獻(xiàn)[24—25]利用8種基本拓?fù)潢P(guān)系謂詞形成推理組合表來計算復(fù)雜區(qū)域間的拓?fù)潢P(guān)系謂詞，但是此類方法不能直接計算出9交矩陣。

本文提出了基于9交矩陣的拓?fù)潢P(guān)系計算方法，將復(fù)雜區(qū)域分解有限個簡單區(qū)域，采用正則表達(dá)式描述其多部分和洞構(gòu)成，通過定義兩個9交關(guān)系矩陣操作算子，利用分解區(qū)域間的拓?fù)潢P(guān)系直接計算復(fù)雜區(qū)域間的9交關(guān)系矩陣。

1 相關(guān)定義

1.1 復(fù)雜區(qū)域

本文定義基于文獻(xiàn)[11]、OpenGIS[12]和文獻(xiàn)[13]中相關(guān)描述。復(fù)雜區(qū)域?qū)ο笫嵌x在二維空間R2上帶確定邊界的正則閉集合，由有限個連通子集構(gòu)成，其結(jié)構(gòu)定義如下：

定義1：簡單區(qū)域同胚于一個圓盤，具有完全連通的內(nèi)部、邊界和外部，如圖1(a)。

定義2：帶洞簡單區(qū)域A是由一個外部廣義區(qū)域A0減去n(n>0)個洞區(qū)域Ai構(gòu)成，如圖1(b)。設(shè)A0,…，An是n+1個簡單區(qū)域，?i，j∈{1，…,n}，i≠j，則Aj和Ai相離而且A0包含Aj和Ai。帶洞簡單區(qū)域A定義為

定義3：多部分區(qū)域A是n(n≥1)個相離的簡單區(qū)域或者帶洞簡單區(qū)域的構(gòu)成，如圖1(c)。設(shè)A1、…、An是n個簡單區(qū)域或者帶洞簡單區(qū)域，?i，j∈{1，…，n}，i≠j，則Aj和Ai相離。多部分區(qū)域A定義為

復(fù)雜區(qū)域既可以是簡單區(qū)域，也可以是帶洞簡單區(qū)域或者多部分區(qū)域及其組合。

圖1 復(fù)雜區(qū)域?qū)ο蠖xFig.1 Definition of complex region

1.2 復(fù)雜區(qū)域的正則表達(dá)式

一個復(fù)雜區(qū)域的結(jié)構(gòu)構(gòu)成形式可由“+”和“-”形成一個正則表達(dá)式。定義2帶洞簡單區(qū)域可表示為A=A1-A2，定義3多部分區(qū)域可記為A=A1+…+An。表1是不同區(qū)域?qū)ο蟮谋磉_(dá)方式，采用正則表達(dá)式可以使用語法樹對表達(dá)式進(jìn)行不同方式的遍歷，本文采用先序遍歷方法，將復(fù)雜區(qū)域逐層級進(jìn)行分解。此外，根據(jù)本文復(fù)雜區(qū)域定義，一個復(fù)雜區(qū)域可能對應(yīng)多個正則表達(dá)式，如表1實例C，C1-(C2-C4)-C3、(C1-C2-C3)+C4以及(C1-(C2+C3))+C4均可表達(dá)該復(fù)雜區(qū)域的結(jié)構(gòu)。為了可以從表達(dá)式中分析出不同對象的層次關(guān)系和包含關(guān)系，建議選擇此類信息的表達(dá)式，如C1-(C2-C4)-C3顯然更能反映出各個簡單對象之間的包含關(guān)系(比如C2包含C4)以及相離關(guān)系(C4與C3相離)。

表1 復(fù)雜區(qū)域的正則表達(dá)式

1.3 9交模型

9交模型[5-6]是通過兩個復(fù)雜區(qū)域A、B的內(nèi)部(°)、邊界(?)和外部(+)的交集來描述拓?fù)潢P(guān)系。由一個3×3的0/1型9交矩陣R9(A，B)表示

R9(A，B)是所能表達(dá)的拓?fù)潢P(guān)系總數(shù)為33種[13]。若A和B均為簡單區(qū)域，如圖2，僅可推導(dǎo)出8種拓?fù)潢P(guān)系，依次定義為：disjoint、meet、contain、cover、inside、coverby、equal和overlap。

圖2 簡單區(qū)域間的基本拓?fù)潢P(guān)系[5](括號內(nèi)為縮寫)Fig.2 Eight basic topological relations between simple regions[5](abbreviations in brackets)

2 基于9交矩陣的拓?fù)潢P(guān)系計算

本文拓?fù)潢P(guān)系計算的主要方法是利用分解區(qū)域間的已知拓?fù)潢P(guān)系推導(dǎo)復(fù)雜區(qū)域間的拓?fù)潢P(guān)系。復(fù)雜區(qū)域的分解是根據(jù)其正則表達(dá)采用先序遍歷的方式逐層分解，每次分解得到兩個新的正則表達(dá)式，直至全為簡單對象。如圖3，計算A、B的拓?fù)潢P(guān)系為：先序遍歷B，B分解為簡單對象后，R9矩陣轉(zhuǎn)置再逐層分解A。整個拓?fù)潢P(guān)系的計算層次表現(xiàn)為8種基本拓?fù)潢P(guān)系進(jìn)行組合的形式?？梢钥闯觯?fù)潢P(guān)系計算的核心是根據(jù)區(qū)域“+”和“-”操作進(jìn)行拓?fù)潢P(guān)系的組合，該組合即為本文提出的兩種9交關(guān)系矩陣操作算子。

圖3 拓?fù)潢P(guān)系的分層計算Fig.3 Hierarchical computation of 9-instesection

2.1 多部分區(qū)域?qū)ο蠓纸夂图硬紶柌僮?/p>

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

?B=?B1∪?B2

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

圖4 集合運算和邏輯運算的差異Fig.4 Differences of set and logical Boolean operators

下面論證加布爾操作不能成立的情況。

B的內(nèi)部(邊界)是B1和B2內(nèi)部(邊界)的并集，不會出現(xiàn)A與B1和B2的內(nèi)部(邊界)相交，而與B的內(nèi)部(邊界)不相交的情況，也不會出現(xiàn)A與B1和B2的內(nèi)部(邊界)都不相交，而與B的內(nèi)部(邊界)相交的情況，故第1列和第2列為邏輯或操作恒成立。

表2 加布爾操作不成立的實例(黑色粗線條表示公共邊界)

推論2：R9(A，B1+B2…+Bn)=

2.2 帶洞區(qū)域?qū)ο蠓纸夂筒畈紶柌僮?/p>

不成立條件

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

?B=?B1∪?B2

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

R9(A，B1-B2)的第2列和第3列為R9(A，B1)和R9(A，B2)兩個分解關(guān)系矩陣的邏輯或，第1列為兩個分解關(guān)系矩陣的邏輯與。

下面論證差布爾操作不能成立的情況。

B的外部(邊界)是B1和B2補(bǔ)集的外部(邊界)的并集，不會出現(xiàn)A與B1和B2補(bǔ)集的外部(邊界)相交，而與B的外部(邊界)不相交的情況，也不會出現(xiàn)A與B1和B2補(bǔ)集的外部(邊界)都不相交，而與B的外部(邊界)相交的情況，故第2列和第3列邏輯或操作恒成立。

表3 差布爾操作不成立的實例(黑色粗線條表示公共邊界)

推論4：R9(A，B1-B2…-Bn)=

2.3 消除不成立條件的方法

從9交關(guān)系矩陣操作算子的證明看出，其不成立原因是集合運算和邏輯布爾運算之間的差異。布爾運算是對集合運算的簡化，一個0/1型矩陣可表示很多種交集可能性。由于從9交矩陣無法獲知復(fù)雜區(qū)域間的真實交集形式，故加和差布爾操作公式直接計算得到的矩陣可能對應(yīng)多種拓?fù)潢P(guān)系，產(chǎn)生表2、表3所示歧義問題。

根據(jù)9交模型的特點以及轉(zhuǎn)置矩陣RT的性質(zhì)，可知R9(A，B)=[R9(B，A)]T。然而，從加和差布爾操作公式不成立條件可以看出，公式發(fā)生歧義時，分別計算R9(A，B)和R9(B，A)，存在R9(A，B)≠[R9(B，A)]T的情況。因為不成立條件影響兩個矩陣元素的位置不一樣，當(dāng)不成立條件對計算R9(A，B)造成影響時，并不對R9(B，A)的計算造成影響。因此，根據(jù)這一特性可消除公式的歧義性。即利用這兩個矩陣的邏輯與運算得到最終的正確結(jié)果。修正公式為

2.4 計算實例

如圖5中兩個帶洞區(qū)域。綠化用地區(qū)域有3個簡單面域構(gòu)成A=A1-B1-B2，建筑用地區(qū)域也有3個簡單面域構(gòu)成B=B1+(B2-C1)。其構(gòu)成簡單區(qū)域間的拓?fù)潢P(guān)系如圖5所示。分別根據(jù)A和B的正則表達(dá)式先序遍歷逐層分解，同時由于算子存在不成立情況，計算中還需要進(jìn)行不成立條件的消除。R9(A，B)的計算如下(方框內(nèi)為分解后的拓?fù)潢P(guān)系，需要修正后才能參與計算)

圖5 計算實例Fig.5 An example for complex regions with holes

從以上過程可以看出，分解過程從上向下進(jìn)行，計算過程從下向上進(jìn)行。計算過程中，方框內(nèi)的拓?fù)潢P(guān)系可能存在計算錯誤的情況，需要按2.3節(jié)的方法進(jìn)行修正，修正后方可進(jìn)行下一步計算。需要修正的關(guān)系主要包括先序遍歷A和B后分解得到的復(fù)雜區(qū)域，如表4，根據(jù)計算的先后順序進(jìn)行修正。本實例中只有最后一步，即R9(A1-B1-B2，B1+(B2-C1))與R9(B1+(B2-C1)，A1-B1-B2)存在計算問題。修正過程如表5所示，R9(A，B)與[R9(B，A)]T在計算有誤的位置處得到的結(jié)果不一致，按邏輯與運算進(jìn)行修正后得到正確的結(jié)果。

表4 消除不成立條件計算表

Tab.4 Computation ofR9and [R9]Tbetween all the decomposed complex regions ofAandB

3 推導(dǎo)已知結(jié)構(gòu)區(qū)域?qū)ο箝g的9交拓?fù)潢P(guān)系

利用以上兩個算子可計算出已知結(jié)構(gòu)區(qū)域?qū)ο箝g所有可能的9交拓?fù)潢P(guān)系。首先利用關(guān)系矩陣表[11]描述復(fù)雜區(qū)域間的精細(xì)拓?fù)潢P(guān)系，然后將關(guān)系矩陣表轉(zhuǎn)化為9交拓?fù)潢P(guān)系。

表5 分層級計算結(jié)果(框內(nèi)是計算有誤進(jìn)行修正的位置)

Tab.5 Results of hierarchally computing topological relations

R9(A1-B1-B2,B1+(B2-C1))修正結(jié)果R9(A1-B1-B2,B1+(B2-C1))計算結(jié)果R9(B1+(B2-C1),A1-B1-B2)計算結(jié)果001011111é?êêù?úú001011111é?êêù?úú101111111é?êêù?úú

設(shè)復(fù)雜區(qū)域A的簡單區(qū)域集合為WA={A1，A2，…，Ai，…，Am}；B的簡單區(qū)域集合WB={B1，B2，…，Bi，…，Bn}，其中m≥1，n≥1。關(guān)系矩陣表，如表6，描述A與B間所有可能的拓?fù)潢P(guān)系。

表6 關(guān)系矩陣表

基于關(guān)系矩陣表的拓?fù)潢P(guān)系計算和推理已有研究[22]。利用A、B與B、C的關(guān)系矩陣表推理A、C關(guān)系矩陣表的公式為

R9(Ai，Cj)∈M(Ai，Cj)=∩Bk∈WBR9(Ai，Bk)°R9(Bk，Cj)

式中，M(Ai，Cj)為推理出的基本關(guān)系集合，R9取值均為為基本關(guān)系，Cj∈WC,Ai∈WA。

分析復(fù)雜區(qū)域的9交拓?fù)潢P(guān)系可利用關(guān)系矩陣表轉(zhuǎn)化為9交關(guān)系矩陣，推導(dǎo)和推理任意復(fù)雜區(qū)域的9交拓?fù)潢P(guān)系。表6中有m×n個基本拓?fù)潢P(guān)系，其能描述的拓?fù)潢P(guān)系個數(shù)為8m×n，其中存在大量不合理的情況，需要設(shè)定一定的條件剔除這些不合理的拓?fù)潢P(guān)系。根據(jù)本文復(fù)雜區(qū)域的定義，簡單對象間的關(guān)系是明確的，且僅存在包含和相離兩種關(guān)系，可以設(shè)置如下限定條件

R9(Ai，Aj)=contain∈M(Ai，Aj)=∩Bk∈WBR9(Ai，Bk)°R9(Bk，Aj)

R9(Ai，Aj)=disjoint∈M(Ai，Aj)=∩Bk∈WBR9(Ai，Bk)°R9(Bk，Aj)

R9(Bi，Bj)=contain∈M(Bi，Bj)=∩Ak∈WAR9(Bi，Ak)°R9(Ak，Bj)

R9(Bi，Bj)=disjoint∈M(Bi，Bj)=∩Ak∈WAR9(Bi，Ak)°R9(Ak，Bj)

例如，當(dāng)已知A=A1-A2，B=B1+(B2-B3)和C=C1+(C2-C3)，從8m×n種關(guān)系中剔除不合理情況后，可以得到關(guān)系矩陣表和9交模型的可能關(guān)系數(shù)如表7。

表7 所有的可能拓?fù)潢P(guān)系(9交模型/關(guān)系矩陣表)

當(dāng)A、B與B、C的拓?fù)潢P(guān)系已知，如圖6所示，可推理出A，C的可能拓?fù)潢P(guān)系為15種，如表8所示，進(jìn)而可得到9交拓?fù)潢P(guān)系為5種，如圖7。注意的是，這里不是基于9交矩陣的推理，利用圖6中的9交矩陣得到的關(guān)系會更多，此處推理計算出的5種關(guān)系，僅是在已知A、B與B、C的具體拓?fù)潢P(guān)系下得到的。

圖6 A、B與B、C的拓?fù)潢P(guān)系Fig.6 Topological relations of A and B，and B and C

C1C2C3A1{d,m,ct,cb,o}{d,m,o}j5i0abt0bA2j5i0abt0bj5i0abt0bj5i0abt0b

圖7 A、C推理結(jié)果：5種9交拓?fù)潢P(guān)系Fig.7 Reasoning results: 5 relations based on 9I

4 局限性

加和差布爾操作公式的局限性主要表現(xiàn)為兩點：

(1) 公式不是完全成立的，其本質(zhì)原因是集合操作和邏輯操作的差異性。應(yīng)用此公式一方面需要小心仔細(xì)地消除不成立條件，另一方面消除過程也使得計算過程變得復(fù)雜，這在計算實例(2.4節(jié))中有所體現(xiàn)。

(2) 公式與復(fù)雜區(qū)域的定義有關(guān)。本文對復(fù)雜區(qū)域的限定條件是比較嚴(yán)格的。比如B=B1+B2要求B1與B2相離，保證了B1與B2不能出現(xiàn)1-meet的拓?fù)潢P(guān)系，故對于一些由相鄰區(qū)域的組合比如被斷層切斷的地層或者多尺度分析中的區(qū)域合并，無法直接使用加布爾操作公式，如圖8(a)所示。同理B=B1-B2，當(dāng)廣義區(qū)域與洞存在公共邊界，差布爾操作公式無法使用，如圖8(b)所示。

圖8 存在公共邊界的復(fù)雜區(qū)域Fig.8 Complex regions with common boundaries

5 結(jié) 論

本文將復(fù)雜區(qū)域分解為有限個簡單區(qū)域并采用正則表達(dá)進(jìn)行結(jié)構(gòu)描述，為了利用分解后的簡單區(qū)域間精細(xì)拓?fù)潢P(guān)系計算出復(fù)雜區(qū)域間的拓?fù)潢P(guān)系，定義了兩個9交關(guān)系矩陣操作算子，通過分解部分的拓?fù)潢P(guān)系直接計算出兩個復(fù)雜區(qū)域的9交關(guān)系矩陣。并證明和分析了兩個操作算子的不成立條件以及消除不成立條件的方法。該算子是基于9交矩陣的拓?fù)潢P(guān)系計算方法，結(jié)合關(guān)系矩陣表法[4]拓?fù)潢P(guān)系的推導(dǎo)和推理過程，在已知復(fù)雜區(qū)域結(jié)構(gòu)的情況下，可以推導(dǎo)出其所有可能9交拓?fù)潢P(guān)系。

本文提出的9交關(guān)系矩陣操作算子也存在一定的局限性，一方面由于要消除不成立條件，計算過程顯得較為復(fù)雜；二是與復(fù)雜區(qū)域的定義有關(guān)，不適用于所有區(qū)域?qū)ο蟆?/p>

由于布爾型9交矩陣對真實空間關(guān)系進(jìn)行了簡化，僅依賴矩陣運算存在信息不足問題，需進(jìn)一步研究如何補(bǔ)充信息(如對圖11公共邊及其相鄰?fù)獠窟M(jìn)行區(qū)分)擴(kuò)展本方法適用于諸如多尺度分析中區(qū)域?qū)ο缶酆喜僮鞯葢?yīng)用[26]；同時后續(xù)研究可考慮將定義操作算子的方法擴(kuò)展到其他類型空間對象(如點、線)以及其他交集模型，如25交[21]、E9I交模型[9]等。

[1] FRANK A U. Qualitative Spatial Reasoning about Distance and Directions in Geographic Space[J]. Journal of Visual Languages & Computing, 1992, 3(4): 343-371.

[2] CLEMENTINI E, SHARMA J, EGENHOFER M J. Modelling Topological Spatial Relations: Strategies for Query Processing[J]. Computers & Graphics, 1994, 18(6): 815-822.

[3] 陳軍, 趙仁亮. GIS空間關(guān)系的基本問題與研究進(jìn)展[J]. 測繪學(xué)報, 1999, 28(2): 95-102. CHEN Jun, ZHAO Renliang. Spatial Relations in GIS: A Survey on Its Key Issues and Research Progress[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(2): 95-102.

[4] EGENHOFER M J, CLEMENTINI E, DI FELICE P. Research Paper: Topological Relations between Regions with Holes[J]. International Journal of Geographical Information Systems, 1994, 8(2): 129-142.

[5] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems, 1991, 5(2): 161-174.

[6] EGENHOFER M J, HERRING J R. Categorizing Binary Topological Relations between Regions, Lines and Points in Geographic Databases[R]. Orono: University of Maine, 1991.

[7] RANDELL D A, CUI Z, COHN A G. A Spatial Logic Based on Regions and Connection[C]∥Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning. Los Altos: Morgan Kaufman, 1992: 165-176.

[8] LI Sanjing, YING Mingsheng. Extensionality of the RCC8 Composition Table[J]. Fundamenta Informaticae, 2002, 55(3-4): 363-385.

[9] CLEMENTINI E, DI FELICE P. Spatial Model for Complex Objects with a Broad Boundary Supporting Queries on Uncertain Data [J]. Data & Knowledge Engineering, 2001, 37(3): 285-305.

[10] TANG Xinming,KAINZ W,WANG Hongyan.Topological Relations between Fuzzy Regions in a Fuzzy Topological Space[J]. International Journal of Applied Earth Observation and Geoinformation, 2010, 12(S2): S151-S165.

[11] WORBOYS M F, BOFAKOS P. A Canonical Model for a Class of Areal Spatial Objects[C]∥Proceedings of the Third International Symposium on Advances in Spatial Databases. London: Springer-Verlag, 1993: 36-52.

[12] OpenGIS? Implementation Specification for Geographic Information: Simple Feature Access: Part 2: SQL Option[R]. Reference Number: OGC 06-104r4, 2006.

[13] SCHNEIDER M, BEHR T. Topological Relationships between Complex Spatial Objects[J]. ACM Transactions on Database Systems, 2006, 31(1): 39-81.

[14] LI Sanjiang. A Complete Classification of Topological Relations Using the 9-intersection Method[J]. International Journal of Geographical Information Science, 2006, 20(6): 589-610.

[15] KURATA Y. The 9+-Intersection: A Universal Framework for Modeling Topological Relations[M]∥COVA T J, MILLER H J, BEARD K, et al. Geographic Information Science. GIScience 2008. Lecture Notes in Computer Science. Berlin: Springer, 2008: 181-198.

[16] CHEN Jun, LI Chengming, LI Zhilin, et al. Voronoi-based 9-intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science, 2001, 15(3): 201-220.

[17] LONG Zhiguo, LI Sanjiang. A Complete Classification of Spatial Relations Using the Voronoi-based Nine-intersection Model[J]. International Journal of Geographical Information Science, 2013, 27(10): 2006-2025.

[18] 歐陽繼紅, 霍林林, 劉大有, 等. 能表達(dá)帶洞區(qū)域拓?fù)潢P(guān)系的擴(kuò)展9-交集模型[J]. 吉林大學(xué)學(xué)報(工學(xué)版), 2009, 39(6): 1595-1600. OUYANG Jihong, HUO Linlin, LIU Dayou, et al. Extended 9-intersection Model for Description of Topological Relations between Regions with Holes[J]. Journal of Jilin University (Engineering and Technology Edition), 2009, 39(6): 1595-1600.

[19] 李健, 歐陽繼紅, 王振鑫. 帶雙洞區(qū)域與簡單區(qū)域間的拓?fù)潢P(guān)系[J]. 吉林大學(xué)學(xué)報(工學(xué)版), 2012, 42(5): 1214-1218. LI Jian, OUYANG Jihong, WANG Zhenxin. Topological Relations between a Region with Two Holes and a Simple Region[J]. Journal of Jilin University (Engineering and Technology Edition), 2012, 42(5): 1214-1218.

[20] 陳占龍, 馮齊奇, 吳信才. 復(fù)合面狀對象拓?fù)潢P(guān)系的表達(dá)模型[J]. 測繪學(xué)報, 2015, 44(4): 438-444. DOI: 10.11947/j.AGCS.2015.20130708. CHEN Zhanlong,FENG Qiqi, WU Xincai. Representation Model of Topological Relations between Complex Planar Objects[J]. Acta Geodaeticaet Cartographica Sinica, 2015, 44(4): 438-444. DOI: 10.11947/j.AGCS.2015.20130708.

[21] 沈敬偉, 周廷剛, 朱曉波. 面向帶洞面狀對象間的拓?fù)潢P(guān)系描述模型[J]. 測繪學(xué)報, 2016, 45(6): 722-730. DOI: 10.11947/j.AGCS.2016.20150352. SHEN Jingwei, ZHOU Tinggang, ZHU Xiaobo. Topological Relation Representation Model between Regions with Holes [J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(6): 722-730. DOI: 10.11947/j.AGCS.2016.20150352.

[22] DU Shihong, GUO Luo, WANG Qiao, et al. Efficiently Computing and Deriving Topological Relation Matrices between Complex Regions with Broad Boundaries[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2008, 63(6): 593-609.

[23] EGENHOFER M J. Deriving the Composition of Binary Topological Relations[J]. Journal of Visual Languages & Computing, 1994, 5(2): 133-149.

[24] TRYFONA N, EGENHOFER M J. Consistency among Parts and Aggregates: A Computational Model[J]. Transactions in GIS, 1996, 1(3): 189-206.

[25] NGUYEN V H, PARENT C, SPACCAPIETRA S. Complex Regions in Topological Queries[C]∥Proceedings of the International Conference on Spatial Information Theory: COSIT97. Laurel Highlands: Springer-Verlag, 1997: 175-192.

[26] DU Shihong, FENG Chenchen, GUO Luo. Integrative Representation and Inference of Qualitative Locations about Points, Lines, and Polygons [J]. International Journal of Geographical Information Science, 2015, 29(6): 980-1006.

(責(zé)任編輯：宋啟凡)

Dividing and Computing Topological Relations between Complex Regions

WANG Zhangang1，DU Qunle1，WANG Xianghong1

1. College of Geosciences and Surveying Engineering，China University of Mining and Technology，Beijing 100083，China; 2. Development and Research Centre，China Geological Survey，Beijing 100037，China

A novel method was proposed for computing topological relations between complex regions based on 9-intersection (9I) matrices. A complex region was composed of a finite set of simple regions and its configuration was represented as a regular expression. Two 9I Boolean matrix operators were defined and used for computing the binary topological relations between complex regions while the relations between the decomposed regions were known. The establishing conditions of the operators were proved and analyzed in detail and the method of eliminating the ambiguities was given to make the computation correct. The approach can be used as a useful computation tool to analysis topological relations between spatial objects with specific configurations. In addition，the operators are dependent on definitions of complex regions and not suitable for regions which violate our definitions.

geographical information system; complex regions; topological relations; 9-intersection model

The National Natural Science Foundation of China (Nos.41672326;41202238)；The Work Project of China Geological Survey (No. 1212011120446)；The Fundamental Research Funds for the Central Universities

WANG Zhangang(1980—), male, PhD, majors in geological Information science.

王占剛，杜群樂，王想紅.復(fù)雜區(qū)域?qū)ο笸負(fù)潢P(guān)系分解與計算[J].測繪學(xué)報，2017,46(8)：1047-1057.

10.11947/j.AGCS.2017.20160209. WANG Zhangang，DU Qunle，WANG Xianghong.Dividing and Computing Topological Relations between Complex Regions[J]. Acta Geodaetica et Cartographica Sinica,2017,46(8):1047-1057. DOI:10.11947/j.AGCS.2017.20160209.

P282

A

1001-1595(2017)08-1047-11

國家自然科學(xué)基金(41672326; 41202238)；中國地質(zhì)調(diào)查局工作項目(1212011120446)；中央高?；究蒲袠I(yè)務(wù)費專項資金

2016-05-03

王占剛(1980—),男，博士，研究方向為地質(zhì)信息科學(xué)。

E-mail： millwzg@163.com

修回日期： 2017-07-14