logo标签列表

3D中，点A是否靠近点B - 距离检查

algorithmperformancedistance
4
我正在寻找一种高效的算法，用于检查一个点在3D空间中是否靠近另一个点。
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius

这似乎不太快，而且我并不需要如此高的精度。还有其他方法可以做到这一点吗？

2
由于有C++标签，我觉得我应该提一下，^表示的是“异或”，而不是“幂”（@Balon肯定已经知道了:-)） - James Hopkin
1
我们可能需要一个类似于维基百科的LaTeX格式化工具，用于数学相关主题。将维基百科公式图像生成代码合并进去不应该太难。 - Thorsten79
当人们抱怨接近度判断速度慢时，通常是因为做了太多的接近度判断。你能否使用空间分割（如八叉树/四叉树或BSP）来解决你的问题？ - drxzcl
1
@JamesHopkin 正如人們所說的“遲到總比不到好” - 我現在已經刪除了 C++ 標籤，因為這個問題非常普遍，並不特定於 C++ :) - kjagiello
10个回答
24

将距离平方，去掉对sqrt()的调用，这样速度更快：

(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius

当然，在许多情况下，至少可以提前计算radius * radius并将其存储为squaredRadius。
2
你为什么认为这不够快？你是否有任何理由认为这段代码会成为问题，比如被运行了十亿次？ - Mr. Boy
2
也许你需要将点存储在空间结构中，比如八叉树中，以便能够有较少的点进行比较。点之间的距离由它们的包围盒之间的距离限制。 - fa.
5
请重新计算一下。只要p，q是非负数，√p < q就等价于p < q²。例如0.6 = √0.36 < 0.7和0.36 < 0.49 = 0.7²。 - kennytm
1
@Balon：你是否已经测量了立方体距离的速度，还是只是猜测？因为我认为立方体距离（使用此处提供的公式）在最好的情况下大约同样快，在最坏的情况下则更慢。毕竟，它基本上用比较和条件跳转（因为&&短路）交换了加法和乘法。这似乎并不像应该提高性能的东西。 - Grizzly
1
@Balon：如果 abs(x) 比 (x * x) 更快，特别是对于非整数而言，那将是一台不寻常的机器。然而，了解哪个算法更快的一般规则是测试两者并自行判断。 - Drew Dormann
显示剩余9条评论
10

如果你可以接受立方距离而不是球形距离，那么一个相当简单的实现方式如下：

Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius

如果Math.Abs成为瓶颈，您可以使用自己喜欢的优化方法。

我还应该补充一点，如果其中一个维度通常变化比其他维度小，那么将它放在最后应该会提高性能。例如，如果您主要处理“地面”x-y平面上的对象，则最后检查z轴，因为您应该能够通过使用x和y检查更早地排除碰撞。

如果它在立方体内，您仍然可以将其细化为球形距离。+1 - xtofl
+1 这是最基本的估算距离的方法。 - ziggystar
1
示例代码的第三个条件应为 Math.Abs(z2-z1) < radius。 - Joris Timmermans
3

如果您不需要高度精确的话，也许可以检查第二个点是否在立方体内（边长为“2a”），而不是球形中心点为第一个点：

|x2-x1|<a && |y2-y1|<a && |z2-z1|<a
哇，那是什么编程语言？ |a| 表示“绝对值”是数学符号，但它也有 '&&' 吗？ - JBRWilkinson
2

由于流水线处理器架构，现在大多数情况下，进行两次FPU计算比进行一次分支更有效率。如果出现分支预测错误，将会导致CPU停滞很长时间。

因此，我宁愿选择计算方式，而不是分支方式。

1

如果你不需要准确性，可以检查你是否在一个立方体而不是一个球体中。

这里也有一些选择，你可以选择围住球体的立方体（没有假阴性），与球体相同体积的立方体（有一些假阳性和假阴性，但最大误差被最小化），包含在球体内部的立方体（没有假阳性）。

这种技术也很好地扩展到更高的维度。

如果你想获得靠近另一个点的所有点，某种形式的空间索引可能也是合适的（例如kd树）

1

如果您需要检查许多其他点，您可以考虑使用空间排序方法快速发现靠近某个位置的点。请查看此链接： 维基链接

1
如果我们要优化这个程序，因为它被运行了数十亿次，我会使用unwind的方法来解决，并使用SIMD并行化。有几种不同的方法可以做到这一点。你可以简单地在一个操作中完成所有的减法(x2-x1,y2-y1,z2-z1)，然后在一个操作中完成所有的乘法。这样你就可以在方法内部并行化，而无需重新设计算法。
或者你可以编写一个批量版本，计算许多元素上的(x2-x1)^2+(y2-y1)^2+(z2-z1)^2 - r^2，并将结果存储在一个数组中。你可能可以获得更好的吞吐量，但这意味着需要重新设计你的算法，具体取决于测试的用途。
如果你真的要连续进行大量的测试，你也可以很容易地使用像OpenMP这样的东西来优化它。
0

这个函数计算了立方体距离，如果你要处理很多点，大部分时间它只会执行第一个测试。

close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);
0

使用 max(abs(x1-x2), abs(y1-y2), abs(z1-z2))

5
那样做真的更快吗？毕竟现代CPU上乘法并不低效。 - Mr. Boy
条件逻辑也绝非低效！ - JBRWilkinson
1
实际上，在紧密循环中使用条件逻辑可能不如计算所有内容高效，因为会出现分支预测错误。 - Joris Timmermans
你是否需要为 double abs(double) 和 double max(double, double) 使用条件逻辑呢？ - MSalters
不确定。如果我没有记错，这不是标准操作，因此假设优化是有风险的。 - Mr. Boy
0

去掉平方根后，如果值变得较大，最好应用对数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接