Оглавление
Быстрый выпад
-
Основы Quickhull
- Quickhull – это метод для вычисления выпуклой оболочки в n-мерном пространстве.
- Он использует подход “разделяй и властвуй” и имеет наихудшую временную сложность O(n^2) для 2D и 3D пространств.
- В случае ограниченной точности ввода, его сложность может быть O(n log r), где n – количество точек, а r – количество обработанных точек.
-
История и разработка
- Алгоритм был изобретен в 1996 году C. Брэдфордом Барбером, Дэвидом П. Добкиным и Ханну Хухданпаа.
- Он является расширением алгоритма Quickhull Джонатана Скотта Гринфилда 1990 года и детерминированным вариантом алгоритма Кларксона и Шора 1989 года.
-
Двумерный алгоритм
- Двумерный алгоритм включает в себя этапы нахождения точек с минимальными и максимальными координатами, разделения точек на подмножества и определения выпуклой оболочки.
- Для больших измерений алгоритм учитывает множество граней и использует специальные структуры данных для их обработки.
-
Расширение до трех измерений
- В трехмерном случае алгоритм использует стратегию “получения максимального балла” для выбора стартового корпуса.
- Если стартовые точки вырождены, то и все облако точек вырождается.
-
Псевдокод и дополнительные ресурсы
- Псевдокод для двумерного случая доступен у Джордана Смита, а для трехмерного – в презентации алгоритма с подробностями реализации.