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

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

` `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()` `

（几个月后） `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)` `

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

Interesting Posts