174
Paola Podest` a, Barbara Catania, and Alberto Belussi
same single-tile relation inside a multi-tile one. Finally, item (iii) provides a normal
form for cardinal directional relations, specifying that two single-tile relations are
adjacent in the list if and only if their corresponding tiles are adjacent in the plane.
This is a reasonable assumption as we consider only connected objects.
The semantics of the basic cardinal directional relations can be defined by considering the intersection of the tiles with the target object. For this purpose, it is useful to introduce the concepts of greatest lower bound and lowest upper bound of an
object on a given axis. Given an object A, the greatest lower bound of the projection
of A on the x-axis (respectively y-axis) is denoted by in f x (A) (respectively in f y (A)).
The lowest upper bound of the projection of A on the x-axis (respectively y-axis) is
denoted by sup x (A) (respectively sup y (A)). The minimum bounding box of A, denoted by mbb(A), is the box formed by the straight lines x = in f x (A), x = sup x (A),
y = in f y (A), and y = sup y (A). Table 8.2 presents the semantics of the relations of the
set BCR. Such semantics, which guarantees that basic cardinal directional relations
are mutually exclusive, has been obtained by extending that presented in [16, 17] to
deal with reference and target objects with possibly different dimensions.
5
The semantics of the relations of CREL can be defined considering the semantics
of the basic cardinal directional relations as follows.
Definition 8.3. Let A, B ∈ OBJ, let θ ∈ CREL, θ = R 1 : . . . : R k . A θ B is satisfied
if and only if there exist A 1 , . . . , A k ∈ OBJ, A i A j , i j, 1 ≤ i, j ≤ k, such that
A = A 1 ∪,. . .,∪A k and A 1 R 1 B, A 2 R 2 B,. . .,A k R k B are true.
We remark that the previous definition does not take into account what percentage of object intersects a given tile. Rather, it assumes that when an object intersects more than one tile, it is uniformly distributed among them. We also notice that
the semantics of single-tile relations coincides with the semantics of basic cardinal
directional relations.
From Definition 8.3 and Table 8.2, it follows that, differently from topological relationships, all single-tile relations are defined for any dimension of the reference and
target object, even if the corresponding definition may change. As a consequence, all
multi-tile relations are defined for any dimension of the reference object and for any
dimension, different from P, of the target object. Indeed, it is easy to show that when
the target object is a point, only single-tile relations can be defined. In the following, given two dimensions d 1 , d 2 ∈ {R, L, P}, we denote with CREL(d 1 , d 2 ) the set of
cardinal relationships defined for a target object with dimension d 1 and a reference
object with dimension d 2 .
8.5.2 Distance Function for Cardinal Directional Relations
In defining the distance function for cardinal directional relations, we first notice
that the approach used for topological relationships is not sufficient. To show this,
we first compute the distance between two 5×5 matrices, similarly to what we have
5 Notice that this is not true in [16, 17].
Paola Podest` a, Barbara Catania, and Alberto Belussi
same single-tile relation inside a multi-tile one. Finally, item (iii) provides a normal
form for cardinal directional relations, specifying that two single-tile relations are
adjacent in the list if and only if their corresponding tiles are adjacent in the plane.
This is a reasonable assumption as we consider only connected objects.
The semantics of the basic cardinal directional relations can be defined by considering the intersection of the tiles with the target object. For this purpose, it is useful to introduce the concepts of greatest lower bound and lowest upper bound of an
object on a given axis. Given an object A, the greatest lower bound of the projection
of A on the x-axis (respectively y-axis) is denoted by in f x (A) (respectively in f y (A)).
The lowest upper bound of the projection of A on the x-axis (respectively y-axis) is
denoted by sup x (A) (respectively sup y (A)). The minimum bounding box of A, denoted by mbb(A), is the box formed by the straight lines x = in f x (A), x = sup x (A),
y = in f y (A), and y = sup y (A). Table 8.2 presents the semantics of the relations of the
set BCR. Such semantics, which guarantees that basic cardinal directional relations
are mutually exclusive, has been obtained by extending that presented in [16, 17] to
deal with reference and target objects with possibly different dimensions.
5
The semantics of the relations of CREL can be defined considering the semantics
of the basic cardinal directional relations as follows.
Definition 8.3. Let A, B ∈ OBJ, let θ ∈ CREL, θ = R 1 : . . . : R k . A θ B is satisfied
if and only if there exist A 1 , . . . , A k ∈ OBJ, A i A j , i j, 1 ≤ i, j ≤ k, such that
A = A 1 ∪,. . .,∪A k and A 1 R 1 B, A 2 R 2 B,. . .,A k R k B are true.
We remark that the previous definition does not take into account what percentage of object intersects a given tile. Rather, it assumes that when an object intersects more than one tile, it is uniformly distributed among them. We also notice that
the semantics of single-tile relations coincides with the semantics of basic cardinal
directional relations.
From Definition 8.3 and Table 8.2, it follows that, differently from topological relationships, all single-tile relations are defined for any dimension of the reference and
target object, even if the corresponding definition may change. As a consequence, all
multi-tile relations are defined for any dimension of the reference object and for any
dimension, different from P, of the target object. Indeed, it is easy to show that when
the target object is a point, only single-tile relations can be defined. In the following, given two dimensions d 1 , d 2 ∈ {R, L, P}, we denote with CREL(d 1 , d 2 ) the set of
cardinal relationships defined for a target object with dimension d 1 and a reference
object with dimension d 2 .
8.5.2 Distance Function for Cardinal Directional Relations
In defining the distance function for cardinal directional relations, we first notice
that the approach used for topological relationships is not sufficient. To show this,
we first compute the distance between two 5×5 matrices, similarly to what we have
5 Notice that this is not true in [16, 17].