Алгоритм Джарвиса

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

Алгоритм Джарвиса построения выпуклой оболочки

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

Пусть дано множество $P = \{p_1, p_2, ... p_n\}$ точек. В качестве начальной берётся самая левая нижняя точка $p_1$ (ее можно найти за $O(n)$ обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Затем для каждой точки $p_i$ ищется против часовой стрелки точка $p_{i+1}$ путём нахождения за $O(n)$ среди оставшихся точек (+ самая левая нижняя) точки с наименьшим полярным углом $p_{i-1}p_{i}p_{i+1}$. Она и будет следующей вершиной выпуклой оболочки. При этом сам угол не обязательно вычислять, достаточно вычислить векторное произведение (обобщением векторного произведения для двумерного случая является псевдоскалярное произведение) между лучами $p_{i}p'_{i+1}$ и $p_{i}p''_{i+1}$, где $p'_{i+1}$ найденный на данный момент минимум, $p''_{i+1}$ претендент (первым минимумом может быть выбрана любая точка). Если векторное произведение отрицательно, то найден новый минимум. Если равно нулю, то есть $p'_{i+1}$ и $p''_{i+1}$ лежат на одной прямой, то минимум та, которая лежит дальше от точки $p_i$. Алгоритм продолжается пока $p_{i+1} \neq p_1$. Почему алгоритм остановится? Потому что самая левая нижняя точка в любом случае принадлежит выпуклой оболочке.

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

Анализ

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

См. также

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

Литература

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

Ссылки

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