两点之间的距离粗略计算

Question

我希望计算两点之间的大致距离，以减少计算开销。

我使用以下公式来计算（x1，y1）和（x2，y2）之间的距离：

Dist = Mod (x1 - x2) + Mod (y1 - y2)

其中Mod是模数运算符，使得Mod(x) = |X|。

这似乎有效。

我想知道，如果我漏掉了什么……

- Alphaneo

---

你听说过勾股定理吗？ - user541686

@Mehrad，很想使用欧几里得距离，但是不想要平方和平方根的开销。 - Alphaneo

平方一个数非常快，因为它只是将该数乘以自身；如果你很幸运只需要比较距离而不是计算距离，那么你可以跳过平方根。 - Martin Booth

Answer 1

三种常见距离的图形表示：

（注意：这个图形展示了在这三种度量下半径为4的圆。）

- Dr. belisarius

---

红线不是4*sqrt(2)吗？那条线不是8吗？ - mtrw

@mtrw 红线是 mod[x]+mod[y] == 4，而蓝线是 max[mod[x],mod[y]] == 4。 - Dr. belisarius

对不起，我完全忽略了某些东西。蓝线不是 mod[x] + mod[y] 吗？ - mtrw

@mtrw 那张图片很令人困惑。这就是为什么我链接了另一张图片的原因。请查看此处最后一个部分（指标）中的图片 http://www.comp.lancs.ac.uk/~kristof/research/notes/basicstats/index.html - Dr. belisarius

该页面上曼哈顿距离的公式为sum(abs(x_i-y_i))。在您的图片中，x = (4,0)，y = (0,4)，并且sum(abs(4-0) + abs(0-4)) = 8。该图片展示了曼哈顿距离的对角线，因为它表明该对角线上所有点与原点的距离相同。因此曼哈顿距离用对角线表示，欧几里得距离用圆表示。 - mtrw

Answer 2

只要您获取了绝对值（如您所述的|X|），而不是使用模函数，那么这将给您两个点之间的曼哈顿距离。

如果这就是您想要的，那么您没有遗漏任何内容。

如果您想要直线距离，请使用勾股定理。这是sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)。

- Martin Booth

Answer 3

您确定您正确使用了模运算符吗？看起来您正在使用MOD作为ABSOLUTE。

http://en.wikipedia.org/wiki/Modulo_operation

无论如何，正如Mehrdad所说，使用勾股定理：

Dist = Sqrt( (x1-x2)^2 + (y1-y2)^2 )

- Beno

Answer 4

你需要在想要计算的距离方面具体明确。

距离公式：给定两个点（x1，y1）和（x2，y2），这些点之间的距离由以下公式给出：

这是我们在坐标几何中用于找到点之间距离的标准公式，并且是MinKowski distance在一维上的特例化。

- Algorithmist

Answer 5

你的距离计算公式对于大概的距离来说是没问题的。但使用(x₂ - x₁)² + (y₂ - y₁)²可以得到实际距离的平方。只要铭记这是距离的平方，它就更为准确。并且根据你实现的架构不同，它可能会更快——乘法可能比模数中的分支少花时间，或者对于硬件实现而言可能需要相同的时间。你需要进行基准测试以确保。

- mtrw

---

请注意，abs通常不需要分支 - 它无条件地将一个位设置为零。 - Cris Luengo

Answer 6

如果您想比较距离并节省时间，不要使用距离本身，而是使用它的平方：(x1-x2)^2 + (y1-y2)^2。不要取sqrt。这样，您的距离将与普通距离一样正常，但速度更快。计算dx=x1-x2和dx2=dx*dx甚至比取ABS（您指的是它，而不是MOD）更快，因为后者是一个函数，您必须为其付费。

ABS距离在理论上是正确的-但如果对于您的目标来说太粗糙，那有什么用呢？

- Gangnus

Answer 7

我编写了这个算法来计算两点之间的直线距离：

var distance = function(x1, y1, x2, y2) {
            //Distance Horizantally
            var horizontalDistance = 0;
            /Distance Vertically
            var verticalDistance = 0;
            
            if(x1 > x2) {
                horizantalDistance = x1 - x2;
            }
            else {
                horizantalDistance = x2 - x1;
            }
            
            if(y1 > y2) {
                verticalDistance = y1 - y2;
            }
            else {
                verticalDistance = y2 - y1;
            }

            var answer = 0;
            
            if(verticalDistance !== 0 && horizantalDistance !== 0) {
                //Use the Pathagoreum Theorum
                answer = Math.sqrt(verticalDistance + horizantalDistance);
            }
            else if(horizantalDistance === 0) {
                //Use the Vertical Distance
                answer = verticalDistance;
            }
            else if (verticalDistance === 0) {
                //Use the Horizantal distance
                answer = horizantalDistance;
            }
            //Return the answer
            return answer;
        }

- Ptolemy2002