162
Paola Podest` a, Barbara Catania, and Alberto Belussi
The remainder of this chapter is organized as follows. In Sect. 8.2 we briefly
survey related work on topological and cardinal relationships. The reference spatial
model and motivating scenarios are discussed in Sect. 8.3. Distance functions for
topological and cardinal directional relationships are then presented in Sects. 8.4 and
8.5, respectively. In Sect. 8.6, the defined functions are used to provide consistency
checking methods. Examples of the application of the proposed approaches are then
presented in Sect. 8.7. Finally, Sect. 8.8 presents some conclusions and outlines future research directions.
8.2 Related Work
As remarked in Sect. 8.1, the techniques we propose for checking map similarity and
consistency rely on the definition of distance functions for topological and cardinal
directional relationships. Therefore, in the following we survey the most relevant
existing approaches for modeling and analyzing such spatial relationships.
8.2.1 Topological Relationships
Topological relations capture the essential spatial relationships between the objects
belonging to a map; they consider connectivity and adjacency of objects and are
invariant under continuous transformations of space such as translation, rotation, and
scaling.
The most relevant papers concerning the representation of topological properties are [6, 9, 10]. According to the model presented in [9], known as 4-intersection
model, spatial objects are modeled as point-sets describing their interior and their
boundary, as shown in Fig. 8.1(a). Only regions are considered and topological
relations are defined as 2×2 matrices, containing the value empty ( or 0) or nonempty (¬¬ or 1) for each intersection of the point-sets of the objects involved (see
Fig. 8.1(b)). As an example, Fig. 8.1(c) presents the 4-intersection model configuration for the topological relation Overlap between two regions.
The 4-intersection model has subsequently been extended by considering also
object exterior [10], leading to the definition of the 9-intersection model. In the
9-intersection model, each spatial object A is represented by 3 point-sets: its interior
A
◦ , its exterior A
− , and its boundary ∂A (see Fig. 8.1(d)). The definition of binary
topological relations between two spatial objects A and B is then based on the 9
intersections between each pair of object components. Thus, a topological relation
can be represented as a 3×3 matrix, called 9-intersection matrix (see in Fig. 8.1(e)).
As an example, Fig. 8.1(f) presents the 9-intersection model configuration for the
topological relation Overlap between two regions.
By considering the value empty or non-empty for each intersection, one can categorize in a complete way all the relationships between regions, lines, and points
embedded in R
2 . In [6], the 9-intersection model has been extended by considering
the dimension of the intersection. As the number of the resulting relationships is
quite high, a partition of extended 9-intersection matrices has been proposed in [6],
Paola Podest` a, Barbara Catania, and Alberto Belussi
The remainder of this chapter is organized as follows. In Sect. 8.2 we briefly
survey related work on topological and cardinal relationships. The reference spatial
model and motivating scenarios are discussed in Sect. 8.3. Distance functions for
topological and cardinal directional relationships are then presented in Sects. 8.4 and
8.5, respectively. In Sect. 8.6, the defined functions are used to provide consistency
checking methods. Examples of the application of the proposed approaches are then
presented in Sect. 8.7. Finally, Sect. 8.8 presents some conclusions and outlines future research directions.
8.2 Related Work
As remarked in Sect. 8.1, the techniques we propose for checking map similarity and
consistency rely on the definition of distance functions for topological and cardinal
directional relationships. Therefore, in the following we survey the most relevant
existing approaches for modeling and analyzing such spatial relationships.
8.2.1 Topological Relationships
Topological relations capture the essential spatial relationships between the objects
belonging to a map; they consider connectivity and adjacency of objects and are
invariant under continuous transformations of space such as translation, rotation, and
scaling.
The most relevant papers concerning the representation of topological properties are [6, 9, 10]. According to the model presented in [9], known as 4-intersection
model, spatial objects are modeled as point-sets describing their interior and their
boundary, as shown in Fig. 8.1(a). Only regions are considered and topological
relations are defined as 2×2 matrices, containing the value empty ( or 0) or nonempty (¬¬ or 1) for each intersection of the point-sets of the objects involved (see
Fig. 8.1(b)). As an example, Fig. 8.1(c) presents the 4-intersection model configuration for the topological relation Overlap between two regions.
The 4-intersection model has subsequently been extended by considering also
object exterior [10], leading to the definition of the 9-intersection model. In the
9-intersection model, each spatial object A is represented by 3 point-sets: its interior
A
◦ , its exterior A
− , and its boundary ∂A (see Fig. 8.1(d)). The definition of binary
topological relations between two spatial objects A and B is then based on the 9
intersections between each pair of object components. Thus, a topological relation
can be represented as a 3×3 matrix, called 9-intersection matrix (see in Fig. 8.1(e)).
As an example, Fig. 8.1(f) presents the 9-intersection model configuration for the
topological relation Overlap between two regions.
By considering the value empty or non-empty for each intersection, one can categorize in a complete way all the relationships between regions, lines, and points
embedded in R
2 . In [6], the 9-intersection model has been extended by considering
the dimension of the intersection. As the number of the resulting relationships is
quite high, a partition of extended 9-intersection matrices has been proposed in [6],