8 Using Qualitative Information in Query Proc. over Multiresolution Maps
165
of its box. The tiles result in the usual set of directions {N, NE, E, MBB, SE, S, SW, W,
NW}. We notice that all tiles, excluding MBB, are unbounded. Their union coincides
with R
2 .
Based on the D 9 model, cardinal relations between two regions can be represented as 3×3 matrices containing the value empty or non-empty for each intersection between the target object A and the tiles generated by a reference object B (see
Fig. 8.3(a)). In [12, 13], this basic model has been extended to deal with regions
without holes, lines, and points. In this case, a cardinal directional relation is represented again using a 3×3 matrix, but now each cell contains a 9-cells vector, called
neighbor code (see Fig. 8.3(b)). A neighbor code records information concerning
dir RR (A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
NW B ∩ A N B ∩ A NE B ∩ A
W B ∩ A MBB B ∩ A E B ∩ A
S W B ∩ A S B ∩ A SE B ∩ A
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
(a)
(b)
D(A, B) =
⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
NW B ∩ A N-NWL B ∩ A N B ∩ A N-NEL B ∩ A NE B ∩ A
W-NWL B ∩ A NWP B ∩ A NL B ∩ A NEP B ∩ A
E-NEL B
W B ∩ A
W B
MBB B ∩ A
E B ∩ A
E B ∩ A
W-S WL B ∩ A SWP B ∩ A SL B ∩ A SEP B ∩ A E-S EL B ∩ A
S W B ∩ A S-S WL B ∩ A S B ∩ A S-S EL B ∩ A SE B ∩ A
⎞
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
(c)
(d)
(e)
Fig. 8.3. Models for cardinal directional relationships: (a) the 3×3 directional matrix; (b)
the neighbor code; (c) the 5×5 directional matrix; (d) space subdivision corresponding to the
directional matrix; (e) the cardinal directional conceptual graph