Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 31 down vote accepted

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.

share|improve this answer
13  
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. –  John Calsbeek Feb 11 '12 at 11:48
    
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 –  Aralox Feb 11 '12 at 13:04
1  
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. –  Jonathan Dickinson Feb 18 '12 at 10:35
2  
In the case of A* you're not merely comparing distances, but adding them, so skipping the sqrt does make a difference. –  amitp Feb 19 '12 at 17:49
1  
@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. –  John Calsbeek Mar 13 '13 at 0:33
show 1 more comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
Thanks for the very valid point! –  Aralox Feb 17 '12 at 9:23
    
Most people use floats for coordinates, which only overflow after about 10^38 not int. –  bobobobo Mar 11 '13 at 20:31
    
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). –  Jimmy Shelter Mar 12 '13 at 1:32
add comment

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!

share|improve this answer
    
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. –  bobobobo Mar 12 '13 at 23:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.