2

I hope this is not a ridiculously stupid question but I can't seem to come up with an immediate algorithm for this:

I have a list of (lat,lng), which represent a list of waypoints on a map. At any point the user can click on the map and create a new waypoint corresponding to that new (lat,lng) coordinate. The waypoints correspond to a flight path to follow, and I potentially have thousands of waypoints already defined. The new waypoint needs to be inserted in between the 2 closest waypoints already defined in the list of waypoints. This needs to be done as efficiently as possible.

One option would be to calculate the great circle distance between the new waypoint and the all the previously defined waypoints, and then add the new waypoint in between the 2 closest.

I was wondering if there is a better algorithm for this? Any pointers to efficient/fast algorithms would be very helpful

1

I think what you need is an R-tree. It's a form of spatial indexing. There are other spatial indexing algs too. Just run a Google search

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.