2D Convex hull - выпуклая оболочка на плоскости

Задача

Имется набор точек на плоскости (рис. 1), нужно расчитать такой набор точек который образует выпуклый многоугольник. т.е. точки из первоначального набора будут либо его вершинами либо будут лежать внутри него (рис. 2).

Решение

Найдем такой прямоугольник чтобы все точки из первоначального набора лежали либо внутри него, либо на его сторонах. Выберем 8 точек лежащих на сторонах найденного прямоугольника (рис. 3).

2 точки лежащие на левой стороне прямоугольника самую нижнюю и самую верхнюю.

2 точки лежащие на верхней стороне прямоугольника самую левую и самую правую.

2 точки лежащие на правой стороне прямоугольника самую верхнюю и самую нижнюю.

2 точки лежащие на нижней стороне прямоугольника самую правую и самую левую.

Если на любой из этих сторон прямоугольника только одна точка, то берем только ее одну для соответствующей стороны. В результате получиться основная фигура - выпуклый многоугольник с обходом по часовой стрелке.

Основной набор легко найти за 1 проход по набору начальных точек.

Точки из основного набора попарно образуют прямоугольники. AB образует фиолетовый прямоугольник, BC - синий, CD - коричневый, DE - зеленый, EA - красный (рис. 4)

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

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

Например сегмент BC (на рис. 5) рассматриваются только точки лежащие в прямоугольнике образованые точками B и C. Серые точки исключены так как лежат справа от BC.

Оставшиеся точки попроядку вставляются в сегмент BC (рис. 6 - 8). Точка вставляется только если она находится выше любого сегмента рассматриваемого промежутка. Например точка P1 находится выше сегмента BP0 поэтому ее вставляют в набор результатов до точки P0. После вставки точки необходимо проверить появились ли после вставки новой точки точки лежащие справа от сегментов входящих в обрабатываемый основной сегмент. Так как точка P0 на (рис. 7) стала правее сегмента P1C ее удалают.

Приложение пример

Скачать пример

Щелчек левой кнопкой мыши внутри окна создает точку. Программа автоматически начнет вычислять выпуклую оболочку как только количество точек станет больше 3. Красные точки - не вошедшие в решение, зеленые - точки образующие выпуклую оболочку.