数学建模社区-数学中国

标题: 【论文】基于GPU的二维凸壳计算并行Graham扫描算法 [打印本页]
作者: qq_1537237806    时间: 2020-12-19 15:31
标题: 【论文】基于GPU的二维凸壳计算并行Graham扫描算法
本文基于图形处理器(GPU)提出了一种用于计算二维散落点凸包的并行Graham扫描算法。提出的基于GPU的并行算法主要包含以下两个步骤1)在GPU上进行两轮并行剔除内部点操作。首先将四个极值点构成的四边形内的内部点剔除,并按角度对剩余点进行排序,将其分为左右两个区域。对于每个区域,采用所提出的预处理方法进行第二轮过滤以进一步剔除内部点。(2)通过计算剩余点的凸壳得到所需全部散乱点的凸壳。为提高并行算法的效率,采用了CUDA开发组件中Thrust库提供的并行排序、并行规约等高效操作。比较结果表明,所提出的并行算法能在0.5秒内计算出20M散乱点的凸壳,计算效率比现有的基准算法(即著名的QuickHull算法)提高了6～7倍;且该并行算法过程简单,易于编程实现。
2 h7 u9 b) U# G+ _: N+ R: }) n
4 Y) t6 l! ^4 P! n  @* s) O+ Z
: ^3 O1 |$ K' i/ M4 y5 _
+ Q/ E. \* Q) [( ?/ e0 @0 P

基于GPU的二维凸壳计算并行Graham扫描算法_英文_龙沁圆.pdf

191.7 KB, 下载次数: 0, 下载积分: 体力 -2 点

售价: 1 点体力  [记录]  [购买]





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5