优化二维数组中最近点的索引查找

问题描述：

2d NumPy 数组x_array包含 x 方向的位置信息和y_arrayy 方向的位置。然后我有一个 x、y 点列表。对于列表中的每个点，我根据以下代码找到最接近该点的位置的数组索引：

import time
import numpy

def find_index_of_nearest_xy(y_array, x_array, y_point, x_point):
    distance = (y_array-y_point)**2 + (x_array-x_point)**2
    idy,idx = numpy.where(distance==distance.min())
    return idy[0],idx[0]

def do_all(y_array, x_array, points):
    store = []
    for i in xrange(points.shape[1]):
        store.append(find_index_of_nearest_xy(y_array,x_array,points[0,i],points[1,i]))
    return store


# Create some dummy data
y_array = numpy.random.random(10000).reshape(100,100)
x_array = numpy.random.random(10000).reshape(100,100)

points = numpy.random.random(10000).reshape(2,5000)

# Time how long it takes to run
start = time.time()
results = do_all(y_array, x_array, points)
end = time.time()
print 'Completed in: ',end-start

我想加快速度。

解决方案 1：

以下是一个scipy.spatial.KDTree例子

In [1]: from scipy import spatial

In [2]: import numpy as np

In [3]: A = np.random.random((10,2))*100

In [4]: A
Out[4]:
array([[ 68.83402637,  38.07632221],
       [ 76.84704074,  24.9395109 ],
       [ 16.26715795,  98.52763827],
       [ 70.99411985,  67.31740151],
       [ 71.72452181,  24.13516764],
       [ 17.22707611,  20.65425362],
       [ 43.85122458,  21.50624882],
       [ 76.71987125,  44.95031274],
       [ 63.77341073,  78.87417774],
       [  8.45828909,  30.18426696]])

In [5]: pt = [6, 30]  # <-- the point to find

In [6]: A[spatial.KDTree(A).query(pt)[1]] # <-- the nearest point 
Out[6]: array([  8.45828909,  30.18426696])

#how it works!
In [7]: distance,index = spatial.KDTree(A).query(pt)

In [8]: distance # <-- The distances to the nearest neighbors
Out[8]: 2.4651855048258393

In [9]: index # <-- The locations of the neighbors
Out[9]: 9

#then 
In [10]: A[index]
Out[10]: array([  8.45828909,  30.18426696])

解决方案 2：

scipy.spatial还有一个kd树的实现：scipy.spatial.KDTree。

该方法通常是首先使用点数据构建 kd 树。其计算复杂度约为 N log N，其中 N 是数据点的数量。然后可以以 log N 复杂度进行范围查询和最近邻搜索。这比简单地循环遍历所有点（复杂度为 N）要高效得多。

因此，如果您有重复范围或最近邻查询，强烈建议使用 kd 树。

解决方案 3：

如果您可以将数据调整为正确的格式，那么快速的方法是使用以下方法scipy.spatial.distance：

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

特别是pdist提供cdist计算成对距离的快速方法。

解决方案 4：

搜索方法分为两个阶段：

1. npt从数据点（你的x y）构建搜索结构，例如 KDTree

2. 查找nq查询点。

不同的方法有不同的构建时间和不同的查询时间。你的选择很大程度上取决于npt和nq：

scipy cdist
的构建时间为 0，但查询时间为 ~ npt * nq。KDTree

的构建时间很复杂，查找速度非常快，~ ln npt * nq。

在常规（曼哈顿）网格上，你可以做得更好：参见（咳咳）
find-nearest-value-in-numpy-array。

一个小型
测试台：：构建一个 5000×5000 个二维点的 KDTree 大约需要 30 秒，然后查询需要几微秒；
在我的旧 iMac 上， scipy cdist
2500 万×20 个点（所有对，4G）大约需要 5 秒。

解决方案 5：

我一直在尝试跟进这一点，但对 Jupyter Notebooks、Python 和这里讨论的各种工具还不熟悉，但我已经设法在路上取得了一些进展。

BURoute = pd.read_csv('C:/Users/andre/BUKP_1m.csv', header=None)
NGEPRoute = pd.read_csv('c:/Users/andre/N1-06.csv', header=None)

我从 BURoute 数据框创建了一个组合 XY 数组

combined_x_y_arrays = BURoute.iloc[:,[0,1]]

我使用以下命令创建点

points = NGEPRoute.iloc[:,[0,1]]

然后我施展 KDTree 魔法

def do_kdtree(combined_x_y_arrays, points): 
    mytree = scipy.spatial.cKDTree(combined_x_y_arrays)
    dist, indexes = mytree.query(points)
    return indexes

results2 = do_kdtree(combined_x_y_arrays, points)

这给了我一个索引数组。我现在想弄清楚如何计算点与结果数组中的索引点之间的距离。

解决方案 6：

def find_nearest_vector(self,arrList, value):
    
    y,x = value
    offset =10
    
    x_Array=[]
    y_Array=[]

    for p in arrList:
        x_Array.append(p[1])
        y_Array.append(p[0])
        

    x_Array=np.array(x_Array)
    y_Array=np.array(y_Array)


    difference_array_x = np.absolute(x_Array-x)
    difference_array_y = np.absolute(y_Array-y)

    index_x = np.where(difference_array_x<offset)[0]
    index_y = np.where(difference_array_y<offset)[0]


    index = np.intersect1d(index_x, index_y, assume_unique=True)

    nearestCootdinate = (arrList[index][0][0],arrList[index][0][1])
    

    return nearestCootdinate