python - 在空间中查找比某个值更近的点

Question

在我正在开发的 python 应用程序中，我有一个 3D 点数组(大小在 2 到 100000 之间)，我必须找到彼此之间一定距离内的点(比如在两个值之间，例如 0.1和 0.2)。我需要这个用于图形应用程序并且这个搜索应该非常快(对于 10000 个点的样本大约需要 1/10 秒)

作为第一个实验，我尝试使用 scipy.spatial.KDTree.query_pairs 实现，并使用 5000 点的样本返回索引需要 5 秒。您知道任何可能适用于这种特定情况的方法吗？

关于应用程序的更多信息:

点代表原子坐标，距离搜索有助于确定原子之间的键。键不一定是固定的，但可能会在每一步发生变化，例如氢键。

Answer 1

好问题!这是我的建议:

将每个坐标除以您的“epsilon”值 0.1/0.2/whatever，并将结果四舍五入为整数。这创建了一个点的“商空间”，其中不再需要使用距离公式来确定距离，而只需比较每个点的整数坐标即可。如果所有坐标都相同，则原始点之间的距离大约在三倍 epsilon 的平方根范围内(例如)。这个过程是 O(n) 并且应该花费 0.001 秒或更少。

(注意:您可能希望使用此除法和舍入产生的三个额外整数来增加原始点，这样您就不会丢失精确坐标。)

使用字典式规则按数字顺序对点进行排序，并将坐标中的三个整数视为单词中的字母。这个过程是 O(n * log(n)) 并且应该比你的 1/10 秒要求少。

现在您只需继续这个排序列表并将每个点的整数坐标与之前和之后的点进行比较。如果所有坐标都匹配，那么两个匹配点都可以移到您的“保留”点列表中，而所有其他点都可以标记为“丢弃”。这是一个 O(n) 的过程，应该只需要很少的时间。

结果将是所有原始点的子集，其中仅包含可能涉及任何键的那些点，键被定义为与原始集合中其他点的距离大约为 epsilon 或更小。

这个过程在数学上并不精确，但我认为它绝对很快并且适合您的目的。