ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
170
AN ALGEBRA FOR SPATIAL RELATIONS
Zhilin LI \ Renliang ZHAO 1,2 and Jun CHEN 2
1 Department of Land Surveying and Geo-Informatics
The Hong Kong Polytechnic University, Kowloon, Hong Kong, China
lsllz@polyu.edu.hk
2 National Geometries Center of China,
1 Baishengcun, Zizhuyuan, Beijing, China, 10004
KEYWORDS: Spatial algebra, spatial relation, topological relation, set operation, Voronoi region, Voronoi diagram
ABSTRACT
Spatial relation is a very important topic for spatial reasoning, query and analysis in GIS. This paper presents a generic algebra for
spatial relations. In this algebra, (a) appropriate operators from set operators (i.e. union, intersection, difference, difference by,
symmetric difference, etc) are utilised to distinguish the spatial relations between neighbouring spatial objects; (b) three types of values
are used for the computational results of set operations, -- content, dimension and number of connected components; (c) a spatial
object is treated in a whole but the Voronoi region of an object is employed to enhance its interaction with neighbours; This is a more
generic model than existing ones in theory and practice. This approach overcomes the shortcomings of both decomposition-based and
whole-based approaches. The models developed in this project form an algebra which can effectively describes the relations of spatial
objects. From practical viewpoint, using this approach, the integration of the description and computation of spatial relations in both
vector and raster space is realised in a natural way.
1. INTRODUCTION
A formal theory of description and determination for relations
between spatial objects is usually important to spatial query,
analysis and reasoning in GIS field. For example, in the case
of digital map generalisation, spatial relations between map
objects will be altered after applying generalisation operations
such as selective omission, aggregation, displacement,
exaggeration and so on. These relations could be metric
and/or topological. Due to such changes, spatial conflicts may
be created by these operations and such conflicts need to be
checked and resolved. Recently, much attention has been paid
to this topic (e.g. Dettori and Puppo, 1996). For such a purpose,
appropriate mathematical models for spatial relations are
required.
The importance of spatial relation theory has already been
recognised in early 1980s (Marble 1984, Abler 1987). Since
then, many papers on this topic have been published by
researchers from computing science and GIS communities.
The approaches used in these works can be classified into two
categories, i.e. decomposition-based and whole-based
(Abdelmoty et al. 1994). In the former, a spatial object is
represented in terms of the set of its components, and,
relations are described and determined by the combinatorial
relations of those components. In the latter, the spatial object is
considered as a whole and, spatial relations between spatial
objects are described and determined by the interaction
between whole bodies of these objects instead of their
components.
In the category of decomposition-based approaches, most
models are built upon point set topology (Guting 1988, Pullar
1988, Egenhofer 1989, Clementini et al. 1993). In these
models, two or three components of a spatial object, i.e. interior,
boundary and exterior, are utilised. The most fundamental one
is the 4-intersection model by Egenhofer and Franzona (1991),
making use of the interior and boundary of a spatial object.
Later, this model has been extended to 9-intersection model
(Egenhofer and Herring 1991), in which the exterior of a spatial
object is also included. These models have been implemented
in raster mode by Winter and his collaborators (Winter 1995,
Winter and Frank 2000), through the use of vector
representation for raster cells. The 9-intersection model is then
modified by Chen et al. (2001) by replacing the complement of
a spatial object with its Voronoi region.
In the category of whole-based approach, main work includes
the spatial logic model developed by Randell et al. (1992) and
temporal logic model by Allen (1983). The former is built upon
the calculus of individuals (Clarke 1981) which is in turn based
on “region connection" ontology. In this model, a set of
topological relationships between concave regions is
axlomatised. Some other work based on Clarke's region
theory can also been found in literature (e.g. Vieu 1993). The
main advantage of such work rests in its rigorous logic so as to
facilitate the mathematical deduction and proof. Such models
have mainly been applied to objects of regions in the context of
artificial intelligence. Allen's temporal logic relations (Allen
1983) was originally put forward to handle two-dimensional
temporal but later it has been widely extended to higher
dimensional space (e.g. Freksa 1991, 1992; Hernandez 1993,
1994). Unfortunately, most of these models are limited to the
point-based abstraction of spatial objects.
In spite of these efforts and progresses in the last decade, it is
not deniable that there are many imperfections associated with
existing work as will be discussed in Section 2. In other words,
the formal description and determination of spatial relations is
still an open issue and it deserves further research (e.g. Vasilis
et al. 1999). In this paper, an alternative approach is proposed,
i.e. an algebraic approach based on Voronoi regions. This is
indeed a whole-based approach. In order to capture the
