phica information sci-
ical Information Sys-
ormation Geography.
1 workshop on Geo-
Beijing, pp.200—204
for GIS/ LIS? Asia
lysis conference, Hong
of dynamic change on
umision [I proceeding
SPATIAL RELATIONS BETWEEN SETS
Xiaoyong CHEN
AAS Research Institute,
Asia Air Survey Co., LTD. ,
8-10, Tamura-Cho, Atsugi-Shi, Kanagawa 243, JAPAN
Commission III, Working Group III/IV
KEY WORDSS: GIS Theory, Integration, Metric Topology, Spatial Relations, Spatial Reasoning.
ABSTRACT:
In this paper, after an introduction to the basic ideas and notations of metric topology, a integrated theory of spatial relations (such
as metric, order and topology) between sets is developed in which the relations are defined in terms of the intersections of the
boundaries, interiors and exteriors of two dynamically generated sets based on the Hausdorff metric. Then some extended models
are presented mainly for quantitatively deriving spatial relations between partially separated objects and objects in constrained
spaces. Finally, examples for integrally reasoning different kind of spatial relations are given and some potential applications of
presented theories in GIS area are also suggested.
1. INTRODUCTION
Conditions among spatial data are commonly expressed in
terms of spatial prepositions or spatial relations. The spatial
relations are often classified into metric (distances and
directions), order (partial or total order) and topology three
groups. Over the passed few years, the investigation of formal
and sound methods of describing spatial relations have received
unprecedented attention in the GIS area. Much progress has
been made, particularly in the area of formalizing topological
relations based on the mathematically well-defined 4/9-
intersection model [Egenhofer and Franzosa, 1991, 1994;
Egenhofer and Herring, 1991; Mark and Egenhofer, 1995]. In
the meantime, many investigations also have been made for
quantitatively deriving metric relations [Frank 1992; Peuquet
and Zhang, 1987; Chen et al., 1995], and partial or total order
relations [Kainz et al., 1993]. However, unlike the studies of
topological relations, formalizations of metric and order
relations are generally based on a diversity of models. How to
integrally derive different kinds of spatial relations between
sets (non-point-like) based on an mathematically well-defined
unified algebra framework is still an open problem up to now.
This lack of an integrated comprehensive theory of spatial
relations has been a major impediment for solving many
sophisticated problems in GIS, such as formally deriving
complex spatial relations among spatial objects with multiple
representations or uncertainties, integrally reasoning metric,
order and topological spatial relations, and generation of the
related standards for transferring spatial relations.
This paper focuses on the development of the unified algebra
framework and associated models for deriving different kinds of
spatial relations between sets. At first, after an introduction to
the basic ideas and notations of metric topology, a integrated
theory of spatial relations between sets is developed in which
the relations are defined in terms of the intersections of the
boundaries, interiors and exteriors of two dynamically
generated sets based on the Hausdorff metric. Then some
extended models are presented mainly for quantitatively
determining spatial relations between partially separated
objects and objects in constrained spaces. Finally, examples for
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
integrally reasoning different kind of spatial relations are given
and some potential applications of presented theory in GIS area
are also suggested.
The remainder of this paper is structured as follows: Chapter 2
firstly reviews some related fundamental definitions. In chapter
3 a integrated theory of spatial relations is developed based on
the metric topology theory and the dynamic 9-intersections.
Chapter 4 contains some extensions of the presented theories
and models. Practical algorithms and examples for integrally
reasoning different kind of spatial relations are given in chapter
5. In the last chapter conclusions and outlook for further
research are given.
2. THE FUNDAMENTAL DEFINITIONS
2.1. Partially Ordered Sets and Lattices
(a). Partially ordered sets: Let P be a set, a partial order on Pis
a binary relation< on P such that, for every x, y, z €F:
(1).x< x (reflexive); (2). if x<y and y<x, then x=y
(antisymmetric); (3). if x<y and y<z, then x<z
(transitive). A set with a reflexive, antisymmetric and transitive
relation (order relation) « is called a partially ordered set (or
poset).
(b). Upper and lower bounds: Let P be a poset and $ c P. An
element x €P is an upper bound of Sif sEx forall seS.A
lower bound is defined by duality. The set of all upper bounds
of S is denoted by S^ and the set of all lower bounds is denoted
by S,.If S’has a least element, it is called the least upper
bound of S. By duality, if S, has a largest element, it is called
the greatest lower bound of S. A least upper bound or a greatest
lower bound is always unique.
(c). Lattices: A lattice L is a poset in which every pair of
elements has a least upper bound and a greatest lower bound. A
lattice is called complete when a greatest lower bound and a
least upper bound exist for every subset of the poset. It can be
