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

Эта статья находится в разработке!

Выпуклая оболочка множества точек

Определение:

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

Еще одно определение:

Определение:

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

Будем рассматривать множество точек на плоскости и способы построения их выпуклых оболочек.

Некоторые свойства выпуклых оболочек:

1. Экстремальные всегда принадлежат выпуклой оболочке.
2. Для равномерно распределенных в прямоугольнике точек, выпуклая оболочка будет состоять из логарифма точек.
3. Если в изначальном массиве точка на 0-й позиции будет самой левой, то после построения выпуклой оболочки in-place она останется там же.

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

Алгоритм Джарвиса определяет последовательность точек, образующую выпуклую оболочку множества точек на плоскости. Так же известен как алгоритм "заворачивания подарка".

Время работы алгоритма — [math] O(h \cdot n) [/math], где [math] h [/math] — количество точек в выпуклой оболочке. В случае [math] h = n [/math] получаем [math] O(n ^ 2) [/math].

Алгоритм в силу своей простоты легко реализуется in-place.

Псевдокод

int jarvis(std::vector<dot> &dots)
{
   int last = 0;
   dots.push_back(dots[0]);
   int size = dots.size();
   do
   {
      for(int i = last + 2; i < size; i++)
      {
         std::swap(dots[last + 1], max_element(dots[last + 1], dots[i]));
      }
   }
   while(dots[last] != dots[0]);
   
   std::swap(dots[last], dots[size - 1]);
   dots.pop_back();
   
   return last;
};