Reasoning with Cardinal Directions in 3D Space Based on Block Algebra

Abstract

Spatial relations have been studied in various interrelated areas such as qualitative spatial reasoning, geographic information science, image retrieval, and others. Direction as one of the most important spatial relations has received much attention. In this paper, we introduce a new formalism, we name BCD calculus, for qualitative spatial reasoning with block cardinal direction relations between blocks in 3D space. Based on the theory of block algebra, the correlations between block cardinal direction relations in 3D and block algebra are explained, and the tractable subset of convex block cardinal direction relations is identified. We show that the consistency problem for convex block cardinal direction network can be solved in polynomial time, by translating qualitative networks of BCD calculus to qualitative network of block algebra and applying a suitable adaption of path consistency algorithm.