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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}}»)
 
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 +
 +
=Выпуклая оболочка множества точек=
 +
 +
{{Определение
 +
|definition=Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.}}
 +
 +
Еще одно определение:
 +
{{Определение
 +
|definition=Выпуклой оболочкой множества точек называется линейная комбинация минимального набора точек, дающая все остальные точки.}}
 +
 +
Будем рассматривать множество точек на плоскости и способы построения их выпуклых оболочек.
 +
 +
Некоторые свойства выпуклых оболочек:
 +
# Экстремальные всегда принадлежат выпуклой оболочке.
 +
# Для равномерно распределенных в прямоугольнике точек, выпуклая оболочка будет состоять из логарифма точек.
 +
# Если в изначальном массиве точка на 0-й позиции будет самой левой, то после построения выпуклой оболочки in-place она останется там же.
 +
 +
==Алгоритм Джарвиса==
 +
'''Алгоритм Джарвиса''' определяет последовательность точек, образующую выпуклую оболочку множества точек на плоскости. Так же известен как алгоритм "заворачивания подарка".
 +
 +
Время работы алгоритма {{---}} <tex> O(h \cdot n) </tex>, где <tex> h </tex> {{---}} количество точек в выпуклой оболочке. В случае <tex> h = n </tex> получаем <tex> O(n ^ 2) </tex>.
 +
 +
Алгоритм в силу своей простоты легко реализуется 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;
 +
};

Версия 15:46, 2 мая 2012

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

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

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


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

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


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

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

  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;
};
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости&oldid=21770»