Изменения

Перейти к: навигация, поиск
Алгоритм Джарвиса
== Описание Алгоритма ==
[[File:Graham1.png|thumb|250px|Промежуточный шаг алгоритма. Для точки <tex>p_i</tex> ищем следующую перебором.]] <br/><br/>
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множествас самой маленькой у-координатой (если таких несколько, берем самую правую из них). Добавляем ее в ответ.
2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> {{Acronym|с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию)|Считать углы не нужно, можно просто подставить в функцию сравнения предикат поворота}}. Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
Анонимный участник

Навигация