Главная | Обратная связь | Поможем написать вашу работу!

Задача построения выпуклой оболочки

В завершение мы рассмотрим задачу построения выпуклой оболочки для конечного множества точек в двумерном Евклидовом пространстве. Эта задача хорошо исследована, является составной частью большого числа задач вычислительной геометрии, и имеет много приложений в области распознавания образов, при обработке изображений, в математической статистике, в задачах раскроя материалов и т.п. С другой стороны задача построения выпуклой оболочки множества тесно связана с задачей сортировки данных. Ранее было показано, что задача сортировки за линейное время сводится к задаче построения выпуклой оболочки множества, в силу чего нижняя оценка времени для задачи построения выпуклой оболочки на множестве из точек составляет . Построение выпуклой оболочки является прекрасным примером задачи, когда идеи, полученные на одном классе задач переносятся на другой класс и дают при этом хорошие результаты. Рассмотрим некоторые подходы к решению задачи в двумерной области, изложенные в [4,5,26]

Определение 1. Множество , будет называться выпуклым, если для любой пары точек и из отрезок с концами и целиком принадлежит .

Определение 2. Точка выпуклого множества называется крайней, если не существует пары точек и , из таких, что , (т.е. не является внутренней точкой отрезка с концами и ).

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

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

1. Определение всех крайних точек.

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

Для решения первой задачи можно использовать следующий результат.

Теорема[5]. Точка не является крайней точкой множества только тогда, когда она лежит в некотором треугольнике, вершины которого принадлежат S, но сама она не является вершиной этого треугольника.

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

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

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

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

Грэхем предложил просматривать вершины исходного множества в последовательности, упорядоченной по величине угловой меры множества векторов, построенных из некоторой фиксированной точки к точкам множества . Как уже отмечалось, выпуклая оболочка конечного множества представляет собой выпуклый многоугольник. Рассмотрим некоторую внутреннюю точку этого многоугольника (в предположении, что он имеет непустую внутренность). Для поиска такой точки можно зафиксировать две вершины из и, перебирая в качестве третьей оставшиеся точки, найти треугольник, имеющий непустую площадь. После этого необходимо выбрать точку внутри этого треугольника. Несложно видеть, что эта процедура в худшем случае занимает времени. Введем полярную систему координат с центром в точке . Каждая точка множества задается в полярных координатах парой , где - угол наклона к оси абсцисс, а - радиус. Линейный порядок на определяется отношением:

, если или при .

Построенный порядок может быть получен движением против часовой стрелки по точкам из луча с центром в точке . Этот процесс называется заметанием.

Поскольку для построения требуемого линейного порядка можно использовать любой алгоритм сортировки, то этот процесс требует времени. Следующий этап заключается в сканировании слева направо построенной последовательности с фильтрацией вершин, которые не являются крайними. Грэхем показал, что анализируя три соседние точки последовательности, можно ответить на вопрос, является ли точка внутренней точкой множества. Будем говорить, что точки образуют «правый поворот» (двигаясь по прямолинейно от к через , в точке мы поворачиваем направо), если внутренний относительно точки угол больше или равен . В противном случае эти точки образуют «левый поворот». Случай правого поворота приведен на рисунке.

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

образуют правый поворот. Удалить вершину , и проверить тройку
образуют левый поворот. Продолжить просмотр, перейдя к проверке тройки

Заметим, что формально направление поворота определяется знаком определителя векторного произведения

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

Рассмотрим пример: Пусть точки на плоскости отсортированы относительно вершины в порядке следования номеров:

На первом шаге рассматривается тройка вершин 1, 2, 3. В виду того, что мы имеем левый поворот, то на следующем шаге необходимо рассматривать вершины 2, 3, 4. Поскольку эта тройка образует правый поворот, то вершина 3 исключается из списка кандидатов на крайнюю вершину. Далее просмотр точек 1, 2, 4 исключает вершину 2. Последней в рассматриваемом фрагменте исключается вершина 5. В результате в конце просмотра данного фрагмента в списке остаются вершины 1, 4 и 6. Обход продолжается, пока не будет достигнута стартовая точка последовательности.

Таким образом, алгоритм построения выпуклой оболочки по Грэхему состоит в сортировке в определенном порядке вершин исходного множества с дальнейшим последовательным обходом этих вершин и выборе крайних точек (или удалении внутренних вершин). Проверка свойства быть крайней точкой определяется предикатом, который вычисляется на трех соседних точках-кандидатах за константное время. Поскольку каждое применение предиката включает одну новую точку последовательности, обход всех вершин с построением выпуклой оболочки занимает шагов. АТД для этой задачи, включает операции удаления и позиционирования текущих элементов со сдвигом влево и вправо, в качестве структуры данных естественно использовать двусторонние циклические списки. Учитывая время, необходимое для построения отсортированной последовательности получим, что выпуклая оболочка точек на плоскости может быть найдена за время при памяти с использованием только арифметических операций и сравнений.

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

Следует отметить, что поскольку алгоритм Грэхема требует предварительной сортировки вершин исходного множества, все точки этого множества должны быть известны до начала работы алгоритма. Если требуется модификация строящейся оболочки при поступлении новых вершин в реальном времени (on-line режим), то самый простой способ - перезапустить алгоритм на новых данных. Но при этом, если добавляются вершин, сложность алгоритма составляет . Если после получения каждой новой вершины не производить сортировку заново, а вставлять полученную вершину в отсортированную последовательность, то сложность алгоритма можно понизить до . Препарата показал, что используя сбалансированные деревья поиска для хранения и поиска вершин можно построить открытый алгоритм сложности . Интересные структуры данных возникают, когда в реальном времени разрешается как добавление новых вершин, так и удаление существующих[5].

Алгоритм Джарвиса

Анализируя свойства выпуклой оболочки можно заметить, что если провести прямую по ребру принадлежащему оболочке, все вершины множества окажутся по одну сторону от этой прямой или на самой прямой (свойство ). Используя это свойство можно выделить ребер, удовлетворяющих заданному критерию, а затем расставить их в порядке следования. Очевидно, в худшем случае . Джарвис предложил алгоритм, несколько оптимизирующий указанный выше способ. Алгоритм Джарвиса обходит выпуклую оболочку, порождая в нужном порядке последовательность крайних точек, по одной на каждом шаге. Этот процесс очень напоминает заворачивание предмета в бумагу, поэтому он имеет также другое название - «заворачивание подарка».

Выбор вершин выпуклой оболочки ведется по некоторому критерию, сохраняющему свойство . Рассмотрим следующую последовательность операций:

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

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

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

4. Далее начинается обратный проход, который повторяет шаг 2 с единственной ремаркой: при сравнении полярных углов необходимо искать минимальный относительно отрицательного направления оси абсцисс.

Пример отбора точек при обходе Джарвиса показан на рисунке:

Оценим время работы этого метода. Для каждой вершины выпуклой оболочки находятся полярные углы всех остальных точек (это требует времени), и среди этих полярных углов ищется минимальный (еще ). Нетрудно видеть, что данный процесс напоминает сортировку простым выбором минимального элемента! Если оболочка состоит из точек, то время работы равно [26]. Наихудшим будет случай, когда все точки исходного множества принадлежат выпуклой оболочке. В этом случае время работы метода составит .

Как следует из анализа сложности алгоритма, для худшего случая алгоритм Джарвиса затрачивает больше времени, чем алгоритм Грэхема. Однако, если число вершин выпуклой оболочки невелико (или является медленно растущей функцией (медленнее, чем )), то алгоритм Джарвиса в этом случае является более предпочтительным.

⇐ Предыдущая 1 2 3 4 5 6 7 8910 Следующая ⇒