В вычислительной геометрии , то алгоритм упаковки подарков является алгоритм для вычисления выпуклой оболочки данного множества точек.
Плоский корпус
В двумерном случае алгоритм также известен как марш Джарвиса в честь Р. А. Джарвиса, который опубликовал его в 1973 г .; он имеет временную сложность O ( nh ) , где n - количество точек, а h - количество точек на выпуклой оболочке. Его реальная производительность по сравнению с другими алгоритмами выпуклой оболочки является благоприятной, когда n мало или ожидается, что h будет очень маленьким по отношению к n [ необходима цитата ] . В общих случаях алгоритм превосходит многие другие (см. « Алгоритмы выпуклой оболочки» ).
Алгоритм
Для простоты в приведенном ниже описании предполагается, что точки находятся в общем положении , т. Е. Никакие три точки не лежат на одной прямой . Алгоритм может быть легко модифицирован, чтобы иметь дело с коллинеарностью, включая выбор, должен ли он сообщать только крайние точки (вершины выпуклой оболочки) или все точки, лежащие на выпуклой оболочке [ необходима цитата ] . Кроме того, полная реализация должна иметь дело [ как? ] с вырожденными случаями, когда выпуклая оболочка имеет только 1 или 2 вершины, а также с проблемами ограниченной арифметической точности как компьютерных вычислений, так и входных данных.
Алгоритм упаковки подарков начинается с i = 0 и точки p 0, которая, как известно, находится на выпуклой оболочке, например, самой левой точки, и выбирает точку p i + 1 так , чтобы все точки были справа от линии p i p. я + 1 . Эта точка может быть найдена за время O ( n ) путем сравнения полярных углов всех точек относительно точки p i, взятой за центр полярных координат . Положив i = i +1 и повторяя с до тех пор, пока не будет достигнуто p h = p 0, мы снова получим выпуклую оболочку за h шагов. В двух измерениях алгоритм упаковки подарков похож на процесс наматывания веревки (или оберточной бумаги) вокруг набора точек.
Подход может быть расширен на более высокие измерения.
Псевдокод
алгоритм jarvis (S) is // S - набор точек // P будет набором точек, которые образуют выпуклую оболочку. Окончательный размер набора - i. pointOnHull = крайняя левая точка в S //, которая гарантированно является частью CH (S) я: = 0 повторить P [i]: = pointOnHull endpoint: = S [0] // начальная конечная точка для края кандидата на корпусе для j от 0 до | S | делать // endpoint == pointOnHull - редкий случай и может произойти только тогда, когда j == 1 и лучшая конечная точка еще не установлена для цикла если (endpoint == pointOnHull) или (S [j] находится слева от строки от P [i] до конечной точки), то endpoint: = S [j] // найден больший левый поворот, обновляем конечную точку я: = я + 1 pointOnHull = конечная точка пока endpoint = P [0] // оборачивается до первой точки корпуса
Сложность
Внутренний цикл проверяет каждую точку в наборе S , а внешний цикл повторяется для каждой точки корпуса. Следовательно, общее время работы равно. Время выполнения зависит от размера выходных данных, поэтому марш Джарвиса является алгоритмом, чувствительным к выходным данным .
Однако, поскольку время работы линейно зависит от количества вершин корпуса, оно быстрее, чемалгоритмы, такие как сканирование Грэма, когда число h вершин корпуса меньше log n . Алгоритм Чана , другой алгоритм выпуклой оболочки, сочетает логарифмическую зависимость сканирования Грэма с выходной чувствительностью алгоритма упаковки подарков, обеспечивая асимптотическое время работы. это улучшает как сканирование Грэма, так и подарочную упаковку.
Смотрите также
Рекомендации
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «33.3: Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 955–956. ISBN 0-262-03293-7.
- Джарвис, РА (1973). «Об отождествлении выпуклой оболочки конечного множества точек на плоскости». Письма об обработке информации . 2 : 18–21. DOI : 10.1016 / 0020-0190 (73) 90020-3 .