Re: Алгоритм Овермарса (Леювена)

From

Andrew Novikov ()

To

Ivan Boldyrev

Date

2003-01-04T11:49:41Z

Area

RU.ALGORITHMS

From: "Andrew Novikov" <mail@an.kiev.ua>

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)