求numpy x和y坐标数组中最近点的索引

mcdcgff0 于 2023-01-17 发布在其他

关注(0)|答案(6)|浏览(137)

我有两个二维numpy数组：x_array包含x方向上的位置信息，y_array包含y方向上的位置。
这样我就有了一长串的x，y点。
对于列表中的每个点，我需要找到最接近该点的位置（在数组中指定）的数组索引。
基于这个问题，我天真地编写了一些代码：Find nearest value in numpy array
即

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

我在一个大数据集上做这件事，真的想加快一点。有人能优化它吗？
谢谢。
更新：根据@silvado和@justin（下文）的建议提供的解决方案

# Shoe-horn existing data for entry into KDTree routines
combined_x_y_arrays = numpy.dstack([y_array.ravel(),x_array.ravel()])[0]
points_list = list(points.transpose())

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

start = time.time()
results2 = do_kdtree(combined_x_y_arrays,points_list)
end = time.time()
print 'Completed in: ',end-start

上面这段代码将我的代码（在100x100矩阵中搜索5000个点）的速度提高了100倍，有趣的是，使用scipy.spatial.KDTree（而不是scipy.spatial.cKDTree）与我的简单解决方案相比，其时间相当，因此使用cKDTree版本是绝对值得的......

numpy

来源：https://stackoverflow.com/questions/10818546/finding-index-of-nearest-point-in-numpy-arrays-of-x-and-y-coordinates

6条答案

按热度按时间

wdebmtf21#

下面是一个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])

赞(0）回复(0）举报 2023-01-17

yhuiod9q2#

scipy.spatial也具有k-d树实现：scipy.spatial.KDTree.
一般来说，方法是先用点数据建立一棵k-d树。计算复杂度约为NlogN，其中N是数据点的数目。然后，范围查询和最近邻搜索可以以logN的复杂度进行。这比简单地循环遍历所有点（复杂度N）效率高得多。
因此，如果您有重复的范围或最近邻查询，强烈建议使用k-d树。

赞(0）回复(0）举报 2023-01-17

x4shl7ld3#

如果您可以将数据转换为正确的格式，一个快速的方法是使用scipy.spatial.distance中的方法：
http://docs.scipy.org/doc/scipy/reference/spatial.distance.html
特别地，pdist和cdist提供了计算成对距离的快速方式。

赞(0）回复(0）举报 2023-01-17

aamkag614#

搜索方法有两个阶段：
1.从npt数据点（您的x y）构建搜索结构，例如KDTree
1.查找nq个查询点。
不同的方法有不同的构建时间和不同的查询时间。您的选择将在很大程度上取决于npt和nq：
scipy cdist的构建时间为0，但查询时间约为npt * nq。
KDTree的构建时间很复杂，查找速度非常快，大约ln npt * nq。
在常规（Manhatten）栅格上，您可以做得更好：参见（ahem）查找数字数组中的最近值。
一个小测试台：：建立一个5000 × 5000个二维点的KDTree需要30秒左右，查询则需要微秒;scipy cdist 2500万× 20个点（所有配对，4G）大约需要5秒钟，在我的旧iMac上。

赞(0）回复(0）举报 2023-01-17

rt4zxlrg5#

我一直在努力跟上这一点，但对Jupyter笔记本、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 Dataframe 创建了组合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)

这给了我一个索引数组，现在我试着找出如何计算结果数组中的点和索引点之间的距离。

赞(0）回复(0）举报 2023-01-17

ha5z0ras6#

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

赞(0）回复(0）举报 2023-01-17

我来回答

求numpy x和y坐标数组中最近点的索引

6条答案

相关问题

热门标签

最新问答