基于GPU的二维凸壳计算并行Graham扫描算法

gScan:A Parallel Graham Scan Algorithm for Calculating Two-dimensional Convex Hulls onGraphic Processing Units

本文基于图形处理器(GPU)提出了一种用于计算二维散落点凸包的并行Graham扫描算法。提出的基于GPU的并行算法主要包含以下两个步骤:(1)在GPU上进行两轮并行剔除内部点操作。首先将4个极值点构成的四边形内的内部点剔除,并按角度对剩余点进行排序,将其分为左右两个区域。对于每个区域,采用所提出的预处理方法进行第二轮过滤以进一步剔除内部点。(2)通过计算剩余点的凸壳得到所需全部散乱点的凸壳。为提高并行算法的效率,采用了CUDA开发组件中Thrust库提供的并行排序、并行规约等高效操作。比较结果表明,所提出的并行算法能在0.5秒内计算出20 M散乱点的凸壳,计算效率比现有的基准算法(即著名的QuickHull算法)提高了6~7倍;且该并行算法过程简单,易于编程实现。

This paper presents a parallel Graham scan algorithm for calculating two-dimentional(2D)convex hulls of scattered points on Graphic Processing Units(GPUs).The proposed parallel algorithm consists of two stages:(1)two rounds of preprocessing performed on the GPU and(2)the finalization of finding the convex hull on the CPU.We first discard those interior points locating inside a quadrilateral formed by four extreme points,sort the remaining points according to the angles,and divide them into the left and the right regions.For each region,we perform a second round of filtering using the proposed preprocessing approach to further discard interior points.We finally obtain the desired convex hull by calculating the convex hull of the remaining points.We strongly exploit the parallel sorting,reduction,and partitioning provided by the library Thrust for better efficiency and simplicity.Comparative results indicate that our parallel algorithm can calculate the convex hull of 20 M scattered points in less than 0.5 second on personal computers,and achieve a speedup of 6x^7x over the state-of-the-art baseline algorithm(i.e.,the famous QuickHull algorithm).Although our algorithm cannot be much faster than the QuickHull algorithm,it is very simple and easy to implement when compared to some related work.It could be an alternative in practice.