234
правки
Изменения
→Алгоритм Эндрю
= Алгоритм Эндрю =
Алгоритм, очень похожий на алгоритм Грехема. Он заключается в том, что мы находим самую левую и самую правую точки, ищем для точек над и под этой прямой выпуклую оболочку Грехемом - для них начальные точки будут лежать на <tex>\pm inf</tex>, а сортировка по углу относительно далекой точки аналогична сортировке по координате; после этого объединяем две оболочки в одну.
== Описание Алгоритма ==
[[File:andrew1.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)Сортируем все Находим самую левую и самую правую точки по хмножества -координате<tex>p_0</tex> и <tex>p_1</tex>.
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/>
