Algoritmo para encontrar el punto más cercano

18

Tengo una lista de unos cientos de ciudades con su latitud / longitud. Dada otra ubicación (también en lat / long) necesito encontrar la ciudad más cercana.

Como no uso ningún SIG, el algoritmo obvio ahora es hacer un bucle para todas las ciudades, calculando la distancia entre los puntos.

Hacer el bucle es factible para mí, pero ¿hay algún algoritmo fácil de implementar para lograrlo de manera más eficiente? ¿O alguna biblioteca Java ligera que pueda ayudar a resolver eso?

Notas : No necesito / quiero una solución SIG completa o una biblioteca pesada / complicada. Prefiero una solución menos buena pero más fácil y más ligera porque eso es lo único que necesito resolver.

lujop
fuente
¿Entonces no importa que la distancia no sea correcta? ¿Y no desea tener en cuenta las carreteras que pueden hacer que una ciudad esté más lejos que otra (diagonal versus cuadrada)?
Brad Nesom el
Sí, los caminos no son importantes para mí. Necesito la ciudad más cercana en distancia lineal porque es para predicciones meteorológicas.
lujop
1
Predicciones del tiempo? Espero que tenga una supercomputadora y un equipo de meteorólogos capacitados a su disposición.
Michael Todd
Las predicciones están hechas Michael, solo tengo que tomar la más cercana :)
lujop

Respuestas:

24

Investigué exactamente esta pregunta hace 20 años cuando diseñé un SIG de escritorio. Necesitábamos encontrar distancias punto a punto de manera interactiva; Nuestro objetivo era hacer los cálculos en menos de 1/2 segundo para miles de puntos. Las pruebas (¡en una PC 486 de 25 MHz!) Demostraron que podíamos calcular todas las distancias, exactamente como usted describe (con el algoritmo simple y obvio), tan rápido que no tenía sentido crear una solución más sofisticada, como una estructura quadtree .

Para calcular distancias a un solo punto de "sonda", sus opciones incluyen (a) proyectar todos los puntos usando una proyección equidistante centrada en el punto de la sonda o (b) adoptar un modelo de tierra esférica y usar la fórmula de Haversine . El primero es apropiado si necesita la precisión de un modelo elipsoidal. En cualquier caso, los cálculos son razonablemente rápidos, probablemente con menos de 1000 ticks: puede consultar alrededor de un millón de puntos por segundo con un solo procesador.

¿Lo suficientemente rápido para ti? De lo contrario, el método de fuerza bruta se paraleliza fácilmente y se escala directamente con el número de procesadores: simplemente divida los puntos entre los procesadores y luego haga una comparación final del más cercano encontrado por cada procesador.

Si necesita ir más rápido, puede usar varias aproximaciones para puntos de pantalla. Por ejemplo, si está entre -88 y +88 grados de latitud y el punto más cercano encontrado hasta ahora está a 200 km de distancia, entonces cualquier punto cuya latitud difiera de la latitud del punto de la sonda en más de 2 grados no puede estar más cerca (porque en cualquier lugar del tierra, un grado de latitud supera los 110 km). En muchos casos, este tipo de preselección podría permitirle procesar cientos de millones de puntos por segundo.

whuber
fuente
1
Para una discusión sobre la fórmula de Haversine,
whuber
4

Estoy de acuerdo con otros en que un bucle simple debería ser efectivo para "unos pocos cientos de ciudades".

Dada su aplicación, tratar con distancias elipsoidales es probablemente una exageración importante: probablemente esté lidiando con predicciones meteorológicas cuya localidad apenas se encuentra a unos pocos metros. La geometría esférica es lo suficientemente simple como para que puedas hacerlo fácilmente en tu bucle.

Podría ser aún más simple (p. Ej., Use delta lat como y y delta lon * cos (lat) como x y encuentre el mínimo x ^ 2 + y ^ 2). Está utilizando el coseno de la latitud objetivo, que solo calcula una vez. Esto será cada vez más inexacto para ciudades distantes, pero de todos modos serán rechazados, así que no importa. Suponiendo que su ciudad más cercana se encuentra generalmente dentro de un par de cientos de kilómetros, las posibilidades de un resultado diferente (ciudad más cercana) usando esto versus una fórmula más precisa son bastante pequeñas y ocurrirían solo cuando las diferencias sean lo suficientemente pequeñas como para "cuál pronóstico es más precisa "probablemente dependería de otros factores de todos modos (es decir, pérdida en el ruido).

A menos que esté utilizando un sistema embebido o un intérprete lento, probablemente pueda permitirse el lujo de usar los formales esféricos que otros sugieren, aunque.


fuente
1

Esto se suma a lo que ya se ha dicho, pero pensé que notaría la importancia de elegir una estructura de datos adecuada. Escribí mi propio código para una función K en .NET, y descubrí que el uso de colecciones eficientes aceleró sustancialmente. Lo siento, no sé la notación O para velocidades exactas. Utilicé dos diccionarios para las coordenadas xey con la ID del punto como clave. No conozco Java, así que no podría sugerir nada.

Saludos, David

dslamb
fuente