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?
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
Of course the squared length scales quite differently than the Euclidean distance and is therefore a bad candidate for things like pathfinding heuristics.
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
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
x*x is less than
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.
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
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,
So, I ended up with an incorrect result there. Oops!
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.
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:
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.