计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (26): 51-54.DOI: 10.3778/j.issn.1002-8331.2008.26.015

• 理论研究 • 上一篇    下一篇

点物体主方向关系的一致性检验

刘正林1,齐玉斌1,高爱华1,钱 颖2   

  1. 1.河北科技师范学院 欧美学院 信息技术系,河北 秦皇岛 066004
    2.河北科技师范学院 网络中心,河北 秦皇岛 066004
  • 收稿日期:2007-11-07 修回日期:2008-03-10 出版日期:2008-09-11 发布日期:2008-09-11
  • 通讯作者: 刘正林

Consistency checking for cardinal direction relations of point objects

LIU Zheng-lin1,QI Yu-bin1,GAO Ai-hua1,QIAN Ying2   

  1. 1.Dept. of Info. Tech.,Europe&America College,Hebei Normal University of Science and Technology,Qinhuangdao,Hebei 066004,China
    2.Network Center,Hebei Normal University of Science and Technology,Qinhuangdao,Hebei 066004,China
  • Received:2007-11-07 Revised:2008-03-10 Online:2008-09-11 Published:2008-09-11
  • Contact: LIU Zheng-lin

摘要: 一致性检验问题是主方向关系推理中非常重要的基础理论问题,提出了一种利用欧几里德空间坐标图实施一致性检验的新方法。首先对研究的问题进行了定义,阐述了方向关系的坐标图表示方法,从而使得对点物体方向关系约束集的一致性检验就转化为检测图中是否存在环的问题,通过一致性判定、环的检测、实施方法这3个环节来具体实现。其算法的时间复杂度是O(n+e),优于传统的O(n2

关键词: 一致性检验, 方向关系约束集, 坐标图

Abstract: In this paper,the authors address the problem of consistency checking for point objects.A coordinates graph representation is proposed to maintain the Euclidean spatial constraints among point objects.The basic idea is to project the spatial constraints on both X and Y coordinates,and the coordinates graph is constructed on each coordinates.By using the coordinates graph representation,the problem of consistency checking is then transformed to a graph cycle detection problem.The consistency checking can be achieved with O(n+e)time as well as space complexity,where n is the number of spatial objects,and e is number of direction predicates in the constraint.The proposed approach to consistency checking for point objects is faster than O(n2)when the number of predicates is much smaller than n2.

Key words: consistency checking, constraint sets of direction predicates, coordinates graph