Алгоритм выпуклого многоугольника в Cuda?

Question

Я ищу алгоритм, чтобы найти выпуклый многоугольник, чтобы содержать все случайные точки, используя Cuda. Кто-нибудь знает очень эффективный алгоритм, который я могу адаптировать?

Answer 1

Если вы (или будущие пользователи SO) все еще ищете алгоритм 3D Hull для CUDA, вы можете проверить этот документ с ноября 2011 года:

"CudaHull: быстрая параллельная 3D выпуклая оболочка на графическом процессоре" от Ayal Stein, Eran Geva и Jihad El-Sana

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

Авторы утверждают, что ускорение от Qhull в 27–40 раз (http://www.qhull.org) составляет 10 и 20 миллионов баллов соответственно. Однако для меньшего количества точек (< 10000) их алгоритм CPU / GPU на самом деле медленнее, чем Qhull.

Я не реализовал это сам, но наткнулся на ваш вопрос SO и статью CudaHull при поиске алгоритмов трехмерного выпуклого корпуса для CUDA.

Answer 2

На HiPC представлена ​​статья о запуске алгоритма выпуклых оболочек на графическом процессоре с CUDA.

Сканирование Грэма - это простой алгоритм поиска выпуклой оболочки набора точек. В статье в Википедии существует ее псевдокодовая версия.