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 万个点的列表上运行它。

我已经阅读了 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。