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

摘要

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.