8 Using Qualitative Information in Query Proc. over Multiresolution Maps
175
Table 8.2. Definition of the semantics of the basic cardinal directional relations BCR. A is the
target object and B is the reference object
name
definition
type of the refer. obj. B
NW
in f y (A)> sup y (B), in f x (B)> sup x (A)
REG ∪ S LINE
in f y (A)> y B , in f x (B)> sup x (A)
H LINE
in f y (A)> sup y (B), x B > sup x (A)
V LINE
in f y (A)> y B , x B > sup x (A)
POINT
N
in f x (B)≤ in f x (A), sup x (A)≤ sup x (B), sup y (B)< in f y (A)
REG ∪ S LINE
y B < in f y (A), in f x (B)≤ in f x (A), sup x (A)≤ sup x (B)
H LINE
in f x (A)≤ x B ≤ sup x (A), in f y (A)< sup y (B)
V LINE
in f x (A)≤ x B ≤ sup x (A),y B < in f y (A)
POINT
NE
in f y (A)> sup y (B), sup x (B)< in f x (A)
REG ∪ S LINE
in f y (A)> y B , sup x (B)< in f x (A)
H LINE
in f y (A)> sup y (B), x B < in f x (A)
V LINE
in f y (A)> y B , x B < in f x (A)
POINT
W
in f y (B)≤ in f y (A), sup y (A)≤ sup y (B), in f x (B)> sup x (A)
REG ∪ S LINE
sup x (A)< in f x (B), in f y (A)≤ y B ≤ sup y (A)
H LINE
sup x (A)< x B , in f y (B)≤ in f y (A), sup y (A)≤ sup y (B)
V LINE
in f y (A)≤ y B ≤ sup y (A), x B > sup x (A)
POINT
MBB in f x (B)≤in f x (A), sup x (A)≤sup x (B), in f y (B)≤in f y (A), sup y (A)≤sup y (B)
REG ∪ S LINE
in f x (B)≤ in f x (A), sup x (A)≤ sup x (B),in f y (A)≤ y B ≤ sup y (A)
H LINE
in f y (B)≤ in f y (A), sup y (A)≤ sup y (B), in f x (A)≤ x B ≤ sup x (A)
V LINE
(x B ,y B )∈ A
POINT
E
in f y (B)≤ in f y (A), sup y (A)≤ sup y (B), sup x (B)< in f x (A)
REG ∪ S LINE
in f y (A)≤ y B ≤ sup y (A), sup x (B)< in f x (A)
H LINE
in f y (B)≤ in f y (A), sup y (A)≤ sup y (B), x B < in f x (A)
V LINE
in f y (A)≤ y B ≤ sup y (A), x B < in f x (A)
POINT
SW
sup y (A)< in f y (B), in f x (B)> sup x (A)
REG ∪ S LINE
sup y (A)< y B , in f x (B)> sup x (A)
H LINE
sup y (A)< in f y (B), x B > sup x (A)
V LINE
sup y (A)< y B , x B > sup x (A)
POINT
S
in f x (B)≤ in f x (A), sup x (A)≤ sup x (B), in f y (B)> sup y (A)
REG ∪ S LINE
sup y (A)< y B , in f x (B)≤ in f x (A), sup x (A)≤ sup x (B)
H LINE
in f x (A)≤ x B ≤ sup x (A), sup y (A)< in f y (B)
V LINE
in f x (A)≤ x B ≤ sup x (A), sup y (A)< y B
POINT
SE
sup y (A)< in f y (B), sup x (B)< in f x (A)
REG ∪ S LINE
sup y (A)< y B , sup x (B)< in f x (A)
H LINE
sup y (A)< in f y (B), x B < in f x (A)
V LINE
sup y (A)< y B , x B < in f x (A)
POINT
done for topological relations. Such a distance, denoted by d 25 , is defined as the fraction between the number of different cells in the two matrices and the total number
of cells (25). Two cells are considered different if one corresponds to a non-empty
intersection and the other to an empty intersection. Based on this distance, given two
cardinal relationships θ 1 ∈ CREL(d 1 , d 2 ) and θ 2 ∈ CREL(d 3 , d 4 ), their matrix-based
distance, denoted by d m (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )), can now be computed as the minimum distance between any 5×5 matrix defining θ 1 and any 5×5 matrix defining θ 2 .
In [2], the following result has been obtained stating that the matrix-based distance
just depends on the number of different single-tile relations in θ 1 and θ 2 .
Proposition 8.1. Let d 1 , d 2 , d 3 , d 4 ∈ {R, L, P}, θ 1 ∈ CREL(d 1 , d 2 ), θ 2 ∈
CREL(d 3 , d 4 ). Then, d m (θ 1 , (d 1 , d 2 ), θ 2 , (d 3 , d 4 )) = |(S (θ 1 ) ∪ S (θ 2 )) − (S (θ 1 ) ∩ S (θ 2 ))|.
Based on the previous results, we can show that function d m is not a good distance
for cardinal relations. To this end, consider the following example.