|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Belyakov 2:5020/400 28 Oct 2001 19:11:54
To : All
Subject : Точка в эпсилон окресности отрезка?
--------------------------------------------------------------------------------
Hi, All !
Подумал сам - дай другому, может есть лучшее рещение.
Hа плоскости дан отрезок А(P1(x1,y1),P2(x2,y2)) и точка P(x,y).
Требуется ответить на вопрос - находится ли точка P в
e-окрестности отрезка A. (e-окрестность - небольшое
произвольное фиксировнное кратчайшее расстояние от
точки до отрезка)
Задача в общем-то не на то, чтобы посчитать расстояние от
точки до отрезка по перпендикуляру. Устраивает именно
оценка нахождения точки в e-окрестности отрезка плюс
требуется быстрый и робастный алгоритм. Как минимум
без извлечения корней и вычисления тригонометрических
функций.
Из того, что пришло в голову. Проверяем нахождение точки в
квадрате, где диагональ - отрезок А + 2 * e. Дальше - считаем
площадь прямоугольника - e * len(A) и называем это e-площадью.
(В принципе можно посчитать один раз - чуть менее точно.)
Теперь считаем площадь треугольника <P,P1,P2>. Сравниваем...
Как оптимизацию - модифицируем расчет площади треугольника
- умножаем на 2 и возводим в квадрат и делаем тоже самое с
е-площадью...
Есть ли возможность сделать это быстрее/точнее/робастнее?
Опсс... Координаты точек - целочисленные. e-окрестность -
не превышает 15 единиц.
--
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
