176
Paola Podest` a, Barbara Catania, and Alberto Belussi
Example 8.2. Consider maps M 4 , M 5 , M 6 shown in Fig. 8.7. The target object A
is a region in M 4 and becomes a line in map M 5 and in map M 6 , while the reference object B is a region in all the maps. Intuitively, map M 4 seems more similar to map M 5 than to map M 6 as target objects in M 4 and M 5 are spatially closer
than target objects in M 4 and M 6 . However, the matrix-based distance between
M 4 and M 5 coincides with the matrix-based distance between M 4 and M 6 . Indeed,
d m (NW:N, (2, 2), NE:E, (1, 2)) = d m (NW:N, (2, 2), SE:S, (1, 2)) = 4. Thus, function
d m is not able to discriminate between the two situations that are different.
The problem in the previous example is that function d m does not take into
account the distance between the two configurations in the plane. To consider this
aspect, given two cardinal directional relations θ 1 and θ 2 , it seems more reasonable
to define a distance function which takes into account the distance in the plane among
the single-tile relations contained in the support of θ 1 and θ 2 . In order to define such a
distance, we rely on the cardinal directional conceptual graph, shown in Fig. 8.3(e).
The conceptual graph contains a node for each single-tile and an edge between any
pair of adjacent tiles. Given two single-tile relations θ
s
1 and θ
s
2 ∈ CREL, that is, given
two nodes of the conceptual graph, we denote with Path Min (θ
s
1 , θ
s
2 ) the length of the
shortest path between θ
s
1 and θ
s
2 in the conceptual graph. The path-based distance
between two single or multi-tile relations, denoted by d path , is now defined by computing the average Path Min distance between each single tile of one relation and each
single tile of the other relation, which is not contained in the first one. Function d path
can be defined as follows.
Definition 8.4 (Path Distance). Let θ 1 ∈ CREL(d 1 , d 2 ), θ 2 ∈ CREL(d 3 , d 4 ), with
d 1 ,d 2 ,d 3 ,d 4 ∈ {R, L, P} . Let θ 1 = R 1 : .... : R k and θ 2 = S 1 : .... : S h . The path
distance between θ 1 and θ 2 , denoted by d path (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )), is defined as
follows:
(i) If S(θ 1 ) = S(θ 2 ), then 0.
(ii) If S(θ 1 ) ⊂ S(θ 2 ), then
1
|S (θ 1 )|×|S (θ 2 )−S (θ 1 )|
θ
s
i ∈S (θ 1 )
θ
s
j ∈S (θ 2 )−S (θ 1 )
Path Min (θ
s
i , θ
s
j ).
M 4
M 5
M 6
Fig. 8.7. Comparing different cardinal relations
Paola Podest` a, Barbara Catania, and Alberto Belussi
Example 8.2. Consider maps M 4 , M 5 , M 6 shown in Fig. 8.7. The target object A
is a region in M 4 and becomes a line in map M 5 and in map M 6 , while the reference object B is a region in all the maps. Intuitively, map M 4 seems more similar to map M 5 than to map M 6 as target objects in M 4 and M 5 are spatially closer
than target objects in M 4 and M 6 . However, the matrix-based distance between
M 4 and M 5 coincides with the matrix-based distance between M 4 and M 6 . Indeed,
d m (NW:N, (2, 2), NE:E, (1, 2)) = d m (NW:N, (2, 2), SE:S, (1, 2)) = 4. Thus, function
d m is not able to discriminate between the two situations that are different.
The problem in the previous example is that function d m does not take into
account the distance between the two configurations in the plane. To consider this
aspect, given two cardinal directional relations θ 1 and θ 2 , it seems more reasonable
to define a distance function which takes into account the distance in the plane among
the single-tile relations contained in the support of θ 1 and θ 2 . In order to define such a
distance, we rely on the cardinal directional conceptual graph, shown in Fig. 8.3(e).
The conceptual graph contains a node for each single-tile and an edge between any
pair of adjacent tiles. Given two single-tile relations θ
s
1 and θ
s
2 ∈ CREL, that is, given
two nodes of the conceptual graph, we denote with Path Min (θ
s
1 , θ
s
2 ) the length of the
shortest path between θ
s
1 and θ
s
2 in the conceptual graph. The path-based distance
between two single or multi-tile relations, denoted by d path , is now defined by computing the average Path Min distance between each single tile of one relation and each
single tile of the other relation, which is not contained in the first one. Function d path
can be defined as follows.
Definition 8.4 (Path Distance). Let θ 1 ∈ CREL(d 1 , d 2 ), θ 2 ∈ CREL(d 3 , d 4 ), with
d 1 ,d 2 ,d 3 ,d 4 ∈ {R, L, P} . Let θ 1 = R 1 : .... : R k and θ 2 = S 1 : .... : S h . The path
distance between θ 1 and θ 2 , denoted by d path (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )), is defined as
follows:
(i) If S(θ 1 ) = S(θ 2 ), then 0.
(ii) If S(θ 1 ) ⊂ S(θ 2 ), then
1
|S (θ 1 )|×|S (θ 2 )−S (θ 1 )|
θ
s
i ∈S (θ 1 )
θ
s
j ∈S (θ 2 )−S (θ 1 )
Path Min (θ
s
i , θ
s
j ).
M 4
M 5
M 6
Fig. 8.7. Comparing different cardinal relations