如何有效地计算环形空间中的距离？

Question

我有一个640×480大小的游戏窗口，它由粒子填充，但是当一个粒子移到一边时，它会绕到另一边（也就是说，它是一个圆环体）。在

我想计算每个粒子之间的距离，因为这将用于对每个粒子施加不同的力。在

一开始我循环遍历每一对粒子，然后重新缩放每一个粒子，使对中的第一个粒子居中，然后计算到第二个粒子的距离，但运行起来非常慢。在

然后我在scipy.spatial.distance公司这样我就可以很快地计算出所有点之间的距离，但唯一的问题是它没有考虑环绕。在

这是我当前的代码

from scipy.spatial.distance import pdist, squareform
...
distance = squareform(pdist([(p.x, p.y) for p in particles]))

这适用于靠近中心的粒子，但如果一个粒子位于（1320），而另一个粒子位于（639320），则计算它们的距离为638，而不是2。它不考虑包装。在

我可以使用不同的函数吗，或者可以在前后应用一些转换来考虑包装？在

Answer 1

假设你复制了四块板，上面，下面，左边和右边到原始板上，同时把原来板上的粒子复制到新的板上。让我们也标记粒子。在

表示原始板上的N粒子，o(i)，i从1和{}运行。a(i)上面复制板上的粒子。b(i)，l(i)，r(i)分别代表下方、左侧和右侧。在

对于所有不同的i和j，您需要找到o(i)和{}、o(i)和{}之间的距离，依此类推。每对i和{}需要计算5x5=25的距离。一旦你有了所有这些距离，取每对的最小值，这就是i和{}的距离。在

我在想也许有办法删减计算。但我的想法是，你至少需要计算出粒子到板的距离，并与原始板上的距离进行比较。这也是一个开销。在

Answer 2

可以计算x和y差异中较小的一个（窗口内差异与边交叉距离），如下所示：

game_width = 640
game_height = 480

def smaller_xy(point1, point2):

    xdiff = abs(point1.x - point2.x)
    if xdiff > (game_width / 2):
        xdiff = game_width - xdiff

    ydiff = abs(point1.y - point2.y)
    if ydiff > (game_height / 2):
        ydiff = game_height - ydiff

    return xdiff, ydiff

也就是说，如果x或y方向的窗口内距离大于该方向窗口大小的一半，则最好离开边缘，在这种情况下，该距离将是该方向上的窗口大小减去原始窗口内距离。在

显然，一旦有了x和y的分离，就可以计算点之间的距离，如下所示：

^{pr2}$

但是，根据力计算的定义方式，您可能会发现，您真正需要的只是距离的平方（仅（small_x**2 + small_y**2）），因此您可以避免寻找sqrt的工作。在

要将其放入scipy.pdist，请注意除了点之外，pdist还可以使用函数参数调用，如下所示：

Y = pdist(X, func)

这是pdist在https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html#scipy.spatial.distance.pdist的描述中显示的最后一种调用形式

您应该能够使用该功能使pdist根据应用smaller_xy计算的回调函数计算的距离，在所有对点矩阵之间建立其距离。在