环绕式（x和y方向上的环绕）地图上两点之间的最短距离是多少？

Question

我有一个类似于环形的欧几里得式地图。也就是说，这个表面是一个平坦的欧几里得矩形，但当一个点移动到右边界时，它将出现在左边界（在相同的y值处），用公式表示为x_new = x_old % width。

基本上，根据以下方式绘制了点：*请查看修改

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

想象一下吃豆人游戏 -- 走到屏幕的一侧会出现在另一侧。

最佳方法是计算经典变化量X和环绕变化量X，以及经典变化量Y和环绕变化量Y，并使用每对中较小的数值在Sqrt（x^2+y^2）距离公式中进行计算。

但这将涉及许多检查、计算和操作 -- 其中一些可能是不必要的。

是否有更好的方法？

---

编辑

当对象移动时，它移动到位置（x_old，y_old），运行上述公式，并将（x_new，y_new）存储为其位置。上述公式仅用于澄清对象越过边界时会发生什么事情；实际上，每个对象一次仅存储一个（x，y）对。

- Justin L.

---

你的几何形状和《小行星》游戏中的一样吗？http://en.wikipedia.org/wiki/Asteroids_(video_game) - Eric J.

顺便说一下，在物理术语中，我们会说你正在使用二维周期边界条件。实际上，它等同于（我认为是同构的）一个环面的表面。 - David Z

Answer 1

我能想到的最好方法是计算经典Delta X和包裹Delta X，以及经典Delta Y和包裹Delta Y，然后在Sqrt(x^2+y^2)距离公式中使用每对值中的较小值。

就这样，我认为没有更快的方式了。但这并不是很难的计算；你可以做一些类似于

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

(我相信你可以将其翻译成你偏好的语言)

- David Z

---

哈哈，同一秒钟，同一想法 :) - zerm

这里有很多好点子，但这一个是最先想到的。我喜欢你可以快速比较宽度的一半而不是计算两个增量的方式。谢谢！ - Justin L.

Answer 2

在周期性域中，两点之间的最短距离可以通过以下方式计算，而无需使用任何循环。

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

这将提供一个带符号的最短距离。ANINT是一种FORTRAN内置函数，它会返回最接近整数的值，其大小小于abs(x)+0.5，与x相同的符号。例如，ANINT(0.51)=1.0，ANINT(-0.51)=-1.0等。其他语言中也存在类似的函数。

- GreenEye

---

不错的解决方案，但在某些情况下需要取结果的绝对值以避免出现负数答案。 - ClimateUnboxed

Answer 3

为找到新坐标系中值为a1和a2的最小a轴差距，其中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))

这实际上就是你所建议的，但我不会说它涉及到“许多检查、计算和操作”。

- namin

---

就目前而言，那个 delta 函数似乎只适用于 a1>a2 的情况。当 a1<a2 时，aBoundary 上的符号必须翻转。将第二个 min 参数更改为：abs(abs(a2 - a1) - aBoundary)，以涵盖这两种情况。 - Maple

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

- Matt O'Neill

---

如果您解释一下如何计算距离以及为什么这是一个好的方法（因为OP正在寻求“最佳方法”），那么您的答案将更有用。仅仅放置一大段代码而没有解释通常被认为是质量较差的答案。 - devlin carnate

好观点。我是在对比别人的解决方案与我的解决方案的优雅程度时做出反应的。我的做法是给定两个点，我想知道从第一个点到第二个点最快的路线以及如何到达那里。关键不是找出哪个点最近，而是以一种返回该点“坐标”的方式来完成。我将该点投影到屏幕每个方向1/2大小的缓冲区中，然后计算到每个点的距离并返回最短的距离。然后我创建了一条路径来移动我的初始点以到达它。 - Matt O'Neill

Answer 5

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

- MSN

---

你是否意识到 abs(x_old - x_new) 等同于 abs(x_new - x_old)？ - namin

Answer 6

任何距离都不可能大于宽度/2和高度/2。如果你得到一个（X1-X2）大于宽度/2的差异，那么减去宽度/2就可以得到最短距离。然后像往常一样计算距离。

- zerm

---

实际上，您希望从宽度中减去吗？例如，如果X1-X2 == 0.55宽度，则应该得到0.45宽度。 - David Z

你猜得对。不过你也可以减去整个宽度，无论如何。 - zerm

Answer 7

你不能在模运算符中使用“abs”函数！

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

- Waleed A.K.