识别具有最小欧几里得距离的点

Question

我有一组n维的点，我想找出其中两个点之间的距离最近。对于二维的情况，我想到的方法是：

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（v0.9）中的Delaunay三角剖分工具。这样可以确保最近的两个点会成为三角剖分中的一个边，这样比起检查所有可能的点对组合，处理的点对数量要少得多。

下面是代码（已更新为适用于一般的N维情况）：

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)：

Answer 2

关于这个问题，维基百科上有一整页的内容，看看这里： http://en.wikipedia.org/wiki/Closest_pair_of_points

简单来说，你可以通过一种递归的分治算法来达到 O(n log n) 的效率（这个算法在上面的维基页面上有介绍）。

Answer 3

试试 scipy.spatial.distance.pdist(myArr)。这个命令会给你一个压缩的距离矩阵。你可以在这个矩阵上使用 argmin，这样就能找到最小值的索引。然后你可以把这个索引转换成成对的信息。