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