我正在寻找有效的算法来检查一个点是否在 3D 中靠近另一个点。
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius
这似乎并不太快，实际上我不需要这么大的准确性。我还能怎么做？
问问题
683 次
10 回答
24
平方距离，然后调用sqrt()，这要快得多：
(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius
当然，在许多情况下，至少radius * radius可以提前计算并存储为例如squaredRadius.
于 2010-01-22T10:23:38.657 回答
10
好吧，如果您可以满足于立方体距离而不是球面距离，那么一个非常幼稚的实现将是这样的：
Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius
如果证明存在瓶颈，您可以使用自己喜欢的优化 Math.Abs 的方法。
我还应该补充一点，如果其中一个维度的变化通常小于其他维度，那么将最后一个维度放在最后应该会带来性能提升。例如，如果您主要处理“地面”xy 平面上的对象，那么最后检查 z 轴，因为您应该能够通过使用 x 和 y 检查来更早地排除碰撞。
于 2010-01-22T10:26:47.047 回答
3
如果您不需要很高的精度，也许您可以检查第二个点是否在立方体内（边长'2a'），而不是第一个点在中心的球体：
|x2-x1|<a && |y2-y1|<a && |z2-z1|<a
于 2010-01-22T10:29:02.590 回答
2
Because of the pipelined processor architectures it is - nowadays - in most cases more efficient to do the FPU calculation twice, as branching once. In case of a branch mis-prediction you are stalling for ages ( in cpu-terms ).
So, I would rather go the calculation-way, not the branching-way.
于 2010-01-22T11:05:28.657 回答
1
如果我们要优化它，因为它运行了数十亿次，我会使用unwind 的方法来解决这个问题，然后使用 SIMD 并行化它。有几种不同的方法可以做到这一点。您可以简单地在一个操作中执行所有减法 (x2-x1,y2-y1,z2-z1)，然后在一个操作中进行乘法运算。这样你就可以在方法内部进行并行化，而无需重新设计算法。
或者，您可以编写一个批量版本，对许多元素计算 (x2-x1)^2+(y2-y1)^2+(z2-z1)^2 - r^2 并将结果存储在一个数组中。您也许可以获得更好的吞吐量，但这意味着重新设计您的算法并取决于测试的用途。
如果您真的连续进行大量测试，您也可以使用 OpenMP 之类的工具轻松优化它。
于 2010-01-22T13:43:32.070 回答
1
如果您不需要准确性，您可以检查您是否在立方体而不是球体中。
这里也有一些选项，您可以选择包围球体的立方体（无误报） 与球体体积相同的立方体（一些误报和否定，但最大误差最小化），包含在球体（无误报）。
这种技术也可以很好地扩展到更高的维度。
如果你想让所有点靠近另一个点，某种形式的空间索引也可能是合适的（也许是 kd-tree）
于 2010-01-22T10:27:39.687 回答
1
如果您必须检查许多其他点，您可以考虑使用空间排序方法来快速发现某个位置附近的点。看看这个链接： wiki 链接
于 2010-01-22T11:12:00.830 回答
0
去掉平方根后，如果值变大，最好应用对数。
于 2010-01-22T13:27:50.107 回答
0
使用最大值（abs（x1-x2），abs（y1-y2），abs（z1-z2））
于 2010-01-22T10:26:22.693 回答
0
这是立方距离，如果你做很多点，大多数时候它只做第一次测试。
close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);
于 2010-01-22T15:36:35.223 回答