基于MBR的拓扑、方位、尺寸结合的定性空间推理  

Integrative Reasoning with Topological,Directional and Size Information Based on MBR

作　　者：陈娟[1,2] 刘大有[1,2] 贾海洋[1,2] 张长海[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《计算机研究与发展》2010年第3期426-433,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60496321;60573073;60603030;60773099;60703022);国家"八六三"高技术研究发展计划基金项目(2006AA10Z245);教育部高等学校博士学科点专项科研基金项目(20070183057);吉林大学基本科研业务费专项基金项目(421032041421)

摘　　要：解决实际问题需将多方面空间关系结合进行推理,多方面空间关系结合推理已成为定性空间推理的研究热点;已有工作主要集中在两方面空间关系结合,缺少两方面以上空间关系结合工作.为解决上述问题,通过最小外包矩形近似表示区域对象,利用其在坐标轴上投影间的关系表示相应空间关系;提出扩展矩形关系模型,实现拓扑、方位和尺寸关系的统一表示和推理;给出RCC8、主方位及尺寸关系转换成扩展矩形关系的转换算法;讨论其上关系取反和复合,指出其复合是基于相容性而非存在性;证明(强预)凸扩展矩形关系约束网是可处理的.It is inadequate considering only one aspect of spatial information in practical problems, where several aspects are usually involved together. Reasoning with multi-aspect spatial information has become one of the focuses of qualitative spatial reasoning. Current research about the integrative reasoning concentrates on the reasoning with two aspects information and lacks the work over three or more aspects. To solve this problem, the extended rectangle relation is proposed to realize the integrative representing and reasoning of topology, direction and size information. Considering the high cost of representing and reasoning with single aspect spatial information and the need of efficiency, the minimal bounding rectangle （MBR） is used to approximate regions; so the spatial relations between regions can be presented by the relevant relations between the projections of MBRs on each axis. The translating algorithm which converts the RCC8, cardinal direction and size relations into extended rectangle relations is given. The basic reverse and composing operations are discussed, and it is pointed out that the composition of extended rectangle relations is based on consistency not existence. According to the definitions of convex and strongly preconvex extended rectangle relations, the consistency of the network consisting of these two sets of relations is proved to be decided in polynomial time.

关 键 词：定性空间推理 拓扑 方位 尺寸 扩展矩形关系 约束满足问题 

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]