e
d, max (a,b)
4
the distance properties.
d separable.
tric is defined on the
compact set of R? . If
npact set in R^ (or
is the closed ball with
|, B(&)j [4]
ausdorff metric. From
est closed ball B such
€ B(£) generated by
ed set KO B(c). t
e p(K,K,) satisfies
[Serra, 1982]. Fig.2
Iausdorff distances.
reduced to two points,
es with the Euclidean
WEEN SETS
ns that are preserved
r sheeting. The model
1 the usual concepts of
sets [Egenhofer et al.,
between two objects,
intersection of K,'s
rior (K, ) with K,'s
terior (K ) A 3x3
lows:
[5]
a 1996
o9 © @)(9 eS:
001] Y) 100 100 001] ] 100 1:111
0601] 001 100 010 0-17] 1 13-0 171-1
Ik 001] ] 1] 001 Ix 1 1 137] 13:1]
disioint inside contains equal meet covers coveredBy overlay
: . . . 2
Fig.3. The eight topological relations between two regions in IR” .
n 7
epa (SB-(28-( 28
ASeı Mor
yr NN AN A B A B A B
6 -—-06 -656)-9$)—-66$
um / A eer
t
Fig.4. The dynamic topological relations derived by the dynamic
9-intersections.
BOE?
Topological invariance, applicable to the 9-intersection, are the
content (i.e. emptiness or non-emptiness) of a set, the
dimension, and the number of separations [Egenhofer and
Franzosa, 1994]. The contents invariant is the most general
criterion as other invariant can be considered refinements of
non-empty intersections, and is only invariant discussed in this
paper. By considering the values empty (0) and non-empty (1),
one can distinguish between 2°’ =512 binary topological
relations in which only a small subset can be realized when the
objects of concern are embedded in 78? . Egenhofer and Herring
(1991) showed that, for two regions with connected boundaries
embedded inrr°, the 9-intersection distinguishes just 8
different relations, i.e. disjoint, contains, inside, equal meet,
covers, coveredBy, and overlap [see Fig.3]. However, when we
apply the 9-intersection model to describing topological
relations between other types of spatial objects, such as point-
objects and line-objects, as well as binary topological relations
combining different types of spatial objects such as a line and a
region, a point and a line, or a point and a region, the situation
will be more complicated. According to the results of Mark et.
al. (1995), for two simple lines 33 different spatial relations are
possible, and for a line and a region, 19 are possible. For the
detail descriptions of topological relations, please find in
[Egenhofer and Franzosa, 1991, 1994; Mark et. al. 199531.
3.2. Metric Relations between Sets
3.2.1. Dynamic 9-intersection
According to the topological properties of morphological
dilation [Serra, 1982], if the set K, and the structure element
set B(s,) are both closed sets, then the dilated set K,@B(e,) is
also the closed set. Based on this result, we extent the general
9-intersection to the dynamic intersections as follows:
[K,®B(e)I’0K; [K®B(e)I'NeK, [KDB(s)’NK;
S00 (8)7 AK @B(E)INK; AK ®B(EYINCK, eL K,GB(e,)]^ K;
[K9B(es) ^K? [K,98(&)] ^6K, [K,9B(e)] ^K;
[6]
K'nrqK,9B(s, K'^epE,9B(e;)) KCUG9BG p
301 (8,)= eK CLE, 9B(e;). CK, ER, BCe;)] KN K,®B(¢,)]
KK, ®B(8,)1° Ky oL K,9B(,)) K, n9, Xj
where the K, and K, are given two closed sets, the K,@B(e,)
means relevant morphological dilation by the closed ball B with
radius ¢ , and the 37 (¢,) means dynamic 9-intersection with
parameter e, from K, to K,. Based on equations [6] and [7], we
can derive dynamic topological relations by using the different
parameter e, [see Fig.4].
In particular case, whene,-0, the structure element B(e,) is
reduced to the original point (o), according to the algebraic
properties of morphological dilation [Serra, 1982], we have
K, 9 B(z)) - K, € (o - K,, then the dynamic 9-intersections
So (5&) defined in equations [6] and [7] coincide with the
general 9-intersection 5$, in equation [4].
3.2.2. Distance relations between sets
Distance relations are spatial relations that are defined under
different distance functions, such as the 4, , d, and 4,, -metrics
between spatial points, as well as the Hausdorff distance p
between spatial objects. Since spatial points are the special
spatial objects with simple structures, in general cases only the
Hausdorff distance p is discussed in this paper.
According to the derived dynamic topological relations by the
dynamic 9-intersections of equations [6] and [7] with different
parameter e,, such as dynamic equal, dynamic covers (or
dynamic corveredBy) and dynamic contains (or dynamic inside),
we can simply get the Hausdorff distance p(K,,K,) between
two closed sets K, and K, by calculating the minimum and
maximum dilated distances based on equation [4]:
p(K, ,K,)-max(min(e,), min(e; )5 when
100][000] [111]f011] [oor] roorj[111][1*1
50,,(5)2010 [010 001/001, OLI, 111p 10111;
001/|001/||001/|001| |001| |001||001||001|* [8]
100][000] [100][000][000] [010]|110]| 1*0
3, ,(¢,)=/010({010,| 100 || 100010}, | 010 || 100 | *10
001/|001||111/|111/|111 | [111 [[111]{111
| |
equal contains convers
where "*" means either empty (0) or non-empty (1). The
binary distance relations derived by equation [8] are suitable for
different types of spatial objects, such as point-objects, line-
objects and region-objects, as well as combining different types
of spatial objects such as a line and a region, a point and a line,
or a point and a region. Some examples are shown in Fig.5.
3.2.3. Directional relations between sets
The Hausdorff metric between sets is effected by the choice of
that metric functions. Directional relations between sets can be
defined by the Hausdorff metric of angular bearings. The
computation of direction from one spatial object to another is
identical to that for metric function except that the angular
bearing is computed for each ordered pair in the Cartesian
product. The angular bearing is measured in the sense of
navigation bearings (i.e. increasing clockwise from north).
For calculation of the directional relation p(K,,K,) between two
non empty compact sets K, and K,in R^, we select the
angular bearing set R(a,) as instead of closed ball B(z,) , then
101
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
