最近邻搜索：Python的(Nearest Neighbor Search: Python)

我有一个2维阵列：

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 。

我已经解决了通过每个元素比较所有其他元素的问题，但是这需要15分钟左右的时候你的清单是22K点长。 我们希望在约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. 查询cKDTree为内6个单位作为这样的最近邻：

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

   对于中的每个项目YourArray ， TheResult将是两个点之间的距离的元组，并在点的位置的索引YourArray 。

文章来源: Nearest Neighbor Search: Python