32
\$\begingroup\$

I use distance squared checks for basically all my distance (vector3 length) checking, due to the performance increase from not incurring a square root (like in plain length checks).

From the looks of it, squared distance checks work fine in every situation:

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

I am not considering situations where x or y is less than 0, as distance and distance-squared is always going to be positive.

Since this works, it looks like distance checks are never ever needed, but I have a nagging feeling that i'm missing something. Will this still hold up in accuracy-critical situations?

\$\endgroup\$

6 Answers 6

44
\$\begingroup\$

There's no disadvantage I'm aware of when using squared length to compare distances. Think about it like that: You're just skipping the sqrt which doesn't give you any additional accuracy. If you don't need the actual Euclidean distance, then you can safely leave the sqrt out.

Of course the squared length scales quite differently than the Euclidean distance and is therefore a bad candidate for things like pathfinding heuristics.

\$\endgroup\$
7
  • 17
    \$\begingroup\$ The square root actually removes accuracy from the distance check. You can think of it as an attempt to take the square root of a fixed point number between 1 and 2 and storing the result (between 1 and sqrt(2)) in exactly the same range. Some distances that compare as x^2 < y^2 will compare as x = y after you take the square root. The squared length check is both faster and more accurate. \$\endgroup\$ Feb 11, 2012 at 11:48
  • \$\begingroup\$ Thank you for your excellent answers bummzack and John Calsbeek! Your responses combined perfectly answers my question. I did not consider the additional memory space from not using a square root, really nice pickup there. And that heuristics link makes for a great read \$\endgroup\$
    – Aralox
    Feb 11, 2012 at 13:04
  • 1
    \$\begingroup\$ Except in the case of A*. I recall reading an article that described the tested of different heuristics and d^2 performed horrible. In A* |dx| + |dy| works nicely. I don't have the link as I read a month or so back. \$\endgroup\$ Feb 18, 2012 at 10:35
  • 3
    \$\begingroup\$ In the case of A* you're not merely comparing distances, but adding them, so skipping the sqrt does make a difference. \$\endgroup\$
    – amitp
    Feb 19, 2012 at 17:49
  • 1
    \$\begingroup\$ @bobobobo I agree; I mostly made it to shoot down a potential argument in the other direction, i.e. the normal distance somehow being more accurate. \$\endgroup\$ Mar 13, 2013 at 0:33
14
\$\begingroup\$

As bummzack hinted with the Path-finding analogy, you NEED to use the "normal" length every time you add distances together and want to compare their sum. (Just because summs of squares of lengths are different from squared summs of lengths).

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

\$\endgroup\$
0
4
\$\begingroup\$

The only disadvantage I can think of is when dealing with large numbers which will overflow when squared.

For example, in 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!

Also worth noting that is what happens when you use Math.pow() with the exact same numbers and cast back to int from the double returned from 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!

Is it working? No, it only gave the correct answer because y*y is clamped to Integer.MAX_VALUE, and x*x is less than Integer.MAX_VALUE. If x*x was also clamped to Integer.MAX_VALUE then you would get an incorrect answer.

Similar principles also apply with floats & doubles (except they obviously have a greater range before they overflow) and any other language which silently allows overflows.

\$\endgroup\$
4
  • \$\begingroup\$ Most people use floats for coordinates, which only overflow after about 10^38 not int. \$\endgroup\$
    – bobobobo
    Mar 11, 2013 at 20:31
  • \$\begingroup\$ But at 10^38 you've lost so much precision that you really can't be sure that your distance comparisons are valid any more - overflow isn't the only problem here. See altdevblogaday.com/2012/02/05/dont-store-that-in-a-float (the "Tables" section summarises precision loss up to 1 billion). \$\endgroup\$ Mar 12, 2013 at 1:32
  • 1
    \$\begingroup\$ You will have the same overflow problem with sqrt(x*x). I don't see your point. This is not about Manhattan distance etc. \$\endgroup\$
    – bogglez
    Aug 4, 2014 at 11:10
  • \$\begingroup\$ @bogglez - depends if your library (or CPU) up-casts to double or not. \$\endgroup\$ Oct 11, 2018 at 14:01
3
\$\begingroup\$

One time I was working in square distances, and made the mistake of accumulating squared distances, for an odometer count.

Of course, you can't do this, because mathematically,

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

So, I ended up with an incorrect result there. Oops!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Also I might add that there have been more than a few times where I tried using squared distances, only to find I needed actual distances later in that same branch of code. So, don't overdo it. Sometimes it's not worth the inconvenience of keeping squared coefficients everywhere, when you need to end up doing the sqrt operation anyway. \$\endgroup\$
    – bobobobo
    Mar 12, 2013 at 23:46
3
\$\begingroup\$

You may run into trouble if you're writing an algorithm which requires that you compute an optimized position. For example, let's say you had a set of objects, and you were trying to compute the position with the smallest total distance from all of the objects. Just for a concrete example, say we're trying to power three buildings, and we want to figure out where the power plant should go so that we can connect it to all the buildings using the smallest total length of wire. Using the distance squared metric, you would end up with the x-coordinate of the power plant being the average of the x-coordinates of all the buildings (and analogously for the y-coordinate). Using the ordinary distance metric, the solution would be different, and often very far off from the distance squared solution.

\$\endgroup\$
3
  • \$\begingroup\$ It seems arguable which would be better or worse for a given situation. I recall that mathematicians often choose to use distance-squared when fitting a line to a set of points. Perhaps they do that because it reduces the influence of lone outliers. In your three-building case, outliers might not be a risk. Or perhaps they do it because x^2 is easier to work with than |x|. \$\endgroup\$ Dec 1, 2015 at 10:55
  • \$\begingroup\$ @joeytwiddle Outliers actually affect linear regression more with least squares fits than absolute distance. You're right that it's used because it's easier to work with. In the example I gave (even if it is modified to contain a large number of buildings), the distance squared metric is solved with a simple formula (the arithmetic average of each coordinate), but the absolute distance metric is mathematically intractable and must be solved approximately using one of a number of numerical methods. \$\endgroup\$ Dec 3, 2015 at 2:49
  • \$\begingroup\$ Thanks for the correction. Of course you are right, the square of the distance generates a larger error for outliers, increasing their influence rather than reducing it, as I incorrectly stated above. That is fascinating how much more difficult the least-absolute-distance solution is to compute. \$\endgroup\$ Dec 3, 2015 at 3:09
1
\$\begingroup\$

Using distance squared is almost always just fine and good for performance. The following considerations are important:

If you want to think about the sum of a number of distances, distance squared will be inaccurate. For instance, I have two distances and I want to make sure their sum is less than 10. The following code is incorrect:

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

It fails to assert in the following invalid case: a=36 and b=49. In this case, the first length is 6 and the second 7; their sum is greater than 10, but the sum of the squares is not 100 or greater.

Another consideration: for real-valued distances, distance squared will always be positive. If you're measuring displacement for instance, you may need to deal with negative values, and squaring them will not do.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .