给定一组(x，y，z)形式的点，以及一组(x，y，z，半径)形式的球体。
对于每个球体，目标是计算球体内的点数。
我比较了球心和点的欧氏距离与球体半径的关系，该算法需要 O(N*M) 时间复杂度，其中 N、M 分别是点和球体的数量。
我尝试排除 (x ± r, y ± r, z ± r) 框外的点，但它根本无法缩短计算时间。
所以我研究了一些数据结构，如线段树、四叉树、八叉树和 k-d 树，但我很难将它们应用到我的目标中。
如何将时间复杂度降级为 O(NlogM)、O(MlogN) 或其他值？
最佳答案
如果坐标范围有限，可以将空间分割为相等的立方体，并将点分配给相应的立方体(单元)。
对于每个球体，您必须仅检查该球体附近的单元格(以球体中心为中心的大致大立方体)。
真正的增益取决于单元大小和点分布的正确选择。
您提到的 k-d 树 - 对于此类问题来说它似乎是一个不错的选择。
(例如 - using this approach 对于寻找紧密对的 2d 问题，对于具有相当均匀分布的 64K 点，时间增益为 11466 ms => 62 ms(相对于成对比较))
关于algorithm - 如何快速确定球体包含给定集合的多少个点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/71170420/