Как найти расстояние между двумя точками быстрее?

Question

[i__egor]

Кто знает более производительный способ найти расстояние в двумерном пространстве от точки А до Б. Нужно что-то быстрее чем точное: sqrt((x1-x2)^2 - (у1-у2)^2) и более точное чем самое простое: модуль(х1-х2)+модуль(у1-у2)

Comments

[vaut]

Вам нужно само значение расстояния или сравнение расстояний?
Для сравнения отлично подойдет квадрат расстояния. Извлечение корня дорогая операция..

Еще есть не точные способы извлечения корня.

[i__egor]

vaut, нужно само расстояние можно не такое точное. помню находил такую функцию без корня выглядела она не как круг, а равносторонний многоугольник

Answer 1

[longclaps]

Например так:

x, y = 1.2345, 3.2109
le0 = sqrt(x * x + y * y)
if x < y:
    x, y = y, x
y /= x
le1 = x * (1.0 + y * y * 0.5)
print(le1 / le0) #  1.0023767214085302, неплохо

В худшем случае, когда x == y, ошибка составит +6%.
Только не так уж это быстро.

Есть способ побыстрей/попроще, тут погрешность до +8%

if x < y:
    x, y = y, x
le1 = x + y * 0.41421356237309515 # sqrt(2.0) - 1.0

Comments

[longclaps]

i__egor, чего молчишь? Не вдупляешь?

[Wataru]

longclaps, Тут нет ошибки?

le0 = sqrt(x * x + y * y)

Это же уже подсчет расстояния получается.

[longclaps]

Wataru, это используется для оценки погрешности

[i__egor]

уже нашел. https://gamedev.ru/tip/?id=41

[longclaps]

i__egor, рад за тебя, но я всё же ответил на твой вопрос, в полном соответствии с тем, как ты его поставил.
Я вижу, ты не любитель помечать ответы решением. Таких принято считать жлобами.

Answer 2

[Rsa97]

А конечная цель метрики какая? Например, для сортировки или проверки нахождения в заданном радиусе можно убрать корень.