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

Chen, Jun

Bibliographic data

Monograph

Persistent identifier:: 856566209

Author:: Chen, Jun

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

Sub title:: May 23 - 25, 2001, Bangkok, Thailand

Scope:: VI, 434 Seiten

Year of publication:: 2001

Place of publication:: Pathumthani, Thailand

Publisher of the original:: AIT

Identifier (digital):: 856566209

Illustration:: Illustrationen, Diagramme, Karten

Language:: English

Usage licence:: Attribution 4.0 International (CC BY 4.0)

Publisher of the digital copy:: Technische Informationsbibliothek Hannover

Place of publication of the digital copy:: Hannover

Year of publication of the original:: 2016

Document type:: Monograph

Collection:: Earth sciences

Chapter

Title:: QTM-BASED ALGORITHM FOR THE GENERATING OF VORONOI DIAGRAM FOR SPHERICAL OBJECTS. Xuesheng ZHAO, Jun CHEN

Document type:: Monograph

Structure type:: Chapter

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 analyzing the advantages and disadvantages of vector-based 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[1975] 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. [1985] give an 0(m 2 ) time insertion method for computing the Voronoi diagram of a set of m points on a sphere. Renky [1997] 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 [1988] 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 [1996] 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 [1999] 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.

Access restriction

Copyright

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

Monograph

Chapter

Table of contents

Cite and reuse

Monograph

Chapter

Image

Image fragment

Citation links

Citation recommendation