Existem desvantagens no uso de verificações de distância ao quadrado em vez de distância?

29

Uso verificações de distância ao quadrado para basicamente todas as minhas verificações de distância (comprimento do vetor3), devido ao aumento de desempenho por não incorrer em uma raiz quadrada (como nas verificações de comprimento simples).

Pelo que parece, as verificações de distância ao quadrado funcionam bem em todas as situações:

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

Não estou considerando situações em que x ou y é menor que 0, pois a distância e a distância ao quadrado sempre serão positivas.

Como isso funciona, parece que nunca são necessárias verificações de distância, mas sinto que estou perdendo alguma coisa. Isso ainda se mantém em situações críticas de precisão?

mathematics spaces Aralox
fonte

Respostas:

41

Não tenho nenhuma desvantagem ao usar o comprimento ao quadrado para comparar distâncias. Pense assim: você está pulando o sqrtque não fornece precisão adicional. Se você não precisar da distância euclidiana real, poderá sair com segurança sqrt.

É claro que o comprimento ao quadrado varia de maneira bem diferente da distância euclidiana e, portanto, é um candidato ruim para coisas como heurísticas de busca de caminhos .

bummzack
fonte
16
A raiz quadrada realmente remove a precisão da verificação de distância. Você pode pensar nisso como uma tentativa de obter a raiz quadrada de um número de ponto fixo entre 1 e 2 e armazenar o resultado (entre 1 e sqrt (2)) exatamente no mesmo intervalo. Algumas distâncias comparadas como x ^ 2 <y ^ 2 serão comparadas como x = y após a raiz quadrada. A verificação do comprimento ao quadrado é mais rápida e precisa.
John Calsbeek
Obrigado por suas excelentes respostas bummzack e John Calsbeek! Suas respostas combinadas respondem perfeitamente à minha pergunta. Eu não considerei o espaço de memória adicional por não usar uma raiz quadrada, uma captura muito boa lá. E que as heurísticas ligar faz para uma ótima leitura
Aralox
1
Exceto no caso de A *. Lembro-me de ler um artigo que descreveu os testes de diferentes heurísticas e d^2teve um desempenho horrível. Em A * |dx| + |dy|funciona bem. Não tenho o link enquanto leio mais ou menos um mês.
Jonathan Dickinson
3
No caso de A *, você não está apenas comparando distâncias, mas adicionando-as, portanto, pular o sqrt faz a diferença.
Amitp
1
@bobobobo Eu concordo; Eu principalmente consegui derrubar um argumento em potencial na outra direção, ou seja, a distância normal, de alguma forma, é mais precisa.
John Calsbeek
14

Como bummzack sugeriu com a analogia de localização de caminho, você PRECISA usar o comprimento "normal" toda vez que adicionar distâncias e desejar comparar sua soma. (Só porque somas de quadrados de comprimentos são diferentes de somas de quadrados de comprimentos).

x ^ 2 + y ^ 2! = (x + y) ^ 2

Imi
fonte
4

A única desvantagem em que consigo pensar é quando se lida com números grandes que transbordam ao quadrado.

Por exemplo, em 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!

Também é importante notar que é o que acontece quando você usa Math.pow () com exatamente os mesmos números e retorna ao int a partir do dobro retornado deMath.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!

Está funcionando? Não , apenas deu a resposta correta porque y*yestá presa Integer.MAX_VALUEe x*xé menor queInteger.MAX_VALUE . Se x*xtambém foi preso Integer.MAX_VALUE, você obteria uma resposta incorreta.

Princípios semelhantes também se aplicam a carros alegóricos e duplos (exceto que obviamente têm um alcance maior antes do transbordamento) e a qualquer outro idioma que silenciosamente permita transbordamentos.

Caspar
fonte
A maioria das pessoas usa floats para coordenadas, que só transbordam depois de 10^38pouco tempo int.
bobobobo
Mas em 10 ^ 38 você perdeu tanta precisão que realmente não pode ter certeza de que suas comparações de distância são válidas mais - o excesso não é o único problema aqui. Consulte altdevblogaday.com/2012/02/05/dont-store-that-in-a-float (a seção "Tabelas" resume a perda de precisão de até 1 bilhão).
Maximus Minimus 12/03
Você terá o mesmo problema de estouro com sqrt (x * x). Eu não entendo o seu ponto. Isto não é sobre Manhattan distância etc.
bogglez
@bogglez - depende se a sua biblioteca (ou CPU) lança para duplicar ou não.
Maximus Minimus 11/11
3

Uma vez eu estava trabalhando em distâncias quadradas e cometi o erro de acumular distâncias quadradas, para uma contagem de odômetros.

Claro, você não pode fazer isso, porque matematicamente,

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

Então, acabei com um resultado incorreto lá. Opa!

bobobobo
fonte
1
Além disso, devo acrescentar que houve mais de algumas vezes em que tentei usar distâncias quadradas, apenas para descobrir que precisava de distâncias reais posteriormente no mesmo ramo de código. Então, não exagere. Às vezes, não vale a pena o inconveniente de manter os coeficientes quadrados em todos os lugares, quando você precisa terminar a sqrtoperação de qualquer maneira.
bobobobo
3

Você pode ter problemas se estiver escrevendo um algoritmo que exija a computação de uma posição otimizada. Por exemplo, digamos que você tenha um conjunto de objetos e esteja tentando calcular a posição com a menor distância total de todos os objetos. Apenas para um exemplo concreto, digamos que estamos tentando alimentar três edifícios e queremos descobrir para onde a usina deve ir, para que possamos conectá-la a todos os edifícios usando o menor comprimento total de fio. Usando a métrica da distância ao quadrado, você terminaria com a coordenada x da usina sendo a média das coordenadas x de todos os edifícios (e analogamente para a coordenada y). Usando a métrica de distância comum, a solução seria diferente e geralmente muito distante da solução ao quadrado da distância.

Alexander Gruber
fonte
Parece discutível o que seria melhor ou pior para uma determinada situação. Lembro-me de que os matemáticos geralmente escolhem usar o quadrado da distância ao ajustar uma linha a um conjunto de pontos. Talvez eles façam isso porque reduz a influência de discrepantes isolados. No seu caso de três edifícios, os valores extremos podem não ser um risco. Ou talvez o façam porque x^2é mais fácil trabalhar com isso |x|.
Joeytwiddle #
@joeytwiddle Os outliers realmente afetam a regressão linear mais com menos quadrados que a distância absoluta. Você está certo de que é usado porque é mais fácil trabalhar com ele. No exemplo que eu dei (mesmo que modificado para conter um grande número de construções), a métrica da distância ao quadrado é resolvida com uma fórmula simples (a média aritmética de cada coordenada), mas a métrica da distância absoluta é matematicamente intratável e deve ser resolvido aproximadamente usando um dos vários métodos numéricos.
Alexander Gruber
Obrigado pela correção. É claro que você está certo, o quadrado da distância gera um erro maior para os discrepantes, aumentando sua influência em vez de reduzi-la, como afirmei incorretamente acima. Isso é fascinante quanto mais difícil é a solução da menor distância absoluta de distância.
Joeytwiddle
0

Usar a distância ao quadrado quase sempre é bom e bom para o desempenho. As seguintes considerações são importantes:

Se você quiser pensar na soma de um número de distâncias, a distância ao quadrado será imprecisa. Por exemplo, tenho duas distâncias e quero garantir que a soma seja menor que 10. O código a seguir está incorreto:

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

Falha ao afirmar no seguinte caso inválido: a=36eb=49 . Nesse caso, o primeiro comprimento é 6 e o ​​segundo 7; sua soma é maior que 10, mas a soma dos quadrados não é 100 ou maior.

Outra consideração: para distâncias com valor real, a distância ao quadrado sempre será positiva. Se você está medindo o deslocamento, por exemplo, pode ser necessário lidar com valores negativos, e a quadratura deles não é suficiente.

Expiação limitada
fonte