I understand the difference between Euclidian, Manhattan and Chebyshev distances.

My question is:

How to calculate a distance metric from point1 to point2 on a grid including diagonals given that orthogonal adjacent cell distance is 1, and diagonal adjacent cell distance is sqrt(2).

I understand how to write a code for that. I guess it is the least cost path on Moore neighbourhood (where cost of a step is Euclidian distance of the step).

But is there a way to calculate a general equation?

  • 1
    $\begingroup$ Does this make sense? d=min(|x1-x2|,|y1-y2|)*sqrt(2)+| |x1-x2| - |y1-y2| | $\endgroup$ – Lizardie Aug 18 '15 at 8:26

Suppose point 1 is the origin $(0,0)$ and point 2 is $(p,q)$. Suppose for simplicity that $p \geq q \geq 0$.

Then the shortest path is achieved by first moving diagonally $\min (p,q) = q$ steps, which will lead to location $(q,q)$ and then move $p-q$ steps to the goal. This gives the distance $q\sqrt{2} + (p-q)$.

Note that the order in which the steps are taken does not matter.

Note that if you replace any diagonal step by one step in $x$ and one step in $y$ direction, the path lengthens. This is a partial explanation for why this is a shortest path. The other part is figuring out that there is no benefit in moving farther from the target - you always want to approach it.

On the assumptions

The assumptions are not particularly restrictive. Since the problem is translation invariant, you can translate it so that the initial point is the origin. You can also rotate the problem by any multiple of $\pi/2$ (90 degrees), therefore making $p,q \geq 0$. By symmetry the distance to $(p,q)$ and $(q,p)$ from origin is the same, so you can assume $q \leq p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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