Voronoi图栅格生成算法GPU并行实现

摘要

Aimed at the complexity of calculation and storage in Vector⁃based method for Voronoi diagram,the raster⁃based method is researched emphatically. different methods’complexity and efficiency of generating the Voronoi diagram are an⁃alyzed. A raster⁃based method for Voronoi diagram generating with GPU parallel technology is raised to resolve the problem of low speed. Compared with other methods,grid size was not took into account in this method. It improves the generation speed ob⁃viously.%针对矢量法生成Voronoi图计算与存储复杂的缺点，重点分析研究了Voronoi图的栅格生成方法。对不同的栅格生成算法的复杂性和效率进行了比较分析，并针对以往方法速度较慢的问题，提出一种CUDA平台下GPU并行栅格扫描的方法。该方法利用GPU的多线程特性，将各个栅格的计算分散到不同的线程中并行处理。相比其他栅格生成方法，该方法不需要考虑栅格的规模，能够以几乎线性的时间完成Voronoi图的生成，极大地提高了生成速度。