rely by 
duction 
1anging 
puts, a 
dgetary 
ment of 
enge. 
rds for 
rogram 
Draft 
is for 
imply 
Describing Spatial Relation based on Voronoi Diagram in Discrete Space 
Chengming LI Jun CHEN 
LIESMARS, Wuhan Technical University of Surveying and Mapping 
Wuhan P.R. China, 430072 
Tel: +$6-027-7881292 
Fax. t$6-027-—7314185 
[Abstract] 
Thi 
1s paper focus on the description of topological spatial relations in the 
= 
discret 
«D 
space. First. introducing the method of constructing the raster Voronoi 
Diagram in the discrete space. Then, a V-framework for description of topological 
spatial relations is constructed, it can also represent the spatial adjacent 
relations. At last, two examples are given to explain that raster Voronoi Diagram 
can be used for description spatial relations especially for lateral adjacent 
relations. 
1. Introduction 
The planar-based model and raster tessellation-based are the two spatial data 
models commonly used in designing GIS systems today. The spatial entities are 
described and represented in the planar graph-based spatial data model as point, 
line, polygon objects and the topological relationships among these objects (Such as 
spatial contiguity, connectivity and inclusion) are represented by special 
topological data structure. However, some other spatially topological relationships 
(i.e., the lateral spatial adjacency between two objects) are not described and 
represented in the planar graph-based spatial data model. For instance, the spatial 
objects of two entities who are spatially adjacency may not have ccmmon edges or 
points, such as boundaries cf a playground and the point-like place of a ball 
faliing within the playgrcund. In that case, a pclygen should be formed for 
representing the playground and the line-intersection approach would be used for 
determining if the lateral spatial adjacency exists between the polygon and the 
point, which is often time-consuming. Therefore, the ordinary planar graph-based 
model should be extended for better representing the spatial entities and their 
spatially tcpological relationships. 
With the development of research about computational geometry, many researchers 
managed to use the Voronoi Diagram to represent the lateral spatial relations by 
the Vorcnoi Diagram of the point, line and polygon objects[Gold, C. M., 1992; Gold 
and Edwards. 1992]. In fact, spatial objects has its own Voronoi region which 
defines implicitly the spatial adjacency with the adjacent objects. However, the 
227 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996