algorithm - 环形包裹(x 和 y 包裹) map 上点之间的最短距离？

Question

我有一张环状欧几里德式 map 。即表面是一个平坦的欧几里德矩形，但是当一个点移动到右边界时，它将出现在左边界(在相同的 y 值)，由 x_new = x_old % width 给出

基本上，点的绘制基于:* see edit

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

想想吃 bean 人——离开屏幕的一个边缘会让您出现在另一边。

计算两点之间最短距离的最佳方法是什么？典型的实现建议 map 相对角上的点距离较大，而实际上，真正的包裹距离非常近。

我能想到的最好方法是计算经典 Delta X 和 Wrapped Delta X，以及经典 Delta Y 和 Wrapped Delta Y，并在 Sqrt(x^2+y^2) 距离公式中使用每对中的较低者.

但这将涉及许多检查、计算和操作——我认为有些可能是不必要的。

有没有更好的办法？

---

编辑

当一个物体移动时，它移动到位置(x_old,y_old)，通过上面的公式运行它，并存储(x_new, y_new)作为它的位置。添加上面的公式只是为了阐明当物体移动越过边界时会发生什么；实际上，一次只有一个 (x,y) 对存储在每个对象中。

Answer 1

The best way I can think of is calculating Classical Delta X and Wrapped Delta X, and Classical Delta Y and Wrapped Delta Y, and using the lower of each pair in the Sqrt(x^2+y^2) distance formula.

就是这样，我认为没有更快的方法。但这并不难计算；你可以做类似的事情

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

(我相信您可以将其翻译成您喜欢的语言)