# Full text: The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics

```ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
395
From figure 9, we can see that distance distortion of QTM cells
dilations is not only related to distance, but also related to
location. The distortions change differently by dilation increasing
when the origin objects in different location.
• Distance distortion between great circle distance and QTM
cells distance change little when the object is located at or
near corner triangles (as points 2, 3 and 4 in Fig.9);
• Distance distortion is an almost linear function of distance
r
( 1 ) raster in planar ( 2 ) left-corner triangle
itself when the object is located at or near triangles in
midpoint of edges (as points 5, 6 and 7).
• If the objects are located in or near the center of the octant
triangle, the distortion increases when the distance
increases. But when the dilation covers half globe,
distortion decreases when the distance increases, and
reduces to zero at in the end (as points 8 in Fig.9).
( 3 ) right corner triangle
( 4 ) top comer triangle
Fig.9 Distance distortion of QTM cells dilations in different location
7 CONCLUSIONS
Voronoi diagram data structure becomes an efficient tool to
solve global GIS dynamic data model by its dynamic stability.
Hierarchical expression of spherical QTM presents a method
of data generalization to deal with large quantity of data. In this
paper, Voronoi generating algorithms is presented by recursive
dilation of spherical objects and calculated program is
developed in platform OpenGL with VC +t language. An
analysis of experiment results and errors are made, and
conclusion are as followings:
1) QTM-based method for generating Voronoi diagram of
spherical objects has simple concepts and easily
extent. Voronoi diagram for arcs and area sets can
also be constructed as easily as for point sets.
2) Data of spherical objects expressed by QTM address
code have hierarchical quadtree structure, and suitable
to solve the problem of multi-hierarchical
generalization of large quantity of spherical data.
3) Consume of time and space of algorithms is direct
proportion to partition levels, and the quantity of data
can be controlled by the size of pixel. Error of
generating Voronoi diagram is related to location of
sets, and has no relation to the distances.
8 ACKNOWLEDGEMENTS
The National Science Foundation of China under grant No.
69833010 supported this research.
REFERENCES
Augenbaum, M.& Pesken C., 1985, On the Construction of the
Voronoi Mesh on a Sphere. Computational Physics Vol 59.
PP177-192.
Aurenhammer, F., 1991, Voronoi Diagram-A Survey of a
Fundamental Geometric Data Structure, ACM Computing
Survey, Vol.23(3), pp345-350
Dutton, G., 1996, Encoding and Handling Geospatial Data with
Hierarchical Triangular Meshes, Proceeding of 7th
International Symposium on Spatial Data Handling.
pp34-43
Dutton, G.,1999, Scale, Sinuosity, and Point Selection in Digital
Line Generalization, Cartography and Geographic
Information Science, Vol. 26, No.1, pp33-53
Gold C.M, 1997, the Global GIS, Proceeding of the
International Workshop on Dynamic and Multi-Dimension
GIS, Hong-Kong, China, pp80-91
Goodchild, M.F., and Yang Shiren, 1992. A hierarchical data
structure for global geographic information systems.
CVGIP, 54:1, pp.31-44.
Goodchild, M.F., Yang Shiren and GDutton, 1991. Spatial Data
Representation and Basic Operations for A Triangular
Hierarchical Data Structure, NCGIA report, 91-8.
Lukatela.H, 1987, Hipparchus Geopositioning Model: An
Overview. Proceedings of the Eighth International
Symposium on Computer-Assisted Cartography, pp. 87-96
Lukatela.H,1989 Hipparchus Data Structure: Points,Lines
and Regions in Spherical Voronoi Grid. Proceedings of the
Ninth International Symposium on Computer-Assisted
Cartography, pp. 164-170
Okabe.A., Boots,B., and Sugihara.K., 1992, Spatial
Tessellations Concepts and Applications of Voronoi
Diagrams, pp192-194, 269-271
Robert J.R., 1997, Delaunay Triangulation and Voronoi
Diagram on the Surface of a Sphere, ACM Transactions
on Mathematical Software, Vol.23, No.3, September,
pp416-434..
Yang W. C.Gold, 1996, Managing Spatial Objects With the
VMO-Tree, Proceeding of 7th International Symposium on
Spatial Data Handling, Netherlands, pp15-31
Watson, D.F., 1988, Natural neighbor sorting on the
n-dimensional sphere, Pattern Recognition, 21(1), 63-67
Wright, D. & Goodchild, M.F., 1997, Data from Deep:
Impliications for the GIS Community, INT.J. Geographical
Information Science, Vol. 11, No. 6, pp523-528
White, D., Kimmerling.J., and Overton,W.S., 1992,
Cartographic And Geometric Components of a Global
Sampling Design For Environment Monitoring. CaGIS,
19:1, pp. 5-22.
```

## Note to user

Dear user,

In response to current developments in the web technology used by the Goobi viewer, the software no longer supports your browser.