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

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

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

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

Описание алгоритма[править | править вики-текст]

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

Псевдокод[править | править вики-текст]

Jarvis(P)
    1) p[1] = самая левая нижняя точка множества P;
    2) p[2] = соседняя точка от p[1] справа (находится через минимальный положительный полярный угол)
    3) i = 2;
    4) do:
         p[i+1] = любая точка из P (кроме уже попавших в выпуклую оболочку, но включая p[1]);
             (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) выполнится h раз, при этом цикл (a) каждый раз выполняется за \Theta(n). Все остальные операции выполняются за O(1). Следовательно, алгоритм работает за \Theta(hn) или \Theta(n^2) в худшем случае, когда в выпуклую оболочку попадут все точки.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]