Comparación de coordenadas lat y largas

Question

Tengo una lista de más de 15 mil coordenadas de latitud y longitud.Dadas las coordenadas X, Y, ¿cuál es la forma más rápida de encontrar las coordenadas más cercanas en la lista?

Answer 1

Querrás utilizar una construcción geométrica llamada diagrama de voronói.Esto divide el plano en varias áreas, una para cada punto, que abarcan todos los puntos más cercanos a cada uno de los puntos dados.

El código de los algoritmos exactos para crear el diagrama de Voronoi y organizar las búsquedas de estructuras de datos es demasiado grande para caber en este pequeño cuadro de edición.:)

@Linor:Eso es esencialmente lo que harías después de crear un diagrama de Voronoi.Pero en lugar de hacer una cuadrícula rectangular, puedes elegir líneas divisorias que coincidan estrechamente con las líneas del diagrama de Voronoi (de esta manera obtendrás menos áreas que crucen las líneas divisorias).Si divide de forma recursiva su diagrama de Voronoi por la mitad a lo largo de la mejor línea divisoria para cada subdiagrama, podrá realizar una búsqueda de árbol para cada punto que desee buscar.Esto requiere un poco de trabajo desde el principio, pero ahorra tiempo después.Cada búsqueda sería del orden de log N donde N es el número de puntos.¡16 comparaciones es mucho mejor que 15.000!

Answer 2

Hice esto una vez para un sitio web.Es decir.encuentre el distribuidor dentro de 50 millas de su código postal.utilicé el cálculo del gran círculo para encontrar las coordenadas que estaban 50 millas al norte, 50 millas al este, 50 millas al sur y 50 millas al oeste.Eso me dio un lat mínimo y máximo y un largo mínimo y máximo.A partir de ahí hice una consulta a la base de datos:

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Dado que algunos de esos resultados aún estarán a más de 50 millas de distancia, utilicé el fórmula del gran círculo una vez más en esa pequeña lista de coordenadas.Luego imprimí la lista junto con la distancia desde el objetivo.

Por supuesto, si quisieras buscar puntos cerca de la línea de cambio de fecha internacional o de los polos, esto no funcionará.¡Pero funciona muy bien para búsquedas dentro de Norteamérica!

Answer 3

El concepto general que estás describiendo es búsqueda de vecino más cercano, y existen toda una serie de técnicas que se ocupan de resolver este tipo de consultas, ya sea de forma exacta o aproximada.La idea básica es utilizar una técnica de partición espacial para reducir la complejidad de O(n) por consulta a (aproximadamente) O(log n) por consulta.

Los KD-Trees y sus variantes parecen funcionar muy bien, pero los árboles cuádruples también funcionarán.La calidad de estas búsquedas depende de si su conjunto de 15.000 puntos de datos es estático (no está agregando muchos puntos de datos al conjunto de referencia).El trabajo de Mount y Arya en el Vecino más cercano aproximado La biblioteca es fácil de usar y comprender, incluso sin una buena base en matemáticas.También le brinda cierta flexibilidad en los tipos y tolerancias de sus consultas.

Answer 4

Más bien depende de cuántas veces desee hacerlo y de los recursos disponibles; si realiza la prueba una vez, entonces las técnicas O (log N) son buenas.Si lo hace mil veces en un servidor, construir una tabla de búsqueda de mapas de bits sería más rápido, ya sea dando el resultado directamente o como una primera etapa.2 GB de mapa de bits pueden mapear todo el mundo en latitud a un valor de 32 bits a 0,011 grados de píxeles (1,2 km en el ecuador) y deberían caber en la memoria.Si solo está haciendo un solo país o puede excluir los polos, puede tener un mapa más pequeño o una resolución más alta.Para 15.000 puntos, probablemente tengas un mapa mucho más pequeño; primero lo dimensioné como primer paso para realizar búsquedas de latitud a código postal, que necesitan una resolución más alta.Dependiendo de los requisitos, puede utilizar el valor asignado para señalar el resultado directamente o para hacer una lista corta de los candidatos (lo que permitiría un mapa más pequeño, pero requiere un mayor procesamiento posterior; ya no se encuentra en el territorio de búsqueda O(1)). ).

Answer 5

No especificaste lo que querías decir con más rápido.Si desea obtener la respuesta rápidamente sin escribir ningún código, le daría la filtro de radio gpsbabel atrás.

Answer 6

Según sus aclaraciones, usaría una estructura de datos geométrica como un árbol KD o un árbol R.MySQL tiene un tipo de datos ESPACIAL que hace esto.Otros lenguajes/marcos/bases de datos tienen bibliotecas para admitir esto.Básicamente, dicha estructura de datos incrusta los puntos en un árbol de rectángulos y busca en el árbol utilizando un radio.Esto debería ser lo suficientemente rápido y creo que es más sencillo que construir un diagrama de Voronoi.Supongo que hay un umbral por encima del cual preferirías el rendimiento adicional de un diagrama de Voronoi, por lo que estarás dispuesto a pagar la complejidad adicional.

Answer 7

Esto se puede solucionar de varias formas.Primero abordaría este problema generando un Delaunay red que conecta los puntos más cercanos entre sí.Esto se puede lograr con el comando v.delaunay en la aplicación SIG de código abierto. CÉSPED.Podrías completar el problema en GRASS usando uno de los muchos módulos de análisis de red en HIERBA.Alternativamente, puede utilizar el RDBMS espacial gratuito PostGIS para hacer las consultas a distancia.Las consultas espaciales de PostGIS son considerablemente más potentes que las de MySQL, ya que no están limitadas a operaciones BBOX.Por ejemplo:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Dado que está utilizando Longitud y Latitud, probablemente desee utilizar el Funciones de distancia esferoide.Con un índice espacial, PostGIS se adapta muy bien a grandes conjuntos de datos.

Answer 8

Incluso si crea un diagrama de Voronoi, eso significa que necesita comparar sus coordenadas x, y con las 15 mil áreas creadas.Para hacerlo más fácil, lo primero que me vino a la mente fue crear algún tipo de cuadrícula sobre los valores posibles, de modo que puedas colocar fácilmente y coordinar x/y en uno de los cuadros de una cuadrícula, si es lo mismo. hecho para la lista de áreas, debe reducir rápidamente los posibles candidatos para comparar (debido a que la cuadrícula sería más rectangular, es posible que un área esté en múltiples posiciones de la cuadrícula).

Answer 9

La optimización prematura es la fuente de todos los males.

Las coordenadas de 15K no son tanto.¿Por qué no iterar sobre las coordenadas de 15K y ver si eso es realmente un problema de rendimiento?Podría ahorrar mucho trabajo y tal vez nunca sea demasiado lento como para darse cuenta.

Answer 10

¿En qué área se distribuyen estas coordenadas?¿En qué latitud están?¿Cuánta precisión necesitas?Si están bastante juntos, probablemente puedas ignorar el hecho de que la Tierra es redonda y tratarlo como un plano cartesiano en lugar de jugar con geometría esférica y distancias de círculo máximo.Por supuesto, a medida que nos alejamos del ecuador, los grados de longitud se vuelven más pequeños en comparación con los grados de latitud, por lo que algún tipo de factor de escala puede ser apropiado.

Comience con una fórmula de distancia bastante simple y una búsqueda de fuerza bruta y vea cuánto tiempo llevará y si los resultados son lo suficientemente precisos antes de ponerse sofisticado.

Answer 11

Gracias a todos por las respuestas.

@Tom, @Chris Upchurch:Las coordenadas están bastante cerca unas de otras y se encuentran en un área relativamente pequeña de unos 800 kilómetros cuadrados.Supongo que puedo asumir que la superficie es plana.Necesito procesar las solicitudes una y otra vez y la respuesta debería ser lo suficientemente rápida para tener más experiencia web.

Answer 12

Una cuadrícula es muy simple y muy rápida.Básicamente es solo una matriz 2D de listas.Cada entrada de la matriz representa los puntos que se encuentran dentro de una celda de la cuadrícula.Muy fácil de configurar la cuadrícula:

for each point p
  get cell that contains p
  add point to that cell's list

y es muy fácil buscar cosas:

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

alejo

Answer 13

Para ser contrario, ¿te refieres a una distancia cercana o a un tiempo (de conducción)?En un área urbana, con mucho gusto conduciría 5 millas (5 minutos) por la autopista que 4 millas (20 minutos con parada y arranque) en otra dirección.

Por lo tanto, si lo que necesita es una métrica "más cercana", buscaría bases de datos SIG con métricas de tiempo de viaje.