Изменения

Перейти к: навигация, поиск
м
Описание Алгоритма
[[File:Graham2.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)# Находим точку <tex>p_0</tex> нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них), добавляем в ответ. 2)# Сортируем все остальные точки {{Acronym|по полярному углу относительно <tex>p_0</tex>|Сортировка с компаратором 'Предикат поворота'}}. 3)# Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек. 4)# Берем следующую по счету точку <tex>t</tex>. Пока <tex>t</tex> и две последних точки в текущей оболочке <tex>p_i</tex> и <tex>p_{i-1}</tex> образуют неправый поворот (вектора <tex>p_i t</tex> и <tex>p_{i-1} p_i</tex>), удаляем из оболочки <tex>p_i</tex>. 5)# Добавляем в оболочку <tex>t</tex>. 6)# Делаем п.5, пока не закончатся точки.
== Корректность ==
222
правки

Навигация