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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время 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.

Ссылки[править | править исходный текст]