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

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 dis开发者_JS百科tance 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.

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 - dx;
// again with x -> y and width -> height

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

The shortest distance between two points in a periodic domain can be computed as follows without using any loops.

    dx = x2-x1
    dx = dx - x_width*ANINT(dx/x_width)

This will give a signed shortest distance. ANINT is an intrinsic FORTRAN function such that ANINT(x) gives the nearest whole number whose magnitude is less than abs(x)+0.5, with the same sign as x. For eg., ANINT(0.51)=1.0 , ANINT(-0.51)=-1.0 , etc. Similar functions exist for other languages.

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

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.

(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)))

Man I did something WAY different...

there's a little extra fuctionality in here but the core is the distance on a wrapped screen...

from math import sqrt
import pytweening

class ClosestPoint_WD(object):
def __init__(self, screen_size, point_from, point_to):
    self._width = screen_size[0]
    self._height = screen_size[1]
    self._point_from = point_from
    self._point_to = point_to
    self._points = {}
    self._path = []

def __str__(self):
    value = "The dictionary:" + '\n'
    for point in self._points:
        value = value + str(point) + ":" + str(self._points[point]) + '\n'

    return value

def distance(self, pos0, pos1):
    dx = pos1[0] - pos0[0]
    dy = pos1[1] - pos0[1]
    dz = sqrt(dx**2 + dy**2)

    return dz

def add_point_to_dict(self, x, y):
    point = x, y
    self._points[point] = 0

def gen_points(self):
    max_x = self._width * 1.5 - 1
    max_y = self._height * 1.5 - 1

    # point 1, original point
    self.add_point_to_dict(self._point_to[0], self._point_to[1])

    # add the second point: x-shifted
    if self._point_to[0] + self._width <= max_x:
        self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1])
    else:
        self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1])

    # add the third point: y-shifted
    if self._point_to[1] + self._height <= max_y:
        self.add_point_to_dict(self._point_to[0], self._point_to[1] + self._height)
    else:
        self.add_point_to_dict(self._point_to[0], self._point_to[1] - self._height)

    # add the fourth point: diagonally shifted
    if self._point_to[0] + self._width <= max_x:
        if self._point_to[1] + self._height <= max_y:
            self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] + self._height)
        else:
            self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] - self._height)
    else:
        if self._point_to[1] + self._height <= max_y:
            self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] + self._height)
        else:
            self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] - self._height)

def calc_point_distances(self):
    for point in self._points:
        self._points[point] = self.distance(self._point_from, point)

def closest_point(self):
    d = self._points
    return min(d, key=d.get)

def update(self, cur_pos, target):
    self._point_from = cur_pos
    self._point_to = target
    self._points = {}
    self.gen_points()
    self.calc_point_distances()
    self.shortest_path()

def shortest_path(self):
    path = pytweening.getLine(self._point_from[0], self._point_from[1], self.closest_point()[0], self.closest_point()[1])
    #path = pytweening.getLine((self._point_from)
    ret_path = []

    for point in path:
        ret_path.append((point[0] % self._width, point[1] % self._height))

    self._path = ret_path
    return self._path

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)