4

我正在寻找一种有效的算法，对于具有已知高度、宽度和长度的空间，给定一个固定的半径 R，以及一个点列表 N，在该空间中具有 3 维坐标，将找到固定范围内的所有点网格上任意点的半径 R。此查询将使用不同的点多次完成，因此昂贵的预处理/排序步骤以换取快速查询可能是值得的。这是我正在处理的应用程序的一个瓶颈步骤，所以任何时候我可以切断它都是有用的

到目前为止我尝试过的事情：

- 朴素算法，遍历所有点并计算距离

- 将空间划分为长度为 R 的立方体的网格，并将点放入其中。这样，对于每个点，我只需要查询直接相邻的存储桶。这有显着的加速

-我尝试使用曼哈顿距离作为启发式方法。也就是说，在桶内，在计算到任何点的距离之前，使用曼哈顿距离过滤掉那些不可能在半径 R 内的（即曼哈顿距离 <= sqrt(3)*R 的那些） ）。我认为这会提供加速，因为它只需要加法而不是乘法，但它实际上使程序减慢了一点

编辑：为了比较距离，我使用平方距离来消除必须使用 sqrt 函数。

显然，我可以加快多少速度会有一些限制，但我可以使用任何关于现在尝试的事情的建议。

并不是说它在算法层面上可能很重要，但我正在使用 C 语言工作。

4

6 回答 6

3

不要在半径上比较，在半径的平方上比较。原因是，如果两点之间的距离小于R，则距离的平方小于R^2。

这样，当您使用距离公式时，您不需要计算平方根，这是一项非常昂贵的操作。

于 2012-06-15T15:35:10.140 回答
3

将点存储在具有三个维度的kd 树中可能会提高速度。这将使您在 O(log n) 摊销时间内进行搜索。

于 2012-06-15T15:37:19.980 回答
1

我建议使用 KD 树或 z 曲线： http ://en.wikipedia.org/wiki/Z-order_%28curve%29

于 2012-06-15T15:37:46.157 回答
1

二叉索引树怎么样？（参考Topcoder教程）可以扩展到n维，编码更简单。

于 2012-06-15T16:22:08.760 回答
1

Nicolas Brodu's NEIGHAND library do exactly what you want, improving on the bin-lattice algorithm.

More details can be found in his article: Query Sphere Indexing for Neighborhood Requests

于 2012-06-29T13:34:52.483 回答
0

[我可能误解了这个问题。我发现问题陈述难以解析。]

在过去，设计一种带有“早期输出”的算法通常很好，这些算法会进行测试以避免更昂贵的计算。在现代处理器中，分支预测的失败通常是非常昂贵的，而这些早期测试实际上可能比完整计算更昂贵。（确定的唯一方法是测量。）

在这种情况下，计算非常简单，因此最好避免构建数据结构或进行任何巧妙的提前检查，而是尝试优化、向量化和并行化以获得所需的吞吐量。

对于一个点 P(x, y, z) 和一个球体 S(x_s, y_s, z_s, radius)，隶属度检验是：

(x - x_s)^2 + (x - y_s)^2 + (z - z_s)^2 < radius^2

whereradius^2可以为查询中的所有点预先计算一次（避免任何平方根计算）。这些计算都是独立的，您可以并行计算多个点。使用 SSE 之类的东西，您可能一次可以做四个。如果您有很多点要测试，您可以拆分列表并进一步并行化跨多个内核的工作。

于 2012-06-15T17:53:09.063 回答