234
правки
Изменения
→Алгоритм
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%80%D1%8D%D1%85%D0%B5%D0%BC%D0%B0 Русская статья — Wikipedia]
= Алгоритм Эндрю = Алгоритм, очень похожий на алгоритм Грехема.
== Описание Алгоритма ==
[[File:andrew1.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)Сортируем все точки по х-координате.
2)Пусть самая правая точка - <tex>p_1</tex>. Добавляем ее в ответ.
3)Идем от <tex>p_1</tex> по уменьшению х-координаты. Берем следующую по счету точку t. Пока t и две последних точки в текущей оболочке p_i и p_{i-1} образуют неправый поворот, удаляем из оболочки p_i. (если в оболочке одна точка <tex>p_1</tex>, считаем, что перед ней точка <tex>(0, -inf)</tex> )
4)Добавляем в ответ <tex>t</tex>.
5)Делаем так, пока не дойдем до <tex>p_0</tex> - самой левой точки.
6)Повторим проход 3-5 для "нижней" половины оболочки в порядке увеличения х-координаты.
<br/>
== Корректность ==
<br/>
См. доказательство алгоритма Грехема.
<br/>
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</tex>
Andrew(S)
sort S[1..n] by x-coordinate backward(than by y backward)
k = 2
for p = 3..n
while S[k - 1], S[k], S[p] has non-right orientation
k--
swap(S[p], S[k + 1])
k++
sort S[k + 1..n] by x-coordinate (than by y)
for p = k + 1..n
while S[k - 1], S[k], S[p] has non-right orientation
k--
swap(S[p], S[k + 1])
return k + 1
== Сложность ==
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность двух обходов - <tex> 2 \cdot O(n)</tex>. Суммарное время - <tex>O(n \log n)</tex>.
== Ссылки ==
* [http://en.wikipedia.org/wiki/Gift_wrapping_algorithm Английская статья — Wikipedia]* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0 Русская статья — WikipediaGraham_scan#Notes Одно предложение о нем]
= Алгоритм Чена =
