我正在寻找一种有效的算法，对于已知高度、宽度和长度的空间，给定固定半径 R 和点列表 N，在该空间中具有 3 维坐标，将找到所有点在网格上任意点的固定半径 R 内。该查询将针对不同的点进行多次，因此昂贵的预处理/排序步骤以换取快速查询可能是值得的。这是我正在处理的应用程序的一个瓶颈步骤，所以任何时候我可以切断它都是有用的
到目前为止我尝试过的事情:
-朴素算法，遍历所有点并计算距离
-将空间划分为长度为 R 的立方体的网格，并将点放入这些立方体中。这样，对于每个点，我只需要查询直接相邻的桶。这有显着的加速
-我试过使用曼哈顿距离作为启发式方法。也就是说，在桶内，在计算到任何点的距离之前，使用曼哈顿距离过滤掉那些不可能在半径 R 内的(即那些曼哈顿距离 <= sqrt(3)*R ).我认为这会提供一个加速，因为它只需要加法而不是乘法，但它实际上减慢了程序的速度
编辑:为了比较距离，我使用平方距离来避免使用 sqrt 函数。
显然，我可以加快多少会有一些限制，但我可以使用任何关于现在尝试的建议。
这在算法层面可能并不重要，但我正在使用 C 语言工作。
最佳答案
将点存储在 k-d tree 中可能会提高速度具有三个维度。这将为您提供 O(log n) 摊销时间的搜索。
关于algorithm - 在任意坐标周围找到半径为 r 的球体中的所有点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11053820/