在空间中寻找距离小于某值的点
我正在开发一个Python应用程序，里面有一组3D点（数量在2到100000之间），我需要找出那些彼此之间距离在某个范围内的点（比如说在0.1到0.2之间）。这个功能是为了图形应用，所以这个搜索过程必须非常快（大约在0.1秒内能处理10000个点）。
作为第一次尝试，我用了scipy.spatial.KDTree.query_pairs这个方法，但在处理5000个点时，返回结果需要5秒钟。你知道有什么方法可以更快地解决这个问题吗？
关于这个应用程序的更多信息：
这些点代表的是原子的坐标，而寻找距离的功能是为了确定原子之间的键。原子之间的键并不是固定的，可能会在每一步发生变化，比如氢键的情况。
2 个回答
我首先想到的是：如果我们计算这组原子之间的距离，那就需要进行O(N^2)的操作，这样会非常慢。那有没有办法呢？可以考虑引入一个统计正交网格，设定一些单元格的大小（比如接近你感兴趣的距离），然后确定每个单元格里有哪些原子（这只需要O(N)的操作）。完成这个步骤后，你就可以更快地找到邻近的原子了。
这是个好问题！我来给你提个建议：
把每个坐标值都除以你的“epsilon”值，比如0.1、0.2或者其他的，然后把结果四舍五入成整数。这样就能创建一个“商空间”，在这个空间里，点之间的距离不需要用复杂的距离公式来计算，而只需要比较每个点的整数坐标。如果所有坐标都一样，那就说明这些原始点之间的距离大约在三倍的epsilon范围内（比如说）。这个过程的复杂度是O(n)，应该在0.001秒以内完成。
（注意：你需要把原始点加上这次除法和四舍五入得到的三个整数，这样就不会丢失原始坐标的准确性。）
接下来，按照数字的顺序对这些点进行排序，使用字典式的规则，把坐标中的三个整数当作单词里的字母来处理。这个过程的复杂度是O(n * log(n))，肯定会在你要求的1/10秒以内完成。
然后，你只需遍历这个排序后的列表，比较每个点的整数坐标和前后相邻的点。如果所有坐标都匹配，那么这两个匹配的点就可以放入你的“保留”列表中，而其他的点可以标记为“丢弃”。这个过程的复杂度是O(n)，应该花费的时间非常少。
最后，你会得到一个原始点的子集，这个子集中只包含那些可能与其他点有联系的点，联系的定义是距离在epsilon或更小的范围内。
这个过程虽然不是数学上完全精确，但我觉得它确实快速，并且适合你的需求。