|
|
Oriented Point Relation Algebra
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 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.
The relations A RightLeft B (left) and A SameRight B (right)
 |
 |
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.
Granularity of with m=2 (left) and m=4 (right)
|
|
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 and defined as members of the cyclic group  .
The same o-points in relations for different values of m:
 (left) and
 (right)
|
|
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 the literature.
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
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.
| |
- Project R3-[Q-Shape]