摘要
一致性检验问题是主方向关系推理中非常重要的基础理论问题,提出了一种利用欧几里德空间坐标图实施一致性检验的新方法。首先对研究的问题进行了定义,阐述了方向关系的坐标图表示方法,从而使得对点物体方向关系约束集的一致性检验就转化为检测图中是否存在环的问题,通过一致性判定、环的检测、实施方法这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.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第26期51-54,共4页
Computer Engineering and Applications
关键词
一致性检验
方向关系约束集
坐标图
consistency checking
constraint sets of direction predicates
coordinates graph
