Есть ли какие-либо недостатки в использовании проверок на расстоянии от квадрата, а не на расстоянии?

Я использую проверки расстояния в квадрате для практически всех моих проверок расстояния (длины вектора 3) из-за увеличения производительности в результате отсутствия квадратного корня (как при проверке простой длины).

Судя по всему, квадратные дистанционные проверки отлично работают в любой ситуации:

if x^2 < y^2, then x < y, even when 0 < (x or y) < 1

Я не рассматриваю ситуации, когда x или y меньше 0, так как расстояние и квадрат расстояния всегда будут положительными.

Поскольку это работает, похоже, что дистанционные проверки никогда не нужны, но у меня есть ноющее чувство, что я что-то упускаю. Будет ли это сохраняться в критических ситуациях?

Нет недостатка в том, что я использую квадрат длины для сравнения расстояний. Подумайте об этом так: вы просто пропускаете то, sqrtчто не дает вам никакой дополнительной точности. Если вам не нужно фактическое евклидово расстояние, то вы можете спокойно sqrtпропустить.

Конечно, квадрат длины масштабируется совсем не так, как евклидово расстояние, и поэтому является плохим кандидатом на такие вещи, как эвристика поиска пути .

Как намекал bummzack на аналогию с поиском пути, вам НУЖНО использовать «нормальную» длину каждый раз, когда вы складываете расстояния и хотите сравнить их сумму. (Просто потому, что суммы квадратов длин отличаются от квадратов сумм длин).

х ^ 2 + у ^ 2! = (х + у) ^ 2

Единственный недостаток, о котором я могу думать, это когда приходится иметь дело с большими числами, которые будут переполнены в квадрате.

Например, в Java:

int x = Integer.MAX_VALUE / 1000000; //2147
int y = Integer.MAX_VALUE / 5000; //429496
System.out.println("x < y: " + (x < y)); //true
System.out.println("x*x: " + (x * x)); //4609609
System.out.println("y*y: " + (y * y)); //-216779712 - overflows!
System.out.println("x*x < y*y: " + (x * x < y * y)); //false - incorrect result due to overflow!

Также стоит отметить, что это происходит, когда вы используете Math.pow () с точно такими же числами и приводите обратно к int из двойного числа, возвращаемого из Math.pow():

System.out.println("x^2: " + (int) (Math.pow(x, 2))); //4609609
System.out.println("y^2: " + (int) (Math.pow(y, 2))); //2147483647 - double to int conversion clamps to Integer.MAX_VALUE
System.out.println("x^2 < y^2: " + ((int) (Math.pow(x, 2)) < (int) (Math.pow(y, 2)))); //true - but for the wrong reason!

Работает? Нет , он дал только правильный ответ, потому что y*yограничен Integer.MAX_VALUE, и x*xменьше, чем Integer.MAX_VALUE. Если бы x*xтакже был привязан к, Integer.MAX_VALUEто вы получите неправильный ответ.

Подобные принципы также применимы к плавающим и двойным значениям (за исключением того, что они, очевидно, имеют больший диапазон перед переполнением) и любому другому языку, который позволяет незаметно переполняться.

Однажды я работал на квадратных расстояниях и допустил ошибку, рассчитав квадратные расстояния для счетчика одометров.

Конечно, вы не можете сделать это, потому что математически,

(a^2+b^2+c^2+d^2)!=(a+b+c+d)^2

В итоге я получил неверный результат. К сожалению!

У вас могут возникнуть проблемы, если вы пишете алгоритм, который требует, чтобы вы вычислили оптимизированную позицию. Например, допустим, у вас был набор объектов, и вы пытались вычислить позицию с наименьшим общим расстоянием от всех объектов. Просто в качестве конкретного примера, скажем, мы пытаемся питать три здания, и мы хотим выяснить, куда должна идти электростанция, чтобы мы могли подключить ее ко всем зданиям, используя наименьшую общую длину провода. Используя метрику расстояния в квадрате, вы получите координату X электростанции, представляющую собой среднее значение координаты X всех зданий (и аналогично координате Y). Используя обычную метрику расстояния, решение будет отличаться, и часто очень далеко от решения по квадрату расстояния.

Использование квадрата расстояния почти всегда просто отлично и хорошо для производительности. Важны следующие соображения:

Если вы хотите подумать о сумме нескольких расстояний, квадрат расстояния будет неточным. Например, у меня есть два расстояния, и я хочу убедиться, что их сумма меньше 10. Следующий код неверен:

a = get_distance_squared(c,d);
b = get_distance_squared(e,f);
assert(a+b < 10^2);

Он не может быть утвержден в следующем неверном случае: a=36и b=49. В этом случае первая длина равна 6, а вторая 7; их сумма больше 10, но сумма квадратов не больше 100 или больше.

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