Encontrar eficientemente el par de coordenadas más cercano de un conjunto en Python
El problema
Imagina que estoy parado en un aeropuerto. Dado un par de coordenadas geográficas, ¿cómo se puede determinar eficientemente en qué aeropuerto estoy parado?
Entradas
Un par de coordenadas(x,y)
representando la ubicación en la que estoy parado.Un conjunto de pares de coordenadas.[(a1,b1), (a2,b2)...]
donde cada par de coordenadas representa un aeropuerto.Salida deseada
Un par de coordenadas(a,b)
del conjunto de pares de coordenadas del aeropuerto que representan el aeropuerto más cercano al punto(x,y)
.
Solución ineficiente
Aquí está mi intento ineficiente para resolver este problema. Es claramente lineal en la longitud del conjunto de aeropuertos.
shortest_distance = None
shortest_distance_coordinates = None
point = (50.776435, -0.146834)
for airport in airports:
distance = compute_distance(point, airport)
if distance < shortest_distance or shortest_distance is None:
shortest_distance = distance
shortest_distance_coordinates = airport
La pregunta
¿Cómo se puede mejorar esta solución? Esto podría implicar alguna forma de prefiltrar la lista de aeropuertos en función de las coordenadas de la ubicación en la que nos encontramos actualmente, o clasificarlos de antemano en un cierto orden.