R3-[Q-Shape] - Research: Qualitative Spatial Reasoning
Oriented Point Relation Algorithm (OPRA)
A Relative Orientation Algebra with Adjustable Granularity
The granularity of spatial calculi and the resulting mathematical properties have always been a major question in solving spatial tasks qualitatively. The Oriented Point Relation Algebra 
is a new orientation calculus with adjustable granularity. Since it is a relation algebra in the sense of Tarski, fast standard inference methods can be applied.
The Calculus
In most prior approaches objects and locations are represented as simple, featureless points.
is based on objects which are represented as oriented points. O-points, our term for oriented points, are specified as pair of a point and a direction on the 2D-plane.
The coarsest representation of a single o-point induces the sectors depicted in the picture on the right. "Front" and "Back" are linear sectors. "Left" and "Right" are half-planes. The position of the point itself is denoted as "Same".
Reasoning with Coarse O-Point Relations
For the general case of the two points having different positions we use the concatenated string of both sector names as the relation symbol. Then the configuration shown in the picture on the right is A RightLeft B. If both points share the same position the relation symbol starts with the word "Same" (see picture below)
The coarsest representation (m=1) contains 20 different atomic relations (four times four general relations plus four with the o-points at the same position).
These relations are jointly exhaustive and pairwise disjoint (JEPD). The relation SameFront is the identity relation.
 |
 |
Finer grained O-Point Calculi
The design principle for 
can be generalized to calculi with arbitrary 
. Then an angular resolution of 
is used for the representation.
 |
 |
For o-points A and B at different positions, the relation 
reads like: Given a granularity m, the relative position of B with respect to A is described by j, and the relative position of A with respect to B is described by i. Note that i and j are defined as members of the cyclic group 
. Below, the same o-points in relations for different values of m: 
(left) and 
(right) are presented.
 |
 |
Composition
Composition of two relations and 
is mainly a composition of angular intervals, which translates to additions of elements of . If we want to describe the relative position of C with respect to A, we need to combine the angular intervals which correspond to i, j and k. The first possible sector which can contain C is either i or i-j+k-2m-2, depending on which one is "first" in a circular order. The composition rule is given as an algebraical formula. For details on the composition see [MoDyFr05].
The example to the right shows the composition of two relations and with m=4. The values in this example are i=13, j=5 and k=11. Because the direction of C is not depicted in this example, no value of l is given. As a result of the composition, C may lie in sectors 9 to 13 with respect to A.
Literature
[MoDyFr05]: Reinhard Moratz, Frank Dylla, and Lutz Frommberger. A relative orientation algebra with adjustable granularity. In Proceedings of the Workshop on Agents in Real-Time and Dynamic Environments (IJCAI 05), 2005.
