WikiSort.ru - Не сортированное

Алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время ${\displaystyle O(nh)}$ , где ${\displaystyle n}$  — общее число точек на плоскости, ${\displaystyle h}$  — число точек в выпуклой оболочке.

Описание алгоритма

Пусть дано множество точек ${\displaystyle P=\{\,p_{1},p_{2},\ldots ,p_{n}\,\}}$ . В качестве начальной берётся самая левая нижняя точка ${\displaystyle p_{1}}$ (её можно найти за ${\displaystyle O(n)}$ обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Следующей точкой (${\displaystyle p_{2}}$ ) берём такую точку, которая имеет наименьший положительный полярный угол относительно точки ${\displaystyle p_{1}}$ как начала координат. После этого для каждой точки ${\displaystyle p_{i}}$ (2<i<=|P|) против часовой стрелки ищется такая точка ${\displaystyle p_{i+1}}$ , путём нахождения за ${\displaystyle O(n)}$ среди оставшихся точек (+ самая левая нижняя), в которой будет образовываться наибольший угол между прямыми ${\displaystyle p_{i-1}p_{i}}$ и ${\displaystyle p_{i}p_{i+1}}$ . Она и будет следующей вершиной выпуклой оболочки. Сам угол при этом не ищется, а ищется только его косинус через скалярное произведение между лучами ${\displaystyle p_{i-1}p_{i}}$ и ${\displaystyle p_{i}p'_{i+1}}$ , где ${\displaystyle p_{i}}$  — последний найденный минимум, ${\displaystyle p_{i-1}}$  — предыдущий минимум, а ${\displaystyle p'_{i+1}}$  — претендент на следующий минимум. Новым минимумом будет та точка, в которой косинус будет принимать наименьшее значение (чем меньше косинус, тем больше его угол). Нахождение вершин выпуклой оболочки продолжается до тех пор, пока ${\displaystyle p_{i+1}\neq p_{1}}$ . В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, алгоритм останавливается — выпуклая оболочка построена.

Псевдокод

 Jarvis(P)
    1) p[1] = самая левая нижняя точка множества P;
    2) p[2] = соседняя точка от p[1] справа (находится через минимальный положительный полярный угол)
    3) i = 2;
    4) do:
             (a)for для каждой точки j от 1 до |P|, кроме уже попавших в выпуклую оболочку, но включая p[1]
                 p[i+1] = point_with_min_cos(p[i-1], p[i], P[j]); //точка, образующая минимальный косинус с прямой p[i-1]p[i],
             (b)i = i + 1;
       while p[i] != p[1]
    5) return p;

Анализ

Цикл (4) выполнится ${\displaystyle h}$ раз, при этом цикл (a) каждый раз выполняется за ${\displaystyle \Theta (n)}$ . Все остальные операции выполняются за ${\displaystyle O(1)}$ . Следовательно, алгоритм работает за ${\displaystyle \Theta (hn)}$ или ${\displaystyle \Theta (n^{2})}$ в худшем случае, когда в выпуклую оболочку попадут все точки.

См. также

• Алгоритм Грэхема
• Алгоритм Чана

Литература

• Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — 478 с.
• Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. — 304 с.
• Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ = Introduction to Algorithms. — 2-e изд. — “Вильямс”, 2005. — 1296 с.

Ссылки

• Визуализатор
• Реализация на c++

Для улучшения этой статьи желательно: Викифицировать статью. Проставив сноски, внести более точные указания на источники.