CODEWITHSUNDEEP
mathimage-processinggeometry
Alphaneo
Alphaneo

Reputation: 12539

Rough computation of distance between 2 points

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 ...

Upvotes: 5

Views: 7781

Answers (7)

Dr. belisarius
Dr. belisarius

Reputation: 61016

Graphical representation of three usual distances:

enter image description here

(Note: this represents a circle of radius 4 in these three metrics.)

Upvotes: 14

Ptolemy2002
Ptolemy2002

Reputation: 145

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;
        }

Upvotes: 0

Gangnus
Gangnus

Reputation: 24464

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?

Upvotes: 1

mtrw
mtrw

Reputation: 35088

Your distance metric is fine for rough distance. But (x2 - x1)2 + (y2 - y1)2 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.

Upvotes: 1

Algorithmist
Algorithmist

Reputation: 6695

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: enter image description here

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.

Upvotes: 2

Beno
Beno

Reputation: 4753

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 )

Upvotes: 3

Martin Booth
Martin Booth

Reputation: 8595

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)

Upvotes: 12

Related Questions