- 在线时间
- 113 小时
- 最后登录
- 2022-8-4
- 注册时间
- 2018-9-18
- 听众数
- 5
- 收听数
- 0
- 能力
- 0 分
- 体力
- 4357 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 1539
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 464
- 主题
- 473
- 精华
- 0
- 分享
- 0
- 好友
- 1
TA的每日心情 | 衰 2021-1-13 09:31 |
---|
签到天数: 8 天 [LV.3]偶尔看看II
|
发表于 2020-12-19 15:31
|显示全部楼层
|
本文基于图形处理器(GPU)提出了一种用于计算二维散落点凸包的并行Graham扫描算法。提出的基于GPU的并行算法主要包含以下两个步骤1)在GPU上进行两轮并行剔除内部点操作。首先将四个极值点构成的四边形内的内部点剔除,并按角度对剩余点进行排序,将其分为左右两个区域。对于每个区域,采用所提出的预处理方法进行第二轮过滤以进一步剔除内部点。(2)通过计算剩余点的凸壳得到所需全部散乱点的凸壳。为提高并行算法的效率,采用了CUDA开发组件中Thrust库提供的并行排序、并行规约等高效操作。比较结果表明,所提出的并行算法能在0.5秒内计算出20M散乱点的凸壳,计算效率比现有的基准算法(即著名的QuickHull算法)提高了6~7倍;且该并行算法过程简单,易于编程实现。
' O( X8 I3 l; @8 {3 ]
@8 ~" P# g: \ C. V9 j$ J$ i
! L0 O1 _: Y p5 O! a( Z" R' ?: z# |. o8 {
|
zan
|