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

Question

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

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

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

关于8邻里的情况，我发现了这个问题:Calculate distance on a grid between 2 points (在我的情况下，我会将 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 的最大值)