最近邻搜索: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和Ÿ点的坐标.

对于数组中的每个元素,我想找到以半径X单位返回其单个最近邻居的最快方法.我们假设这是在2D空间.

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

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

我已经阅读了关于Kd树并了解基本概念,但却无法理解如何编写脚本.

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. 查询cKDTree6个单位内的最近邻居:

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

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