复杂体目标之间三维拓扑关系描述模型

曹雪峰

（信息工程大学地理空间信息学院，河南 郑州 450052）

0 引言

空间关系是地理信息科学中的重要理论问题，包括拓扑关系、方向关系、距离关系3类空间关系的描述和推理［1］。拓扑关系描述方法主要有点集拓扑方法、DEM方法、最小边界矩形法、区域连接法、CBM方法、符号投影法、Voronoi图法、广义交模型方法、符号阵列法等［2，3］，基于点集拓扑理论的四交模型（4IM）和九交模型（9IM）是GIS领域中广泛使用的拓扑关系描述方法。

9IM模型［4］是Egenhofer等研究二维空间实体拓扑关系提出的。陈军等用DE＋9IM方法［5］研究三维空间中单纯形间的拓扑关系，可以区分59中拓扑关系，其中有意义且可实现的拓扑关系分为6种：相邻（touch）、包含（in）、相交（cross）、部分覆盖（overlap）、相离（disjoint）和相等（equal）。采用 Open－GIS的数据模型，使用9IM方法能够区分并实现的体－体拓扑关系有8种［6］。刘新等［2］使用9IM方法研究三维空间中单纯形间的拓扑关系，其中两个四面体之间的拓扑关系有8种。

目前对拓扑关系描述的研究主要集中在二维拓扑关系。关于三维拓扑关系描述的研究，主要是基于9IM模型围绕三维空间中的折线段、表面（不含岛）、体（不含洞）等简单空间目标展开。9IM模型用两个物体的内部、边界和外部间的交所组成的3×3矩阵来描述两物体间的拓扑关系。但是，三维空间中物体的边界也具有自身的结构，可能由多个部分组成，因而，两个体目标边界间的相交等价于两个复杂面目标的相交，有可能存在的接触于一点、相交于一个面、相互交错或者接触、相交、交叉等交的情况共存于一处或多处。由于9IM模型的基本元素难以分辨这些相交细节，大量复杂体目标之间的拓扑关系就得不到区分。关于复杂体目标三维拓扑关系的研究还不够全面和系统，

以点集拓扑理论［7］为基础，提出点邻域模型（Point Neighborhood Model，PNM）。给出点邻域结构的定义，研究所有可能存在的点邻域结构类型，设计了描述两个复杂体目标间三维拓扑关系的编码。对点邻域模型与9IM模型进行比较分析，结合实例说明点邻域模型对三维拓扑关系的描述更精细。

1 点邻域模型

点邻域模型的基本思路是通过三维空间中点邻域内各点的归属关系刻画体目标之间的拓扑关系。

基于点集拓扑理论，将体目标建模为三维欧氏空间中的特定无限点集，研究含有洞或由多个部分组成的复杂体之间的三维拓扑关系。通过分析点邻域中各点归属关系的组合，描述两个体目标之间的三维拓扑关系。其中，某一个点的邻域结构描述了“靠近”参考点的各点的归属关系，以布尔值表示点邻域中每个点的归属关系，对于点邻域中的各个点就形成了一组确定的布尔值集合。

例如，对于包含体目标A和B的场景，若存在一点p，邻近它的点都既属于A又属于B，就将对应的邻域结构exist nei in overlap（见定义1）标记为true，这个邻域结构标记将用于A与B之间拓扑关系的描述。

1.1 点邻域及其结构

为了描述三维空间拓扑关系，首先定义相关的拓扑与度量概念，给出点邻域的形式化描述，然后分析所有可能的点邻域结构。

首先引入必需的拓扑与度量概念和点邻域定义。令R代表自然数集合，R＋＝｛x∈R｜x＞0｝。令R3代表三维欧氏空间，存在欧氏距离函数：

对于任意一点p∈R3和r∈R＋，集合Nr（p）＝｛q∈R3｜d（p，q）≤r｝称为以p为中心、半径为r闭包球。令ε代表一个小的正数值（ε→0），称闭包球Nε（p）为（包围）p的邻域。这样，可以将p的邻域认为是一个极小的封闭的包围球，其中包含了R3中所有距离p最近的点。

本文研究含有两个体目标的三维场景中各点可能存在的邻域结构。假定体目标A和B为R3中的点集（即A⊂R3，B⊂R3），则对于给定点p∈R3，其邻域Nε（p）中任一点q（即q∈Nε（p））可能的归属关系为以下4种之一：q∈A∧q∉B；q∉A∧q∈B；q∈A∧q∈B；q∉A∧q∉B。因此，可以通过某个邻域中所有点的归属关系的组合，来描述该邻域的归属。将这种邻域归属关系的描述结果称为点邻域结构。利用某个点所有可能的4种归属关系，可以获得一个邻域的24－1＝15种可能的归属关系组合，组合数量为15而不是16的原因是一个邻域中归属关系为空（即不属于这4种关系的任意一种）的情况不存在。换言之，15种邻域结构涵盖A和B所处的R3中任意一点的所有可能的归属关系。

1.2 点邻域结构标记

在定义1中，规定了A和B所处的R3中15种对应的邻域结构标记。

定义1 令A⊂R3，B⊂R3，p∈R3，Nε（p）为p的一个具有极小半径ε的邻域。首先为p定义4种归属关系标记：

对A和B所处的R3中15种邻域结构标记定义为：

上述15种邻域结构标记描述了R3中两个体目标A与B之间在任意一个点上所有可能的相交情况，图1给出了对应的示例。例如，图1（8）表示的标记为true，则存在一个点，其邻域仅包含属于前操作对象A的点和属于后操作对象B的点，进一步的，exist＿nei＿contain＿op1＿op2标记为true，说明A 与B之间为面拓扑相切关系。

图1 点p的15种可能的邻域结构Fig.1 The drawing of the 15 neighborhood structures for point p

1.3 三维拓扑关系编码

前文已为欧氏空间R3中两个体目标引入了15种邻域结构标记。这些标记描述了三维欧氏空间R3中两个体目标每一个点的所有拓扑情况，也就是说通过一个点的邻域结构，就可以在很低的粒度层次上刻画两个体之间的拓扑关系。因而，确定两个体之间的拓扑关系，只需要获得所有15种邻域结构标记的布尔值。更进一步的，假定这些标记按定义1中的顺序存储在F中，则定义2规定了基于点邻域结构的两个体目标之间三维拓扑关系的编码。

定义2 令A与B为R3中的两个体目标（A⊂R3，B⊂R3），令FV代表对两个体之间关于第i种（1≤i≤15）邻域结构标记值的拓扑相交关系进行编码的函数，则有：

显然，采用15bit数组就可以对A与B之间拓扑关系进行编码。拓扑关系编码TRE的形式化描述如下：

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

定义2为两个体目标之间的拓扑关系表达引入15bit二进制表示法。图2给出3个编码示例。图2a显示了由A与B组成的场景中9个拓扑关系标记为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，并标识了对应的点pi。在图2b中，另有3个为true的标记，分别对应p8、p11、p14。图2给出的3种不同拓扑关系分别是编码为111111001100001的overlap、编码为111111011110011的overlap with meet on face、编码为111111001110001的overlap with meet on edge。

图2 拓扑关系编码示例Fig.2 Examples of topological relationship encodings

理论上，基于点邻域模型的三维拓扑关系编码可以获得总计215＝32 768种可能的拓扑关系编码值，即隐含在两个体目标之间的拓扑关系编码存在总计32 768种可能。但并非所有编码表示的拓扑关系都是真实存在的。显然，当且仅当该拓扑关系可以从含有两个体目标的现实世界场景中抽象出来时，对应的拓扑编码才有效。例如，在现实世界中不存在编码为000000000000000的拓扑关系。由此引发一些问题：对于两个复杂体目标的拓扑关系，究竟哪些编码是有效的？对于两个简单体目标的拓扑关系，究竟哪些编码是有效的？这些有效的拓扑关系编码数量有多少？在此，本文仅仅提出了基本的建模思想，这些问题还需更深入的研究。

2 PNM与9IM的比较分析

点邻域模型（PNM）与9IM模型存在共同的理论基础，即点集拓扑理论。因此，点邻域模型与9IM模型对拓扑关系的建模方法仅依赖于点集和拓扑空间，而与空间目标的表达形式无关。基于空间目标某一特定表达的拓扑关系模型对同一空间目标的不同表达形式，可能得出不同的拓扑关系判断结果，因而不具有通用性。例如，基于空间目标维度元素的维度模型［8］高度依赖空间目标的具体表达形式，对于边界光滑的圆和由相连片段组成近似边界的圆将得出不同的结果。相比而言，无论空间目标采用怎样的数据表达，基于点集拓扑理论的模型总是适用的，所以，基于点集拓扑理论的空间关系模型相比其他模型更具有一般性。

由于建立在相同的点集拓扑理论基础上，点邻域模型与9IM模型在拓扑关系的描述结构、描述方式上存在对应关系。点邻域模型的“点邻域结构”与9IM模型的“内部—边界—外部”三元组对应，都是作为拓扑关系描述结构的基本元素。点邻域的拓扑关系编码与9IM模型的拓扑关系矩阵对应，都被用作拓扑关系的描述形式。

以一些典型的三维空间拓扑关系为例，对点邻域模型与9IM模型进行比较分析，以说明点邻域模型能够识别两个体目标之间的三维拓扑关系种类更多。

9IM模型可以区分8种两个简单体目标之间的三维拓扑关系。图3显示了这8种拓扑结构与对应的9IM矩阵，并对应地给出了基于点邻域模型的拓扑关系编码。对应于不同的拓扑关系，9IM模型和点邻域模型都给出了唯一的拓扑关系描述结果。

图3 9IM与PNM均可区分的8种拓扑关系Fig.3 The 8 topological relationships between two volumes that can be distinguished with both 9IM and PNM

但是，9IM模型只能识别出overlap等主要的拓扑关系，无法区分相切于一面等同时存在的其他拓扑关系，而点邻域模型能够对这些拓扑关系进行正确的描述。对于图4给出的4种拓扑关系，9IM模型给出的描述矩阵与overlap的描述矩阵相同，而在点邻域模型中，这4种拓扑关系的编码是不同的，它们被清晰地区分开。除了A、B之间的overlap关系，类似于A在外侧切于B、A相切于B的内侧、A与B部分相交同时A与B重合于一面（分别对应图4所示的第2、3、4种情况）等，点邻域模型均能够给以唯一的编码描述结果将其区分开。这些实例表明，相比9IM模型，点邻域模型能够区分出两个复杂体目标之间的三维拓扑关系种类更多。

图4 9IM无法区分但PNM可以区分的4种拓扑关系Fig.4 Topological relationships that can be distinguished with PNM but not 9IM

3 结论

现有拓扑关系描述模型对于三维空间中体目标之间拓扑关系的刻画不够精确。基于点集拓扑理论，提出了点邻域模型，定义了三维空间中点邻域的空间结构，利用点邻域结构标记实现对三维拓扑关系的编码描述。点邻域模型与9IM模型的比较结果表明，9IM模型能够区分出的三维拓扑关系在点邻域模型中同样可以区分描述，9IM模型无法区分开的三维拓扑关系在点邻域模型中仍然可以区分描述，因而点邻域模型所能够区分的三维拓扑关系的种类更多。理论上，点邻域模型能够区分的三维拓扑关系数量巨大，本文未能对其进行完全分析，这将是今后研究的方向。此外，如何将点邻域模型推广到三维空间的曲线、曲面等其他复杂空间目标还需要进一步研究。

［1］ 刘瑜，龚咏喜，张晶，等.地理空间中的空间关系表达和推理［J］.地理与地理信息科学，2007，23（5）：1－7.

［2］ 刘新，刘文宝，李成明.三维空间关系的描述及其定性推理［M］.北京：测绘出版社，2010.

［3］ 吴长彬，闾国年.空间拓扑关系若干问题研究现状的评析［J］.地球信息科学学报，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］ 陈军，郭薇.三维空间实体间拓扑关系的矩阵描述［J］.武汉测绘科技大学学报，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］ 熊金城.点集拓扑讲义（第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.