Алгоритм упаковки подарков - Gift wrapping algorithm

Анимация алгоритма упаковки подарков. Красные линии - это уже размещенные линии, Черная линия - это текущее наилучшее предположение для новой строки, а зеленая линия - следующее предположение.

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

Планарный корпус

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

Алгоритм

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

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

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

Псевдокод

Марш Джарвиса, вычисляющий выпуклый корпус.

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

Сложность

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

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

Смотрите также

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

использованная литература

Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «33.3: Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 955–956. ISBN 0-262-03293-7.
Джарвис, Р. А. (1973). «Об отождествлении выпуклой оболочки конечного множества точек на плоскости». Письма об обработке информации. 2: 18–21. Дои:10.1016/0020-0190(73)90020-3.