使用 Python 查找最接近的 coordinates/tuples 对

Finding the closest pair of coordinates/tuples using Python

我一直在尝试从元组列表中找到最接近的两个 points/coordinates/tuples。

例如,如果函数 nearest_neighbor() 的输入列表如下所示:

[(1, 2), (4, 5), (5, 5), (4, 1)]

函数应该return如下:

(4, 5), (5, 5)

下面是我的尝试,但不幸的是我无法让它工作。

import numpy as np
A = [(1, 2), (4, 5), (5, 5), (4, 1)]
A = np.array(A)
len = []
for i in range((len(A)):
  leftbottom = np.array(A[i])
  distances = np.linalg.norm(A-leftbottom, axis=1)
  min_index = np.argmin(distances)
  len.append(distances[min_index])

print(f"the closest point is {len.min()}")

正如@Frank Yellin 指出的那样,distances = np.linalg.norm(A-leftbottom, axis=1) 行正在计算 matrix norm,而不是向量范数。您甚至可以在不使用 numpy 的情况下获得问题的解决方案,这是我的 O(n^2) 解决方案:

def nearest_neighbours(tup):
    smallest_dist = None
    first = None
    second = None
    for i in range(len(tup)-1):
        for j in range(i+1, len(tup)):
            dist = (tup[i][0]-tup[j][0])**2 + (tup[i][1]-tup[j][1])**2
            if smallest_dist is None or dist < smallest_dist:
                smallest_dist = dist
                first = tup[i]
                second = tup[j]
    return first, second

不使用numpy的解决方案:

from itertools import combinations
import math

A = [(1, 2), (4, 5), (5, 5), (4, 1)]

def distance(p1, p2):
    d1 = p2[0] - p1[0]
    d2 = p2[1] - p1[1]
    return math.sqrt(d1**2 + d2**2)

closest_points = None
min_dist = float('inf')

for p1, p2 in combinations(A, 2):
    dist = distance(p1,p2)

    if dist < min_dist:
        closest_points = (p1,p2)
        min_dist = dist

print(f"the closest points are {closest_points}")

您的代码中有很多错误。首先你定义 len 为一个列表,然后尝试调用内置的 len 函数来计算数组 A 的长度。另一个问题是当你计算两点之间的距离时,你必须检查它们是否相同。距离的最小值也没有给出两点,它只有 return 距离。

import numpy as np
A=np.array([(1,2),(4,5),(5,5),(4,1)])
l=[]
min_dist=np.linalg.norm(A[0]-A[i])# initialising minimum distance
closest_pts=(A[0],A[1] )# initialising closest points

for i in range(len(A)):
  pt_i=A[i]
  pts_rest=np.delete(A,i,axis=0)#creates another array without the ith element
  distances=np.linalg.norm(pts_rest-pt_i,axis=1)
  
  if min_dist>min(distances):
    min_index=np.argmin(distances)
    pt_j=pts_rest[min_index]
    closest_pts=(list(pt_i),list(pt_j))

print(f"The closest points are {closest_pts}")