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