-4

I have an list of lists : 

[[0, 2], [1, 3], [2, 5], [3, 2], [4, 5]]

and a value in a list, for example : [4,0]

Imagine this to be xy-grid and i would like to find the closest value in the list of lists as possible. I have looked here Find nearest value in numpy array more exactly this line : idx = np.array([np.linalg.norm(x+y) for (x,y) in array-value]).argmin()

The problem is that it sum up x+y, so it would say that [1,3] is the closest one and it could be true in some cases but not all and in this specific case [3,2] is closer.

Please help.

Community
  • 1
  • 1
macbug
  • 121
  • 1
  • 7

1 Answers1

2
In [4]: arr = np.array([[0, 2], [1, 3], [2, 5], [3, 2], [4, 5]])

In [5]: value = np.array([4,0])

In [6]: np.linalg.norm(arr-value, axis=1)
Out[6]: array([ 4.47213595,  4.24264069,  5.38516481,  2.23606798,  5.        ])

In [7]: np.linalg.norm(arr-value, axis=1).argmin()
Out[7]: 3

In [8]: arr[np.linalg.norm(arr-value, axis=1).argmin()]
Out[8]: array([3, 2])

Note that if arr is very large and you need to compute the point in arr closest to many other points, it is more efficient to use a KDTree since once you have the data in the KDTree (which takes O(n log n) time), searching for the nearest point requires only O(log n) time. Using arr[norm(...).argmin()] requires O(n) time.

So if you have scipy, you could find the nearest point like this:

In [22]: from scipy import spatial

In [23]: tree = spatial.KDTree(arr)

In [24]: distances, indices = tree.query([4, 0])

In [25]: tree.data[indices]
Out[25]: array([3, 2])
unutbu
  • 842,883
  • 184
  • 1,785
  • 1,677