我有两个x-y坐标数组,我想找到一个数组中每个点与另一个数组中所有点之间的最小欧几里德距离 . 阵列的大小不一定相同 . 例如:
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循环,并以某种方式在两个数组之间进行逐元素计算?我设想生成一个距离矩阵,我可以在其中找到每行或每列中的最小元素 .
另一种看待问题的方法 . 假设我将 xy1
(长度为m)和 xy2
(长度为p)连接成 xy
(长度为n),并存储原始数组的长度 . 从理论上讲,我应该能够从那些坐标中生成一个n×n距离矩阵,我可以从中获取一个m×p子矩阵 . 有没有办法有效地生成这个子矩阵?
5 回答
(几个月后)
scipy.spatial.distance.cdist( X, Y )
给出所有距离对,X和Y 2 dim,3 dim ......它还有22种不同的规范,详细here .
要计算m乘以距离的矩阵,这应该工作:
.outer
调用产生两个这样的矩阵(沿着两个轴的标量差异),.hypot
调用将它们变成相同形状的矩阵(标量欧氏距离) .接受的答案并没有完全解决这个问题,它要求找到两组点之间的距离,而不是两组中的点之间的距离 . {1844518_} .
尽管原始问题的直接解决方案确实包括计算 every 对之间的距离并随后找到最小值,但如果只对 minimum 距离感兴趣,则不需要这样做 . 对于后一个问题,存在更快的解决方案 .
所有提出的解决方案都有一个运行时间,可以扩展为
m*p = len(xy1)*len(xy2)
. 对于小型数据集来说这是可以的,但是可以编写一个最佳解决方案,可以扩展为m*log(p)
,从而为大型数据集节省了大量资金 .可以使用scipy.spatial.cKDTree如下实现该最佳执行时间缩放
其中
mindist
是xy1
中每个点与xy2
中的点集之间的最小距离对于你想要做的事情:
编辑:您可以使用
numpy.hypot
代替调用sqrt
,做方格等 .