基于25交模型实现带洞面域拓扑关系描述模型间的转换

王占刚，屈红刚，王想红

1. 中国矿业大学地球科学与测绘工程学院，北京 100083； 2. 中国地质调查局发展研究中心,北京 100037

描述复杂对象间的拓扑关系是地理信息科学中的一个基础性研究问题。面域对象是最重要的空间对象之一，结构构成上可表现为多部分构成，可以带洞以及岛[1-6]。目前描述面域对象间拓扑关系的模型主要有针对简单面域的4交，9交模型[7-8]和区域链接法(region connection calculus,RCC)[9-10]等方法，扩展9交模型的方法如9+交集模型[11]、V9I模型[12-13]，以及直接针对存在带洞、多部分构成复杂面域的方法如关系矩阵表[2,6]、扩展9-交集模型[14-15]、16交模型[5]及25交模型[5,16]等。

以上拓扑关系描述模型的一般特点是，基于点集拓扑理论根据复杂对象的结构构成进行对象或者点集分解，用已知对象或者点集间的关系描述拓扑关系。对比传统的Egenhofer 9交模型[7-8]，采用拓扑点集或者对象分解的方法分辨拓扑关系的能力普遍提高，并广泛用于空间数据推理[6,17]、多尺度空间数据库或复杂对象的拓扑变化识别[18]、不同分辨率拓扑一致性评价[19]等。然而，拓扑关系分辨能力高的描述模型也使得推导或者推理拓扑关系变得更加复杂，比如如何推导出两个复杂面域间所有可能的拓扑关系。相关的研究主要针对具有简单结构的面域进行分析，如带洞区域和简单区域拓扑关系[20]、凹形区域和带单洞区域间拓扑关系的表示[21]。文献[22]提出的关系矩阵表方法可以处理任意复杂面域的情况，可精细表达拓扑关系，但是关系矩阵表结构复杂，不便于实现空间查询和分析，这就需要将其转换为其他模型或者拓扑关系谓词。文献[23]和[24]利用推理组合表推导多部分构成以及带洞面域间的拓扑关系，但这种方法只限于处理简单面域，推导结果只能属于8种基本谓词之一，不能给出所有可能的拓扑关系。同时，不同拓扑关系描述模型之间的关系以及转换也缺少系统研究。

本文分析了6种描述带洞面域拓扑关系的模型以及之间的联系，基于25交模型提出了一种利用简单面域间拓扑关系推导复杂面域间拓扑关系的方法，实现了拓扑关系描述模型之间的转换，应用于推导和推理具有特定结构复杂面域间的所有拓扑关系。

1 带洞面域定义

1.1 带洞面域的构成结构

一个带洞面域将二维空间R2从内向外可划分为5个拓扑子集(如图1)：Ao是面域的内部，内外部A-1由所有洞的内部构成，外外部A+1是除去A-1的面域外部点集，内边界∂A-1由分割Ao和A-1的边界构成，外边界∂A+1是除去∂A-1的面域边界部分，分割外外部空间。其中，A+1，∂A+1和Ao均不能为空，∂A-1和A-1可能为空且满足(∂A-1≠Ø∧A-1≠Ø)∨(∂A-1=Ø∧A-1=Ø)。复杂面域的边界∂A=∂A+1∪∂A-1，所有的洞Ah=A-1∪∂A-1。

图1 复杂面域的5个拓扑子集 Fig.1 Five topologically distinct and mutually exclusive parts

1.2 复杂面域分解与正则表达式

参考文献[3]和OpenGIS[25]相关定义，复杂面域既可以是简单面域，也可以是带洞简单面域或者多部分面域及其组合[26]。对于洞内不带洞的复杂面域对象，其面域分解和表达定义如下：

通过定义1和定义2，利用“+”和“-”形成一个正则表达式表示复杂面域的分解过程，且正则表达式可进一步采用语法树进行先序遍历[26]。比如，带洞简单面域可表示为A=A1-A2，多部分面域可记为A=A1+…+An。正则表达式反映了各个简单对象之间的包含关系以及相离关系。

2 带洞面域的拓扑关系描述模型

本文主要分析基于对象分解和点集拓扑理论的带洞面域间拓扑关系描述模型，下文分别介绍6种主要模型以及其联系。

2.1 主要模型

2.1.1 经典9交模型

Egenhofer 9交模型[7-8](本文称为经典9交模型，简称9I)采用对象的内部(o)、边界(∂)和外部(+)三个子集间的交集描述拓扑关系，其定义为

2.1.2 宽边界扩展9交模型[4]

该模型(简称E9I)主要针对边界不确定性区域，边界采用宽边界(Δ)描述。其定义为

2.1.3 关系矩阵表

该方法将带洞面域分解为简单面域，利用简单面域间的拓扑关系描述整体对象间的拓扑关系。带洞面域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。表中每个元素是简单面域间的拓扑关系，采用8种基本拓扑关系，能描述的拓扑关系个数为8m×n。

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

该方法(简称D9I)利用A、B分解后简单面域间的内部、边界和外部交集构建一个mn+1位的二进制编码代替经典9交模型中的相应交集。其定义为

2.1.5 4元组模型[18,27]

该方法(简称4-Tuple)是对关系矩阵表的简化，将面域对象的广义面域和洞进行了合并，通过合并后的面域构建关系矩阵表，此表中仅有4个元素。其定义为

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

2.1.6 25交模型[5,16]

25交模型是通过两个面域A、B的5个拓扑子集的交集来描述拓扑关系，表示为一个5×5的0/1型25交矩阵R25(A,B)

2.2 对比分析

根据上文不同带洞面域间拓扑关系描述模型的定义，本文从模型构建方式、对洞的表达、存储方式推理分析及拓扑关系分辨能力5个方面进行了对比分析，如表1所示。模型构建方式主要分为基于点集拓扑构建交集矩阵和利用对象分解构建对象交集矩阵。不同模型对洞的表达以及对象构成细节描述不一样，也使得它们对拓扑关系的分辨能力不同，当然描述的细节信息越多，所需存储空间相对也越多。对于关系矩阵表模型，其表内每个元素仅需要描述简单面域间的拓扑关系，即8种可能性，因此二进制编码的存储位数最多是3mn。分辨能力高的模型，一般只能给出所能描述拓扑关系可能性的理论数字，目前研究只是给出了经典9交模型所能描述复杂面域间的所有33种拓扑关系。其他模型由于自身复杂性还没有给出描述面域间拓扑关系个数的准确数值。在拓扑关系推理方面，分辨能力低的模型由于无法表达面域的细节构成，一般只能给出简单对象之间的推理组合表，而关系矩阵表则可适用于任意复杂面域间的拓扑关系推理，相关内容在4.1节阐述。

表1 不同模型对比

2.3 不同模型之间的转换

根据以上6种模型的定义，尽管可以采用基于点集拓扑和对象分解的方法构建拓扑关系描述模型，但是当所表达的面域细节信息相同时，不同模型对拓扑关系的描述是等价的，比如关系矩阵表和扩展9交模型、25交模型和4元组模型对拓扑关系的分辨能力相同，描述是等价的(第3部分给出等价证明)。同时，不同模型之间可以转换：相同分辨能力的模型之间可以转换，分辨能力高的模型可以转换为分辨能力低的模型。这种转换可直接实现也可以间接实现，如图2。直接转换是根据定义无须进行复杂的推理计算即可实现，比如25交模型转换为宽边界9交模型以及25交模型转换为4元组模型等；间接转换则需要进行推理计算一些未知信息，比如关系矩阵表和4元组模型都无法直接给出整体面域的内部交集Ao∩Bo信息，所以无法直接转换为25交模型。本文第3部分基于25交模型给出了实现间接转换的方法。

图2 不同模型之间的转换Fig.2 Conversion of different models

3 不同拓扑关系模型间的转换推导

参考文献[26]对复杂区域对象拓扑关系分解与计算的思路，比如给定两个面域A和B，其中B=B1+B2B，对象分解为B1和B2，拓扑关系R(A,B)可由R(A,B1)和R(A,B2)计算得到。这就需要研究给出基于25交模型的拓扑关系分解计算方法，然后利用拓扑关系分解计算方法推导不同拓扑关系描述模型之间的转换。

3.1 基于25交模型的拓扑关系分解计算

从上述复杂面域的分解可知，当给定两个面域A和B，就可以将其分解为简单面域表达的形式。当推导其25交关系矩阵R25(A,B)时，根据面域对象的分解，将拓扑关系的推导也相应分解，进而将复杂对象拓扑关系的推导转化为对简单面域间拓扑关系的处理。这其中最主要的问题是如何根据分解后对象间的已知拓扑关系推导计算出A和B的拓扑关系。为此，本文提出两个主要25交关系矩操作算子。

若复杂面域B=B1+B2，B1与B2相离，则复杂面域A和B的25交关系矩阵加布尔操作公式为

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

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

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

设Ma={A-1，∂A-1，Ao，∂A+1，A+1}，∀a∈Ma可得

R25(A,B)是0/1布尔型矩阵，需要将上述集合的并和交操作直接转化为逻辑或和逻辑与。显然，集合的并和逻辑或对应，且运算不会产生歧义，故

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

设Ma={A-1，∂A-1，Ao，∂A+1，A+1}，∀a∈Ma可得：

将上述集合的并和交操作直接转化为逻辑或和逻辑与，形成R25(A,B)的0/1布尔型矩阵形式

参考文献[26]，根据25交模型的特点以及转置矩阵RT的性质，可知R25(A,B)=[R25(B,A)]T。因此，当公式发生歧义时，分别计算R25(A,B)和R25(B,A)，存在R25(A,B)≠[R25(B,A)]T的情况。根据这一特性消除25交关系矩操作算子的歧义性。

3.2 不同模型的转换证明

当给定两个面域A和B将其分解为简单面域表达的形式，并采用关系矩阵表描述其拓扑关系，则利用上述两个25交关系矩操作算子，即可将关系矩阵表转换为25交模型。这样可实现分辨能力高的模型向分辨能力低的模型进行转换。下面重点讨论不同模型的等价性。

证明25交模型和4元组模型是等价的。

首先，25交模型可以直接转换为4元组模型。

4元组模型由整体广义面域和洞构成，表示为A=AE-AH，B=BE-BH。与5个拓扑子集的关系为

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)。则面域的内部、边界和外部与5个拓扑子集的关系为

以T2=R9(AE,BH)为例

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

可见，利用25交模型可以得到4元组模型中的各个交集值，而且一个25交矩阵只能转换为一个对应的4元组模型。因此，25交模型可以直接转换为4元组模型。

其次，4元组模型可间接转换为25交模型。

R25(AE-AH,BE-BH)=

由于AE、AH、BE、BH都不带洞，此时可利用9交矩阵可以构建出25交模型(内外部和内边界为空集合)，进而得到R25(A,B)=R25(AE-AH,BE-BH)。而且，一个对应的4元组模型只能转换为一个25交矩阵。因此，4元组模型可通过一定计算间接得到25交模型。

最后，通过以上分析，4元组模型和25交模型可相互转换，而且转换是唯一的，因此，对特定拓扑关系，其描述是等价的。证明关系矩阵表模型和扩展9交集模型是等价的。

从关系矩阵表模型和扩展9交集模型的定义看，两种模型都是利用了带洞面域对象分解后的所有简单面域的内部、边界和外部交集信息，所以所能描述拓扑关系的信息量是一致的，这些信息只是存储在了不同的二进制编码位置上。两种模型的差异在于，扩展9交集模型外加了一个整体面域的9交拓扑关系。基于25交模型的拓扑关系分解计算可知，通过关系矩阵表模型可以转换为唯一一个25交模型以及进一步得到9交模型，这也说明整体面域的9交模型不是独立信息，可由其他信息推导出来的。因此，扩展9交集模型外加的9交拓扑关系在于方便获知整体面域间的拓扑关系，并没有增加模型的拓扑关系分辨能力。由于两个模型所记录的细节信息一致，故其对拓扑关系的描述是等价的。

4 基于25交模型的拓扑关系分析实例

4.1 具有特定结构的带洞面域拓扑关系推导

利用25交模型在模型转换过程中的“桥梁”作用，则可推导出采用不同模型的所有可能拓扑关系以及拓扑关系推理。

利用关系矩阵表描述复杂面域间的精细拓扑关系。通过A、B与B、C的关系矩阵表推理A、C关系矩阵表的公式[6,29]为

R25(Ai,Cj)∈M(Ai,Cj)=∩Bk∈WBR25(Ai,Bk)·R25(Bk,Cj)，其中，R25取值为基本拓扑关系,Cj∈WC,Ai∈WA。根据复杂面域的定义，25交模型推理中剔除不合理拓扑关系的条件为[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)

在以上限定条件下，利用关系矩阵表描述精细拓扑关系以及拓扑关系推理，基于25交模型的拓扑关系分解计算得到不同分辨能力的拓扑关系模型。

比如，给定4个已知构成的面域对象A=A1-A2，B=B1+(B2-B3)，C=C1+(C2-C3)和D=D1-D2，如图3所示。利用关系矩阵表，25交模型和经典9交模型推导的所有拓扑关系见表2。

当A、B与B、C的具体拓扑关系如图4所示，则采用关系矩阵表推理得到A、C的可能拓扑关系为15种，如表3所示，将这些关系转换为25交模型，可得到5种拓扑关系，如图5所示。其中8种基本拓扑关系disjoint，meet，contain，cover，inside，coverby，equal和overlap的缩写为d,m,cn,cv,i,cb,e,o。

图3 4个面域对象：A,B,C和DFig.3 Four regions:A,B,C and D

表2 A,B,C和D间的所有拓扑关系

图4 A,B与B,C的拓扑关系Fig.4 Topological relations of A and B，and B and C

表3 A,C推理结果

图5 A、C推理结果：5种25交拓扑关系Fig.5 Reasoning results：5 relations based on 25I

4.2 实例分析

中国行政区化上存在大量“飞地”现象。如图6所示，天津市宁河区，其行政区域表现为带洞复杂区域对象。在一些应用中需要区分洞内外空间关系，例如利用行政区和矿权界线的25交拓扑关系可以使得矿权隶属分类更加详细。行政单元边界和单一矿权区用简单区域表示，采用正则表达式构成各行政区和复合矿权区。矿权分析系统只记录行政单元边界和单一矿权边界简单区域间的拓扑关系。复杂区域间拓扑关系通过计算得到。宁河区A=A1-A2,矿权区B=B1+B2,则A和B的拓扑关系为

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 带洞区域对象的拓扑关系描述实例Fig.6 An example of the topological relations between regions with holes

相对于9交模型，25交模型更好地描述了该矿区与宁河区及飞地之间的关系。此外，当单一矿权区域的所有人发生变化，由于简单区域之间的拓扑关系并没有变化，矿权区与行政区间的拓扑关系按本文方法实时计算得到。

5 结 论

本文将带洞复杂面域分解为有限个简单面域并采用正则表达式进行结构说明，分析了6种不同表达带洞面域的拓扑关系描述模型。分析证明，关系矩阵表和扩展9交模型、25交模型和4元组模型实质上对拓扑关系的分辨能力相同。基于25交模型实现了拓扑关系分辨能力高的模型向分辨能力低的模型的转换，这样可方便实现对具有特定结构的复杂面域间拓扑关系的推导。

同时，文献[2]提出的关系矩阵表可用于任意复杂面域对象间拓扑关系的精细表达，并可进行拓扑关系的有效推导和推理。25交模型和4元组模型是对该方法的一种概化，主要是对洞整体信息进行描述，不关注洞的细节构成。通过对比分析也发现，一方面25交模型比4元组模型存储空间更少；另一方面利用本文定义的25交矩阵操作算子可直接基于矩阵计算实现复杂面域间拓扑关系的分析，而基于4元组模型尚不能实现该功能。