Геометрия: построение выпуклой оболочки
Выпуклой оболочкой множества точек на плоскости является выпуклый многоугольник с вершинами из точек заданного множества. Существует несколько алгоритмов построения выпуклой оболочки. Самыми простыми для реализации являются алгоритмы Джарвиса и Грэхема.
Идея алгоритма Джарвиса построения выпуклой оболочки (его называют еще алгоритмом «заворачивания подарка») заключается в следующем:
- Ищется точка с минимальной координатой по оси $OX$. От нее задается первоначальное вертикальное направление.
- По очереди, перебирая все остальные точки, ищется такая, чтобы вектор с концом в этой точке, а началом в исходной образовал с первоначальным вектором минимальный угол. Найденная таким образом точка будет точкой из выпуклой оболочки.
- Найденная точка принимается за исходную, новый построенный вектор задает исходное направление и из оставшихся $N-2$ точек ищется следующая точка.
- Процесс продолжается до первоначальной выбранной точки.
Идея алгоритма Грэхема построения выпуклой оболочки заключается в следующем:
- Найти левую верхнюю точку. Запомнить ее.
- Отсортировать все остальные точки по возрастанию угла в полярной системе координат с центром в запомненной точке.
- По очереди перебирая все отсортированные точки, исключать те, которые будут содержаться внутри выпуклой оболочки. Оставшиеся при таком отборе точки и составят выпуклую оболочку.
Реализация на языке программирования Pascal.