Алгоритм Quickhull для нахождения выпуклой оболочки

Хабрахабр / Лучшие публикации за сутки.

Как гласит определение, выпуклая оболочка некоторого множества — это наименьшее выпуклое множество , содержащее в себе это множество . Выпуклой оболочкой конечного множества попарно различных точек является многогранник.
Для реализации одномерного случая алгоритма Quickhull годится функция std::minmax_element. В сети можно найти множество реализаций алгоритма Quickhull для плоского случая. Однако, для случая произвольной размерности сходу находится лишь одна тяжёловесная реализация с сайта qhull.org. Читать дальше →

Добавить комментарий