python - 最近邻搜索 : Python

Question

我有一个二维数组:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

前两个元素MyArray[0]和MyArray[1]分别是X和Y坐标点数。

对于数组中的每个元素，我想找到 最快 方法来返回其半径为 X 个单位的单个最近邻居。我们假设这是在二维空间中。

让我们说这个例子 X = 6.

我通过将每个元素与其他元素进行比较来解决了这个问题，但是当您的列表长度为 22k 点时，这需要 15 分钟左右。我们希望最终能在大约 3000 万个点的列表上运行它。

我已经阅读了 K-d 树并理解了基本概念，但在理解如何编写它们时遇到了困难。

Answer 1

感谢 John Vinyard 建议 scipy。经过一些很好的研究和测试，这里是这个问题的解决方案:

先决条件:安装 Numpy 和 SciPy

1. 导入 SciPy 和 Numpy 模块

2. 复制 5 维数组，包括仅 X 和 Y 值。

3. 创建 cKDTree 的实例像这样:

   YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
   #Play with the leafsize to get the fastest result for your dataset
   

4. 在 cKDTree 中查询 6 个单元内的最近邻:

   for item in YourArray:
       TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)
   

   对于 YourArray 中的每一项，TheResult 将是两个点之间的距离的元组，以及 YourArray 中该点的位置索引.