Rough computation of distance between 2 points

Question

I want to calculate the rough (approximate) distance between two points to reduce the computation overhead.

I am using the following formula for the distance between (x1, y1) & (x2, y2):

Dist = Mod (x1 - x2) + Mod (y1 - y2)

Where Mod is the Modulus operator such that Mod(x) = |X|.

This seems to be working.

I want to know, if I have missed out something ...

Answer 1

As long as you're getting the absolute value (like you stated |X|) and not using the modulus function then that will give you the manhattan distance between the two points

If that is what you want, then you've not missed anything

If you want the straight line distance use the pythagorean theorem. This is sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)

Answer 2

Your distance metric is fine for rough distance. But (x₂ - x₁)² + (y₂ - y₁)² will give you the square of the actual distance. As long as you keep in mind that it's the square of the distance, this will be more accurate. And depending on the architecture you're implementing this on, it might be faster - the multiply might take less time than the branch in the modulus, or for hardware implementations might well take the same time. You will need to benchmark to be sure.

Answer 3

I made this algorithm to calculate the straight line distance between 2 points:

var distance = function(x1, y1, x2, y2) {
            //Distance Horizantally
            var horizontalDistance = 0;
            /Distance Vertically
            var verticalDistance = 0;
            
            if(x1 > x2) {
                horizantalDistance = x1 - x2;
            }
            else {
                horizantalDistance = x2 - x1;
            }
            
            if(y1 > y2) {
                verticalDistance = y1 - y2;
            }
            else {
                verticalDistance = y2 - y1;
            }

            var answer = 0;
            
            if(verticalDistance !== 0 && horizantalDistance !== 0) {
                //Use the Pathagoreum Theorum
                answer = Math.sqrt(verticalDistance + horizantalDistance);
            }
            else if(horizantalDistance === 0) {
                //Use the Vertical Distance
                answer = verticalDistance;
            }
            else if (verticalDistance === 0) {
                //Use the Horizantal distance
                answer = horizantalDistance;
            }
            //Return the answer
            return answer;
        }

Answer 4

are you sure you have the Modulus operator correct? It looks like you are use MOD as ABSOLUTE

http://en.wikipedia.org/wiki/Modulo_operation

anyway, as Mehrdad says, using the pythagorean theorum:

Dist = Sqrt( (x1-x2)^2 + (y1-y2)^2 )

Answer 5

If you wish to compare distances and save time, use not the distance itself, but its square: (x1-x2)^2 + (y1-y2)^2. Don't take sqrt. So, your distances will work exactly as normal ones, but quickly. Counting dx=x1-x2 and dx2=dx*dx is even faster than taking ABS(you meant it, not MOD really), because the last is a function and you have to pay for it.

ABS distance is a correct one - in theory. But what is the use of it, if it is rough for your targets?

Answer 6

You have to be specific in terms of distance that you want to calculate.

Distance Formula: Given the two points (x1, y1) and (x2, y2), the distance between these points is given by the formula:

This is the standard formula that we use in Co-Ordinate geometry to find the distance between points and is specialization of MinKowski distance for One Dimension.