Выпуклая оболочка
Материал из Algocode wiki
Версия от 12:32, 18 февраля 2022; Rationalex (обсуждение | вклад)
Содержание
Определения
Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству
Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.
Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.
Задача
Дано множество точек, требуется построить его минимальную выпуклую оболочку.
Алгоритм Джарвиса(Метод заворачивания подарка)
Дополнительно
Что делать, если не сдаётся задачка на выпуклую оболочку
- Проверьте, что ваш код корректно обрабатывает совпадающие точки
- Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки
- Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex