Find minimum distance between points of two lists in Python

Question

I have two lists of coordinates:

s1 = [(0,0), (0,1), (1,0), (1,1)] s2 = [(3,2), (1,9)] 

I want to calculate the minimum distance of each point in s1 to any point in s2. for example, the results should be as follows.

 result = [3.60, 3.16, 2.82, 2.23] 

Question: What is the most optimized way in terms of runtime to achieve this result?

So far I have tried this, but the runtime does not promise:

 import math def nearestDistance(boundary, p): minDistList = map(lambda b: (b[0] - p[0])**2 + (b[1] - p[1])**2, boundary) minDist2 = min(minDistList) return math.sqrt(float(minDist2)) d = [] for p in s1: d.append(nearestDistance(s2, p)) 

Should I change the structure of s1 and s2 (instead of points, use 2d arrays, for example)?

Answer 1

The easiest way is to use scipy.spatial.distance.cdist :

 import numpy as np from scipy.spatial import distance s1 = np.array([(0,0), (0,1), (1,0), (1,1)]) s2 = np.array([(3,2), (1,9)]) print(distance.cdist(s1,s2).min(axis=1)) # array([3.60555128, 3.16227766, 2.82842712, 2.23606798]) 

Another speed can be obtained by directly outputting 0 for any point from s1 , which is also located in s2 .

Answer 2

Have you tried using cdist :

 import numpy as np from scipy.spatial.distance import cdist np.min(cdist(s1,s2)) 

returns

 array([ 3.60555128, 3.16227766, 2.82842712, 2.23606798]) 

You can also get a performance boost by replacing s1 and s2 with np.array s, although scipy can do this internally, I'm not sure.

If this is not optimized enough, I think you can do it in O (n _s2 * log (n _s2 ) + n _s1 ) by finding the Voronoi diagram of points in s2 , and then going through s1 to see which area the point falls into which will correspond to the nearest point in s2 .

Answer 3

To compute N distances, there is no better method than a rough one, forcing all the possibilities. If you need some kind of higher level, for example, the largest or minimum distance is possible, you can reduce the number of calculations based on some external knowledge, but, given your setup, the best thing you are going to get is O (n ^ 2 performance )

EDIT: Given your comment, there are methods that include a general divide and conquer approach. Wikipedia has a good overview , and I will copy, perhaps, the corresponding bit here:

The problem can be solved in O (n log n) time using the approach of recursive division and subjugation, for example, as follows:

• Sort points according to their x coordinates.
• Divide the set of points into two subsets of equal size along the vertical line x = x _mid .
• Solve the problem recursively in the left and right subsets. This gives the minimum distances left and right on the side d _Lmin and d _Rmin , respectively.
• Find the minimum distance d _LRmin among the set of pairs of points at which one point lies to the left of the dividing vertical and the other point lies to the right.
• The final answer is the minimum of d _Lmin , d _Rmin and d _LRmin .

Answer 4

Brute force is truly the main path. You can get performance compression using KDTree, since your data is low in size. scipy.spatial.KDTree

 kdtree = scipy.spatial.KDTree(s2) neighbours = kdtree.query(s1)