我正在寻找一种有效的算法，对于已知高度，宽度和长度的空间，给定固定的半径R，并且在该空间中具有三维坐标的点N的列表将找到固定点内的所有点网格上任意点的半径R。此查询将多次使用不同的点进行，因此以快速查询为代价的昂贵的预处理/排序步骤可能是值得的。这是我正在处理的应用程序的瓶颈步骤，因此，只要我能切断它，这都是很有用的

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

-天真的算法，遍历所有点并计算距离

-将空间分成长度为R的多维数据集的网格，然后将点放入其中。这样，对于每个点，我只需要查询直接相邻的存储桶。这大大加快了速度

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

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

显然，我可以加快这个速度有一定的限制，但是现在我可以使用任何建议来尝试。

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