ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
173
a spatial relation cannot be sufficiently described even
dimension is used. In this case, connected number should also
be considered.
4. VORONOI-BASED SPATIAL ALGEBRA FOR SPATIAL
RELATIONS: FURTHER EXTENSION
In the previous section, a simple spatial algebra is developed
for spatial relations. However, as will be discussed later, some
spatial relations will be confused if only the spatial objects are
used. In order to make the spatial algebra more general,
Voronoi regions of spatial objects are introduced into this model
expressed in Equation (1).
4.1 Voronoi region as a topological component of a
spatial object
Spatial relations essentially reflect the spatial configuration
between objects. In other words, for individual object, the
surrounding space must also be taken into account in addition
to the surrounding objects if sound models for spatial relations
are to be developed. The role of Voronoi region in this study
serves the purpose of tightening the inter-relation among a
spatial object and its neighbouring objects and space.
A Voronoi region describes the spatial proximity or influent
region of a spatial object. The Voronoi regions of all spatial
objects together will form a tessellation of space. This
tessellation is called Voronoi diagram. There are also other
names but such discussion and other topics could be found
elsewhere (Li et al. 1999). The dual graph is the well-known
Delaunnay triangulation network in GIS and computational
geometry. Figure 2 illustrates Voronoi regions, Voronoi
diagram and the corresponding Delaunnay triangulation of a
point set. Figure 4 shows Voronoi regions of two objects with
two different kinds of spatial configurations.
(a) (b)
Figure 4: Voronoi regions of spatial objects with complex
configurations
It is clear that the Voronoi region of a spatial object could serve
for two purposes, i.e. to connect spatial objects together to form
a space tessellation and, at the same time, to serve as a
confined exterior of the spatial object. Therefore, Voronoi
region is introduced into the spatial algebra for spatial relations.
As a result, a Voronoi-based spatial algebra is presented for
general use.
4.2 Voronoi-based spatial algebra: further extension
Let a v be the Voronoi region of spatial object 'a' and b v be the
Voronoi region of spatial object 'b\ then the spatial relation B(a,
b) between object a and object b can be listed in Table 1
concisely, which can be expanded to be a matrix form as in
Table 2:
Table 1: Concise representation of the new algebraic model
B(a,b)=F{A T 0 B)
b
b v
a
(a 6b)
(a 1 6b v )
a v
(a v 6 b)
(a 1 Ob')
Table 2: The extended form of the algebraic model based
on Voronoi regions
B(a,b)- F(A T 0 B)
(a. b)
(a. h v )
(a 1 : h)
(a . h y )
Union ci
au b
au b 1
a' ub r
a' u b'
Intersect n
ar\b
a r> A 1
a v r\h'
ä 1 n h'
Difference \
a \ h
a ’ h {
a' h 1
a' \ h‘
Difference by /
alb
alb'
a v lb v
a'/h'
Symmetric difference A
a Ab
a A h'
a' A b'
a' Ah'
Other operators
Mathematically, let A = [a, a 1 '] and B = [b, b v ], then the relations
could be described by the following equation:
B(a,b ) = F(A r 0B) = F{[a, a v } r 0[b ,b v ])
(a 0b) {adb v )\
(„'№> (S»«')J
Where, F is function similar to the fin Equation (1). Generally
speaking, the following function is sufficient:
B\a,b)= F {( a Ob), (a y Ob y )} (3a)
In practice, if a spatial relation can be sufficiently described by
(aOb), the other operand, i.e. (a 0 b v ), may be ignored.
Of course, one may also try to use the (a 1 Ob 1 ) first if he
wishes. As a result, in this way, spatial relations can be
described in a flexible manner.
5. TOPOLOGICAL RELATIONS WITH THE SPATIAL
ALGEBRA
In the previous section, the basic algebraic model has been
presented. In this section, the realization of this model in
real-world relations will be presented.
5.1 Assumptions used in the model
In fact, not all the values of the Equation (3) and/or Table 2 are
valid in practical applications. A number of assumptions could
be made for the determination the useful values of the Equation
(3) and Tables 1 and 2. These assumptions are formulated by
considering a number of factors, i.e. the properties of spatial
objects, the embedding space, the relations between selected
operators in the model and so on. These assumptions are
