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

Question

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

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

对于 4 邻点情况，没有周期性边界条件，距离为曼哈顿距离d=|i1-i2|+|j1-j2|。如果我想考虑周期性边界，我可以多次计算距离（例如改变(i2,j2)）(i2,j2-L)并取最小值，但我确信有一种更有效的方法来做到这一点。

关于 8-neighbor 的情况，我发现了这个问题：Calculate distance on a grid Between 2 point (在我的例子中，我将替换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)，水平/垂直部分为 Abs(dx - dy)。这些表达式的总和等于 dx, dy 的最大值）