418
правок
Изменения
м
==Алгоритм Грэма==
===Описание Алгоритма===
===Псевдокод===
v = begin;
w = prev(v);
f = false;
while (next(v) != begin || f == false)
{
if (next(v) == w)
f:= true;
if (left_turn(v, next(v), next(next(v))))
v = next(v);
else
{
next(v).erase();
v = prev(v);
}
}
==Алгоритм Эндрюса==
Нет описания правки
===Описание Алгоритма===
Будем реализовывать алгоритм in-plaсe.Предположим, что <tex> d_0, d_1, \dots, d_{i - 1} </tex> {{---}} первые <tex> i </tex> точек выпуклой оболочки. Научимся находить следующую.Для этого будем перебирать все точкиточку, еще не вошедшие в ответ (но включая <tex> d_0 </tex>). Точка <tex> d_{i + 1} </tex> {{---}} точка с наименьшим полярным углом <tex> d_{i от предыдущей стороны. Если таких точек несколько - 1} d_{i} d_{i + 1} </tex>брать самую дальнюю. И так до тех пор, пока выпуклая оболочка не замкнется.
===Псевдокод===
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>
[[Категория: Вычислительная геометрия]]
