Distanza più breve tra i punti su una mappa con avvolgimento toroidale (avvolgimento x e y)?

Question

Ho una mappa euclidea toroidale. Quella è la superficie è un rettangolo piatto euclideo, ma quando un punto si sposta verso il limite destro, apparirà al limite sinistro (con lo stesso valore y), dato da x_new = x_old% larghezza

Fondamentalmente, punti sono tracciati in base a: * vedere Modificare

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

Pensate Pac Man - a piedi fuori un bordo dello schermo vi farà apparire sul bordo opposto.

Qual è il modo migliore per calcolare la distanza più breve tra due punti? L'implementazione tipica suggerisce una grande distanza per i punti sugli angoli opposti della mappa, quando in realtà, la distanza reale avvolta è molto vicina.

Il modo migliore che riesco a pensare è calcolare Delta Delta classico e Delta X avvolto, Delta classico Y e Delta avvolto Y, e utilizzare il più basso di ogni coppia nella distanza Sqrt (x^2 + y^2) formula.

Ma ciò implicherebbe molti controlli, calcoli, operazioni, alcune che ritengo potrebbero non essere necessarie.

C'è un modo migliore?

---

modifica

Quando un oggetto si muove, si muove alla posizione (x_old, y_old), convoglia attraverso la formula di cui sopra, e memorizza (x_new, y_new) come la sua posizione. La formula sopra è stata aggiunta solo per chiarire cosa succede quando gli oggetti si muovono attraverso il confine; in realtà, solo una coppia (x, y) è memorizzata in ogni oggetto alla volta.

Answer 1

Il modo migliore che posso pensare sta calcolando classica Delta X e avvolto Delta X, Classico e Delta Y e avvolto Delta Y, e con il più basso di ciascuna coppia nel sqrt (x^2 + y^2) formula della distanza.

Ecco, non credo ci sia un modo più rapido. Ma non è troppo difficile da calcolare; si potrebbe fare qualcosa di simile

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

(Mi fido di te può tradurre che nella vostra lingua preferita)

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

Nessuna distanza può essere maggiore di larghezza/2 e l'altezza/2. Se ottieni una differenza (X1-X2) maggiore di larghezza/2, sottragga larghezza/2 per ottenere la distanza di scorciatoia. Calcola quindi la distanza come al solito.

Answer 4

Per trovare il più piccolo delta del a -axis per nuove coordinate con valori a1 e a2, dove aBoundary è il confine sul a -axis:

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

Quindi, se avete due punti con nuove coordinate x1,y1 e x2,y2, si può solo fare:

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

Questo è effettivamente quello che suggeriscono, ma non direi è "molti controlli, calcoli e operazioni".

Answer 5

non è possibile utilizzare la funzione "abs" con l'operatore mod!

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

Answer 6

La distanza più breve tra due punti in un dominio periodico può essere calcolata come segue senza utilizzare alcun anello.

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

Questo darà una distanza minima segnalata. ANINT è una funzione FORTRAN intrinseca tale che ANINT (x) restituisce il numero intero più vicino la cui grandezza è minore di abs (x) +0,5, con lo stesso segno di x. Ad esempio, ANINT (0.51) = 1.0, ANINT (-0.51) = - 1.0, ecc. Esistono funzioni simili per altre lingue.

Answer 7

uomo ho fatto qualcosa modo diverso ...

c'è un po 'più in fuctionality qui, ma il nucleo è la distanza su uno schermo avvolto ...

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