8 Using Qualitative Information in Query Proc. over Multiresolution Maps
177
(iii) If S(θ 2 ) ⊂ S(θ 1 ), then
1
|S (θ 2 )|×|(S (θ 1 )−S (θ 2 )|
θ
s
i ∈S (θ 2 )
θ
s
j ∈S (θ 1 )−S (θ 2 )
Path Min (θ
s
i , θ
s
j ).
(iv) In all the other cases
1
X+Y (
θ
s
i ∈S (θ 2 )
θ
s
j ∈S (θ 1 )−S (θ 2 )
Path Min (θ
s
i , θ
s
j ) +
θ
s
i ∈S (θ 1 )
θ
s
j ∈S (θ 2 )−S (θ 1 )
Path Min (θ
s
i , θ
s
j ))
where X = |S (θ 1 )| × |S (θ 2 ) − S (θ 1 )| and Y = |S (θ 2 )| × |S (θ 1 ) − S (θ 2 )|.
It is easy to show that function d path is symmetric and its value ranges between
0 and 4 (the maximum length of a path connecting two tiles). The cardinal distance
of two cardinal relations θ 1 and θ 2 can now be defined as the product of d path (θ 1 , θ 2 )
and their matrix-based distance. Such a distance is then normalized to get a value
between 0 and 1. Thus, as d path ranges in [0, 4] and d m ranges in [0, 9], the product is
divided by 36. The resulting distance extends the distances presented in [12, 13] to
cope with multi-tile relations.
Definition 8.5 (Cardinal Distance). Let θ 1 ∈ CREL(d 1 , d 2 ), θ 2 ∈ CREL(d 3 , d 4 ). Let
θ 1 = R 1 : .... : R k and θ 2 = S 1 : .... : S h . The cardinal distance between θ 1 and θ 2 ,
denoted by d c (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )), is defined as follows:
d c (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) =
1
36
d path (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) × d m (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )).
Figure. 8.8 presents some values for d c (NW, (R, R), θ 2 , (d 3 , d 4 )), with d 3 P. As
expected, we notice that d c increases by increasing the number of different singletiles in the two input cardinal directional relations, since in this case d m increases, and
by increasing the distance between the tiles corresponding to the relation supports,
since in this case d path increases.
Fig. 8.8. Some distance values for the NW cardinal directional relationship
177
(iii) If S(θ 2 ) ⊂ S(θ 1 ), then
1
|S (θ 2 )|×|(S (θ 1 )−S (θ 2 )|
θ
s
i ∈S (θ 2 )
θ
s
j ∈S (θ 1 )−S (θ 2 )
Path Min (θ
s
i , θ
s
j ).
(iv) In all the other cases
1
X+Y (
θ
s
i ∈S (θ 2 )
θ
s
j ∈S (θ 1 )−S (θ 2 )
Path Min (θ
s
i , θ
s
j ) +
θ
s
i ∈S (θ 1 )
θ
s
j ∈S (θ 2 )−S (θ 1 )
Path Min (θ
s
i , θ
s
j ))
where X = |S (θ 1 )| × |S (θ 2 ) − S (θ 1 )| and Y = |S (θ 2 )| × |S (θ 1 ) − S (θ 2 )|.
It is easy to show that function d path is symmetric and its value ranges between
0 and 4 (the maximum length of a path connecting two tiles). The cardinal distance
of two cardinal relations θ 1 and θ 2 can now be defined as the product of d path (θ 1 , θ 2 )
and their matrix-based distance. Such a distance is then normalized to get a value
between 0 and 1. Thus, as d path ranges in [0, 4] and d m ranges in [0, 9], the product is
divided by 36. The resulting distance extends the distances presented in [12, 13] to
cope with multi-tile relations.
Definition 8.5 (Cardinal Distance). Let θ 1 ∈ CREL(d 1 , d 2 ), θ 2 ∈ CREL(d 3 , d 4 ). Let
θ 1 = R 1 : .... : R k and θ 2 = S 1 : .... : S h . The cardinal distance between θ 1 and θ 2 ,
denoted by d c (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )), is defined as follows:
d c (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) =
1
36
d path (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) × d m (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )).
Figure. 8.8 presents some values for d c (NW, (R, R), θ 2 , (d 3 , d 4 )), with d 3 P. As
expected, we notice that d c increases by increasing the number of different singletiles in the two input cardinal directional relations, since in this case d m increases, and
by increasing the distance between the tiles corresponding to the relation supports,
since in this case d path increases.
Fig. 8.8. Some distance values for the NW cardinal directional relationship