|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 27 Mar 2002 04:49:43
To : Alexey Tomin
Subject : Re: Расстояние до ломанной
--------------------------------------------------------------------------------
From: Andrey Tarasevich <atarasevich@telocity.com>
Alexey Tomin wrote:
>
> U>> Есть точка A(X,Y). Есть ломаная, заданная группой точек излома
> U>> P1(X,Y)...PN(X,Y)
> U>> Как быстрее всего найти расстояние от точки до ломаной?
> > Хочешь не хочешь а перебрать все сегметы ломаной тебе придется, т.е.
> > за O(n), ища расстояние до каждого отрезка ломанной.
>
> Hет.
> Пусть k-й отрезок это P[k] - P[k+1]
> Если угол O - P[k] - P[k+1] или O - P[k+1] - P[k] тупой, тоъ
> искать расстояние до отрезка не надо (оно больше расстояния до вершины).
> Только вот выгодно ли искать углы?
> ...
Искать сами углы не надо - скалярного произведения сторон достаточно для
ответа на вопрос о том, острый угол или тупой.
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
