УДК 004.021

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

Пугачев Анатолий Иванович – кандидат технических наук, доцент Самарского государственного технического университета.

Аннотация: В статье рассматривается новый алгоритм построения минимальной выпуклой оболочки для множества точек на плоскости. Изложена реализация трех этапов алгоритма на основе функций обработки множеств точек. Так же детально рассмотрены алгоритмы реализации каждой функции. Оценена трудоемкость предложенного алгоритма. Приведен результат, полученный при программной реализации алгоритма.

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

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

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

Пусть P – заданное множество точек на плоскости. Требуется построить минимальную выпуклую оболочку P, то есть упорядоченный список H вершин выпуклого многоугольника, ограничивающего множество P, такого, что вершинами списка H будут точки этого множества.

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

В большинстве алгоритмов построения МВО [3] нахождение каждой последующей вершины минимальной выпуклой оболочки основано на просмотре всех точек множества P. В силу этого трудоемкость алгоритмов построения МВО без предварительно обработки оценивается как O(nh), где n – мощность множества P, а h – количество вершин МВО.

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

image001

Рисунок 1. Сокращение числа рассматриваемых точек.

В предлагаемом алгоритме такой подход служит основным приемом сокращения трудоемкости. Алгоритм представлен ниже.

V[0] = MinY(P); V[1] = MaxX(P);

V[2] = MaxY(P); V[3] = MinX(P);

V[4] = V[0];

H.Clear();

for (i = 0; i < 4; i++)

      if (V[i] != V[i + 1])

      {

            T = Subset(P, V[i], V[i + 1]);

            if (T.Count() != 0) 

                  H = H.Concat(Hull(T [i], V[i], V[i + 1]));

            else H.Add(pe);

      }

H = Press(H);

Первым этапом является нахождение списка V экстремальных вершин МВО. В данном алгоритме функция MinY(P) возвращает вершину V[0] с наименьшим значением y, MaxX(P) возвращает вершину V[1] с наибольшим значением x, MaxY(P) возвращает вершину V[2] с наибольшим значением y, а функция MinX(P) возвращает вершину V[3] с наименьшим значением x (рисунок 1). Точка V[4] = V[0] добавляется в список V для удобства дальнейшей обработки.

На втором этапе в цикле четырехкратно из множества P выделяется подмножество T, содержащее часть списка H вершин МВО, затем эти вершины находятся и добавляются в список H.

Каждое подмножество T лежит справа от отрезка, заданного двумя ближайшими экстремальными вершинами. Первое подмножество ограничено отрезком V[0]V[1], второе ограничено отрезком V[1]V[2], третье ограничено отрезком V[2]V[3], а четвертое – отрезком V[3]V[0] (рисунок 1).

Отбор точек из P в каждое подмножество выполняется функцией Subset(P, pb, pe). Точки pb, pe – это начало и конец отрезка, ограничивающего подмножество T. Алгоритм этой функции включает последовательный просмотр точек множества P. Каждая точка pt из P вместе с точками pb и pe рассматриваются как вершины ориентированного треугольника pbpept, удвоенная площадь которого вычисляется по известной [2] формуле 

Sq(pb, pe, pt) = (pe.xpb.x)(pt.ypb.y) – (pe.ypb.y)(pt.xpb.x).

image002

Рисунок 2. Поиск очередной вершины в подмножестве T.

Если Sq(pb, pe, pt) < 0, то точка pt расположена справа от pb pe. В этом случае она добавляется в T. Иначе, если Sq(pb, pe, pt) ≥ 0, то pt находится слева от отрезка pb pe или лежит на нем и поэтому пропускается.

Если T пусто, то в список H вершин МВО добавляется единственная точка pe, то есть H.Add(pe), иначе далее с помощью функции Hull(T, pb, pe) выполняется поиск вершин МВО в подмножестве T. Функция Concat добавляет в конец списка H вершины, найденные функцией Hull.

Алгоритм функции Hull представлен ниже.

ps = pe;

while (pb != pe)

{

      for (i = 0; i < T.Count(); i++)

      {

            pt = T[i];

            if (Sq(pb, pe, pt) < 0) pe = pt;

      }

      H.Add(pe);

      pb = pe; pe = ps;

}

В каждом цикле последовательно просматриваются точки pt из T. Если Sq(pb, pe, pt) < 0, значит pt расположена справа от отрезка pbpe и, следовательно, может быть очередной вершиной МВО. В этом случае точка pe принимает значение pt и процесс поиска циклически продолжается с очередной точкой pt из T вплоть до последней. По окончанию цикла просмотра pt из T последнее значение pe будет очередной вершиной МВО, которая добавляется в список H: H.Add(pe).

Перед началом следующего цикла поиска очередной вершины за pb принимается pe, а pe восстанавливает первоначальное значение: pe = ps.

Условием завершения цикла поиска вершин в подмножестве T служит равенство pb = pe.

Четырехкратное применение процедуры Hull(T) дает полное упорядоченное множество вершин МВО. Но при этом в списке H могут оказаться «лишние» вершины. Это может происходить, когда три или более следующих друг за другом вершины, расположены на одной прямой. Для исключения таких вершин выполняется третий этап алгоритма, на котором вершины из H переписываются в новый список H2, пропуская «лишние». Алгоритм функции Press, выполняющей такое преобразование списка H, приведен ниже.

h = H.Count();

for (i = 0; i < h; i++)

{

      if (Sq(H[i], H[(i + 1) % h], H[(i + 2) % h]) != 0)

            H2.Add(H[(i + 1) % h]);

}

Признаком исключения i+1-ой точки исходного списка служит равенство нулю площади треугольника из тех последовательных вершин в списке H.

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

Рассмотренный алгоритм состоит из трех этапов: поиск экстремальных точек; поиск вершин МВО в подмножествах множества P; исключение лишних точек из списка вершин МВО. По сравнению с известными данный алгоритм отличается простотой реализации каждого этапа.

image003

Рисунок 3. Результат программной реализации алгоритма.

Трудоемкость первого этапа O(n). Второй этап включает поиск вершин МВО в четырех подмножествах. Трудоемкость этого этапа можно оценить как O(4(mh/4)) = O(mh), где m – среднее количество точек в одном подмножестве. Если считать, что в среднем m = n/8, то O(nh/8). Трудоемкость четвертого этапа O(h). Таким образом, трудоемкость всего алгоритма определяется трудоемкостью O(nh/8) второго этапа, что ниже трудоемкости алгоритма Джарвиса [2].

Список литературы

  1. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. – М.: Мир, 1989. – 478 с.
  2. Ивановский С.А., Преображенский А.С., Симончик С.К. Алгоритмы вычислительной геометрии. Выпуклые оболочки: простые алгоритмы // Компьютерные инструменты в образовании, 2007, № 1, с. 4 – 19.
  3. Чаднов Р.В., Скворцов А.В., Мирза Н.С. Обзор алгоритмов построения выпуклой оболочки на плоскости // Вестник Томского государственного университета. – 2004, S9-2 – с. 116 – 121.