具有周期性边界的格子上的距离

Question

我有一个方形格子，大小为 LxL。在这个格子中，我可以有经典的 4 邻域网格或 8 邻域格子（也包括对角线）。

给定格子上两个点的坐标 (i1,j1) 和 (i2,j2)，我想计算它们在 4 邻域网格和 8 邻域网格中的距离，同时考虑周期性边界条件。

对于4邻居的情况，没有周期性边界条件，距离是曼哈顿距离d=|i1-i2|+|j1-j2|。如果我想考虑周期性边界，我可以多次计算距离（例如，将 (i2,j2) 更改为 (i2,j2-L)）并取最小值，但我确信还有更多执行此操作的有效方法。

关于8邻域的情况，我发现了这个问题：（在我的例子中，我将sqrt(2)替换为1）但它并没有解决边界条件的问题。

关于如何计算这些距离的任何伪代码？越快越好

Answer 1

求循环坐标差：

dx = Abs(x1 - x2)
if dx > L/2
   dx = L - dx
similar for dy

这种情况下的距离称为曼哈顿距离

dist = dx + dy

如果对角线移动成本为 1，那么对于 8 邻域的情况解决方案很简单 - 要到达新位置，必须从 dx 和 dy 步执行最大值，但不需要更多步，因为沿较短方向移动是组合的沿着更长的方向移动 - 对角线移动。

dist = Max(dx, dy)

（另请注意，对角线部分是 Min(dx, dy)，hor/vert 部分是 Abs(dx - dy)。这些表达式的总和等于 dx, dy 的最大值）

Distances on lattices with periodic boundaries