= Алгоритм Джарвиса =
По-другому "Gift wrapping" (Заворачивание подарка").
== Описание Алгоритма ==
[[File:Graham1.png|right|250px|Промежуточный шаг алгоритма]] <br/><br/>
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множества. Добавляем ее в ответ.
[[File:Temp2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию). Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.gif|thumb|250px|Промежуточный шаг алгоритма]]
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множества. Добавляем ее в ответ.
2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию). Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
<br/><br/><br/><br/>
== Корректность ==
Точка <tex>p_0</tex>, очевидно, принадлежит оболочке. На каждом последующем шаге алгоритма мы получаем прямую <tex>p_{i-1}p_i</tex>, по построениению построению которой все точки множества лежат слева от нее. Значит эти точки принадлежат выпуклой оболочке, выпуклая оболочка состоит из <tex>p_{i}</tex>-ых и только из них.
== Псевдокод ==
Подаем в функцию исходное множество S, возвращаем позицию <tex>k</tex> Inplace- в реализация алгоритма. <tex>S[1..k - 1n]</tex> будет хранится наша оболочка.<tex>turn(a, b, c)</tex> - модифицированная функция поворота, учитывающая случай, когда точки лежат на одной прямойисходное множество.
Jarvis(S)
for find i = 1..n if such that S[i] is right has the lowest y-coordinate and higher than S[1]highest x-coordinate swap(S[1], p0 = S[i]) pi = p0 k = 10
do
k++ for i = 1 and k+1..n if (turn(S[k+1], S[i], has lower angle and higher distance than S[k]))in relation to pi swap(S[k+1i], S[k]) pi = S[k++;] while S[k-1] pi != S[1]p0
return k
