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

Материал из Algocode wiki
Версия от 10:14, 26 февраля 2020; Глеб (обсуждение | вклад) (Новая страница: «==Определения== Выпуклое множество - такое множество точек, что все точки отрезка, образу...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определения

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


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


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

Задача

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

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