Имеется 2 точки с координатами X1,Y1 и X2,Y2
Как можно быстро определить какая из этих точек ближе к третей точке X0,Y0?
Точное расстояное рассчитывать не нужно, нужно именно быстрая оценка какая из точек ближе, соответственно сложные математические функции (возведение в квадрат, корни и пр.) не приветствуются, все на уровне сложения-вычитания...
... << RSDN@Home 1.2.0 alpha rev. 655>>
Re: Быстрый алгоритм оценки ближайшей точки на плоскости
Евклидова норма оценивается сверху l_1-нормой (|x| + |y|), а снизу -- l_\infty-нормой (max(|x|,|y|)). В некоторых случаях этого достаточно, чтобы понять, какое расстояние больше.
Re: Быстрый алгоритм оценки ближайшей точки на плоскости
От:
Аноним
Дата:
06.02.07 09:48
Оценка:
Здравствуйте, dmitry501, Вы писали:
D>Имеется 2 точки с координатами X1,Y1 и X2,Y2 D>Как можно быстро определить какая из этих точек ближе к третей точке X0,Y0?
D>Точное расстояное рассчитывать не нужно, нужно именно быстрая оценка какая из точек ближе, соответственно сложные математические функции (возведение в квадрат, корни и пр.) не приветствуются, все на уровне сложения-вычитания...
Допустим есть три точки A(2,3),B(6,2) и C(3,1).
Определим какая точка ближе к С, A или B.
[ACx] = [Ax — Cx] = [2 — 3] = [-1] = 1
[ACy] = [Ay — Cy] = [3 — 1] = 2
Растояние между А и С равно: AC = ACx + ACy = 1 + 2 = 3
[BCx] = [Bx — Cx] = [6 — 3] = 3
[BCy] = [By — Cy] = [2 — 1] = 1
Растояние между B и С равно: BC = BCx + BCy = 3 + 1 = 4
Осталось сравнить AC и BC и выяснить что меньше.
Задача решена без квадрато и вычисления реального растояния.
Re: Быстрый алгоритм оценки ближайшей точки на плоскости
Здравствуйте, dmitry501, Вы писали:
D>Имеется 2 точки с координатами X1,Y1 и X2,Y2 D>Как можно быстро определить какая из этих точек ближе к третей точке X0,Y0?
D>Точное расстояное рассчитывать не нужно, нужно именно быстрая оценка какая из точек ближе, соответственно сложные математические функции (возведение в квадрат, корни и пр.) не приветствуются, все на уровне сложения-вычитания...
На уровне сложения-вычитания не получится. Но можно свести к двум умножениям.
a=X1-X0;
b=Y1-Y0;
c=X2-X0;
d=Y2-Y0;
Нам надо оценить a*a+b*b < c*c+d*d . Это сводится к (a-c)*(a+c) < (d-b)*(d+b) .
Здравствуйте, dmitry501, Вы писали:
D>Имеется 2 точки с координатами X1,Y1 и X2,Y2 D>Как можно быстро определить какая из этих точек ближе к третей точке X0,Y0?
Если нужны массовые запросы при 2-х фиксированных точках, то можно сделать так.
ГМТ точек равноудалённых от двух несовпадающих точек — это прямая. Находим её уравнение ax+by+c=0.
P(u,v)
au+bv+c>0 -> ближе к одной точке
au+bv+c<0 -> ближе к другой точке
au+bv+c==0 -> на одинаковом расстоянии
Если нужно находить ближайшую точку из множества точек, то можно сделать диаграмму Вороного.
Re: Быстрый алгоритм оценки ближайшей точки на плоскости
Здравствуйте, dmitry501, Вы писали:
D>Имеется 2 точки с координатами X1,Y1 и X2,Y2 D>Как можно быстро определить какая из этих точек ближе к третей точке X0,Y0?
D>Точное расстояное рассчитывать не нужно, нужно именно быстрая оценка какая из точек ближе, соответственно сложные математические функции (возведение в квадрат, корни и пр.) не приветствуются, все на уровне сложения-вычитания...
Можно использовать следующую оценку длины вектора (dx, dy): L(dx,dy) = max(|dx|,|dy|) + 0.4 * min(|dx|,|dy|)
Re[2]: Быстрый алгоритм оценки ближайшей точки на плоскости
Здравствуйте, dmitry501, Вы писали:
D>Здравствуйте, twisted_mind, Вы писали:
_>>Можно использовать следующую оценку длины вектора (dx, dy): L(dx,dy) = max(|dx|,|dy|) + 0.4 * min(|dx|,|dy|)
D>Интересно, откуда взялся магический коэффициент 0,4?
Если начертить график уравнения L(dx,dy)=r для некоторого r, то всё станет ясно. Здесь по сути окружность апроксимируется 8-угольником. Например, если рассмотреть такой график в первой четверти для точек x>=y, получим прямую x + 0.4y = r. Для y = 0 => x = r, а для x = y получаем x = r/1.4 (сравните: окружность с радиусом r пересекает прямую у=x в точке x = r/sqrt(2) ), то есть можно сказать, что окружность делится на 8 частей и каждая часть заменяется на прямую. В идеале вместо 0.4 должно быть sqrt(2) — 1, но по-моему в данном случае это непринципиально.
Здравствуйте, dmitry501, Вы писали:
D>Здравствуйте, <Аноним>, Вы писали:
А>>Сабж. Передумайте и используйте ответ Шахтера.
D>Хотелось обойтись целочисленной арифметикой процессора.
А умножение на 0.4 -- это какая арифметика? Те же два умножения и получатся.
Здравствуйте, dmitry501, Вы писали:
D>Здравствуйте, <Аноним>, Вы писали:
А>>Сабж. Передумайте и используйте ответ Шахтера.
D>Хотелось обойтись целочисленной арифметикой процессора.
И где проблемы? Два целочисленных умножения, причём точных, без всяких "обрезаний".
Здравствуйте, <Аноним>, Вы писали:
А>Здравствуйте, dmitry501, Вы писали:
D>>Здравствуйте, <Аноним>, Вы писали:
А>>>Сабж. Передумайте и используйте ответ Шахтера.
D>>Хотелось обойтись целочисленной арифметикой процессора.
А>И где проблемы? Два целочисленных умножения, причём точных, без всяких "обрезаний".
Поясняю. Координаты точек как-раз занимают машинное слово. При перемножении результат может не помесится в регистре. Но в принципе это не страшно, спасибо всем. Сделал умножением, получилось чуть сложнее, чем рассчитывал.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Re: Быстрый алгоритм оценки ближайшей точки на плоскости
