Центральный Дом Знаний - Алгоритм Джарвиса

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2688

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

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

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24