c - Cuda中的凸多边形算法？

Question

我正在寻找一种算法来使用 Cuda 找到一个包含所有随机点的凸多边形。有没有人知道我可以适应的非常有效的算法？

Answer 1

如果您（或未来的 SO 用户）仍在寻找 CUDA 的 3D Hull 算法，您可以查看 2011 年 11 月的这篇论文：

“CudaHull：GPU 上的快速并行 3D 凸壳”，作者：Ayal Stein、Eran Geva 和 Jihad El-Sana

http://www.cs.bgu.ac.il/~el-sana/publications/pdf/CudaHull.pdf

作者声称在 10 和 2000 万点上分别比 Qhull (http://www.qhull.org) 提高了 27 到 40 倍。但是，对于更少的点（< 10,000），他们的 CPU / GPU 算法实际上比 Qhull 慢。

我自己没有实现它，但是在搜索 CUDA 的 3D 凸包算法时遇到了你的 SO 问题和 CudaHull 论文。

Answer 2

在 HiPC 上发表了一篇关于使用 CUDA 在 GPU 上运行Convex Hull 算法的论文。

Graham Scan是一种简单的算法，用于查找一组点的凸包。在 Wikipedia 文章中存在它的伪代码版本。