我建议使用谷歌搜索边界体积层次结构（特别是 BSP 树）。给定您的点云，您可以找到一个平面，将其分成两个相等的子云。然后，当您需要找到某个测试点半径 R 内的点集合时，您可以先将您的测试点与该平面进行比较，如果它上方的高度大于 R，则该平面下方的整个子云也必须比 R 更远（所以你不需要检查任何这些点）。你也可以递归地应用这个想法，最终产生 n log n 类型的复杂度而不是 n 平方。（这是 BSP / 二进制空间分区，

有几种数据结构用于存储保存位置和接近度信息的数据；通过允许快速最近邻确定。

特别是R-trees（以及像R*-trees这样的特殊形式）和X-trees。许多选择针对略有不同的用途进行了优化。

选择 R*-tree 而不是幼稚的最近邻查找是我从特定代码中获得 10000 倍加速的重要部分。（好吧，也许其中几百个是 R*-tree，其余的大部分是因为天真的查找编码错误，以至于它破坏了缓存。::sigh: :)

这些结构具有典型的（存储点数）插入性能和存储要求以及查找性能，因此如果您要进行多次查找（例如每个点一个，如 DBSCAN）；但是其中一些在最坏情况下的表现非常糟糕。$O(N \log N)$$N$$O(\log N)$

这与分子动力学领域的最大挑战之一非常相似——计算非键合粒子之间的所有成对相互作用。

在那里，我们使用单元列表（或邻居列表）来帮助我们找出附近有什么；对于这个应用程序，单元格列表可能是更容易使用的算法：

• 将盒子分成一系列单元格。
• 对于每个粒子，确定应将其分配给哪个单元格（每个粒子 O(1)）。
• 然后，对于每个粒子，检查“自己的”单元格和相邻单元格；如果其中任何一个被占用，则无需进一步搜索。
• 如果所有最近的邻居都是空的，则扩展到下一个最近的邻居，依此类推，直到找到一个粒子。

如果您的系统具有或多或少均匀分布的粒子，则根据网格的粗糙度，这将大大降低算法的成本。然而，一些微调是必要的：网格太粗，你不会节省太多时间；太好了，你会花很多时间在空的网格单元上循环！

您绝对应该检查作为点集选择方法的KD 树和八叉树（而 BSP 用于一般对象，而网格用于或多或少均匀的密度）。它们可以非常紧凑和快速，最大限度地减少内存和计算的开销，并且易于实现。

当您的点或多或少均匀分布时（即使有空白区域，但必须没有密度奇点或其他高浓度），如果您想尝试类似网格的非分层空间细分，请检查球体填充。