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

29

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

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

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

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

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

Aralox
источник

Ответы:

41

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

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

bummzack
источник
16
Квадратный корень фактически удаляет точность из проверки расстояния. Вы можете думать об этом как о попытке получить квадратный корень из числа с фиксированной точкой между 1 и 2 и сохранить результат (между 1 и sqrt (2)) в том же диапазоне. Некоторые расстояния, которые сравниваются как x ^ 2 <y ^ 2, будут сравниваться как x = y после того, как вы возьмете квадратный корень. Проверка длины в квадрате выполняется быстрее и точнее.
Джон Калсбик
Спасибо за ваши отличные ответы Буммзак и Джон Калсбик! Ваши ответы в совокупности отлично отвечают на мой вопрос. Я не учел дополнительное пространство памяти от неиспользования квадратного корня, действительно хороший пикап там. И эта ссылка эвристики делает для отличного чтения
Aralox
1
За исключением случая A *. Я вспоминаю, что читал статью, в которой рассказывалось о проверке различных эвристик и работал d^2ужасно. В А * |dx| + |dy|работает красиво. У меня нет ссылки, так как я читаю месяц или около того назад.
Джонатан Дикинсон
3
В случае A * вы не просто сравниваете расстояния, но и добавляете их, поэтому пропуск sqrt действительно имеет значение.
amitp
1
@bobobobo Я согласен; Я в основном сделал это, чтобы сбить потенциальный аргумент в другом направлении, то есть нормальное расстояние как-то более точно.
Джон Калсбек
14

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

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

Imi
источник
4

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

Например, в 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то вы получите неправильный ответ.

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

Каспар
источник
Большинство людей используют floats для координат, которые переполняются только после того, как 10^38нет int.
бобобо
Но в 10 ^ 38 вы потеряли так много точности, что вы действительно не можете быть уверены, что ваши сравнения расстояний больше действительны - переполнение здесь не единственная проблема. См. Altdevblogaday.com/2012/02/05/dont-store-that-in-a-float (раздел «Таблицы» суммирует потери точности до 1 миллиарда).
Максимус Минимус
У вас будет та же проблема переполнения с sqrt (x * x). Я не понимаю вашу точку зрения. Это не про манхэттенское расстояние и т. Д.
Богглез
@bogglez - зависит, увеличивает ли ваша библиотека (или процессор) удвоение или нет.
Максимус Минимус
3

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

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

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

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

bobobobo
источник
1
Также я мог бы добавить, что было несколько раз, когда я пытался использовать квадраты расстояний, только чтобы обнаружить, что мне нужно было фактическое расстояние позже в той же самой ветви кода. Так что не переусердствуйте. Иногда не стоит хранить квадратичные коэффициенты повсюду, когда вам sqrtвсе равно нужно будет выполнить операцию.
бобобо
3

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

Александр Грубер
источник
Кажется спорным, что было бы лучше или хуже для данной ситуации. Я помню, что математики часто предпочитают использовать квадрат расстояния при подгонке линии к набору точек. Возможно, они делают это, потому что это уменьшает влияние одиноких выбросов. В вашем случае с тремя зданиями выбросы могут не быть риском. Или, возможно, они делают это, потому что с ними x^2легче работать |x|.
Joeytwiddle
@joeytwiddle Выбросы на самом деле влияют на линейную регрессию больше с наименьшими квадратами, чем с абсолютным расстоянием. Ты прав, что его используют, потому что с ним легче работать. В приведенном мною примере (даже если он изменен для содержания большого числа зданий), метрика расстояния в квадрате решается с помощью простой формулы (среднее арифметическое каждой координаты), но метрика абсолютного расстояния математически неразрешима и должна быть решается примерно с помощью одного из ряда численных методов.
Александр Грубер
Спасибо за исправление. Конечно, вы правы, квадрат расстояния генерирует большую ошибку для выбросов, увеличивая их влияние, а не уменьшая его, как я неправильно указал выше. Это удивительно, насколько сложнее вычислить решение с наименьшим абсолютным расстоянием.
Joeytwiddle
0

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

Если вы хотите подумать о сумме нескольких расстояний, квадрат расстояния будет неточным. Например, у меня есть два расстояния, и я хочу убедиться, что их сумма меньше 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 или больше.

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

Ограниченное искупление
источник