Алгоритм упаковки подарка
В вычислительной геометрии алгоритм упаковки подарков — это алгоритм вычисления выпуклой оболочки заданного набора точек.
Плоский случай [ править ]
В двумерном случае алгоритм также известен как Марш Джарвиса , в честь Р.А. Джарвиса, опубликовавшего его в 1973 году; он имеет O ( nh ) временную сложность , где n — количество точек, а h — количество точек на выпуклой оболочке. Его реальная производительность по сравнению с другими алгоритмами выпуклой оболочки благоприятна, когда n мало или ожидается, что h будет очень малым по отношению к n. [ нужна ссылка ] . В общих случаях алгоритм проигрывает многим другим (см. Алгоритмы выпуклой оболочки ).
Алгоритм [ править ]
Для простоты в приведенном ниже описании предполагается, что точки находятся в общем положении , т. е. никакие три точки не лежат на одной прямой . Алгоритм можно легко модифицировать для решения проблемы коллинеарности, включая выбор, должен ли он сообщать только крайние точки (вершины выпуклой оболочки) или все точки, лежащие на выпуклой оболочке. [ нужна ссылка ] . Кроме того, полная реализация должна выбрать, как бороться с вырожденными случаями , когда выпуклая оболочка имеет только 1 или 2 вершины, а также с проблемами ограниченной арифметической точности как компьютерных вычислений, так и входных данных.
Алгоритм упаковки подарка начинается с i = 0 и точки p 0, которая, как известно, находится на выпуклой оболочке, например, самой левой точки, и выбирает точку p i+1 такую, чтобы все точки находились справа от линии p i p. я+1 . Эту точку можно найти за время O ( n ), сравнивая полярные углы всех точек относительно точки pi , принятой за центр полярных координат . Полагая i = i +1 и повторяя с до тех пор, пока снова не будет достигнут ph получим = p 0, выпуклую оболочку за h шагов. В двух измерениях алгоритм упаковки подарка аналогичен процессу наматывания веревки (или упаковочной бумаги) на набор точек.
Этот подход можно распространить на более высокие измерения.
Псевдокод [ править ]
algorithm jarvis(S) is
// S is the set of points
// P will be the set of points which form the convex hull. Final set size is i.
pointOnHull := leftmost point in S // which is guaranteed to be part of the CH(S)
i := 0
repeat
P[i] := pointOnHull
endpoint := S[0] // initial endpoint for a candidate edge on the hull
for j from 0 to |S| do
// endpoint == pointOnHull is a rare case and can happen only when j == 1 and a better endpoint has not yet been set for the loop
if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) then
endpoint := S[j] // found greater left turn, update endpoint
i := i + 1
pointOnHull := endpoint
until endpoint == P[0] // wrapped around to first hull point
Сложность [ править ]
Внутренний цикл проверяет каждую точку множества S , а внешний цикл повторяется для каждой точки оболочки. Следовательно, общее время работы равно . Время выполнения зависит от размера выходных данных, поэтому марш Джарвиса является алгоритмом, чувствительным к выходным данным .
Однако, поскольку время работы линейно зависит от количества вершин оболочки, оно быстрее, чем такие алгоритмы, как сканирование Грэма , когда число h вершин оболочки меньше log n . Алгоритм Чана , еще один алгоритм выпуклой оболочки, сочетает в себе логарифмическую зависимость сканирования Грэма с выходной чувствительностью алгоритма упаковки подарков, достигая асимптотического времени работы. это улучшает как сканирование Грэма, так и подарочную упаковку.
См. также [ править ]
Ссылки [ править ]
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (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 .