9 June 2006 An integrated method of raster and vector for generating a Voronoi diagram based on linear quadtree structure
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.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jiatian Li, Jiatian Li, Renliang Zhao, Renliang Zhao, Jun Chen, 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); doi: 10.1117/12.681746; https://doi.org/10.1117/12.681746
PROCEEDINGS
9 PAGES


SHARE
Back to Top