王磊, 赵学胜, 官亚勤, 赵龙飞. QTM格网空间中的球面Voronoi图并行生成算法[J]. 武汉大学学报 ( 信息科学版), 2017, 42(5): 691-696. DOI: 10.13203/j.whugis20140910
引用本文: 王磊, 赵学胜, 官亚勤, 赵龙飞. QTM格网空间中的球面Voronoi图并行生成算法[J]. 武汉大学学报 ( 信息科学版), 2017, 42(5): 691-696. DOI: 10.13203/j.whugis20140910
WANG Lei, ZHAO Xuesheng, GUAN Yaqin, ZHAO Longfei. A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 691-696. DOI: 10.13203/j.whugis20140910
Citation: WANG Lei, ZHAO Xuesheng, GUAN Yaqin, ZHAO Longfei. A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 691-696. DOI: 10.13203/j.whugis20140910

QTM格网空间中的球面Voronoi图并行生成算法

A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space

  • 摘要: 根据球面四元三角网(quaternary triangular mesh,QTM)的离散特征及图形处理器(graphics processing unit,GPU)的多线程原理,用距离的计算与比较代替传统的扩张操作,提出了一种基于QTM的球面Voronoi图并行生成算法,并给出了Voronoi边界提取算法。利用C++语言及统一计算设备架构(compute unified device architecture,CUDA)开发了实验系统。实验结果表明,本文算法能够在球面上快速生成点、线、面数据集的Voronoi图,且能够将Voronoi误差控制在两个格网以内。同时,GPU并行计算的使用,提高了算法的效率。

     

    Abstract: Most of the traditional algorithms for the generation of spherical Voronoi diagram are in vector mode and only good for point sets. Recently, approximate raster-based algorithms that easily generate spherical Voronoi diagrams of point, line, and area sets have been proposed. However, almost all these raster-based algorithms are based on dilation operations. Dilation errors however, increase with the growth of dilation steps and are irregularly distributed. To overcome these deficiencies, a parallel algorithm for generating spherical Voronoi diagrams based on the discrete characteristics of a Quaternary Triangular Mesh (QTM) and the multi-thread principle of GPU (Graphics Processing Unit) is proposed. An algorithm for extracting Voronoi boundaries was also developed. Experiments were conducted using C++ and Compute Unified Device Architecture (CUDA). Results show that this algorithm can handle line sets and area sets as well as point sets and the Voronoi error can be limited within two grids. Additionally, efficiency when generating spherical Voronoi diagrams was improved greatly by using GPU parallel computation.

     

/

返回文章
返回