ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
between direction tile and target object is not empty and 0 n °
is not empty in the 4I matrix, then the target object is entirely fall
in this direction region.
Rule 3. For one direction region, If the intersection of 3n”
between direction tiles and target object is not empty, the target
object falls not only in this direction region.
B is not only in the direction region NE A (Fig 1a).
(dlAB D d 2 AB D ••• ndiAB) co(diBCnd2BC n •" ndiBc) = dlAB°°dlBC
U diAB°°d2BC u ••• U diAB°°diBC U d 2 AB°°dlBC D d2AB c °d2BC U ••• u
d2AB c °diBC u U diAB°°diBC U djAB c °d2BC D ••• U diAB^diBC
For example, given the direction relation between target object B
and reference object A; the direction relation between target
object C and reference object B, the direction relation between
target object C and reference object A can be deduced from the
composition of (Nab FI NE A b n E a b )oo(NW B c n W B c )•
Rule 4. Only if the target object meets with the boundary of one
direction region, detailed direction matrix is needed to
complement 4I matrix.
In order to describe directions more intuitionist, we use the 3x3
tessellation of square cells to capture the neighborhood of the
partition around the reference object and registers the
intersections between the target and reference object (Fig. 2).
For example, the two square cell matrixes for the two
configurations in Fig. 1a and 1b are given in Fig. 2a and 2b,
respectively. In square cell matrix, black cells represent
non-empty intersection direction tiles, while white one for empty
intersection direction tiles. If the value of an intersection is
unknown, gray cells are used.
rm Si
(a). (b)
i
»
I
f
Fig.2 square ceil matrix
Fig.3 composition result
Definition 1 (single-item direction relationjlf there is only one
none-empty intersection direction tile, this direction relation is
called single-item direction relation.
Definition 2(multi-item direction relationjlf there exist multi
none-empty intersection direction tiles, this direction relation is
called multi-item direction relation.
Composition table captures all compositions of a set of relations.
The 9x9 single-item direction composition table can be
computed according to the property of projection-based direction
Fig.4 composition result ot single-item direction relations
3 DIRECTION RELATIONS REASONING AND ITS DISTANCE
REFINEMENT
Given the direction relation between area object A and B; and
the relation between B and C, the direction relation between A
and C can be deduced. The single-item direction relation
compositions are given from the composition table (Fig. 4), while
two multi-item direction compositions are broken down into the
composition of single-item direction.
(Nab H NEab H Eab )co(NWbc Fl Wbc )~ Nab°°NWbc U
Nab°°Wbc U NEab^NWbc U NEab^Wbc U Eab« 3 NW B c U E A b«Wbc =
X, X,’X 2 X 2 ’
Fig.5 cardinal directions between objects
The coarse composition result can be further refined according
to the objects maximum and minimum X and Y coordinates.
Given the direction relation between object B and C (Fig. 5), we
can conclude object C’s X coordinate is less or equal to B's
minimum X coordinate(X c ^Xi’). Again from the given direction
relations between object A and B, X^ must less A’s maximum X
coordinate(Xi’<X 2 )(so C’s X coordinate must less X 2 )X C <X2). the
m ;
final result of the composition is: : Fl
Similarly, the direction relations between target object D and
reference object A can be deduced from the composition of (N A b
fl NEabC Eab )°°(SEbdTiSbd ), it is: 8
4 DETAILED DIRECTION RELATION DESCRIPTIONS
There are 218 varied different configurations using our 4I
direction description matrix according to the constraints about
4-connecteness of direction square cells (Goyal 1999), while
Allen’s interval model distinguishes 169 different direction
combinations between two MBRs. However 4I direction matrix
cannot distinguish some group of direction combinations that
Allen’s interval model can do, as shown in figure 6. This is
because primary direction matrix cannot tell which direction tiles’
boundary a target object meets, so detailed direction matrixes
are needed as a refiner. We use V 1 ,V2,V 3 ,V 4 to mark the
minimum bounding rectangles of reference object (Fig 6), then
we get 4 close line V 1 -V 2 ,V 2 -V3,V3-V 4 ,V 4 -Vi, and 8 open
lineV 1 -N,V 1 -W,V2-N,V2-E,V3-S,V 3 -E,V 4 -S,V 4 -W, where V,-N
means the open line with V, as starting point and stretches in N
direction, etc. We use equations 10-13 to differentiate which
direction tiles’ boundary a target object meets; so that more
varied different conditions can be distinguished. For example,
using equation 10 and 11, different direction relations can be
distinguished in fig 7, while 4I direction matrix cannot.
Fig.6 12 objects around the reference