为了找到最近的点，我在实现函数的时候遇到了麻烦，我试过多种方法，但似乎就是想不通。有什么想法，我应该如何去解决？
欧氏距离
def dist(p1, p2):
x1, y1 = p1
x2, y2 = p2
dis = sqrt((x1-x2)**2 + (y1-y2)**2)
return dis
功能
def offices_to_merge(points):
min_p1 = 0
min_p2 = 1
for i in range(len(points)):
for j in range(i+1, len(points)):
dis = dist(points[i], points[j])
if dis < min((dis)) :
min_p1 = i
min_p2 = j
return (min_p1, min_p2)
>>> points = [(350, 150), (500, 250), (150, 150), (50, 400), (200, 100)]
>>> offices_to_merge(points)
(2, 4)
你的代码的问题是，当你在点间迭代时，你没有跟踪观察到的当前最小距离。
def dist(p1, p2):
x1, y1 = p1
x2, y2 = p2
dis = ((x1-x2)**2 + (y1-y2)**2)**0.5
return dis
def offices_to_merge(points):
current_minimum = float('inf')
min_p1 = -1
min_p2 = -1
for i in range(len(points)):
for j in range(i+1, len(points)):
dis = dist(points[i], points[j])
if dis < current_minimum:
min_p1 = i
min_p2 = j
current_minimum = dis
return (min_p1, min_p2)
points = [(350, 150), (500, 250), (150, 150), (50, 400), (200, 100)]
print( offices_to_merge(points) )
Prints:
(2, 4)
你可以使用 cdist 以求得所有 points:
from scipy.spatial.distance import cdist
import numpy as np
points = [(350, 150), (500, 250), (150, 150), (50, 400), (200, 100)]
# calculate all distances between two sets of points
dists = cdist(points, points)
# the self distance is 0 -> we don't want this so make it large
dists[dists == 0] = dists.max()
# get index of smallest distance
np.unravel_index(dists.argmin(), dists.shape)
>>> (2, 4)
你可以使用组合来查看所有可能的位置对。然后计算所有的距离，取最小值，并确定产生最小值的那对点的指数。
from numpy import sqrt
from itertools import combinations
def dist(p1, p2):
x1, y1 = p1
x2, y2 = p2
dis = sqrt((x1-x2)**2 + (y1-y2)**2)
return dis
points = [(350, 150), (500, 250), (150, 150), (50, 400), (200, 100)]
a = list(combinations(points, 2)) # combinations
b = [dist(el1,el2) for el1,el2 in a] # distances
idx = b.index(min(b)) # index of the min
print(a[idx])
如果你的点列表很大，用蛮力的方法将每一个时间复杂度为O(N^2)的点进行配对，会很快成为性能瓶颈。
有一种方法可以在O(NlogN)时间内得到结果，即根据点到任意基点的距离进行排序，该基点比其他所有点都要小（即下面和左边）。 通过这种排序的方法，可以将点的解析限制在目前发现的最短距离范围内的点。
下面是一个例子。
def dist(a,b): return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
def nearest2(points):
minP1,minP2 = points[:2]
minDist = dist(minP1,minP2)
base = tuple(map(min,zip(*points)))
sPoints = sorted((dist(base,p),p) for p in points)
iMin = 0
for ix,(xDist,px) in enumerate(sPoints[1:],1):
for i,(iDist,pi) in enumerate(sPoints[iMin:ix],iMin):
if iDist + minDist <= xDist: iMin = i+1; continue
if dist(px,pi) >= minDist: continue
minP1,minP2 = px,pi
minDist = dist(minP1,minP2)
return minP1,minP2
这个函数将返回两个比列表中任何其他点对更接近的点。请注意，如果 dist()函数是三维距离计算，那么 nearest2()函数将适用于三维空间的点列表
print(nearest2(points))
((200, 100), (150, 150))
为了便于比较，下面是一个蛮力方法的样子（类似于你的函数）。
def bruteForce(points):
minP1,minP2 = points[:2]
minDist = dist(minP1,minP2)
for i,p1 in enumerate(points[:-1]):
for p2 in points[i+1:]:
if dist(p1,p2) >= minDist: continue
minP1,minP2 = p1,p2
minDist = dist(minP1,minP2)
return minP1,minP2
测量性能差异（1000点）说明了基于排序的方法的好处。
from random import randint
from timeit import timeit
count = 1
points = list(set( (randint(0,10000),randint(0,10000)*10) for _ in range(1000)))
t = timeit(lambda:nearest2(points),number=count)
print("nearest2 ",t) # 0.0022362289999999785
t = timeit(lambda:bruteForce(points),number=count)
print("bruteForce",t) # 0.36930638299999996
速度快了150多倍，而且随着积分的增加，差异会更大。
如果你需要列表中的索引，而不是点本身，你可以改编nearest2()函数，或者把它包在一个函数中，从结果的点对中找到索引。
def nearest2Index(points):
p1,p2 = nearest2(points) # bruteForce(points)
iP1 = points.index(p1)
iP2 = points.index(p2)
if iP1 == iP2: iP2 += points[iP1+1:].index(p2) + 1
if iP1>iP2: iP1,iP2 = iP2,iP1
return iP1,iP2
points = [(350, 150), (500, 250), (150, 150), (50, 400), (200, 100)]
print(nearest2Index(points)) # (2,4)