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