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

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

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

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

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

Пусть дано множество точек . В качестве начальной берётся самая левая нижняя точка (её можно найти за обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Следующей точкой () берём такую точку, которая имеет наименьший положительный полярный угол относительно точки как начала координат. После этого для каждой точки (2<i<=|P|) против часовой стрелки ищется такая точка , путём нахождения за среди оставшихся точек (+ самая левая нижняя), в которой будет образовываться наибольший угол между прямыми и . Она и будет следующей вершиной выпуклой оболочки. Сам угол при этом не ищется, а ищется только его косинус через скалярное произведение между лучами и , где  — последний найденный минимум,  — предыдущий минимум, а  — претендент на следующий минимум. Новым минимумом будет та точка, в которой косинус будет принимать наименьшее значение (чем меньше косинус, тем больше его угол). Нахождение вершин выпуклой оболочки продолжается до тех пор, пока . В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, алгоритм останавливается — выпуклая оболочка построена.

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

 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) выполнится раз, при этом цикл (a) каждый раз выполняется за . Все остальные операции выполняются за . Следовательно, алгоритм работает за или в худшем случае, когда в выпуклую оболочку попадут все точки.

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

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

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

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