Алгоритм выпуклого многоугольника в Cuda? - PullRequest
Новая
       28

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

2 голосов
/ 27 января 2011

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

Ответы [ 2 ]

3 голосов
/ 31 января 2012

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

«CudaHull: быстрый параллельный 3D выпуклый корпус на графическом процессоре» Айал Стейн, Эран Гева и Джихад Эль-Сана

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. </p>

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

1 голос
/ 27 января 2011

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

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

...