Calculate distance between two points N,W,E,S

Question

Ok so i am stuck at this: I need to calculate distance between $2$ points...

For example: I have $30\times 30$ square and point$1$ is at $X4,Y5$ and point$2$ is at $X30,Y23$ now I need to get the shortest distance from point$1$ to point$2$. By wich way is the shortest North, East, West, South...

I know i have to do that by "pythagorean theorem" but problem is if point$1$ is $(X4,Y5)$ and point$2$ is $(X28,Y6)$ for example... now the shortest way would be to go East and then you come to the right side out and just go one squeare to South. And the shortest distance would be ($5$)squares.

I don't know exactly to say what i need, but you will probably see on image2 on the link!

Here is an example of $30\times 30$ and here is a full image of what i am talking about

ADDED MORE EXAMPLES:

Here would the shortest be (6).

Here would the shortest be (3).

Here would the shortest be (21).

Here would the shortest be (5, something).

Here would the shortest be (4).

Thank you for any help people! :)

Answer 1

What you're looking for is not the Euclidean distance, calculated using the Pythagorean theorem (which is good for an infinitely extending plane with a continuum of points (and a few other restrictions)), but instead, as mentioned, the taxicab or Manhattan distance, with the additional restriction that it is on a finite set of points that 'wrap around' (are on a torus).

The Manhattan distance between two points is just

$$d( p_1, p_2 ) = |x_1 - x_2| + |y_1 - y_2|. $$

(if $p_1 = (x_1,y_1)$ and $p_2 = (x_2, y_2)$).

This is the sum of the differences in each of the coordinates - the absolute value is just to make sure it doesn't matter which point you start with.

The above works if you have an infinite plane. For the additional constraint that you really have a finite area (it is on a torus) to account for the fact that it may be shorter to go South rather than North or East instead of West, take the min of all possible directions you could go, East/West, and North/South both mod the width/height of the bounded plane. So the better distance function uses that above and tries the minimum in two directions for each coordinate:

$$\begin{eqnarray} d_t(p_1, p_2) = \min(&&d(p_1, p_2) ,\\ && d((x_1+30, y_1),p_2),\\ && d((x_1, y_1+30),p_2),\\ && d((x_1+30, y_1+30),p_2)). \end{eqnarray}$$

These four possibilities are displayed in your image and the above is just taking the smallest one.

Note that this latter calculation will work on a torus also for the Euclidean or other distance measures.

Answer 2

If I understand correctly, you are interested in the distances computed by only moving along horizontal and vertical directions, and not diagonally. Is that right?

Next, you are assuming your square is actually the surface of a torus, so that by "going out" of the right side you re-enter from the left one and so on. Is that right too?

If both are true, then the answer to your question is pretty simple. First of all, consider the case when the two points are on a same row, one of them in column X and the other in column X'. Then their distance is the minimum between |X-X'| (where || denote the modulus, or absolute value) and 30-|X-X'| (of course in the case when the width of the square is different from 30, the new value has to be substituted). If the shortest way is "moving within" the square, the minimum is |X-X'|, while if it is shortest to take a shortcut through the sides, then 30-|X-X'| is the distance.

When the points are on different rows, you have just to add this "horizontal" distance to the "vertical" distance, computed in the same way, but using the Y-coordinates.

Hope this helps!