圆环矩形上两点之间的最短距离

hbghlyj

CRAN - Torus distance matrix 矩形平面被认为是圆环面（即从右侧、左侧、顶部或底部退出矩形会让您重新出现在对面的边缘）。

计算红绿两点之间的最短距离。

一种方法是选择其中一个点（我选择红色）并将其克隆 8 次以包围单元格，如下所示。 您将计算从绿点到 9 个红点中每一个的距离，距离最小的就是答案。

进行 9 次距离计算以找到最小距离并不是那么可取。 您可以使用平方距离而不是常规距离来避免在每个距离计算中都出现平方根，但这仍然需要一些计算。

维度的增加会使问题变得更糟。 在 3D 中，找到最短点需要 27 次距离计算，而在 4D 中需要 81 次距离计算！

幸运的是，有更好的方法来解决这个问题。

假设我们的图像尺寸是 1 x 1。如果您查看具有 9 个红点副本的图像，您可以看到它们只是在每个轴上添加 -1、+0、+1 的 9 种可能组合 到红点的坐标。 添加了 -1、+0 或 +1 的 x 轴和 y 轴的所有可能组合都是红点的有效位置。

根据距离公式我们可以看到，如果我们分别最小化每个坐标，我们最终也会得到最小的整体距离。
\[
d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}
\]
因此，更好的方法是分别最小化每个坐标。

在 x 轴上，当您从红点的 x 轴位置减去 1、保持不变或加 1 时，您会发现红点和绿点之间的 x 轴距离是否最小。

红点的 x 轴值给你最小的 x 轴 1D 距离是要使用的 x 轴位置。

您将为 y 轴重复，以获取要使用的 y 轴位置（并为更高维度的任何其他轴重复）。

这为您提供了最近的点，然后您可以将其代入距离公式以获得环绕空间中各点之间的距离。

你实际上可以做得更好。

仍然单独处理每个轴，您可以计算该轴上两点之间的一维距离的绝对值。 如果该距离大于 0.5，则该轴的实际距离为 1 距离。

这里的直觉是，如果你在一维重复空间中，如果从 A 到 B 的距离超过一半，则意味着你走错了路，而走另一条路更短。 另一种方式的距离是 1 减去你刚刚计算的任何距离，因为从一个点到它自身的距离是 1！

对每个轴执行此操作，并在距离公式中使用这些 1d 距离来获得实际距离。

这使您可以最小化距离，而不必明确找出哪个组合使点最近。

更重要的是，它可以让您有效地计算环形空间（甜甜圈空间！）中两点之间的距离。

计算复杂度要好很多。 它现在在维数上是线性的：O(N)，而不是 O(3^N)。

这里有一段 C++ 向您展示它如何在 2D 中工作。

1. float ToroidalDistance (float x1, float y1, float x2, float y2)
2. {
3.     float dx = std::abs(x2 - x1);
4.     float dy = std::abs(y2 - y1);
6.     if (dx > 0.5f)
7.         dx = 1.0f - dx;
9.     if (dy > 0.5f)
10.         dy = 1.0f - dy;
12.     return std::sqrt(dx*dx + dy*dy);
13. }

Copy the Code

Calculating the Distance Between Points in “Wrap Around” (Toroidal) Space

hbghlyj

在圆环上两个随机选择的点的距离 $≤r$ 的概率
因为度量是平移不变的，可以假设一个点是 $U = (1/2,1/2)$。如果 $0 \le x \le 1$ 和 $0 \le y \le 1$，则圆环上从 $(x,y)$ 到 \((1/2,1/2)\) 的距离等于它们的欧氏距离。
所以 $d(U,V) \le r$ 的概率只是以 $(1/2,1/2)$ 为中心的半径为 $r$ 的圆与正方形 \([0 ,1]\times[0,1]\)的交集面积.