识别欧氏距离最小的点

Question

我有一个n维点的集合,我想找到哪两个是最接近的.我可以为2个维度做的最好的是:

from numpy import *
myArr = array( [[1, 2],
                [3, 4],
                [5, 6],
                [7, 8]] )

n = myArr.shape[0]
cross = [[sum( ( myArr[i] - myArr[j] ) ** 2 ), i, j]
         for i in xrange( n )
         for j in xrange( n )
         if i != j
         ]

print min( cross )

这使

[8, 0, 1]

但这对于大型阵列来说太慢了.我可以应用什么样的优化？

有关:

---

两个不同的Numpy阵列中的点之间的欧几里德距离,而不是在内

Answer 1

试试scipy.spatial.distance.pdist(myArr).这将为您提供精简距离矩阵.您可以使用argmin它并找到最小值的索引.这可以转换为配对信息.

Answer 2

关于这个问题,有一个完整的维基百科页面,请参阅:http: //en.wikipedia.org/wiki/Closest_pair_of_points

执行摘要:您可以使用递归分治算法实现O(n log n)(在上面的Wiki页面上概述).

Answer 3

您可以利用最新版本的SciPy(v0.9)Delaunay三角测量工具.您可以确定最接近的两个点将是三角测量中单形的边缘,这是一个比每个组合更小的对的子集.

这是代码(针对一般ND更新):

import numpy
from scipy import spatial

def closest_pts(pts):
    # set up the triangluataion
    # let Delaunay do the heavy lifting
    mesh = spatial.Delaunay(pts)

    # TODO: eliminate reduncant edges (numpy.unique?)
    edges = numpy.vstack((mesh.vertices[:,:dim], mesh.vertices[:,-dim:]))

    # the rest is easy
    x = mesh.points[edges[:,0]]
    y = mesh.points[edges[:,1]]

    dists = numpy.sum((x-y)**2, 1)
    idx = numpy.argmin(dists)

    return edges[idx]
    #print 'distance: ', dists[idx]
    #print 'coords:\n', pts[closest_verts]

dim = 3
N = 1000*dim
pts = numpy.random.random(N).reshape(N/dim, dim)

似乎O(n):