Алгоритмы построения выпуклой оболочки множества точек на плоскости

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

Задача построения (вычисления) выпуклой оболочки множества точек не только является центральной в целом ряде приложений, но и позволяет разрешить ряд вопросов вычислительной геометрии, на первый взгляд не связанных с ней. Построение выпуклой оболочки конечного множества точек, и особенно в случае точек на плоскости, уже довольно широко и глубоко исследовано и имеет ряд приложений,   например,   в   распознавании   образов,   обработке   изображений,   в   задаче       раскроя и компоновки и множества других [1].

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

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

Задача построения выпуклой оболочки ставится следующим образом: задано множество S, содержащее N  точек,  требуется  построить  их  выпуклую  оболочку.  Под  выпуклой  оболочкой  множества   точек S понимается наименьшее выпуклое множество, содержащее S. Ещё одним важным понятием является понятие крайней точки. Точка выпуклого множества S называется крайней, если не существует пары точек a, b S таких, что p лежит на открытом отрезке ab. Множество E крайних точек S в точности совпадает с множеством вершин выпуклой оболочки S. Исходя из этого, можно вывести основную идею алгоритма поиска:

• определить крайние точки;
• упорядочить эти точки так, чтобы они образовывали выпуклый многоугольник [2].

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

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

Поскольку число возможных треугольников из N точек, является сочетанием из N по 3, то оно прямо пропорционально N3. Проверить принадлежность точки заданному треугольнику можно за постоянное число операций, поэтому за время O(N3) можно определить, является ли конкретная точка крайней.

Рисунок 1 – Пример некрайней точки

Повторение этих действий для всех N точек множества займет O(N4) времени. Хотя такой подход крайне неэффективен, он очень прост и показывает, что крайние точки могут быть найдены за конечное число шагов.

Однако набор крайних точек не является выпуклой оболочкой сам по себе. Чтобы образовать выпуклую оболочку их необходимо упорядочить в соответствии со следующими теоремами.

Теорема 2: Луч, выходящий из внутренней точки ограниченной выпуклой фигуры F, пересекает границу F в точности в одной точке.

Теорема 3: Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки [1].

Отсюда следует, что зная крайние точки некоторого множества, его выпуклую оболочку можно найти,  выбрав  внутреннюю  точку  оболочки  q,  и  упорядочить  затем  крайние  точки  в   соответствии с полярным углом относительно q. Сортировка производится за O(N log N) шагов. Таким образом, задача поиска выпуклой оболочки может быть решена за время O(N4).

Алгоритм со  временем  выполнения  O(N4)  не  позволяет  обрабатывать  большие  наборы данных, и фактически не применим к реальным задачам [3].

Исследования, посвященные вопросу разработки эффективных геометрических алгоритмов, показали, что выполнив предварительно сортировку точек, крайние точки можно найти за линейное время. Этот метод был предложен в 1972 году и стал очень мощным средством в области вычислительной геометрии. Он назван алгоритмом Грэхема по имени автора, также его называют сканированием Грэхема.

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

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

Шаг 2: Остальные точки сортируются в порядке возрастания по углу между осью X и линией проведенной из точки p0 к заданной точке. Затем точки объединяются в список (см. рисунок 3). Список выглядит следующим образом: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Шаг 3: Просмотр точек на принадлежность к внешней оболочке. Берется тройка последовательных точек p1p2p3 и проверяется образуется ли ими «левый поворот». Из выпуклости многоугольника непосредственно  следует,  что  при  его  обходе  будут  делаться  только  «левые  повороты».    Поэтому в зависимости от результата проверки угла возможны два варианта действий. В первом случае, когда p1p2p3 образуют «правый поворот», необходимо удалить вершину р2 из списка,  и  проверить тройку p0p1p3.  Во  втором,  когда  p1p2p3   образуют  «левый  поворот»,  нужно  продолжить  просмотр,   перейдя к проверке тройки p2p3p4.

Рисунок 2 – Первый шаг алгоритма Грэхема

Рисунок 3 – Второй шаг алгоритма Грэхема

Просмотр заканчивается, когда после просмотра всех  точек  алгоритм  возвращается  в  точку  p0 (см. рисунок 4). Список в рассматриваемом примере при этом изменяется так:

-       0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

-       0, 1, 3, 4, 5, 6, 7, 8, 9;

-       0, 1, 3, 5, 6, 7, 8, 9;

-       0, 1, 3, 5, 7, 8, 9;

-       0, 1, 3, 5, 7, 9.

Рисунок 4 – Обход точек в алгоритме Грэхема

По окончании алгоритма список содержит упорядоченные нужным образом вершины оболочки [4].

Следует заметить, что для определения, образуют ли три точки p1,p2,p3 «левый поворот», можно использовать  обобщение  векторного  произведения   на  двумерное  пространство,  а  именно     условие

«левого поворота» будет выглядеть следующим образом:

UxVx - U yVy  > 0 ,                                                                         (1)

где U = {p

• p1x

, p2y

• p1y

}, V = {p

• p1x

, p3y

- p1y }.

То есть в координатах условие может быть выражено следующим образом:

(p2x   - p1x   )(p3x   - p1x   ) - (p2y  - p1y   )(p3y  - p1y   )> 0 .                            (2)

В случае, если разность меньше 0, образуется «правый поворот». Если же разность в точности равна нулю, то это значит что точки лежат на одной прямой, и в данном случае удовлетворяет условию [5].

Время, затрачиваемое на обход точек, равно O(N), в то время как время на сортировку точек O(N lg N), поэтому общее время алгоритма O(N lg N) [3]. Если сравнить с оценкой времени работы предыдущего алгоритма O(N4), то преимущества такого подхода становятся очевидны.

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

Шаг 1: Из множества точек выбирается точка с наименьшей ординатой. Такую точку называют исходной.

Шаг 2: Для исходной точки ищется такая точка в S, чтобы вектор с концом в этой точке, а  началом в исходной образовывал с первоначальным вектором минимальный угол (для самой первой точки, первоначальным вектором принимают горизонталь). Найденную точку принимают исходной, ее следует добавить в список точек оболочки. Если таких точек несколько (то есть они находятся  на  одной прямой),  то  нужно  их  отсортировать  по  мере  удаления  от  исходной  и  последовательно    добавить в список, за исходную принять наиболее удаленную точку.

Шаг 2 повторяется до первоначально выбранной точки (см. рисунок 5) [2].

Рисунок 5 – Обход точек в алгоритме Джарвиса

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

Скалярное произведение векторов a и b может быть вычислено по формуле:

ab = axbx  + ayby .                                                                     (3)

Также оно может быть вычислено как произведение длин векторов и косинуса угла между ними:

ab=| a || b| cos

.                                                                      (4)

Исходя из этого:

cos   =

axbx  + ayby

.                                                                (5)

Так как все N точек множества могут лежать на его выпуклой оболочке, а алгоритм Джарвиса затрачивает на нахождение каждой точки оболочки линейное время, то время выполнения алгоритма в худшем случае равно О(N2), что хуже, чем у алгоритма Грэхема. Если в действительности число вершин выпуклой оболочки равно H, то время выполнения алгоритма Джарвиса будет O(HN), что делает его очень эффективным при относительно небольшом H [5-6].

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

«заворачивания подарка» и предложенного Чандом и Капуром в 1970 году. Метод «заворачивания подарка» применим также в случае пространств размерности больше двух.

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

Теорема 4: Отрезок l, определяемый двумя точками, является ребром выпуклой оболочки тогда и только тогда, когда все другие точки заданного множества лежат на l или с одной стороны от него [1].

На этом принципе основан алгоритм «быстрой оболочки».  Алгоритм является рекурсивным.

Шаг 1: Выбирается самая левая (l) и самая правая (r) точки множества, между ними  строится отрезок lr, который разбивает остальные точки множества на два подмножества, S1 – содержащее точки слева от отрезка и S2 – справа (см. рисунок 6).

Рисунок 6 – Первый шаг алгоритма «быстрой оболочки»

Шаг 2: На множестве S1 ищется точка (t), максимально удаленная от отрезка lr, если таких несколько, выбирается самая левая (см. рисунок 7).

Рисунок 7 – Второй шаг алгоритма «быстрой оболочки»

Шаг 3: Строится два отрезка lt и tr ( направление по часовой стрелке ). Из S1 удаляются все точки, лежащие справа от отрезков, то есть внутри треугольника. Эти точки не могут быть точками оболочки (см. рисунок 8).

Рисунок 8 – Третий шаг алгоритма «быстрой оболочки»

Шаг 4: Шаги 2 и 3 рекурсивно повторяются для отрезков lt и tr и всех порождаемых алгоритмом отрезков до тех пор, пока в S1 останутся только точки принадлежащие отрезкам.

Шаг 5: Оставшиеся в S1 точки упорядочиваются по или против часовой стрелки. Шаг 6: Шаги 2-5 применяются для множества S2 (см. рисунок 9).

Рисунок 9 – Точки, оставшиеся в списке после «быстрой оболочки»

Шаг 7: Упорядоченные множества S1 и  S2 объединяются, это и есть выпуклая оболочка [2].

Лучшим случаем для этого алгоритма является случай, когда все точки находятся внутри оболочки. В таком случае время работы алгоритма O(N). В худшем случае, когда все точки лежат на оболочке, время выполнения составляет O(N2).  Среднее время O (N lg N) [3].

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

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

Алгоритм «быстрой оболочки» наиболее полезен, когда необходимо определить  выпуклые оболочки множества случайных наборов точек, так как в этом случае он обеспечивает максимальную скорость работы [3].

Анализ данных алгоритмов показывает, что для реализации на ЭВМ можно  рекомендовать алгоритм Грэхема.

Литература

1. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. – М.: Мир, 1989. – 478 с.
2. Ласло М.      Вычислительная             геометрия          и     компьютерная    графика  на    C++. - М.: БИНОМ, – 304 с.
3. Шикин Е.В. Начала компьютерной графики. – М.: ДИАЛОГ- МИФИ, 2000. – 374 с.
4. Шикин Е.В. Компьютерная  графика.  Полигональные модели.  – М.:  ДИАЛОГ- МИФИ, 2005.  – 223 с.
5. Седжвик Р. Фундаментальные алгоритмы на С++. – К.: ДиаСофт, 2001. - 688 с.
6. Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. – М.: Добросвет, – 596 с.