Shortest distance between points on a toroidally wrapped (x- and y- wrapping) map?

Question

I have a toroidal-ish Euclidean-ish map. That is the surface is a flat, Euclidean rectangle, but when a point moves to the right boundary, it will appear at the left boundary (at the same y value), given by x_new = x_old % width

Basically, points are plotted based on: * see edit

(x_new, y_new) = ( x_old % width, y_old % height)

Think Pac Man -- walking off one edge of the screen will make you appear on the opposite edge.

What's the best way to calculate the shortest distance between two points? The typical implementation suggests a large distance for points on opposite corners of the map, when in reality, the real wrapped distance is very close.

The best way I can think of is calculating Classical Delta X and Wrapped Delta X, and Classical Delta Y and Wrapped Delta Y, and using the lower of each pair in the Sqrt(x^2+y^2) distance formula.

But that would involve many checks, calculations, operations -- some that I feel might be unnecessary.

Is there a better way?

---

edit

When an object moves, it moves to position (x_old,y_old), runs it through the above formula, and stores (x_new, y_new) as its position. The above formula was only added to clarify what happens when objects move across the boundary; in reality, only one (x,y) pair is stored in each object at a time.

Answer 1

(delta_x, delta_y)= 
     (min(width - abs(x_new - x_new), abs(x_new - x_old)), 
      min(height - abs(y_new - y_old), abs(y_new - y_old)))

Answer 2

The best way I can think of is calculating Classical Delta X and Wrapped Delta X, and Classical Delta Y and Wrapped Delta Y, and using the lower of each pair in the Sqrt(x^2+y^2) distance formula.

That's it, I don't think there is any quicker way. But it's not too hard of a computation; you could do something like

dx = abs(x1 - x2);
if (dx > width/2)
  dx = width/2 - dx;
// again with x -> y and width -> height

(I trust you can translate that into your preferred language)

Answer 3

No distance can be greater than width/2 and height/2. If you get a difference (X1-X2) greater than width/2, substract width/2 to get the short-cut distance. Calculate distance then as usual.

Answer 4

To find the smallest delta in the a-axis for new coordinates with values a1 and a2, where aBoundaryis the boundary on the a-axis:

def delta(a1, a2, aBoundary):
  return min(abs(a2 - a1), abs(a2 + aBoundary - a1))

So if you have two points with new coordinates x1,y1 and x2,y2, you can just do:

sumOfSquares(delta(x1,x2,width), delta(y1,y2,height))

This is effectively what you suggest, but I wouldn't say it's "many checks, calculations and operations".

Answer 5

you can't use the “abs” function with the mod operator!

xd =(x1-x2+Width)%Width
yd=(y1-y2+Height)%Height
D=sqrt(xd^2+yd^2)