两个不同Numpy数组中的点之间的最小欧氏距离,不在

我有两个xy坐标数组,我想找出一个数组中每个点与另一个数组中的所有点之间的最小欧几里得距离。 数组不一定是相同的大小。 例如:

xy1=numpy.array( [[ 243, 3173], [ 525, 2997]]) xy2=numpy.array( [[ 682, 2644], [ 277, 2651], [ 396, 2640]]) 

我当前的方法遍历xy1每个坐标xy ,并计算该坐标和其他坐标之间的距离。

 mindist=numpy.zeros(len(xy1)) minid=numpy.zeros(len(xy1)) for i,xy in enumerate(xy1): dists=numpy.sqrt(numpy.sum((xy-xy2)**2,axis=1)) mindist[i],minid[i]=dists.min(),dists.argmin() 

有没有办法消除for循环,并以某种方式做两个数组之间的逐个元素的计算? 我设想生成一个距离matrix,我可以find每行或每列的最小元素。

另一种方法来看问题。 说我连接xy1 (长度m )和xy2 (长度p )到xy (长度n ),我存储了原始数组的长度。 从理论上讲,我应该能够从这些坐标中生成一个nxn距离matrix,从中我可以获取一个mxp子matrix。 有没有办法有效地生成这个子matrix?

    (几个月后) scipy.spatial.distance.cdist( X, Y )给出所有的距离对,对于X和Y 2 dim,3 dim …
    它也有22个不同的规范, 在这里详细。

     # cdist example: (nx,dim) (ny,dim) -> (nx,ny) from __future__ import division import sys import numpy as np from scipy.spatial.distance import cdist #............................................................................... dim = 10 nx = 1000 ny = 100 metric = "euclidean" seed = 1 # change these params in sh or ipython: run this.py dim=3 ... for arg in sys.argv[1:]: exec( arg ) np.random.seed(seed) np.set_printoptions( 2, threshold=100, edgeitems=10, suppress=True ) title = "%s dim %d nx %d ny %d metric %s" % ( __file__, dim, nx, ny, metric ) print "\n", title #............................................................................... X = np.random.uniform( 0, 1, size=(nx,dim) ) Y = np.random.uniform( 0, 1, size=(ny,dim) ) dist = cdist( X, Y, metric=metric ) # -> (nx, ny) distances #............................................................................... print "scipy.spatial.distance.cdist: X %s Y %s -> %s" % ( X.shape, Y.shape, dist.shape ) print "dist average %.3g +- %.2g" % (dist.mean(), dist.std()) print "check: dist[0,3] %.3g == cdist( [X[0]], [Y[3]] ) %.3g" % ( dist[0,3], cdist( [X[0]], [Y[3]] )) # (trivia: how do pairwise distances between uniform-random points in the unit cube # depend on the metric ? With the right scaling, not much at all: # L1 / dim ~ .33 +- .2/sqrt dim # L2 / sqrt dim ~ .4 +- .2/sqrt dim # Lmax / 2 ~ .4 +- .2/sqrt dim 

    要通过距离matrix来计算m,这应该工作:

     >>> def distances(xy1, xy2): ... d0 = numpy.subtract.outer(xy1[:,0], xy2[:,0]) ... d1 = numpy.subtract.outer(xy1[:,1], xy2[:,1]) ... return numpy.hypot(d0, d1) 

    .outer调用使得两个这样的matrix(沿着两个轴的标量差),这些.hypot调用将这些matrix转换成相同形状的matrix(标量欧几里得距离)。

    对于你想要做的事情:

     dists = numpy.sqrt((xy1[:, 0, numpy.newaxis] - xy2[:, 0])**2 + (xy1[:, 1, numpy.newaxis - xy2[:, 1])**2) mindist = numpy.min(dists, axis=1) minid = numpy.argmin(dists, axis=1) 

    编辑 :而不是调用sqrt ,做广场等,你可以使用numpy.hypot

     dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1]) 
     import numpy as np P = np.add.outer(np.sum(xy1**2, axis=1), np.sum(xy2**2, axis=1)) N = np.dot(xy1, xy2.T) dists = np.sqrt(P - 2*N) 

    接受的答案没有完全解决这个问题,它要求find两组点之间的最小距离,而不是两组中的一点之间的距离。

    尽pipe原始问题的直接解决scheme确实包括计算每一对之间的距离,然后find最小的一个,但是如果只对最小距离感兴趣,则这是不必要的。 后一个问题存在更快的解决scheme。

    所有提出的解决scheme都有一个运行时间,其规模为m*p = len(xy1)*len(xy2) 。 这对于小数据集是可以的,但是可以写成一个最佳解决scheme,其尺寸为m*log(p) ,为大型xy2数据集节省大量资金。

    这个最佳执行时间缩放可以使用scipy.spatial.cKDTree如下来实现

     import numpy as np from scipy import spatial xy1 = np.array( [[243, 3173], [525, 2997]]) xy2 = np.array( [[682, 2644], [277, 2651], [396, 2640]]) # This solution is optimal when xy2 is very large tree = spatial.cKDTree(xy2) mindist, minid = tree.query(xy1) print(mindist) # This solution by @denis is OK for small xy2 mindist = np.min(spatial.distance.cdist(xy1, xy2), axis=1) print(mindist) 

    其中mindistmindist中的每个点与xy1的点集之间的最小距离