Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Джарвиса)
Строка 1: Строка 1:
 
{{notready}}
 
{{notready}}
 
= Алгоритм Джарвиса =
 
= Алгоритм Джарвиса =
 +
 +
По-другому "Заворачивание подарка"
 +
 +
== Описание Алгоритма ==
 +
 +
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множества. <tex>p_0</tex> лежит в выпуклой оболочке, поэтому добавляем ее в ответ.
 +
 +
2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию). Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
  
 
= Алгоритм Грехэма =
 
= Алгоритм Грехэма =

Версия 14:53, 8 января 2014

Конспект не готов.

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

По-другому "Заворачивание подарка"

Описание Алгоритма

1) Возьмем самую правую нижнюю точку [math]p_0[/math] нашего множества. [math]p_0[/math] лежит в выпуклой оболочке, поэтому добавляем ее в ответ.

2) На каждом следующем шаге для последнего добавленного [math]p_i[/math] ищем [math]p_{i + 1}[/math] с максимальным полярным углом относительно [math]p_i[/math] (Если углы равны, надо сравнивать по расстоянию). Добавляем [math]p_{i + 1}[/math] в ответ. Если [math]p_{i + 1} == p_0[/math] , заканчиваем алгоритм.

Алгоритм Грехэма

Описание Алгоритма

Пример

Псевдокод

Сложность

Алгоритм Эндрю

Алгоритм Чена

Алгоритм QuickHull