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

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

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

Определение: Пусть задано некоторое множество точек на плоскости.

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

Многоугольник называется выпуклым, если он лежит по одну сторону от каждой прямой, проходящей через две его соседние вершины.

Существует множество эквивалентных определений:

многоугольник будет выпуклым, если для любых двух точек внутри него соединяющий их отрезок полностью лежит в нём. многоугольник, каждый внутренний угол которого не более развёрнутого угла; многоугольник, все диагонали которого полностью лежат внутри него; выпуклая оболочка конечного числа точек на плоскости; ограниченное множество, являющееся пересечением конечного числа замкнутых полуплоскостей.

Постановка задачи:

Пусть на плоскости дано множество точек. Требуется построить выпуклый многоугольник, чтобы для любой точки из заданного множества было верно одно из трех утверждений:

а) точка является вершиной построенного многоугольника;

б) точка принадлежит одной из сторон многоугольника;

в) точка лежит внутри многоугольника.

(на рисунке показан пример выпуклой оболочки).

Существует множество алгоритмов для решения этой задачи.

В самом простом случае, можно решить эту задачу и прямым перебором (алгоритм решения задачи по определению):

рассмотрим все пары точек: напишем для такой пары уравнение прямой, подставим в него все остальные точки. Если все остальные точки лежат в одной и той же полуплоскости, то данный отрезок принадлежит выпуклой оболочке.

Алгоритм построения по определению

Выбираем произвольную точку i Последовательно проводим прямые через выбранную точку i и произвольную точку j из оставшихся. Проверяем, что ВСЕ точки, кроме i, j лежат по одну сторону от этой прямой. Если найдена такая пара i, j, для которой это верно – добавляем отрезок (i, j) к выпуклой оболочке.

Ниже представлены еще два наиболее распространенных метода для решения подобных задач.

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

Пусть дано множество точек .

В качестве начальной берётся самая левая нижняя точка (ее можно найти обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Проведем через прямую, параллельную Ox. Следующей точкой () берём такую точку, которая имеет наименьший положительный угол относительно проведенной прямой. После этого для каждой точки против часовой стрелки ищется такая точка, путём нахождения среди оставшихся точек (+ самая левая нижняя), в которой будет образовываться наибольший угол между прямыми и Она и будет следующей вершиной выпуклой оболочки.

Сам угол при этом не ищется, а ищется только его косинус через скалярное произведение между лучами и , где — последний найденный минимум, — предыдущий минимум, а — претендент на следующий минимум. Новым минимумом будет та точка, в которой косинус будет принимать наименьшее значение (чем меньше косинус, тем больше его угол).

Нахождение вершин выпуклой оболочки продолжается до тех пор, пока
. В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, алгоритм останавливается — выпуклая оболочка построена.

Обратите внимание на возможность «вырожденного случая», когда в исходном наборе всего одна или две точки, или все точки исходного набора лежат на одной прямой.

В таких частных случаях построение выпуклой оболочки попросту невозможно.

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

Найдем точку (назовем ее P1), заведомо принадлежащую выпуклой оболочке (например, точку с минимальной координатой по y). Отсортируем все остальные точки по возрастанию полярного угла относительно P1, в случае равенства полярных углов – по возрастанию расстояния до нее (полученный порядок обхода точек показан на рисунке; красным цветом показан луч, от которого отсчитываются полярные углы). Для всех отсортированных точек выполним обход Грэхема. Пусть уже построена некоторая часть выпуклой оболочки. Тогда: если на следующем шаге поворот делается против часовой стрелки (что можно выяснить с помощью свойства векторного произведения), то следующая точка включается в оболочку (например, если первая и вторая точки включены в выпуклую оболочку, и рассматривается третья, то на этом этапе она должна быть также включена, так как поворот от 2-й к 3-й делается против часовой стрелки; синим цветом на рисунке показаны стороны, которые принадлежат выпуклой оболочке на данном шаге); если в следующем шаге поворота не делается, то последняя добавленная точка исключается из выпуклой оболочки и добавляется новая (так, при рассмотрении точки 4 необходимо исключить из оболочки точку 3, и поставить новую точку вместо нее). если на следующем шаге делается поворот по часовой стрелке, то последняя (или даже несколько) точек исключается из выпуклой оболочки и вместо них добавляется новая (так, при рассмотрении точки 6 оказывается, что от точки 5 к ней делается поворот по часовой стрелке; в этом случае точка 5 исключается из выпуклой оболочки; фиолетовым цветом показаны исключенные отрезки). Процесс продолжается, пока все точки не будут обработаны. Также необходимо проверить поворот от последней точке к P1 и при необходимости исключить несколько точек в конце оболочки.