An utility package for rectangular cardinal relations. Qualitative spatial representation and reasoning plays a important role in various spatial applications. In this paper we introduce a formalism, we name RCD, for qualitative spatial reasoning with cardinal direction relations between regions of the plane approximated by rectangles. Our calculus suppose an attractive balance between efficiency of the reasoning tasks, simplicity and expressive power, which makes it adequate for applications. We address spatial reasoning using methods embedded in the paradigm of constraint satisfaction problems. We identify a large tractable subclass of the full calculus, exploiting the well-known notion of convex relations from the context of the Interval Algebra and the Rectangle Algebra, that allow to reason efficiently with definite and indefinite or imprecise knowledge about spatial configurations represented in a qualitative constraint network. For such tractable fragment we propose various polynomial algorithms to solve the consistency problem, as well as to find a consistent scenario and the minimal network, by means of a suitable translation between relations expressed in different constraint languages.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element