|
Алгоритм ДжарвисаАлгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время O(nh), где n — общее число точек на плоскости, h — число точек в выпуклой оболочке. Алгоритм Джарвиса построения выпуклой оболочки Пусть дано множество P = {p1,p2,...pn} точек. В качестве начальной берётся самая левая нижняя точка p1 (ее можно найти за O(n) обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Затем для каждой точки pi ищется против часовой стрелки точкаpi + 1 путём нахождения за O(n) среди оставшихся точек (+ самая левая нижняя) точки с наименьшим полярным углом pi − 1pipi + 1. Она и будет следующей вершиной выпуклой оболочки. При этом сам угол не обязательно вычислять, достаточно вычислить векторное произведение (обобщением векторного произведения для двумерного случая является псевдоскалярное произведение) между лучами pip'i + 1 и pip''i + 1, гдеp'i + 1 найденный на данный момент минимум, p''i + 1 претендент (первым минимумом может быть выбрана любая точка). Если векторное произведение отрицательно, то найден новый минимум. Если равно нулю, то есть p'i + 1 и p''i + 1 лежат на одной прямой, то минимум та, которая лежит дальше от точи pi. Алгоритм продолжается пока . Почему алгоритм остановится? Потому что самая левая нижняя точка в любом случае принадлежит выпуклой оболочке. Jarvis(P) 1) p[1] = самая левая нижняя точка множества P; 2) i = 1; 3) do: p[i+1] = любая точка из P (кроме уже попавших в выпуклую оболочку, но включая p); (a)for (для каждой точки j из P, кроме уже попавших в выпуклую оболочку, но включая p) p[i+1] = min_polar_angle(p[i+1], P[j]); // минимум через векторное произведение, как описано выше (b)i = i + 1; while p[i] != p 4) return p; Цикл 3) выполнится h раз, при этом цикл (a) каждый раз выполняется за O(n). Все остальные операции выполняются за O(1). Следовательно, алгоритм работает за O(hn) или O(n2) в худшем случае, когда O(n) точек попадут в выпуклую оболочку. Лит.: Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction — М.: Мир, 1989. — С. 478. Ласло М. Вычислительная геометрия и компьютерная графика на C++ — М.: БИНОМ, 1997. — С. 304. Т. Кормен, Ч. Лейзерсон, Р.Ривест, К.Штайн Алгоритмы. Построение и анализ. = Introduction to Algorithms — 2-e изд. — "Вильямс”, 2005. — С. 1296. |
Loading
|