请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3509|回复: 0

[其他资源] 【论文】基于GPU的二维凸壳计算并行Graham扫描算法

[复制链接]
字体大小: 正常 放大

473

主题

5

听众

1539

积分

  • TA的每日心情

    2021-1-13 09:31
  • 签到天数: 8 天

    [LV.3]偶尔看看II

    发表于 2020-12-19 15:31 |显示全部楼层
    |招呼Ta 关注Ta
    本文基于图形处理器(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 {

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

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

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

    zan
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 18:53 , Processed in 0.567354 second(s), 55 queries .

    回顶部