4

I have two lists with tuples (coordinates), for example:

some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
  • each value in the tuples is a flat
  • the lists are not in the same length

I what to find the two closest points between the two lists. I don't know how, maybe it is possible to do it using distances. I hope there is a more efficient way to do this cause I need this function to work as fast as possible (it is a part of something bigger).

Rakesh
  • 81,458
  • 17
  • 76
  • 113
eran halperin
  • 192
  • 1
  • 12

4 Answers4

2

Alternatively, by taking reference Tim Seed's code. this can be used.

from scipy.spatial import distance
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]

empthy_dict = {}
for i in range(len(some_pt1)):
    for j in range(len(some_pt2)):
        dist = distance.euclidean(some_pt1[i],some_pt2[j])
        empthy_dict[dist] = [some_pt1[i],some_pt2[j]]

shortest = sorted(empthy_dict.keys())[0]
points = empthy_dict[shortest]
print('Shortest distance is ' ,shortest,' and points are ' ,points)
demirbilek
  • 331
  • 1
  • 11
1

How about this

from pprint import pprint

some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]


distance = {}
for x in some_pt1:
    for y in some_pt2:
        dist =abs(abs(x[0])-abs(y[0]))+abs(abs(x[1])-abs(y[1]))
        distance[dist]=[x,y]

shortest =sorted(distance.keys())[0]
print("Min Distance is {} Objects are  {} {} ".format(shortest, distance[shortest][0],distance[shortest][0]))
Tim Seed
  • 5,119
  • 2
  • 30
  • 26
0

In any case you need to do all posible combinations, there are algorithms out there that can help you do it in the best order or avoiding repeating distances. If you want to do it fast you should use a special library that helps compiling with the or precompiling the arrays, this could be done with Numba or Cython. Other libraries such as scipy have special modules suh as scipy.spatial.distance. Look at this post for more doubts similar cuestion.

Example:

import scipy.spatial.distance as sd
import numpy as np
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
np.unravel_index(np.argmin(sd.cdist(some_pt1, some_pt2)), (len(some_pt1), len(some_pt2)))

results: (2, 4)

This code would return the position in the first list and in the second.

Jorge Rodriguez Molinuevo
  • 505
  • 1
  • 4
  • 14
0

By Euclidian distance:

>>> some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
>>> some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
>>> 
>>> def dist_sq(p1_p2):
...     p1, p2 = p1_p2
...     return sum(x*y for x,y in zip(p1, p2))
... 
>>> 
>>> min(((p1, p2) for p1 in some_pt1 for p2 in some_pt2), key=dist_sq)
((3.24, 4.28), (6.91, 0.56))

Which has runtime O(n*m) (where n, m are the lengths of your lists). Since you need to look at all the pairs, it won't get better than this.

Note that comparing the squared distances is enough, no need to compute the root.

timgeb
  • 76,762
  • 20
  • 123
  • 145
  • Thanks, That looks like it could do the job good, but it makes me ask: is there any other way to do it more efficiently then by chacking every single one cause the real lists that I will have will be long and may have points that are extremely far. – eran halperin Apr 13 '18 at 07:57
  • @eranhalperin no, you can't reduce the complexity of the algorithm. You can make it faster with `numpy` and other techniques mentioned by Jorge Rodriguez Molinuevo but you need to compare every pair. – timgeb Apr 13 '18 at 07:59
  • Okay, so how do I use numpy (for example) to make it work faster – eran halperin Apr 13 '18 at 08:02