¿Distancia más corta entre puntos en un mapa envuelto toroidalmente (x e y)?

Question

Tengo un mapa euclidiano toroidal-ish. Esa es la superficie es un rectángulo euclidiano plano, pero cuando un punto se mueve al límite derecho, aparecerá en el límite izquierdo (con el mismo valor y), dado por x_new = x_old% ancho

Básicamente, señala se trazan en función de: * ver editar

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

Piense Pac Man - caminar fuera de uno de los bordes de la pantalla hará que usted aparece en el borde opuesto.

¿Cuál es la mejor manera de calcular la distancia más corta entre dos puntos? La implementación típica sugiere una gran distancia para los puntos en las esquinas opuestas del mapa, cuando en realidad, la distancia real envuelta está muy cerca.

Lo mejor que puedo pensar es calcular Delta X clásico y Delta X envuelto, y Delta clásico Y y Y envuelto, y usar el más bajo de cada par en la distancia Sqrt (x^2 + y^2) fórmula.

Pero eso implicaría muchos controles, cálculos, operaciones, algunas que creo que podrían ser innecesarias.

¿Hay una manera mejor?

---

editar

Cuando un objeto se mueve, se mueve a la posición (x_old, y_old), corre a través de la fórmula anterior, y almacena (x_new, y_new) como su posición. La fórmula anterior solo se agregó para aclarar qué sucede cuando los objetos se mueven a través del límite; en realidad, solo se almacena un par (x, y) en cada objeto a la vez.

Answer 1

La mejor manera que puedo pensar es el cálculo de Delta Classical X y envuelto Delta X, y Delta Classical Y y envuelta Delta Y, y usando la inferior de cada par en el sqrt (x^2 + y^2) fórmula de distancia.

Eso es, no creo que haya una manera más rápida. Pero no es demasiado difícil de un cálculo; usted podría hacer algo como

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

(Confío en que puede traducir eso en su idioma preferido)

Answer 2

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

No hay distancia puede ser mayor que el ancho/2 y la altura/2. Si obtiene una diferencia (X1-X2) mayor que la anchura/2, resta ancho/2 para obtener la distancia de acceso directo. Calcule la distancia entonces como de costumbre.

Answer 4

Para encontrar el delta más pequeño en el eje x a para las nuevas coordenadas con valores a1 y a2, donde aBoundary es el límite en el eje x a:

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

Así que si usted tiene dos puntos con nuevas coordenadas x1,y1 y x2,y2, sólo puede hacer:

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

Esto es efectivamente lo que usted sugiere, pero yo no diría son "muchos controles, cálculos y operaciones".

Answer 5

no puede usar la función "abs" con el operador de mod.

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

Answer 6

La distancia más corta entre dos puntos en un dominio periódico se puede calcular de la siguiente manera sin utilizar ningún bucle.

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

Esto dará una distancia mínima registrada. ANINT es una función intrínseca de FORTRAN tal que ANINT (x) proporciona el número entero más cercano cuya magnitud es menor que abs (x) +0.5, con el mismo signo que x. Por ejemplo, ANINT (0.51) = 1.0, ANINT (-0.51) = - 1.0, etc. Existen funciones similares para otros lenguajes.

Answer 7

hombre hice algo diferente ... MANERA

hay un pequeño extra en fuctionality aquí, pero el núcleo es la distancia en una pantalla envuelta ...

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