Finding the closest pair of coordinates/tuples using Python-CodePudding

I have been trying to find the two closest points/coordinates/tuples from a list of tuples.

For instance, if the input list to function nearest_neighbor() is like below:

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

The function should return the below:

(4, 5), (5, 5)

Below is my try, but unfortunately I am unable to get it working.

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()}")

CodePudding user response：

As @Frank Yellin pointed out, the line distances = np.linalg.norm(A-leftbottom, axis=1) is calculating a matrix norm, not a vector norm. You can get a solution to your problem without even using numpy, here is my O(n^2) solution:

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

CodePudding user response：

A solution that doesn't use 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}")

CodePudding user response：

There are many errors in your code. First you have defined len to be a list and then tried to call inbuilt len function to compute the length of array A. Another problem is that when you are calculating distance between two points, you have to check whether they are the same or not. Also minimum of the distances does not give the two points, it only return the distance.

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}")