Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull
Конспект не готов. |
Алгоритм Джарвиса
По-другому "Заворачивание подарка"
Описание Алгоритма
1) Возьмем самую правую нижнюю точку
нашего множества. лежит в выпуклой оболочке, поэтому добавляем ее в ответ.2) На каждом следующем шаге для последнего добавленного
ищем с максимальным полярным углом относительно (Если углы равны, надо сравнивать по расстоянию). Добавляем в ответ. Если , заканчиваем алгоритм.