Get closest coordinate in 2D array

user_7024856 0
Viewed 3708
coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]

xy = (-222.4, -204.5)

What is the best way so that a given value xy can be compared to a 2D list of coordinates, and return the index number of the closest coordinate?

In this example, xy would be compared to the coordinates list and thus return the closest coordinate (-225.0, -299.5) or, more ideally, the index number 0.

I've tried researching for a method with itertools or numpy, but couldn't seem to understand how to get the result I want in my example.

itertools multidimensional-array coordinates list python
4 Answers

Using scipy.spatial.KDTree:

from scipy import spatial
import numpy as np
coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
x = [(-222.4, -204.5)]
distance,index = spatial.KDTree(coordinates).query(x)
print(distance)
print(index)

The kd-tree method is O(N*log(N)) and is much faster than Brute Force method that takes O(N**2) time for large enough N.

user_105188080

You can use min with a proper key function. Sth along the following lines for instance:

coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
xy = (-222.4, -204.5)

dist = lambda x, y: (x[0]-y[0])**2 + (x[1]-y[1])**2
min(coordinates, key=lambda co: dist(co, xy))
# (-225.0, -299.5)
user_23901820

Your question is equivalent to : How do I sort a Python list using a custom method to define the sorting key. This can be done in raw python without using external libraries.

When using the sorted() function of python you can pass a lambda to the key argument to get the sort done on a specific key.

From there you just have to define the key as your own distance calculation method (here using the distances between the points):

from math import *
coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
xy = (-222.4, -204.5)
results = sorted(coordinates, key= lambda v: sqrt(pow((v[0] - xy[0]), 2) + pow((v[1] - xy[1]), 2)))
# Output : [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]

From there you can just take the first element of the list if you want the closer point, etc. If you still want to external module I think you can use some third parties function such as from scipy.spatial import distance as the key parameter of the sort.

user_106069110

You could simply create a function that iterates through the list of coordinates and keep the index of the one in which the distance between two points is the smallest (using the Pythagorean theorem).

However, if you need something fast given by an external module rather than writing your own, I am not aware of libraries I already used that already have that function, so I'm not helpful here.

user_105958340
Related