|
![](../../../gif/3arrow3.gif) Другие алгоритмы.
Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.
QuickHull.
Автор: Unknown. Перевод: Кантор И.
Этот алгоритм начинает работу с создания четырехугольника, соединяющего крайние точки ( смотри шаг А ). Только точки, лежащие вне его могут лежать на оболочке и будут рассматриваться в дальнейшем. Каждый лежащий вне четырехугольника участок будет рекурсивно обработан функцией Quickhull. На диаграмме ниже изображена обработка верхнего-правого угла.
На шаге А также находится точка точка с, наиболее удаленная от линии ( a , b ). Следующим шагом мы определяем два множества точек: cправа или на линии ( a , c ) и справа или на ( c , b ). Для них вновь запускаем функцию Quickhull.
![](gif/quick_a.gif) ![](gif/quick_b.gif)
Ниже изображена аналогичная обработка первого множества. Находится точка c' ( cм. С ), наиболее удаленная от линии (a',b'), определяются два новых множества точек: справа или на (a',c') и (c',b')... Получается D, которое обрабатывается дальше..
.
![](gif/quick_c.gif) ![](gif/quick_d.gif)
Алгоритм продолжает вызывать Quickhull для этих двух множеств. На рис. E и F показан результат вызова для первого множества. Если множество состоит только из двух точек, рекурсия останавливается, возвращая эти две точки как сторону выпуклой оболочки ( Шаг F, сторону изображает черная линия ).
![](gif/quick_e.gif) ![](gif/quick_f.gif)
Затем обрабатывается второе множество ( Шаг G ), и опять рекурсия останавливается, добравшись до двух точек. И так продолжается, пока не обработан весь верхний-правый угол. После этого ( Шаг H )у нас готова выпуклая оболочка для этого региона.
![](gif/quick_g.gif) ![](gif/quick_h.gif)
Аналогичным способом обрабатываются верхний-левый, нижний-левый и нижний-правый углы, пока не получим полную выпуклую оболочку ( Шаг I ).
![](gif/quick_i.gif)
Псевдокод.
Находим левейшую, правейшую, самую нижнюю и самую верхнюю точки
Соединяем их четырехугольником
Запускаем QuickHull для четырех треугольных регионов вне четырехугольника
function QuickHull(a,b,s)
if S={a,b} then return(a,b)
else
c = index of right of
(a,c)
A = точки справа от
(a,c)
B = точки справа от
(a,b)
return QuickHull(a,c,A)
объединенное с QuickHull(c,b,B)
![](../../../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации.
| |