Cuda中的凸多邊形算法？

我正在尋找一種算法來找到一個凸多邊形來包含所有使用Cuda的隨機點。有沒有人知道我可以適應的一個非常有效的算法？Cuda中的凸多邊形算法？

2011-01-27 Dark

這不僅僅是標準的凸包問題：http://en.wikipedia.org/wiki/Convex_hull？ – 2011-01-27 13:07:13

它是3d的凸包，實際上它是標準的。但問題是要找到一種有效的算法來映射到CUDA GPU多線程。 – Dark 2011-01-29 08:51:27

有一個paper presented at HiPC關於在使用CUDA的GPU上運行Convex Hull Algorithm。

Graham Scan是一個簡單的算法來找到一組點的凸包。維基百科上的文章存在一個僞代碼版本。

2011-01-27 13:43:28 vz0

如果你（或未來SO用戶）仍然在尋找一個3D赫爾算法CUDA，你可能會從2011年11月檢查出本文：

「CudaHull：快速並行三維凸包上的GPU」通過Ayal斯坦，葉蘭Geva（傑瓦），和聖戰埃爾 - 薩納，

作者聲稱一個27X 40倍以上加速Qhull（http://www.qhull.org），用於10個20萬點分別。對於更少的點數（< 10,000），其CPU/GPU算法實際上比Qhull慢。

我自己沒有實現它，但是在爲CUDA搜索3D凸包算法時遇到了您的SO問題和CudaHull文件。

2012-01-30 22:19:08 Rethunk

回答