|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 29 Oct 2001 09:00:44
To : Oleg Polubasoff
Subject : Re: Точка в эпсилон окресности отрезка?
--------------------------------------------------------------------------------
"Oleg Polubasoff" <pbas@spb.cityline.ru> wrote in message
news:9rikie$1445$1@ddt.demos.su...
> 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е округляй промежуточные
результаты.
Hу это уж слишком строго,
все это можно посчитать и в целочисленной арифметике.
if(AB*AC<0) return AC*AC<e*e; // или <=, кто как определит границу
if(BA*BC<0) return BC*BC<e*e; // можно и if(AB*AC>AB*AB)
int ABxAC =(AB.x*AC.y-AB.y*AC.x); // векторное произведение
return ABxAC*ABxAC<e*e*(AB*AB); // и никакого деления ;)
Скорее всего это что-то то вроде наведения мыши на отрезок на экране
для фиксации наезда :) Так что числа должны быть совсем небольшими.
> В результате будет что-то вроде:
>
> // точка 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
Hе должно ли тут везде быть -=, вместо +=, (исходя из формулы сложения
векторов AB+BC=AC)
> }
>
> return AC*AC <= e2;
> }
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
