Построение выпуклой оболочки

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

Один из способов построения выпуклой оболочки конечного набора точек S на плоскости напоминает вычерчивание при помощи карандаша и линейки. Вначале выбирается точка заведомо являющаяся вершиной границы выпуклой оболочки. В качестве такой точки можно взять самую левую точку из набора S (если таких точек несколько, выбираем самую нижнюю). Затем вертикальный луч поворачивается вокруг этой точки по направлению часовой стрелки до тех пор, пока не наткнется на точку Тогда отрезок будет ребром границы выпуклой оболочки. Для поиска следующего ребра будем продолжать вращение луча по часовой стрелке; на этот раз вокруг точки b до встречи со следующей точкой Отрезок будет следующим ребром границы выпуклой оболочки. Процесс повторяется до тех пор, пока мы снова не вернемся в точку а. Этот метод называется методом "заворачивания подарка".

Основным шагом алгоритма является отыскание точки, следующей за точкой, вокруг которой вращается луч.

Временные затраты данного алгоритма равны где h - число вершин в границе искомой выпуклой оболочки. Работа данного алгоритма проиллюстрирована на рис.

Рассмотрим еще один алгоритм для построения выпуклой оболочки, так называемый метод обхода Грэхема. В этом методе выпуклая оболочка конечного набора точек S находится в два этапа. На первом этапе алгоритм выбирает некоторую экстремальную точку и сортирует все остальные точки в соответствии с углом направленного к ним из точки луча. На втором этапе алгоритм выполняет пошаговую обработку отсортированных точек, формируя последовательность многоугольников, которые в конце концов и образуют искомую выпуклую оболочку

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

Для определения того, какая именно точка должна быть включена в границу выпуклой оболочки после точки используется тот факт, что при обходе границы выпуклой оболочки в направлении по часовой стрелки каждая ее вершина должна соответствовать повороту влево. Быстродействие данного алгоритма равно