166
Paola Podest` a, Barbara Catania, and Alberto Belussi
the intersections between the boundaries of a particular tile and the target object A,
using nine bits (x 0 –x 8 ). Bit 0 (x 0 ) records the value of the intersection between A
and the direction tile the vector refers to, say DT, and bits x 1 –x 8 record the values of
the intersections between A and the Left (L), Bottom-Left (BL), Bottom (B), BottomRight (BR), Right (R), Top-Right (TR), Top (T), and Top-Left (TL) boundaries of DT,
respectively. Each neighbor code corresponds to a binary number between 0 and 256.
Thus, each matrix can be seen as a 3×3 matrix of integer numbers. Different matrix
configurations correspond to different cardinal relations. However, by considering
only connected objects, not all possible configurations represent a correct cardinal
directional relation.
The information contained in neighbor codes can also be represented by using a
5×5 matrix, called directional matrix (see Fig. 8.3(c)). In such a matrix, a row and
a column exist for each tile interior and each boundary between two tiles, according
to the space subdivision presented in Fig. 8.2(d). Each matrix element can assume
the value empty or non-empty, depending on whether the target object A intersects
or does not intersect the corresponding portion of space.
A formal model for cardinal directional relations for connected and disconnected
regions, lines, and points is provided in [16, 17], based on the 5×5 matrix.
Consistency of cardinal directional relations has been discussed in [12, 13], in
the context of specialization and generalization operations, by considering binary
3×3 matrices as reference model and introducing the concept of compatibility. A
matrix D 1 is compatible with a matrix D 2 if, for each non-zero element in D 2 , the
corresponding element in D 1 is non-zero. The main problem of this consistency notion is that it is not symmetric. In the same papers, two distance functions for cardinal
relations have been defined. The first is defined for single-tile relations; that is, relations corresponding to intersections of the target object with a single tile, and it
corresponds to the minimum length of the paths connecting the two directions in
a conceptual graph (see Fig. 8.3(e)). Such graph contains a node for each tile and
one edge between pairs of tiles sharing at least one border. The second is defined
for multi-tile relations; that is, relations corresponding to intersections of the target
object with multiple tiles, and it considers the percentage of target object belonging
to each tile. The main problem of this approach is that it does not rely on the model
used for defining cardinal relations and checking compatibility. We believe this is an
important requirement in order to support cardinal directional relations in a complete
and easily implementable way.
8.3 Motivating Scenarios
To explain the basic idea underlying the proposed approach, in the following we
present a more detailed example for each application context pointed out in the
introduction: (i) similarity-based processing in a distributed environment; (ii) query
processing in GIS mediation architectures; (iii) consistency checking for spatial data
sets. Before presenting such scenarios, we introduce the reference spatial model used
in the rest of this chapter.
Paola Podest` a, Barbara Catania, and Alberto Belussi
the intersections between the boundaries of a particular tile and the target object A,
using nine bits (x 0 –x 8 ). Bit 0 (x 0 ) records the value of the intersection between A
and the direction tile the vector refers to, say DT, and bits x 1 –x 8 record the values of
the intersections between A and the Left (L), Bottom-Left (BL), Bottom (B), BottomRight (BR), Right (R), Top-Right (TR), Top (T), and Top-Left (TL) boundaries of DT,
respectively. Each neighbor code corresponds to a binary number between 0 and 256.
Thus, each matrix can be seen as a 3×3 matrix of integer numbers. Different matrix
configurations correspond to different cardinal relations. However, by considering
only connected objects, not all possible configurations represent a correct cardinal
directional relation.
The information contained in neighbor codes can also be represented by using a
5×5 matrix, called directional matrix (see Fig. 8.3(c)). In such a matrix, a row and
a column exist for each tile interior and each boundary between two tiles, according
to the space subdivision presented in Fig. 8.2(d). Each matrix element can assume
the value empty or non-empty, depending on whether the target object A intersects
or does not intersect the corresponding portion of space.
A formal model for cardinal directional relations for connected and disconnected
regions, lines, and points is provided in [16, 17], based on the 5×5 matrix.
Consistency of cardinal directional relations has been discussed in [12, 13], in
the context of specialization and generalization operations, by considering binary
3×3 matrices as reference model and introducing the concept of compatibility. A
matrix D 1 is compatible with a matrix D 2 if, for each non-zero element in D 2 , the
corresponding element in D 1 is non-zero. The main problem of this consistency notion is that it is not symmetric. In the same papers, two distance functions for cardinal
relations have been defined. The first is defined for single-tile relations; that is, relations corresponding to intersections of the target object with a single tile, and it
corresponds to the minimum length of the paths connecting the two directions in
a conceptual graph (see Fig. 8.3(e)). Such graph contains a node for each tile and
one edge between pairs of tiles sharing at least one border. The second is defined
for multi-tile relations; that is, relations corresponding to intersections of the target
object with multiple tiles, and it considers the percentage of target object belonging
to each tile. The main problem of this approach is that it does not rely on the model
used for defining cardinal relations and checking compatibility. We believe this is an
important requirement in order to support cardinal directional relations in a complete
and easily implementable way.
8.3 Motivating Scenarios
To explain the basic idea underlying the proposed approach, in the following we
present a more detailed example for each application context pointed out in the
introduction: (i) similarity-based processing in a distributed environment; (ii) query
processing in GIS mediation architectures; (iii) consistency checking for spatial data
sets. Before presenting such scenarios, we introduce the reference spatial model used
in the rest of this chapter.