Выпуклая оболочка

Материал из Algocode wiki
Перейти к: навигация, поиск

Определения

Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству


Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.


Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.

Задача

Дано множество точек, требуется построить его минимальную выпуклую оболочку.

Алгоритм Джарвиса(Метод заворачивания подарка)

Алгоритм Грэхема

Алгоритм Эндрю

Дополнительно

Алгоритм Чана

Онлайн выпуклая оболочка

Что делать, если не сдаётся задачка на выпуклую оболочку

  • Проверьте, что ваш код корректно обрабатывает совпадающие точки
  • Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки
  • Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin


Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex