Поиск по сайту.

Другие алгоритмы.

Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.

QuickHull.

Автор: Unknown.
Перевод: Кантор И.

     Этот алгоритм начинает работу с создания четырехугольника, соединяющего крайние точки ( смотри шаг А ). Только точки, лежащие вне его могут лежать на оболочке и будут рассматриваться в дальнейшем. Каждый лежащий вне четырехугольника участок будет рекурсивно обработан функцией Quickhull. На диаграмме ниже изображена обработка верхнего-правого угла.

     На шаге А также находится точка точка с, наиболее удаленная от линии ( a , b ). Следующим шагом мы определяем два множества точек: cправа или на линии ( a , c ) и справа или на ( c , b ). Для них вновь запускаем функцию Quickhull.



     Ниже изображена аналогичная обработка первого множества. Находится точка c' ( cм. С ), наиболее удаленная от линии (a',b'), определяются два новых множества точек: справа или на (a',c') и (c',b')... Получается D, которое обрабатывается дальше..

.

     Алгоритм продолжает вызывать Quickhull для этих двух множеств. На рис. E и F показан результат вызова для первого множества. Если множество состоит только из двух точек, рекурсия останавливается, возвращая эти две точки как сторону выпуклой оболочки ( Шаг F, сторону изображает черная линия ).



     Затем обрабатывается второе множество ( Шаг G ), и опять рекурсия останавливается, добравшись до двух точек. И так продолжается, пока не обработан весь верхний-правый угол. После этого ( Шаг H )у нас готова выпуклая оболочка для этого региона.



     Аналогичным способом обрабатываются верхний-левый, нижний-левый и нижний-правый углы, пока не получим полную выпуклую оболочку ( Шаг I ).




Псевдокод.

Находим левейшую, правейшую, самую нижнюю и самую верхнюю точки
Соединяем их четырехугольником
Запускаем 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)


Вверх по странице, к оглавлению и навигации.