Share Email Print
cover

Proceedings Paper

An integrated method of raster and vector for generating a Voronoi diagram based on linear quadtree structure
Author(s): Jiatian Li; Renliang Zhao; Jun Chen
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 9 June 2006
PDF: 9 pages
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
Show Author Affiliations
Jiatian Li, China Univ. of Mining and Technology (China)
National Geomatics Ctr. of China (China)
Renliang Zhao, National Geomatics Ctr. of China (China)
Jun Chen, National Geomatics Ctr. of China (China)


Published in SPIE Proceedings Vol. 6200:
Remote Sensing of the Environment: 15th National Symposium on Remote Sensing of China
Qingxi Tong; Wei Gao; Huadong Guo, Editor(s)

© SPIE. Terms of Use
Back to Top