ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
interaction among whole objects, Voronoi regions of spatial
objects are utilised.
The remainder of this paper is structured as follows: Section 2
introduces the basic strategies of the new approach. In Section
3, spatial components are introduced to set algebra to form a
spatial algebra for spatial relations. In Section 4, Voronoi
regions are employed to make this spatial algebra more
generalised. Section 5 and Section 6 examine possible spatial
relations described and distinguished by this spatial algebra.
Some conclusions are made in Section 7.
2. THE STRATEGIES USED IN THIS STUDY
In order to develop an appropriate strategy of study, a critical
examination of existing models seems appropriate.
As mentioned in the previous section, in the
decomposition-based approach, a spatial object is
decomposed into several topological components such as the
interior and boundary. The interaction between these
components of objects determines the relations between
spatial objects. Most of existing models are based on point-set
topology. The typical examples are the 4-intersection model by
Egenhofer and Franzona (1991) and its extension to
9-intersection model (Egenhofer and Herring 1991). However,
there are some imperfections associated with this model
(Clementini et al. 1993, Molenaar et al. 1994, Chen et al. 2001).
For example, 9-intersection model results in too many relations
for humans to use and the list of cases resulting from this
approach is not directly related to the users' interpretation of
topological facts (Clementini et al. 1993, 1995). More seriously,
the use of complement as exterior in the 9-intersection model
makes the three components linearly dependent (Li et al. 2000,
Chen et al. 2001).
Now let's turn to the whole-based approaches. The
whole-based approach directly uses spatial objects instead of
their components for the description of spatial relations, thus
the problems associated with decomposition-based approach
can be avoided. However, it is not sufficient to consider only
objects themselves for distinguishing spatial relations
(Egenhofer et al. 1993). Indeed, many relations cannot be
distinguished if only the objects themselves are used.
As a consequence of these reasons, in this study, the
whole-based approach will be used as a basis. In order to
overcome the shortcomings with the whole-based approach,
an additional parameter should be introduced and this
parameter must be insensitive to the dimensionality of space.
On the hand, it must be closely related to the object as so to
have functions similar to those of boundary and exterior. As a
result, the Voronoi region of an object is selected, because
Voronoi regions have many good properties (Gold 1992, Li et al.
1999). [A Voronoi region (or Thiessen polygon) for a point is
the locus of points closer to that point than to any other given
one].
Another observation arising from the analysis of existing
literature is that only the ‘intersection’ operator out of the many
Set operators are in use. This is perhaps the most expensive
one in terms of computation. There is no reason why other
operators cannot be used. Therefore, it is attempted to explore
the full range of set operators to constitute a spatial algebra for
the spatial relations.
In summary, the basic strategies adopted here are:
(1)
(2)
a spatial object is treated in a whole;
Voronoi region of an object is employed to enhance
its interconnection with neighbours;
appropriate operators from set operators are
utilised to distinguish the spatial relations between
neighbouring spatial objects; and
several types of values are used for the
computational results of set operations, e.g. content,
dimension and number of connected components
and so on.
3. SPATIAL ALGEBRA FOR SPATIAL RELATIONS: AN
INTEGRATION
In the previous section, the basic strategies employed in this
study are outlined. From this section on, the development of
spatial algebra using such strategies will be described. In this
section, a number of set operators will be employed and spatial
concepts are embedded into the algebra.
3.1 Set operators for spatial relations
Spatial objects are often regarded as sets in space in the
context of GIS. This is very important as it means that objects
can be manipulated by ordinary set operators: union,
intersection, set difference and symmetrical difference and so
on. At the same time, spatial relations can be considered as
the result for handling these "sets". In fact, the theory of sets is
the basis of the description and determination of spatial
relations, especially, topological relations can be regarded as
detailed relations between sets (Worboys, 1995). Figure 1
illustrates working principles of set operators, using line and
area objects as examples.
