An integrated method of raster and vector for generating Voronoi diagram based on linear quadtree structure

Jiatian Li; Renliang Zhao; Jun Chen

doi:10.1117/12.681746

9 June 2006 An integrated method of raster and vector for generating a Voronoi diagram based on linear quadtree structure

Jiatian Li, Renliang Zhao, Jun Chen

Author Affiliations +

Proceedings Volume 6200, Remote Sensing of the Environment: 15th National Symposium on Remote Sensing of China; 62000M (2006) https://doi.org/10.1117/12.681746
Event: Remote Sensing of the Environment: 15th National Symposium on Remote Sensing of China, 2005, Guiyan City, China

Abstract

Voronoi Diagram is a fundamental geometric structure of space partition. To generate the Voronoi diagrams of the line or polygon objects, the raster method is more convenient than the vector method, while raster generation works better with the generation of full-feature Voronoi Diagram. But for the vector data, the computation in the raster method is realized based on the partition of space. So the generation algorithm is high level of space complexity and the obtaining the neighbors of pixel is very difficult. In order to resolve these problems, a generation of Voronoi Diagram with raster and vector properties based on linear quadtree structure is introduced. The main principle is to reduce the space complexity produced by the partition of space and obtains the neighbors by the spatial index which the linear quadtree structure itself is regarded as. The computing model of backward dilation based on mathematical morphology and several optimized computing characteristics of the model are proposed. The test proves that the time complexity of the method is lower than that of uniform grid structure and that of common quadtree structure, and the space complexity is lower than that of uniform grid structure.

Citation Download Citation

Jiatian Li, Renliang Zhao, and Jun Chen "An integrated method of raster and vector for generating a Voronoi diagram based on linear quadtree structure", Proc. SPIE 6200, Remote Sensing of the Environment: 15th National Symposium on Remote Sensing of China, 62000M (9 June 2006); https://doi.org/10.1117/12.681746

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available