|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Novikov 2:5020/400 04 Jan 2003 12:49:41
To : Ivan Boldyrev
Subject : Re: Алгоритм Овермарса (Леювена)
--------------------------------------------------------------------------------
Hello, Ivan!
You wrote to "Andrew Novikov" on Sat, 04 Jan 2003 13:05:26 +0300:
IB> В книге М. Ласло "Вычислительная геометрия и компьютерная графика на
IB> C++" есть он-лайн алгоритм построения оболочки, который работает
IB> следующим образом. Если новая точка попадает внутрь имеющейся
IB> оболочки, то ничего менять не надо. Иначе ищем две касательные из
IB> точки к оболочке и добавляем их в качестве новых рёбер, удалив
IB> ближнюю к точке часть старой оболочки.
IB> Касательные ищутся так: ищется точка, у которой "приходящее" и
IB> "исходящее" рёбра находятся по одну сторону луча. Так как оболочка
IB> на предудущем шаге была выпуклая, то это будет касательная.
Это алгоритм Препарата (если не ошибаюсь). Он не позволяет
динамически удалаять точки из существующей оболочки.
With best regards, Andrew Novikov. E-mail: mail@an.kiev.ua
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
