摘 要 现有空间拓扑关系模型多针对同种类的空间对象进行处理，在实际应用中具有一定的局限性 本文在交集模型的基础上，通过扩展 交集矩阵，对凹形区域和带单洞区域间的拓扑关系进行了表示，得到凹形区域和带单洞区域间 种拓扑关系，并给出前 种拓扑关系的示意图提出算法，并通过程序验证 种拓扑关系均可实现证明所获得的 种基本关系的完备性和互斥性，通过与相关工作的比较可知该表示模型比其它相关模型表达力更强
关键词 拓扑关系，凹形区域，区域连接演算( ) ， 人工智能，带单洞区域， 交集矩阵
　　引 言
　　空间推理［］在地理信息系统(， ) 图形图像处理模式识别机器人导航空间数据库［ ］等方面有广泛应用如，机器人在静态全局路径规划算法［］研究中，对具有凹形障碍的路径规划研究较少或者将凹形障碍近似处理成圆形障碍，再进行路径规划这样会损失地图中的有效信息，当机器人环境中有较多凹形障碍时，近似处理会堵塞事实上存在的通路，从而使路径规划失败为满足实际应用的需求，研究有关凹形区域的拓扑关系具有一定理论和实际意义
　　目前已有的空间拓扑关系模型主要有 交 模型和 交模型［ ］， 交模型［］和区域间拓扑关系的层次表达法［］等多数模型都是对相同类型的空间对象进行建模，针对不同类型空间对象的研究则相对较少而现实世界中空间对象的种类繁多，很多情况下需要对不同类型的空间对象进行处理本文旨在建立适合描述凹形区域和带单洞区域的拓扑关系模型基本工作包括对经典 交集矩阵进行扩展，得到可描述区域连接演算(， ) 关系的扩展 交集矩阵，在此基础上，定义一个 的交集矩阵，用于表示单个凹形区域和单个带单洞区域间的拓扑关系，给出这两个区域间可能存在的 种拓扑关系图，且证明此关系集合的完备性和互斥性再讨论该模型与相关拓扑关系模型的比较，说明该模型的表达力更强，对空间拓扑关系的刻画更准确
　　交集模型扩展
　　交集矩阵等［］提 出 的 交集模型不能表示，因此对 交集矩阵中的元素进行调整，定义扩展 交集矩阵来表示 关系定义 令 为两个简单区域，表示 的内部，表示 的补集，则 间的拓扑关系可用下面的扩展 交集矩阵进行表示:( )( ) ( ) ( )[ ]通过考察矩阵中每项集合的空与非空，可用来描述 关系，如表 所示表 关系的扩展 交集矩阵表示( ，) ( ，) ( ，) ( ，) ( ，)[ ] [ ] [ ] [ ] [ ]交集矩阵的定义本节给出适用于表示凹形区域和带单洞区域间拓扑关系的 交集模型首先，简单介绍有关凹形区域的基本概念定义 取平面区域 中任意两点作连线，若连线上任意点 总在区域 中，则称 为凸形区域定义 取平面区域 中任意两点，若连线上存在一点 不在区域 中，则称 为凹形区域定义 平面内包含区域 的最小凸形区域，称为 的凸壳［］定义 凹形区域 的凸壳与 自身作差得到的部分，称为 的内侧如图 所示，为凹形区域 的内侧图 为凹形区域 的内侧定义 令为凹形区域，为的内侧，则和的拓扑关系可以表示为如下的扩展 交集矩阵:[ ]其中， 分别表示 的内部， 分别表示 补集的内部定义 令 为带单洞区域，为 的洞区域，则 和 的拓扑关系可以表示为如下的扩展 交集矩阵:[ ]模式识别与人工智能 卷其中， 分别表示 的内部， 分别表示补集的内部相同的思路，一个凹形区域和一个带单洞区域( 如图所示) 间的拓扑关系可通过 个区域间的拓扑关系表示定义 令 为凹形区域，为 的内部，为带单洞区域，为 的洞区域，则 的拓扑关系可以表示为如下的 交集矩阵:( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )其中， 分别表示 的内部，分别表示 补集的内部B ACD图 一个凹形区域与一个带单洞区域令 ，其中，，，，等于或，定义 中的 交集矩阵可以进一步记为因而，对于任意的凹形区域和带单洞区域，可用一个的 矩阵表示它们之间的关系 可得种 矩阵，这些矩阵可表示 种凹形区域和带洞区 域 间 的 拓 扑 关 系( 包括可实现和不可实现) 这些 矩阵和 间的拓扑关系一一对应:
　　交集模型的性质本节将讨论 交集模型的若干性质，特别是与 交集模型之间的联系定义 在集合{ ，} 上定义 运算，如表所示对任意 阶 矩阵 ( ) 和( ) ，定义 ( )表 在{ ，} 上的 的运算{ ，}命题 ( ) ( ) ( )记 关系集为 ( 参见表) ，其中[ ]，[ ]，[ ]，[ ]，[ ]{ }对于任意两个简单区域 和，它们的拓扑关系对应的矩阵必属于集合 由命题 可得:定理 凹形区域和带单洞区域，分解为区域，如图 所示，则必有，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，) ，这里，，( )( ) ( ) ( ) ( )同理可得以下格式:，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，) ，期 李 健 等: 凹形区域和带单洞区域间拓扑关系的表示，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，) ，，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，) ，，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，) ，，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，)事实上，定理给出一个 交集矩阵能对应一个可实现拓扑关系的必要条件因为两个集合的交集有且仅有空和非空两种情形定理 交集矩阵模型给出的 个区域间的拓扑关系两两互斥且完备即对任意的 个区域，有且仅有这些关系中的一种，使得有序对 ，，， 满足该关系约束条件为得到所有可实现的 交集模型，下面将加入约束条件以排除不可实现的情形由定理， 交集矩阵模型中对应的元素做运算，恰为相应的两个区域间的拓扑关系因此任意一个 交集矩阵中对应元素做 运算的结果应在 关系集内，这样的 交集矩阵模型才是简单区域可实现的情形 下 面 给 出 个 约束条件约束条件 一种可实现的拓扑关系所对应的一个 交集矩阵满足以下条件:，( )，( )，( )，( )，，( )，( )，( )，( )，，( )，( )，( )，( )，，( )，( )，( )，( )，，( )，( )，( )，( )，，( )，( )，( )，( )约束条件 对于简单区域 ，，，，有必然非空，即约束条件 对于凹形区域和带单洞区域的四个部分 ，有 与 相离( 其中 是 的内侧) ， 包含，也就是 是区域 的洞所以可得如下两个表达式:，( )，( )，( )，( )( ) ( )( ) ( )( ，)[ ]，模式识别与人工智能 卷，( )，( )，( )，( )( ) ( )( ) ( )[ ]( ，)[ ]在此个约束条件下，通过程序计算可得到种 交集矩阵即对任意的凹形区域和带单洞区域对应的交集矩阵，理论上存在 种，但考虑到给出的 个约束条件，排除掉不可实现的情况，最后可得 种 交集矩阵是否这 个 交集矩阵的每个都能对应一个可实现的凹形区域和带单洞区域间的拓扑关系，将逐一验证图 给出序号为的部分拓扑关系图( 详细 种拓扑关系图可联系作者)定理 所有 交集模型给出的凹形区域和带单洞区域间可实现的 种拓扑关系是两两互斥且完备的证明 根据 交集模型的定义，其给出的凹形区域和带单洞区域间的 种拓扑关系( 包括可实现和不可实现的情况) 是两两互斥且完备的，所以只需说明其中可实现的拓扑关系有且仅有种上述的约束条件 ，，是拓扑关系可实现的必要条件，通过这个约束条件得到 种可能实现的拓扑关系，且可穷举出这 种拓扑关系的示意图由于篇幅有限，文中只列出前 种拓扑关系( 如表所示) ，因此凹形区域和带洞区域间可实现的拓扑关系有 种且是两两互斥且完备与相关研究工作的比较与相关凹形区域及带洞区域工作的比较年， 等［］研究简单区域和带单洞区域间的拓扑关系，分别考虑简单区域带单洞区域及洞身区域这 者两两间的二元拓扑关系，定义简单区域和带单洞区域间的 种基本拓扑关系年，欧阳继红等［］通过将 交集矩阵的元素扩展为二进制编码，提出一种表达带洞区域拓扑关系的 交集模型年，欧阳继红等扩展交集矩阵为 交集矩阵，定义描述两个简单凹形区域间拓扑关系的模型将本文提出的 交集模型与这 种模型比较，分析如下) 交集模型是基于 提出的，因此对物体边界是不敏感的; 以上种模型均是在 的期 李 健 等: 凹形区域和带单洞区域间拓扑关系的表示基础上扩展得到且边界敏感) 交集模型主要针对单个凹形区域和单个带单洞区域间拓扑关系，其它 个模型研究对象分别如下( ) 模型( 简称为模型) 主要描述单个简单区域和单个带单洞区域间的拓扑关系对于模型中的 种基本拓扑关系，本文 交集模型均能表达，模型 可看作 交集模型的一种特例( ) 交集模型( 简称为模型) 主要给出一种能同时描述简单区域和带洞区域拓扑关系的通用方法模型中能表示的拓扑关系， 交集模型也能表达; 而模型 不能表达凹形区域和带洞区域间的拓扑关系( ) 模型( 简称为模型) 则研究两个简单凹形区域间的拓扑关系模型中的 交集矩阵是将两个凹形区域分别划分成互不相交且联合完备的个子部分，再考虑一个区域的个子部分与另一区域个子部分间两两相交的情况; 而 交集模型则是将凹形区域和带单洞区域分别划分成两个子部分，考虑每个区域的两个子部分之间及和另一个区域两个子部分间的相交情况模型 能区分出种拓扑关系，而 交集模型能区分出 种拓扑关系从上述工作分析对比中可看出 交集模型在描述凹形区域和带洞区域等非简单区域的拓扑关系时，表达力强于其它 种模型
　　结 束 语
　　本文通过改进 等［］提出的经典 交集矩阵，使其它能描述边界无关的 关系基于扩展 交集矩阵，考虑两个简单区域间内部及其补集内部的两两相交情况，定义一个 交集矩阵，对凹形区域和带单洞区域间的拓扑关系进行表示，得到并给出凹形区域和带单洞区域间的 种拓扑关系图，且通过算法验证这 种关系的完备性和互斥性通过比较分析，本文提出的模型与其它相关研究工作表达力更强当区域都是凹形区域时，拓扑关系会变得更为复杂，下一步工作是对两个( 或多个) 凹形带洞区域的空间关系进行研究
    参 考 文 献 刘大有，刘 亚 彬空 间 推 理 与 地 理 信 息 系 统 综 述软 件 学 报， 孙纯哲，林巨广，楼赣菲，等凹形障碍全局路径规划的双蚁群完全交叉算法农业机械学报， ，( ) : ) 郭 泺，杜世宏，王 桥基于方向关系的不确定区域拓扑关系推理北京大学学报: 自然科学版， ，( ) : )  刘大有，胡 鹤，王 生 生，等时空推理研究进展 软 件 学 报，  欧阳继红，霍琳琳，刘大有，等能表达带洞区域拓扑关系的扩展 交集模型吉林大学学报: 工 学 版， ，( ) :  邓 敏，冯学智，刘文宝，等地理信息系统中拓扑关系的不确定性推理的方法模式识别与人工智能， 欧阳继红，富 倩，刘大有一种简单凹形区域间拓扑关系的表示模型吉林大学学报: 理学版，