在我正在开发的 python 应用程序中，我有一个 3D 点数组（大小在 2 到 100000 之间），我必须找到彼此相距一定距离内的点（比如在两个值之间，如 0.1 和 0.2） . 我需要这个用于图形应用程序，这个搜索应该非常快（对于 10000 个点的样本，大约需要 1/10 秒）
作为第一个实验，我尝试使用 scipy.spatial.KDTree.query_pairs 实现，对于 5000 点的样本，返回索引需要 5 秒。您知道任何可能适用于这种特定情况的方法吗？
关于应用程序的更多信息：
这些点代表原子坐标，距离搜索有助于确定原子之间的键。键不一定是固定的，但可以在每个步骤中发生变化，例如在氢键的情况下。
好问题！这是我的建议：
将每个坐标除以您的“epsilon”值 0.1/0.2/whatever 并将结果四舍五入为整数。这将创建一个点的“商空间”，其中不再需要使用距离公式来确定距离，而只需比较每个点的整数坐标即可。如果所有坐标都相同，则原始点之间的距离大约在 3 倍 epsilon 的平方根范围内（例如）。这个过程是 O(n) 并且应该花费 0.001 秒或更短的时间。
（注意：您可能希望使用除法和舍入产生的三个额外整数来增加原始点，这样您就不会丢失确切的坐标。）
使用字典式规则按数字顺序对点进行排序，并将坐标中的三个整数视为单词中的字母。这个过程是 O(n * log(n)) 并且应该肯定少于你的 1/10 秒的要求。
现在您只需继续浏览这个排序列表，并将每个点的整数坐标与前面和后面的点进行比较。如果所有坐标都匹配，那么两个匹配点都可以移动到您的“保留”点列表中，而所有其他点都可以标记为“丢弃”。这是一个 O(n) 过程，应该花费很少的时间。
结果将是所有原始点的子集，其中仅包含可能涉及任何键的那些点，键被定义为与原始集合中的其他点相距大约 epsilon 或更小。
这个过程在数学上并不精确，但我认为它绝对很快并且适合您的目的。
我想到的第一件事是：如果我们计算集合中每两个原子之间的距离，它将是 O(N^2) 操作。它非常慢。如何引入具有某些单元大小的静态正交网格（例如接近您感兴趣的距离），然后确定属于网格的每个单元的原子（需要 O(N) 操作）在此过程之后，您可以减少搜索邻居的时间。