Алгоритм |
Время - все точки внутри |
Время - все точки на оболочке |
Среднее время |
Оптимальность/ примечания |
O( n ) |
O( nh ) |
Простой принцип работы. h - количество углов оболочки. |
||
в среднем быстрейший |
||||
Время тормозится сортировкой. Сам алгоритм всегда O( n ) |
||||
O( n ) |
O( n ) |
O( n ) |
Вводимые точки должны образовывать ломаную без самопересечений. Если это не так, пользуйтесь другими алгоритмами. Впрочем, этого можно добиться за O(n), например, поразрядной сортировкой сначала по x, затем по y |
Этот алгоритм обводит точки линией, как будто это - кусок веревки. На рисунке ниже дана подробная иллюстрация его действия.
Находим нижнюю-правую точку. Пусть это - i(0). i=i(0).
Повторять :
- Для каждого j != i вычисляем точку с наименьшим углом от предыдущей стороны ( для второй точки - от горизонтали ). Если есть две таких - берем ту, до которой расстояние больше. Пусть ее номер - k.
- Выводим сторону из точек с номерами i и k. i = k.
пока i не станет равно i(0).
Этот алгоритм начинает работу с создания четырехугольника, соединяющего крайние точки ( смотри шаг А ). Только точки, лежащие вне его могут лежать на оболочке и будут рассматриваться в дальнейшем. Каждый лежащий вне четырехугольника участок будет рекурсивно обработан функцией 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)
Первым шагом определяем самую нижнюю-правую точку, пусть это - точка 0. Она наверняка лежит на оболочке ( Шаг А ).
Следующая стадия - сортировка всех точек по углу между осью Х и линией ( 0 , эта точка ). Точка с самым большим углом отправляется в стек за точкой 0 ( Шаг B ).
Дальше все точки обрабатываются по очереди, начиная от самого меньшего угла ( точка 1 ) и до тех пор, пока не достигнута точка 9. Процесс состоит из теста, является ли строго левым поворот к новой точке на пути: верхняя-1 точка стека - верхняя точка стека - тестируемая точка. Если это так, тогда она идет в стек и переходим к следующей точке. Если нет - то убираем вершину стека и повторяем проверку с той же точкой. Это проиллюстрировано в шагах C-L. Иногда из стека приходтся убирать несколько точек подряд, так как они последовательно не проходят проверки: обнаруживается правый поворот. Вообще говоря, в алгоритме еще нужна проверка на то, нет ли поворота _обратно_, и в этом случае точку следует оставить: мы имеем прямую. Но это уже мелочи.
Найти нижнюю ( правую ) точку.
Пометить ее p(0)
Отсортировать все остальные точки по углу относительно p(0)
Если одинаковый угол - по расстоянию.
помечаем их p(1),...,p(n-1)
Стек S=(p(n-1),p(0))=(p(t-1),p(i)); t - индекс вершины
i = 1
while i < n do
if p(i) строго слева от ( p(t-1),p(t) )
then Push(S,i) and i = i + 1
else Pop(S)
Этот алгоритм за O( n ) времени 'выправляет' впуклости многоугольника, то есть замкнутой непересекающейся ломаной, строя таким образом выпуклую оболочку.
Что интересно, точки могут поступать по мере выполнения алгоритма, и их количество может быть заранее не известно. Главное, чтобы ломаная не пересекалась.
Для начала объявим вспомогательную функцию, которая для любой тройки x, y, z будет >0, =0 или <0 в зависимости от того, находится ли z справа, на одной линии или слева от линии ( x, y ).
Пусть ломаная задана точками v1, ..., vm.
Алгоритм начинает с пустого дека D.
Операции:
push v - положить элемент на верх дека,
insert v - положить элемент под низ дека,
pop - убрать верхний элемент дека,
remove - удалить нижний элемент дека.
Шаг 1:
Ввод v1, v2, v3;
if (v1,v2,v3)>0
then {push v1; push v2;}
else {push v2; push v1;}
push v3; insert v3;
Шаг 2:
Ввод v;
until ((v,db,db+1)<0 or (dt-1,dt,c)<0) do { ввод v };
Шаг 3:
until ((dt-1,dt,v)>0) do pop;
push v;
Шаг 4:
until ((v,db,db+1)>0) do remove;
insert v;
Идти на Шаг 2.
Реализация на Си
