CODEWITHSUNDEEP
pythonsearchcoordinateshaversine
cheva
cheva

Reputation: 25

Nearest coordinate of a route to a given point using search algorithm (python)

I have routes that are represented in form of coordinates with lat/long. Depending on the length of the route it might have 100 or even 800 coordinates. Then I have a specific coordinate again with lat/lon which represents my location. What I'm trying to do is to find the nearest point(coordinate) on the route to my location. I can do this with the haversine formula calculating the distance of each point in the route to my location and take the minimum, but this may take too long because some routes are really long and there are a lot of points to compare with. Is there a search algorithm that can help solving this problem? I did a research on the golden section search but couldn't be sure if this is what I was looking for.

Upvotes: 0

Views: 688

Answers (1)

David Blankm
David Blankm

Reputation: 26

I can think of two ways you could solve this. One would be to create a K-D tree for each of the routes, and query your new coordinate point in each tree to search for the nearest point. Check sci-kit KDTree

Another simpler possibility is that you create each route as an array, use some metric between your point and each array and find the one where the metric is minimum, e.g. using the Euclidean distance

import numpy as np
from sklearn.metrics import euclidean_distances

x = np.array([[0.1, 0.5]])
route = np.random.rand((10,2))

array([[0.78275588, 0.92844543],
       [0.30066744, 0.21161873],
       [0.95533462, 0.11647814],
       [0.37786273, 0.58306683],
       [0.86670199, 0.90861542],
       [0.68658895, 0.60087646],
       [0.19966574, 0.57160265],
       [0.34182302, 0.02809684],
       [0.08862117, 0.89459785],
       [0.18083728, 0.39331416]])

dist = euclidean_distances(x,route)

array([[0.80605278, 0.35132774, 0.9373827 , 0.29001344, 0.8687914 ,
        0.59519968, 0.12272001, 0.53025557, 0.39476188, 0.13385266]])

Then if we get the argmin, as you can see the closest point is the 6th element

np.argmin(euclidean_distances(x,route))
6

Upvotes: 1

Related Questions