Y a-t-il des inconvénients à utiliser des vérifications au carré de la distance plutôt que la distance?

29

J'utilise des vérifications au carré de la distance pour pratiquement toutes mes vérifications de distance (longueur vector3), en raison de l'augmentation des performances de ne pas encourir de racine carrée (comme dans les vérifications de longueur simple).

À première vue, les contrôles de distance au carré fonctionnent bien dans toutes les situations:

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

Je ne considère pas les situations où x ou y est inférieur à 0, car la distance et la distance au carré seront toujours positives.

Depuis que cela fonctionne, il semble que les contrôles à distance ne soient jamais nécessaires, mais j'ai le sentiment persistant que je manque quelque chose. Cela tiendra-t-il toujours dans les situations critiques en matière de précision?

Aralox
la source

Réponses:

41

Je ne connais aucun inconvénient lorsque j'utilise la longueur au carré pour comparer les distances. Pensez-y comme ça: vous sautez simplement ce sqrtqui ne vous donne aucune précision supplémentaire. Si vous n'avez pas besoin de la distance euclidienne réelle, vous pouvez laisser de côté en toute sécurité sqrt.

Bien sûr, la longueur au carré est très différente de la distance euclidienne et est donc un mauvais candidat pour des choses comme l'heuristique d'orientation .

bummzack
la source
16
La racine carrée supprime en fait la précision du contrôle de distance. Vous pouvez y voir une tentative de prendre la racine carrée d'un nombre à virgule fixe entre 1 et 2 et de stocker le résultat (entre 1 et sqrt (2)) dans exactement la même plage. Certaines distances qui se comparent à x ^ 2 <y ^ 2 se compareront à x = y après avoir pris la racine carrée. La vérification de la longueur au carré est à la fois plus rapide et plus précise.
John Calsbeek
Merci pour vos excellentes réponses bummzack et John Calsbeek! Vos réponses combinées répondent parfaitement à ma question. Je n'ai pas considéré l'espace mémoire supplémentaire de ne pas utiliser de racine carrée, un très bon ramassage là-bas. Et ce lien heuristique fait une bonne lecture
Aralox
1
Sauf dans le cas de A *. Je me souviens d'avoir lu un article qui décrivait les tests de différentes heuristiques et les d^2performances horribles. Dans A * |dx| + |dy|fonctionne bien. Je n'ai pas le lien comme je l'ai lu il y a environ un mois.
Jonathan Dickinson
3
Dans le cas de A *, vous ne comparez pas simplement des distances, mais vous les ajoutez, donc sauter le sqrt fait une différence.
amitp
1
@bobobobo J'accepte; J'ai surtout réussi à abattre un argument potentiel dans l'autre sens, c'est-à-dire que la distance normale était en quelque sorte plus précise.
John Calsbeek
14

Comme bummzack a fait allusion à l'analogie de recherche de chemin, vous devez utiliser la longueur "normale" chaque fois que vous additionnez des distances et que vous souhaitez comparer leur somme. (Tout simplement parce que les sommations de carrés de longueurs sont différentes des sommations de longueurs au carré).

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

Imi
la source
4

Le seul inconvénient auquel je peux penser est quand il s'agit de grands nombres qui débordent lorsqu'ils sont au carré.

Par exemple, en 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!

Il convient également de noter que c'est ce qui se produit lorsque vous utilisez Math.pow () avec exactement les mêmes nombres et que vous retournez à int à partir du double renvoyé par 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!

Est-ce que ça marche? Non , il n'a donné que la bonne réponse car il y*yest fixé à Integer.MAX_VALUEet x*xest inférieur à Integer.MAX_VALUE. Si x*xétait également fixé, Integer.MAX_VALUEvous obtiendriez une réponse incorrecte.

Des principes similaires s'appliquent également aux flotteurs et doubles (sauf qu'ils ont évidemment une plus grande plage avant qu'ils ne débordent) et à tout autre langage qui autorise silencieusement les débordements.

Caspar
la source
La plupart des gens utilisent floats pour les coordonnées, qui ne débordent qu'après 10^38non int.
bobobobo
Mais à 10 ^ 38, vous avez perdu tellement de précision que vous ne pouvez plus vraiment être sûr que vos comparaisons de distance sont valides - le débordement n'est pas le seul problème ici. Voir altdevblogaday.com/2012/02/05/dont-store-that-in-a-float (la section "Tables" résume la perte de précision jusqu'à 1 milliard).
Maximus Minimus
Vous aurez le même problème de débordement avec sqrt (x * x). Je ne vois pas votre point. Il ne s'agit pas de la distance de Manhattan, etc.
bogglez
@bogglez - dépend si votre bibliothèque (ou CPU) est convertie en double ou non.
Maximus Minimus
3

Une fois, je travaillais sur des distances carrées, et j'ai fait l'erreur d' accumuler des distances carrées, pour un compteur kilométrique.

Bien sûr, vous ne pouvez pas faire ça, car mathématiquement,

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

Donc, je me suis retrouvé avec un résultat incorrect là-bas. Oops!

bobobobo
la source
1
Je pourrais également ajouter qu'il y a eu plus d'une fois où j'ai essayé d'utiliser des distances au carré, seulement pour découvrir que j'avais besoin de distances réelles plus tard dans cette même branche de code. Alors, n'en faites pas trop. Parfois, cela ne vaut pas la peine de garder des coefficients carrés partout, quand vous devez quand même finir par faire l' sqrtopération.
bobobobo
3

Vous pouvez rencontrer des problèmes si vous écrivez un algorithme qui nécessite que vous calculiez une position optimisée. Par exemple, supposons que vous disposiez d'un ensemble d'objets et que vous tentiez de calculer la position avec la plus petite distance totale de tous les objets. Juste pour un exemple concret, disons que nous essayons d'alimenter trois bâtiments, et nous voulons déterminer où la centrale électrique devrait aller pour que nous puissions la connecter à tous les bâtiments en utilisant la plus petite longueur totale de fil. En utilisant la métrique de distance au carré, vous vous retrouveriez avec la coordonnée x de la centrale électrique étant la moyenne des coordonnées x de tous les bâtiments (et de manière analogue pour la coordonnée y). En utilisant la métrique de distance ordinaire, la solution serait différente et souvent très éloignée de la solution de distance au carré.

Alexander Gruber
la source
Il semble discutable qui serait meilleur ou pire pour une situation donnée. Je me souviens que les mathématiciens choisissent souvent d'utiliser la distance au carré lorsqu'ils ajustent une ligne à un ensemble de points. Peut-être qu'ils le font parce que cela réduit l'influence des valeurs aberrantes isolées. Dans votre cas à trois bâtiments, les valeurs aberrantes pourraient ne pas être un risque. Ou peut-être qu'ils le font parce qu'il x^2est plus facile de travailler qu'avec |x|.
joeytwiddle
@joeytwiddle Les valeurs aberrantes affectent en fait davantage la régression linéaire avec les ajustements par moindres carrés que la distance absolue. Vous avez raison, il est utilisé parce qu'il est plus facile de travailler avec. Dans l'exemple que j'ai donné (même s'il est modifié pour contenir un grand nombre de bâtiments), la métrique de distance au carré est résolue avec une formule simple (la moyenne arithmétique de chaque coordonnée), mais la métrique de distance absolue est mathématiquement intraitable et doit être résolu approximativement en utilisant l'une des nombreuses méthodes numériques.
Alexander Gruber
Merci pour la correction. Bien sûr, vous avez raison, le carré de la distance génère une erreur plus importante pour les valeurs aberrantes, augmentant leur influence plutôt que de la réduire, comme je l'ai indiqué à tort ci-dessus. C'est fascinant à quel point la solution de la distance la moins absolue est plus difficile à calculer.
joeytwiddle
0

Utiliser la distance au carré est presque toujours très bien et bon pour les performances. Les considérations suivantes sont importantes:

Si vous voulez penser à la somme d'un certain nombre de distances, la distance au carré sera inexacte. Par exemple, j'ai deux distances et je veux m'assurer que leur somme est inférieure à 10. Le code suivant est incorrect:

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

Il ne parvient pas à affirmer dans le cas non valide suivant: a=36et b=49. Dans ce cas, la première longueur est 6 et la seconde 7; leur somme est supérieure à 10, mais la somme des carrés n'est pas supérieure ou égale à 100.

Autre considération: pour les distances à valeur réelle, la distance au carré sera toujours positive. Si vous mesurez le déplacement par exemple, vous devrez peut-être traiter des valeurs négatives, et les élever au carré ne fera pas l'affaire.

Expiation limitée
la source