Алгоритм упаковки подарков

В вычислительной геометрии алгоритм упаковки подарков — это алгоритм вычисления выпуклой оболочки заданного набора точек.

В двумерном случае алгоритм также известен как марш Джарвиса , в честь RA Jarvis, который опубликовал его в 1973 году; он имеет временную сложность O ( nh ) , где n — количество точек, а h — количество точек на выпуклой оболочке. Его реальная производительность по сравнению с другими алгоритмами выпуклой оболочки благоприятна, когда n мало или h, как ожидается, будет очень малым по отношению к n ^{[ требуется ссылка ]} . В общих случаях алгоритм уступает многим другим (см. Алгоритмы выпуклой оболочки ).

Для простоты в описании ниже предполагается, что точки находятся в общем положении , т. е. никакие три точки не являются коллинеарными . Алгоритм можно легко модифицировать для работы с коллинеарностью, включая выбор, должен ли он сообщать только крайние точки (вершины выпуклой оболочки) или все точки, которые лежат на выпуклой оболочке ^{[ требуется ссылка ]} . Кроме того, полная реализация должна выбирать, как обращаться с вырожденными случаями , когда выпуклая оболочка имеет только 1 или 2 вершины, а также с проблемами ограниченной арифметической точности , как компьютерных вычислений, так и входных данных.

Алгоритм упаковки подарков начинается с i = 0 и точки p _{0 ,} которая, как известно, находится на выпуклой оболочке, например, самой левой точки, и выбирает точку p _i+1 так, чтобы все точки находились справа от линии p _i p _i+1 . Эту точку можно найти за время O ( n ) путем сравнения полярных углов всех точек относительно точки p _{i ,} взятой за центр полярных координат . Полагая i = i +1 и повторяя с до тех пор, пока снова не достигнем p _h = p ₀ , получим выпуклую оболочку за h шагов. В двух измерениях алгоритм упаковки подарков похож на процесс наматывания нити (или оберточной бумаги) вокруг набора точек.

Подход можно распространить и на более высокие измерения.

алгоритм jarvis(S) — это // S — это множество точек // P будет множеством точек, которые образуют выпуклую оболочку. Окончательный размер множества равен i. pointOnHull := самая левая точка в S // которая гарантированно является частью CH(S) я := 0 повторить P[i] := pointOnHull конечная точка := S[0] // начальная конечная точка для потенциального ребра на оболочке для j от 0 до |S| сделать // конечная точка == pointOnHull — редкий случай, который может произойти только тогда, когда j == 1 и для цикла еще не установлена ​​лучшая конечная точка если (конечная точка == pointOnHull) или (S[j] находится слева от линии от P[i] до конечной точки), то конечная точка := S[j] // найден больший поворот налево, обновить конечную точку я := я + 1 pointOnHull := конечная точка до конечной точки == P[0] // обернут вокруг первой точки оболочки

Внутренний цикл проверяет каждую точку в наборе S , а внешний цикл повторяется для каждой точки на корпусе. Следовательно, общее время выполнения равно . Время выполнения зависит от размера выходных данных, поэтому марш Джарвиса является алгоритмом, чувствительным к выходным данным .${\displaystyle O(нч)}$

Однако, поскольку время выполнения линейно зависит от количества вершин оболочки, он быстрее алгоритмов типа сканирования Грэма только тогда, когда количество вершин оболочки h меньше log  n . Алгоритм Чана , еще один алгоритм выпуклой оболочки, объединяет логарифмическую зависимость сканирования Грэма с выходной чувствительностью алгоритма упаковки подарков, достигая асимптотического времени выполнения , которое улучшает как сканирование Грэма, так и упаковку подарков.${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

• Алгоритмы выпуклой оболочки