Calculate distance between two x/y coordinates?

Question

I would like to calculate the distance between two x/y coordinates on the surface of a torus. So, this is a normal grid that has the property that its corners and sides are 'connected'. For example, on a grid of 500x500, the point at (499, 499) is adjacent to (0, 0) and the distance between e.g. (0,0) and (0,495) should then be 5.

Is there any good mathematical way of calculating this?

Answer 1

So you are looking for the Euclidean distance on the two-dimensional surface of a torus, I gather.

sqrt(min(|x1 - x2|, w - |x1 - x2|)^2 + min(|y1 - y2|, h - |y1 - y2|)^2) 

where w and h are the width (x) and height (y) of the grid, respectively.

Answer 2

• If/while the distance between x coordinates is larger than half of the grid X size, add grid X size to the smaller x coordinate.
• Do the same for Y.
• Then calculate the distance.

Answer 3

If your grid wraps around at the edges, there will be four distances between each coordinate (for 2 dimensions). I'm assuming you want to know the shortest distance.

Let's use a smaller grid, the numbers are a bit more manageable. Say the grid is 10x10. Let's also use just one dimension for simplicity (in which case there'll be just two distances), just as you have in your example. Say we have the points 0,2 and 0,6. The two distances between the points are d_1 = (6-2) = 4 and d_2 = (10-6) + 2 = 6, so in this case the shortest distance would be d_1.

In general, you can do the following:

• For each coordinate:
  • subtract the smaller from the larger number
  • if the result is greater than half the width of the grid the shortest distance in this coordinate is the grid width minus the result
  • if the result is less than half the width of the grid, the shortest distance in this coordinate is the result

Then using Pythagoras' theorem, the shortest distance between the two points is the square root of the sum of the squares of the shortest distances in each direction. You can calculate the other three distances by calculating Pythagoras' theorem using the other combinations of distances in each direction.

As another poster has said, the shape formed when you wrap round at the edges (for a 2 dimensional grid) is a torus and I think the method I've used above is the same as the equation given but has the advantage that it can be extended to n-dimensions if required. Unfortunately there's not really an easy visualisation above 2 dimensions.