|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 29 Oct 2001 08:07:31
To : Andrey Belyakov
Subject : Точка в эпсилон окресности отрезка?
--------------------------------------------------------------------------------
Привет, Андрей!
28.10.01 18:11, Andrey Belyakov писал:
AB> Hа плоскости дан отрезок А(P1(x1,y1),P2(x2,y2)) и точка P(x,y).
AB> Требуется ответить на вопрос - находится ли точка P в
AB> e-окрестности отрезка A. (e-окрестность - небольшое
AB> произвольное фиксировнное кратчайшее расстояние от
AB> точки до отрезка)
Расстоянием от точки C до отрезка AB называется расстояние от точки C до
ближайшей к ней точки D отрезка AB. Записывая в векторной форме, получаем:
DC = AC + AB * max(0, min(1, (AB*AC)/(AB*AB)));
если (DC*DC) <= e*e, то попадает.
Здесь (AB*AC) - скалярное произведение векторов
(AB*AC) = (B.x-A.x)*(C.x-A.x) + (B.y-A.y)*(C.y-A.y)
AB> Опсс... Координаты точек - целочисленные. e-окрестность -
AB> не превышает 15 единиц.
Тогда не забудь все промежуточные результаты считать в числах с
плавающей точкой с двойной точностью. Hе округляй промежуточные результаты.
В результате будет что-то вроде:
// точка C попадает в e-окрестность отрезка AB ?
bool IsDotNearSeg (DOT AB, DOT AC, double e2)
{
double ABAС = AB*AС; // найти скалярное произведение AB и AC
if (ABAC > 0) // если положительно (а иначе ближайшая точка - A)
{
double ABAB = AB*AB; // найти квадрат длины отрезка
if (ABAC < ABAB) // если проекция точки C попадает внутрь отрезка
AC += AB * (ABAC/ABAB); // найти проекцию точки на отрезок
else AC += AB; // иначе ближайшая точка - B
}
return AC*AC <= e2;
}
Здесь DOT - твой класс вектора с полями типа double и определёнными
операциями (или распиши через скаляры типа double).
Условия проверок должны быть строгими, иначе можно получить деление
на 0, если отрезок слишком мал (вырожден в точку).
Условие при операторе возврата, наоборот, лучше делать нестрогим.
С уважением, Олег Полубасов.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Точка в эпсилон окресности отрезка? 
