# How to determine relative position of a new waypoint in an array of waypoints?

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

• Take a look into R-Trees en.wikipedia.org/wiki/R-tree Commented Aug 25, 2017 at 14:37
• @firefly-orangeThanks for the link! If you add your comment as an answer I will accept it! :) Commented Aug 25, 2017 at 14:40