Block Algebra-Based Consistency Checking With Cardinal Direction Relations in 3D Space

Abstract

Consistency checking, as a key and challenging problem in the research field of qualitative spatial reasoning with direction relations in 3D space, has received a lot of attention. It is widely used in 3D spatial configuration and anomaly detection in urban planning. To enrich and enhance the ability of reasoning and predict with 3D cardinal direction relations, a new approach for spatial projection on each axis is proposed on the basis of the 3DR27 model for cardinal direction relations in 3D space presented in our previous work. This paper divides the consistency checking of spatial direction relation networks into two processes. Firstly, the projection method is employed to determine whether a network with three-dimensional cardinal directional relations is a convex relation network. Then, by means of the good calculation properties of interval algebra and the mapping between 3D rectangular cardinal direction and 3-block algebra, an algorithm for consistency checking is proposed, which can be used to determine whether one or more than one solution can be found to satisfy the given network constraints. The results of theoretical analysis and verification show that our method is correct and complete. This method effectively improves the ability of intelligent analysis and processing for complex 3D spatial direction relations.

Keywords

• Consistency checking
• qualitative spatial reasoning
• 3D cardinal direction relations
• block algebra
• convex relation