Spatial Reasoning Combining Topological and Cardinal Directional Relation Information

RCC8 calculus (RCC8) and cardinal direction calculus (CDC) based on regions in qualitative spatial reasoning are combined and the interaction tables for the two calculi in two directions, i.e. RCC8-To-CDC and CDC-To-RCC8, are presented. The path consistency algorithm for constraint satisfaction problems combining RCC8 and CDC knowledge is proposed, which is the adaptation of Allen's famous algorithm. The path consistency algorithm is implemented using two queues, which can be operated in parallel. In this algorithm, the interaction operation based on the interaction tables is embedded into it to enforce the whole consistency for the CSPs combining RCC8 and CDC knowledge. The computational complexity of this algorithm is polynomial.