从列表中选择最接近的一对

Question

我有一个列表，比如说：

[(35.9879845760485, -4.74093235801354), (35.9888687992442, -4.72708076713794),
(35.9889733432982, -4.72758983150694), (35.9915751019521, -4.72772881198689), 
(35.9935223025608, -4.72814213543564), (35.9941433944962, -4.72867416528065), 
(35.9946670576458, -4.72915181755908), (35.995946587966, -4.73005565674077), 
(35.9961479762973, -4.7306870912609), (35.9963563641681, -4.7313535758683), 
(35.9968685892892, -4.73182757975504), (35.9976738530666, -4.73194429867996) ]

还有一个坐标 coord = (35.9945570576458, -4.73110757975504)

我想从这个 list 中找出离这个 coord 最近的那一对。

Answer 1

如果点的列表不太大，使用线性搜索就可以解决问题：

def dist_sq(a, b): # distance squared (don't need the square root)
  return (a[0] - b[0])**2 + (a[1] - b[1])**2

def find(l, coord):
  return min(l, key=lambda p:dist_sq(coord, p))

l = [(35.9879845760485, -4.74093235801354), (35.9888687992442, -4.72708076713794), (35.9889733432982, -4.72758983150694), (35.9915751019521, -4.72772881198689), (35.9935223025608, -4.72814213543564), (35.9941433944962, -4.72867416528065), (35.9946670576458, -4.72915181755908), (35.995946587966, -4.73005565674077), (35.9961479762973, -4.7306870912609), (35.9963563641681, -4.7313535758683), (35.9968685892892, -4.73182757975504), (35.9976738530666, -4.73194429867996) ]
coord = (35.9945570576458, -4.73110757975504)

print find(l, coord)

用 numpy 实现同样的解决方案：

import numpy as np
l = np.array([(35.9879845760485, -4.74093235801354), (35.9888687992442, -4.72708076713794), (35.9889733432982, -4.72758983150694), (35.9915751019521, -4.72772881198689), (35.9935223025608, -4.72814213543564), (35.9941433944962, -4.72867416528065), (35.9946670576458, -4.72915181755908), (35.995946587966, -4.73005565674077), (35.9961479762973, -4.7306870912609), (35.9963563641681, -4.7313535758683), (35.9968685892892, -4.73182757975504), (35.9976738530666, -4.73194429867996) ])
coord = np.array((35.9945570576458, -4.73110757975504))
print l[np.argmin(np.apply_along_axis(np.linalg.norm, 1, l - coord))]

如果这样做不太可行，我建议你看看一些更好的算法方法。

Answer 2

你还可以使用一个叫做 scipy cKDTree 的工具，它可以帮助你在数组中找到最近的邻居。这个方法在处理很多点的时候，比起逐个检查每个点会更快一些：

import numpy
from scipy.spatial import cKDTree

data = numpy.array([(35.9879845760485, -4.74093235801354), (35.9888687992442,
-4.72708076713794), (35.9889733432982, -4.72758983150694), (35.9915751019521,
-4.72772881198689), (35.9935223025608, -4.72814213543564), (35.9941433944962,
-4.72867416528065), (35.9946670576458, -4.72915181755908), (35.995946587966,
-4.73005565674077), (35.9961479762973, -4.7306870912609), (35.9963563641681,
-4.7313535758683), (35.9968685892892, -4.73182757975504), (35.9976738530666,
-4.73194429867996) ])

tree = cKDTree(data)
dists, indexes = tree.query(numpy.array([35.9945570576458, -4.73110757975504]), k=3)
for dist, index in zip(dists, indexes):
    print 'distance %f:  %s' % (dist, data[index])

输出结果：

distance 0.001646:  [ 35.99614798  -4.73068709]
distance 0.001743:  [ 35.99594659  -4.73005566]
distance 0.001816:  [ 35.99635636  -4.73135358]

Answer 3

编写一个计算距离的函数，并使用内置的 min 函数，配合键参数来找到最小值。

>>> from functools import partial
>>> dist=lambda s,d: (s[0]-d[0])**2+(s[1]-d[1])**2 #a little function which calculates the distance between two coordinates
>>> a=[(35.9879845760485, -4.74093235801354), (35.9888687992442, -4.72708076713794), ..... ]
>>> coord = (35.9945570576458, -4.73110757975504)
>>> min(a, key=partial(dist, coord)) #find the min value using the distance function with coord parameter
(35.9961479762973, -4.7306870912609)