寻找两个三维点之间距离的有效方法

Question

我正在使用C++编写代码，想要计算两个点之间的距离。

问题1：

我有两个点P(x1, y1, z1)和Q(x2, y2, z2)，其中x、y和z为浮点数/双精度数。

我想要找到这两个点之间的距离。一种方法是：

square_root(x_diff*x_diff + y_diff*y_diff + z_diff*z_diff)

但这可能不是最有效的方法。（例如更好的公式或在math.h中提供的实用程序等）

问题2：

如果我只想确定P和Q是否实际上是相同的点，是否有更好的方法？

我的输入是两个点的x、y和z坐标。

谢谢。

- memC

---

在第二个问题上 - 有什么阻止你只比较3D坐标的每个组件吗？ - Tom Duckering

@Tom Duckering: "什么阻止了你..."--我的大脑！我需要休息一下。 - memC

@Tom，实际上比较操作是相当慢的（可能涉及分支，因此需要进行某种程度的流水线清空），而比较浮点数的相等性从来都不是一个好主意。 - James

比较实际上并不慢；在“典型”硬件上，浮点数比较的速度与浮点数加法大致相同。MSalters 在下面的评论中解释了如何进行三个加法和一个比较的近似相等性测试，这肯定比两个加法、三个乘法（可能是平方根）和一个比较要快。 - Stephen Canon

Answer 1

您需要实际距离吗？您可以使用距离的平方来确定它们是否相同，并且可以用于许多其他目的。（节省sqrt运算）

- James

---

对于比较以及许多其他需要距离的向量运算，这是正确的答案。使用距离的平方！例如，不要写成sqrt(dx*dx + dy*dy + dz*dz) < epsilon，而应该写成dx*dx + dy*dy + dz*dz < epsilonsquared。在数学上是等效的，并且速度更快。 - Rex Kerr

Answer 2

如果我只是想确定P和Q实际上是否为同一点，是否有更好的方法？

那么直接比较坐标即可！

bool areEqual(const Point& p1, const Point& p2) {
     return fabs(p1.x - p2.x) < EPSILON &&
            fabs(p1.y - p2.y) < EPSILON &&
            fabs(p1.z - p2.z) < EPSILON;
}

- Mehrdad Afshari

---

+1，省去了我的打字和测试时间（甚至在IDE启动之前就完成了，呵呵） - mlvljr

你正在使用一个EPSILON大小的立方体来确定接近度。这很合理，但检查(fabs(p1.x - p2.x) + fabs(p1.y - p2.y) + fabs(p1.z - p2.xz)) < EPSILON_3D会更快-只需进行一次比较。(其中 EPSILON <= EPSILON_3D <= 3*EPSILON) - MSalters

@MSalters：不过那不是一回事。我这样做更精确（每个维度的最大差异为“EPSILON”，而在你的解决方案中，“p1.x-p2.x”可以是“3*EPSILON”，而另外两个维度保持相等）。除非我在特定的机器/编译器/平台上进行基准测试，否则我不会打赌它会更快（它需要3次加法而不是3次比较）。无论哪种情况，这都是微小的优化，并带有与之相关的所有警告。 - Mehrdad Afshari

“精度”仅由围绕着“p1”的体积大小决定，这是两个测试中唯一的不同之处。我的测试使用的是一个旋转过的立方体而已。通过适当选择EPSILON_3D（如“sqrt(3) * EPSILON”），可以获得完全相同的盒子大小，从而实现完全相同的精度。至于速度，如果你不信，可以自己测试一下。 - MSalters

MSalters：是的，你关于 sqrt(3) * EPSILON 的想法是正确的。我当时想的是 3 * EPSILON，这个精度要低一些。 - Mehrdad Afshari

Answer 3

没有更有效的计算距离的方法。任何处理特殊情况，例如p.x == q.x等的方法都会平均更慢。

是的，判断p和q是否为相同点最快的方法就是比较它们的x、y、z值。由于它们是浮点数，因此不应该使用==进行比较，而应该允许一些有限的小差异，可以自行定义。

- user231967

Answer 4

您可以尝试使用SSE扩展。例如，您可以初始化两个向量A(x1，y1，z1)和B(x2，y2，z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f)
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f)

然后使用_mm_sub_ps计算差异：

__m128 Diff = _mm_sub_ps(A, B)

下一步计算差异的平方：

__m128 Sqr = __mm_mul_ps(Diff, Diff)

最后：

__m128 Sum = add_horizontal(Sqr)
__m128 Res = _mm_sqrt_ss(Sum)

你的答案将填充到Res [0]中。

附：add_horizontal是一个优化位置。

- shuvalov

---

许多现代编译器自己使用SSE和SSE2。 - AnT stands with Russia

据我所知，SSE3 包含某种 add_horizontal 操作。不过它可能只有双精度版本。 另外，在计算 Diff 时，您使用了 _mm_set_ps 而不是 _mm_sub_ps。我没有足够的忍者力量来自行纠正 :) - Peter

还有一种单精度的水平加法(haddps), 虽然它不能在一个操作中对整个向量求和，需要调用两次才能求和所有四个元素。在某些架构上，这可能比等效的洗牌和加法序列慢，这取决于其他指令正在执行什么操作。 - Stephen Canon

Answer 5

没有更好的方法。

square_root 的实现可能会被优化。

如果您要比较两个距离并想知道哪个更长，但不关心实际距离是多少，则可以完全忽略平方根步骤，并仍然操作平方的距离。例如，这适用于比较两对点以确定它们是否相距相同的距离。

- Will

---

我本来想说，很难有人能够设计出比C++内置的平方根函数更好的函数。但是看看pheelicks的回答吧，也许你可以做到！ - Tyler

Answer 6

您可能会觉得这篇文章很有趣：

http://www.codemaestro.com/reviews/9

该文章介绍了在Quake 3引擎中如何计算平方根，并声称在某些CPU上运行速度比sqrt()函数快4倍。不确定现在是否能在C++中提高性能，但仍然是一篇有趣的阅读。

- pheelicks

Answer 7

请注意，当使用sqrt(dx*dx+dy*dy+dz*dz)时，平方和可能会溢出。 hypot(dx, dy)可以直接计算距离，而没有任何溢出的机会。我不确定最快的三维等效方法是什么，但是hypot(dx, hypot(dy, dz))可以完成任务，并且也不会溢出。

- Darius Bacon

---

我一直认为 hypot 函数只是简单地计算 sqrt(xx + yy)。它具有什么不同之处，可以防止溢出呢？ - Tyler

@MatrixFrog：典型的hypot简单实现检查x和y的缩放；如果它们被很好地缩放，那么就只做sqrt(x*x + y*y)，但如果它们被不良地缩放（这样计算会导致不合理的溢出或下溢），它会将它们重新缩放到某个已知值，然后进行计算，最后再对最终结果进行缩放。当目标是子ulp精度或正确舍入时，可能存在更复杂的实现。如果你感兴趣，我建议看一些开源实现。 - Stephen Canon

Answer 8

Q2答案：如果这些点是相同的，则x1 = x2，y1 = y2和z1 = z2。

考虑到您将点存储为float / double，您可能需要使用一些epsilon进行比较。

- Victor Hurdugaci

Answer 9

有更快的方法可以获得近似距离，但标准库中没有预设。建议阅读FlipCode上的这篇文章，介绍了快速计算2D距离的方法。它将sqrt函数折叠成一个复合线性函数，可以快速计算但不是100％准确的。然而，在现代机器上，fpmath非常快，所以不要过早优化，您可能会发现采用简单方法完全足够。

- Trevor Tippins

Answer 10

GNU Scientific Library 定义了 gsl_hypot3 函数，可以精确计算你在问题的第一部分中想要的距离。如果只是为了这个目的而编译整个库可能有些浪费，但也许你还需要其中的其他功能。

- Charles Stewart