Наименьшее расстояние между точками на карте с тороидальной (x- и y-оберткой)?

Question

У меня есть евклидова карта тороидального затвора. То есть поверхность представляет собой плоский евклидов прямоугольник, но когда точка переместится к правой границе, она появится на левой границе (с тем же значением y), определяемой как x_new = x_old% width

В основном, точки строятся на основе: * см. Редактирование

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

Think Pac Man - если вы выйдете за один край экрана, вы окажетесь на противоположном краю.

Как лучше всего рассчитать кратчайшее расстояние между двумя точками? Типичная реализация предполагает большое расстояние для точек в противоположных углах карты, когда в действительности реальное расстояние в скобках очень близко.

Лучший способ, которым я могу придумать, - это вычисление Классической Дельты X и Обернутой Дельты X, и Классической Дельты Y и Обернутой Дельты Y, и используя нижнюю из каждой пары в формуле расстояния Sqrt (x ^ 2 + y ^ 2) .

Но это потребовало бы многих проверок, вычислений, операций - некоторые из них, я считаю, могут быть излишними.

Есть ли лучший способ?

---

1020 * редактировать *

Когда объект перемещается, он перемещается в позицию (x_old, y_old), проходит через вышеуказанную формулу и сохраняет (x_new, y_new) в качестве своей позиции. Приведенная выше формула была добавлена ​​только для пояснения того, что происходит, когда объекты перемещаются через границу; в действительности только одна (x, y) пара хранится в каждом объекте одновременно.

Answer 1

Лучший способ, который я могу придумать, - это вычисление Классической Дельты X и Обернутой Дельты X, и Классической Дельты Y и Обернутой Дельты Y, и использование нижней части каждой пары в Sqrt (x ^ 2 + y ^ 2) формула расстояния.

Вот и все, я не думаю, что есть более быстрый путь.Но это не слишком сложно для вычисления;Вы могли бы сделать что-то вроде

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

(я надеюсь, что вы можете перевести это на предпочитаемый вами язык)

Answer 2

Кратчайшее расстояние между двумя точками в периодической области может быть вычислено следующим образом без использования петель.

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

Это даст кратчайшее расстояние со знаком.ANINT является встроенной функцией ФОРТРАНА, так что ANINT (x) дает ближайшее целое число, у которого величина меньше abs (x) +0.5, с тем же знаком, что и x.Например, ANINT (0,51) = 1,0, ANINT (-0,51) = - 1,0 и т. Д. Аналогичные функции существуют для других языков.

Answer 3

Найти наименьшую дельту в оси a для новых координат со значениями a1 и a2, где aBoundary - граница на оси a:

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

Итак, если у вас есть две точки с новыми координатами x1,y1 и x2,y2, вы можете просто сделать:

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

Это то, что вы предлагаете, но я бы не сказал, что это "много проверок"., расчеты и операции ".

Answer 4

Чувак, я сделал что-то другое ...

здесь есть небольшая дополнительная функциональность, но ядро ​​- это расстояние на завернутом экране ...

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

Answer 5

Вы не можете использовать функцию «abs» с оператором мод!

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

Answer 6

Никакое расстояние не может быть больше, чем ширина / 2 и высота / 2.Если вы получите разницу (X1-X2) больше, чем ширина / 2, вычтите ширину / 2, чтобы получить расстояние сокращения.Затем рассчитайте расстояние как обычно.

Answer 7

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