Изменения
Нет описания правки
{{В разработке}}
=Выпуклая оболочка множества точек=
{{Определение
|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;
};
