×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

# Full text

Title
The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Author
Chen, Jun

ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS’’, Bangkok, May 23-25, 2001
391
QTM-BASED ALGORITHM FOR THE GENERATING OF VORONOI DIAGRAM FOR SPHERICAL OBJECTS
Xuesheng ZHAO 1 Jun CHEN 2
1 China University of Mining and Technology (Beijing)
D11 Xueyuan Road, Beijing, China, 100083
E-mail, zxs@mail.cumtb.edu.cn
National Geomatics Center of China
No1. Zizhuyuan, Baishengcun, Beijing, China, 100044
E-mail: ¡chen@gps.ceic.aov.cn
KEY WORDS: Spherical dynamic data model QTM Voronoi diagram Recursive dilation
ABSTRACT
This paper present an algorithm for generating of spherical Voronoi diagram based on O-QTM (Octahedral Quaternary Triangular Mesh).
First the methods of spherical surface triangular partition and encode of triangular are reviewed. With the codes of triangular, the direct
and non-direct neighbor triangular can be searched. In this paper, the dilation operator and dilation-structuring element of spherical
triangular are redefined according to the principle of mathematical morphology. So the spherical Voronoi diagram is generated by
recursive dilation of spherical objects expressed by code of triangular. We developed the experimental system using VC++ in OpenGL
platform and analysis the complex degree of algorithm and features of errors. The results demonstrated: the complex degree of
algorithm with points, arcs and curve faces are equal, and proportion to levels of the spherical face partition; and the error of result is
related a little to spherical distance, not as the raster dilation in planar, and is related mainly to the locations of the objects. In the end,
the conclusions and future works are presented.
1 INTRODUCTION
The classical data model cannot manage the global, changed,
and large quantity of data effectively because it is based on
planar and static. In order to effectively store, pick up and
analysis the spatial data in global scale, the digital expression of
the Earth data in computer must be global, continuous and
conjugate, i.e., construct the spherical dynamic data model. As
Voronoi data structure is one of the moat value tools in dynamic
operation by its characters [White et al, 1997]. But the complex
of the Voronoi algorithm limits its application in GIS. There are
few Voronoi algorithms in sphere, only in spherical points sets,
and can not satisfy the requirement of dynamic operation of
spherical data.
So algorithms based on raster starts to be approached. Voronoi
algorithms have simple conception and recursive and can control
quantity and precision by pixels. Now from the papers, Voronoi
algorithms based on raster are only limited on planar and can not
extend these methods to spherical surface because planar and
spherical facet are not homoeomorphism. In this paper spherical
surface is partitioned by QTM. Dilation operator and structure
element are redefined according to the principle of mathematical
morphology. Voronoi generating algorithms is presented by
recursive dilation of spherical objects and calculated program is
developed in platform OpenGL with VC ++ language.
Following this introduction is section for background review and
methods. Section 3 will introduce some basic concepts related to
Voronoi diagram of spherical objects. Section 4 will discuss
partition method of spherical surface and character of QTM code,
and present finding methods of spherical neighbor triangles in
details. In section 5, an algorithm for generating Voronoi of
spherical objects is presented in details by dilation principle of
QTM. An analysis of experiment results and errors are made,
and error control method is presented in section 6. At last, the
conclusions and future works will be presented.
2 METHODS FOR SPHERICAL VORONOI DIAGRAM
GENERATION: A REVIEW AND OVERVIEW
Voronoi diagram has been one of the research hotspots in area
of computer geometry since it is introduced to computer area by
Shamos & Hoey as an efficient data structure. Most of
methods are based on point sets in planar, such as incremental
method, divide and conquer, indirect generating method and
parallel method [Aurenhammer, 1991].
There are a few methods based on spherical surface. Such as,
Aggenbaum et al.  give an 0(m 2 ) time insertion method for
computing the Voronoi diagram of a set of m points on a sphere.
Renky  give an O(NlogN) time to construct the Delaunay
triangular, the dual of the Voronoi diagram of a set of n points on
a sphere. Lukatela [1987,1989] set up a digital geo-positioning
model and develop an operational software package that
provides geometrical & geo-relational functions to applications
that manipulate spatial objects. A Voronoi tessellation is used as
a base for highly efficient indexing system to increase the speed
of data manipulation. It is a first application system based on
sphere surface model in GIS. It is same as Walson  who
use point-sets Voronoi diagram to interpolation on spherical
surface. From above, we can see that Voronoi diagram is
constructed for only point sets on sphere and based on vector
mode. It has been realized [Gold, 1992] that vector-based
methods are good only for point sets and the methods for line
and area sets could be very complex. Especially the arc and area
sets in 3-D and spherical surface are really out of consideration.
That serious deficiency is main obstacle to use widely in GIS
applications. In order to solve this problem, Yang & Gold 
presented a point-line model, i.e. the complex objects are
decomposed to points and lines. Voronoi diagram for points and
lines are generated at first, and then translate to Voronoi diagram
of the complex objects by removing the Voronoi edges between
points or line in a same object. The advantage of this methods
can generate Voronoi diagram of the complex vector-based
objects and deal with dynamic changes of topological relations.
But it has been done by many steps, such as
“decompose”, "calculation”, ’’remove" and “compose". Algorithms
and data structure are complex, especially lack of hierarchical
data structure, and cannot deal with hierarchical generalized
expression of quantity of spherical data.
As the complex of vector-based methods, raster-based methods
have been approached. Li Chengming et.al  presented a
method based on raster by dynamic distance translation with
principle of mathematical morphology and restrict the error to
one pixel. Raster-based methods have simple conception,
hierarchical recursive, and easily extended to 3-D Voronoi
diagram. But now the research limited in planar. So far, the
authors, in a real sense have known no literature purely on the
generation of Voronoi diagram in spherical mesh-based
methods.
3 RELATED CONCEPTS & DEFINITIONS
The followings are related concepts and definitions.