Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XL-4/W2, 45-50, 2013
https://doi.org/10.5194/isprsarchives-XL-4-W2-45-2013
© Author(s) 2013. This work is distributed under
the Creative Commons Attribution 3.0 License.
 
25 Oct 2013
A GPU-Based Algorithm for the Generation of Spherical Voronoi Diagram in QTM mode
L. Wang, X. S. Zhao, W. M. Cao, and J. F. Guo Geoscience and Surveying Engineering College, China University of Mining and Technology (Beijing), Beijing, China
Keywords: Spherical Voronoi Diagram, GPU, CUDA, Global Spatial Grid, QTM Abstract. The spherical Voronoi diagram is a type of the global data model in Digital Earth which has become increasingly important and a lot of efforts have been done to develop the algorithms. However, most of the prior works were in vector mode and based on point sets. Recently, some approximation raster-based algorithms were presented which can generate spherical Voronoi diagrams for point, curve, and face sets easily. However, almost all these raster-based algorithms are based on dilation operation and the dilation errors increase greatly with the growth of dilation steps. To overcome this deficiency, a novel GSG-based algorithm for generating spherical Voronoi diagram is proposed in this paper. In our algorithm, distance computation and comparison based on GPU are used instead of dilation operation to diminish the Voronoi error and improve the efficiency. Results show that line sets and area sets can be handled as well as point sets in this algorithm and the Voronoi error can be limited within half of one grid. Additionally, the efficiency for generating spherical Voronoi diagram is improved greatly.
Conference paper (PDF, 781 KB)


Citation: Wang, L., Zhao, X. S., Cao, W. M., and Guo, J. F.: A GPU-Based Algorithm for the Generation of Spherical Voronoi Diagram in QTM mode, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XL-4/W2, 45-50, https://doi.org/10.5194/isprsarchives-XL-4-W2-45-2013, 2013.

BibTeX EndNote Reference Manager XML