Алгоритм Джарвиса
Алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время , где — общее число точек на плоскости, — число точек в выпуклой оболочке.
Описание алгоритма
Пусть дано множество точек . В качестве начальной берётся самая левая нижняя точка (её можно найти за обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Следующей точкой () берём такую точку, которая имеет наименьший положительный полярный угол относительно точки как начала координат. После этого для каждой точки (2<i<=|P|) против часовой стрелки ищется такая точка , путём нахождения за среди оставшихся точек (+ самая левая нижняя), в которой будет образовываться наибольший угол между прямыми и . Она и будет следующей вершиной выпуклой оболочки. Сам угол при этом не ищется, а ищется только его косинус через скалярное произведение между лучами и , где — последний найденный минимум, — предыдущий минимум, а — претендент на следующий минимум. Новым минимумом будет та точка, в которой косинус будет принимать наименьшее значение (чем меньше косинус, тем больше его угол). Нахождение вершин выпуклой оболочки продолжается до тех пор, пока . В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, алгоритм останавливается — выпуклая оболочка построена.
Псевдокод
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) выполнится раз, при этом цикл (a) каждый раз выполняется за . Все остальные операции выполняются за . Следовательно, алгоритм работает за или в худшем случае, когда в выпуклую оболочку попадут все точки.
См. также
Литература
- Препарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — 478 с.
- Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. — 304 с.
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ = Introduction to Algorithms. — 2-e изд. — “Вильямс”, 2005. — 1296 с.