Algoritmo para encontrar el punto más cercano

17

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

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

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

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

    
pregunta lujop 04.01.2011 - 23:30

3 respuestas

23

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

Para calcular distancias a un único punto de "sonda", sus opciones incluyen (a) proyectar todos los puntos utilizando una proyección equidistante centrada en el punto de la sonda o (b) adoptar un modelo esférico de la Tierra y usar Haversine formula . El primero es apropiado si necesita la precisión de un modelo elipsoidal. En cualquiera de los casos, los cálculos son razonablemente rápidos, probablemente teniendo menos de 1000 tics: 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 paraliza 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 que haya encontrado cada procesador.

Si necesita ir más rápido, puede usar varias aproximaciones para los puntos de la 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, entonces cualquier punto cuya latitud difiera de la latitud del punto de la sonda en más de 2 grados no podrá estar más cerca (porque en cualquier lugar 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.

    
respondido por el whuber 05.01.2011 - 03:09
4

Estoy de acuerdo con los demás 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 se trate de predicciones meteorológicas cuya ubicación es apenas de 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 incluso 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 las ciudades distantes, pero serán rechazadas de todos modos, así que no importa. Suponiendo que su ciudad más cercana está generalmente dentro de un par de cientos de kilómetros, las posibilidades de un resultado diferente (ciudad más cercana) utilizando esta fórmula más precisa son bastante pequeñas y se producirían solo cuando las diferencias sean lo suficientemente pequeñas como para "qué pronóstico es más "preciso" probablemente dependería de otros factores de todos modos (es decir, perdido en el ruido).

A menos que esté utilizando un sistema integrado o un intérprete lento, es probable que pueda darse el lujo de usar solo los formularios esféricos que otros sugieren, aunque.

    
respondido por el Zhahai 06.01.2011 - 22:40
1

Esto es además de lo que ya se ha dicho, pero pensé que destacarí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ó las cosas sustancialmente. Lo siento, no sé la notación O para velocidades exactas. Utilicé dos diccionarios para las coordenadas x e y con el ID de punto como clave. No sé Java, así que no podría sugerir nada.

Saludos, David

    
respondido por el dslamb 05.01.2011 - 18:18

Lea otras preguntas en las etiquetas