1632
правки
Изменения
м
Будем рассматривать множество точек на плоскости и способы построения их выпуклых оболочек.
==Алгоритм Грэма==
==Алгоритм Эндрюса==
rollbackEdits.php mass rollback
{{Определение
|definition=Выпуклой оболочкой множества точек называется линейная комбинация минимального набора точек, дающая все остальные точки.}}
Некоторые свойства выпуклых оболочек:
# Экстремальные всегда принадлежат выпуклой оболочке.
# Для равномерно распределенных в прямоугольнике точек, выпуклая оболочка будет состоять из логарифма точек.
# Если в изначальном массиве точка на 0-й позиции будет самой левой, то после построения выпуклой оболочки in-place она останется там же. Пусть нам дано конечное множество точек на плоскости <tex> D = \{d_0, d_1 \dots, d_n \}. </tex> <tex> d_0 </tex> {{---}} cамая левая нижняя точка, лежит на выпуклой оболочке. Рассмотрим алгоритмы, позволяющие построить выпуклую оболочку <tex>D</tex>
==Алгоритм Джарвиса==
Алгоритм в силу своей простоты легко реализуется in-place.
===Описание Алгоритма===
Будем находить точку, с наименьшим полярным углом от предыдущей стороны. Если таких точек несколько - брать самую дальнюю. И так до тех пор, пока выпуклая оболочка не замкнется.
===Псевдокод===
dot max_element(int j, int i)
{
if (left_turn(dots[j - 1], dots[j], dots[i]))
return dots[j];
else
return dots[i];
}
int jarvis(std::vector<dot> &dots)
for(int i = last + 2; i < size; i++)
{
std::swap(dots[last + 1], max_element(dots[last + 1], dots[i]));
}
}
return last;
};
==Алгоритм Merge hull==
<tex dpi = 140> n \cdot 2 \cdot \frac{1 - 2^{\log \log h}}{1 - 2} = </tex>
<tex dpi = 140> n \cdot 2^{\log \log h + 1} - n \le n \cdot 2^{\log \log h + 1} = 2n \cdot \log h = O(n \cdot \log h)</tex>
[[Категория: Вычислительная геометрия]]
