longitude long latitude lat google from address sorting comparison

sorting - latitude - utm to lat long excel



Comparación de Lat, Long Coordenadas (13)

¿Qué tan grande es un área sobre la que se extienden 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 solo tratar esto como un plano cartesiano en lugar de jugar con la geometría esférica y las grandes distancias circulares. Por supuesto, a medida que se aleja del ecuador, los grados de longitud se hacen más pequeños en comparación con los grados de latitud, por lo que puede ser apropiado algún tipo de factor de escala.

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 que se sienta elegante.

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?

El concepto general que está describiendo es la búsqueda del vecino más cercano , y hay una gran cantidad de técnicas que se ocupan de resolver este tipo de consultas, ya sea de manera 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.

KD-Trees y variantes de KD-Trees parecen funcionar muy bien, pero los quad-trees 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 la biblioteca del vecino aproximado es fácil de usar y entender, incluso sin una buena base en las matemáticas. También le da cierta flexibilidad en los tipos y tolerancias de sus consultas.

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 una especie de cuadrícula sobre los valores posibles, para que pueda ubicar fácilmente y coordenada x / y en una de las casillas de una grilla, si la misma es hecho para la lista de áreas, debe reducir rápidamente los posibles candidatos para comparación (porque la cuadrícula sería más rectangular, es posible que un área esté en múltiples posiciones de cuadrícula).

Más bien, depende de cuántas veces desee hacerlo y qué recursos estén disponibles; si realiza la prueba una vez, las técnicas O (log N) son buenas. Si lo haces mil veces en un servidor, construir una tabla de búsqueda de mapa de bits sería más rápido, ya sea dando el resultado directamente o como una primera etapa de. 2 GB de mapa de bits pueden mapear el lat-lon del mundo entero a un valor de 32 bits a 0.011 grados de píxeles (1.2 km en el ecuador), y deben 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 evalué como un primer paso para hacer búsquedas de códigos postales de larga duración, que necesitan una resolución más alta. Dependiendo de los requisitos, utiliza el valor asignado para señalar el resultado directamente, o para una lista breve de los candidatos (lo que permitiría un mapa más pequeño, pero requiere un mayor procesamiento posterior; ya no está en el territorio de búsqueda O (1) )

Querrá usar una construcción geométrica llamada diagrama de Voronoi . Esto divide el plano en una serie de áreas, una para cada punto, que abarca todos los puntos que están más cerca de cada uno de sus puntos dados.

El código para los algoritmos exactos para crear el diagrama de Voronoi y organizar las búsquedas de la estructura 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 con las líneas del diagrama de Voronoi (de esta forma obtendrás menos áreas que crucen las líneas divisorias). Si recursivamente divide su diagrama de Voronoi a la mitad a lo largo de la mejor línea divisoria para cada subdiagrama, puede hacer una búsqueda en árbol para cada punto que desee buscar. Esto requiere un poco de trabajo por adelantado, pero ahorra tiempo más tarde. Cada búsqueda estaría en el orden del registro N donde N es el número de puntos. ¡16 comparaciones es mucho mejor que 15,000!

En función de sus aclaraciones, utilizaría una estructura de datos geométricos, como un árbol KD o un árbol R. MySQL tiene un tipo de datos ESPACIAL que hace esto. Otros idiomas / marcos / bases de datos tienen bibliotecas para apoyar esto. Básicamente, una estructura de datos de este tipo 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 simple que construir un diagrama de Voronoi. Supongo que hay un umbral por encima del cual preferiría el rendimiento agregado de un diagrama de Voronoi para que esté listo para pagar la complejidad añadida.

Gracias a todos por las respuestas.

@Tom, @Chris Upchurch: Las coordenadas son bastante cercanas entre sí, y se encuentran en un área relativamente pequeña de aproximadamente 800 km2. Supongo que puedo suponer que la superficie es plana. Necesito procesar las solicitudes una y otra vez, y la respuesta debe ser lo suficientemente rápida para una mayor experiencia web.

Una grilla 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 caen dentro de una celda de la cuadrícula. Muy fácil de configurar la grilla:

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

Esto se puede resolver de varias maneras. Primero abordaría este problema generando una red Delaunay conectando 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 GRASS . Puede completar el problema en GRASS usando uno de los muchos módulos de análisis de red en GRASS. Alternativamente, puede usar el RDGMS espacial gratuito PostGIS para hacer las consultas de distancia. Las consultas espaciales de PostGIS son considerablemente más potentes que las de MySQL, ya que no están limitadas a las operaciones de BBOX. Por ejemplo:

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

Como está utilizando Longitude y Latitude, probablemente desee utilizar las funciones de distancia de Spheroid . Con un índice espacial, PostGIS escala muy bien para grandes conjuntos de datos.

Hice esto una vez para un sitio web. Es decir, encontrar 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 a 50 millas al norte, a 50 millas al este, a 50 millas al sur y a 50 millas al oeste. Eso me dio un lat min y max y un min y max long. A partir de ahí hice una consulta en la base de datos:

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

Como algunos de esos resultados aún estarán a más de 50 millas de distancia, utilicé la 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 desea buscar puntos cerca de la línea de fecha internacional o los polos, entonces esto no funcionará. ¡Pero funciona muy bien para búsquedas dentro de América del Norte!

Solo para ser contradictorio, ¿te refieres a distancia o tiempo de conducción? En un área urbana, con gusto conduciría 5 millas (5min) en la carretera de 4 millas (20min de parada y listo) en otra dirección.

Por lo tanto, si se trata de una medida "más cercana" que necesita, buscaría en las bases de datos de GIS las métricas del tiempo de viaje.