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

Consistency checking for cardinal direction relations of point objects

作　　者：刘正林[1] 齐玉斌[1] 高爱华[1] 钱颖[2] 

机构地区：[1]河北科技师范学院欧美学院信息技术系,河北秦皇岛066004 [2]河北科技师范学院网络中心,河北秦皇岛066004

出　　处：《计算机工程与应用》2008年第26期51-54,共4页Computer Engineering and Applications

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

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

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