La forma más rápida de encontrar la ubicación (zip, city, state) dada la latitud/longitud

Question

Necesito una solución gratuita (de código abierto) que, dada la latitud/longitud, puede devolver el armario de ciudad/estado o zip. mysql no es una opción, una pequeña base de datos liviana sería la mejor si es posible.

Actualizaciones: Sin servicios web, con 50 millones de impresiones al día, incluso el complemento más pequeño duele, por lo que agregar una solicitud de servicio podría matar el tiempo de respuesta. Preferiría no agregar más de 200 milisegundos a la solicitud.

Tengo la base de datos, lat/lon/zip/city/state en csv, es solo cómo almacenarla y, lo que es más importante, cómo recuperarla más rápido.

Answer 1

Fuerza bruta: precarga todos tus datos en una matriz. Calcule la distancia entre su punto actual y cada punto de la matriz (hay un método para hacer este cálculo que usa álgebra lineal en lugar de funciones trigonométricas, pero no recuerdo lo que sucede al azar) para encontrar el punto más cercano.

Lea esto antes de bajar a voto: hay formas de acelerar la búsqueda de fuerza bruta de este tipo, pero he encontrado que por lo general no vale la pena la molestia. No solo he usado este enfoque antes para encontrar el zip más cercano de latitud/longitud, lo he usado en una aplicación de Windows Mobile (donde la potencia de procesamiento no es abrumadora) y aún logro tiempos de búsqueda por debajo del segundo. Siempre que evite el uso de funciones trigonométricas, este no es un proceso costoso.

Actualización: se puede acelerar el tiempo de búsqueda mediante el prorrateo de sus datos postales en sub-regiones (cuadrantes, por ejemplo, como el noroeste, sureste, etc.) y guarde el ID de región con cada punto de datos. En la búsqueda, entonces, primero se determina en qué región se encuentra su ubicación actual, y se compara solo con esos puntos de datos.

Para evitar errores de límite (como cuando su ubicación actual está cerca del borde de su región, pero está más cerca de un cierre relámpago en la región vecina), las regiones deben superponerse en cierta medida. Esto significa que algunos de sus registros zip se duplicarán, por lo que su conjunto de datos general será un poco más grande.

Answer 2

No es de código abierto, pero tal vez usted podría utilizar la API de Google Maps:

Reverse Geocoding

Answer 3

Otro hilo recomienda mod_geoip a través de MaxMind. Se ejecuta en el nivel de Apache, incluso antes de llegar a PHP/.NET/Java. Maxmind geolocation apis: Apache vs PHP

Answer 4

Si tiene el largo y el lat para el zip y la ubicación actual, puede calcular un radio y encontrar los puntos dentro de ese círculo. Si crea una delimitación asumida de cada rango de código postal, podría acelerar la búsqueda.

Si puede usar SQL 2008 (estándar o express) puede usar los tipos Spatial data.

Answer 5

El Yahoo! Placemaker es un servicio web gratuito que puede hacer esto. Puede buscar nombres de lugares ("Nueva York", "Buckingham Palace") pero también puede buscar latitudes y longitudes utilizando Geo microformat.

Para utilizar el servicio, se envía una solicitud POST, y devuelve XML:

Un pequeño ejemplo de línea de comandos (he oscurecido mi Yahoo!ID de aplicación; tendrá que registrar su propia):

$ curl -X POST -ddocumentContent='<div class="geo">GEO: <span class="latitude">37.386013</span>, <span class="longitude">-122.082932</span></div>' -ddocumentType='text/html' -dappid='your_yahoo_app_id' http://wherein.yahooapis.com/v1/document 

Esto devuelve un documento XML muy detallado, parte de la cual es:

<type>Town</type> 
<name><![CDATA[Los Altos, CA, US]]></name> 

También contiene los siguientes datos:

<type>Zip</type> 
<name><![CDATA[94024, Los Altos, CA, US]]></name> 

no he utilizado Placemaker mucho, pero han utilizado su Geocoding API y es muy rápido. Asocie esto con un memcached local y los usuarios no tienen idea de que los datos no son locales.

Answer 6

que debe salir geonames. tienen una API que devuelve XML y/o JSON. también, puede dl su base de datos.

Answer 7

mirada a la base de datos geonames.org de datos de origen.

Para una base de datos de la luz, SQLite es una buena opción.

geonames también hace un servicio web, pero si desea hacerlo usted mismo sin una llamada web (y suena como si lo hiciera), entonces necesitará una base de datos local. A continuación, sólo tiene que hacer los cálculos trigonométricos adecuadas para trabajar a cabo la distancia ortodrómica (Google que) entre un par de puntos LAT/LNG y luego ordena los resultados por distancia. También puede usar un cuadro delimitador o un radio, si desea limitar el radio de búsqueda antes de hacer los cálculos.

Si su base de datos local puede estar basada en SQL (que sqllite3 es), todo se suma a una consulta SQL que agrega un montón de cálculos trigonométricos para calcular una columna de "distancia" y tal vez también una cláusula "where" similar a limite la búsqueda dentro de un radio o cuadro delimitador. Habiendo calculado la columna de distancia en su consulta, es fácil ordenar por distancia y agregar cualquier otro criterio que desee. Si conoces rubí/rieles y quiere ver un buen ejemplo de cómo se hace esto, mira a los rieles Geokit plugin de origen.

Answer 8

Utilice un kd-tree para acelerar la búsqueda del vecino más próximo. Debe haber muchas implementaciones gratuitas disponibles sea cual sea su plataforma.

Answer 9

Cómo lejos de la ubicación de origen habría que esperar que la ciudad más cercana que sea? 50 millas? 200 millas? ¿500 millas? Si dos ciudades son casi equidistantes, ¿Importa si su algoritmo escoge exactamente la más cercana? Puede usar esta información para acelerar su búsqueda.

Si puede suponer razonablemente que la diferencia de distancia es pequeña (~ 250 mi o tan probablemente sea lo suficientemente pequeña como para considerarse 'pequeña'), y su cálculo de distancia puede ser un poco 'difuso', entonces puede optimizar el 'fuerza bruta' comprobar al limitar su espacio de búsqueda a +/- 5 lat de la fuente (~ 70 millas por lat, por lo que este le da aproximadamente 350 millas al norte y al sur), y +/- 5 de largo (que presumiendo no están buscando ciudades en los polos, esto es desde ~ 350 mi en el ecuador a ~ 100 mi en el norte de Canadá). Ajuste estos rangos a lo que considere apropiado para su espacio problemático.

Mientras trig funciones ayudará a darle una indicación precisa de la distancia, para distancias más pequeñas como éstas Pitágoras es generalmente lo suficientemente cerca para una 'mejor estimación' respuesta, con x = 69,1 * (sourcelat - citylat) ey = 53,0 * (sourcelong - citylong).

Answer 10

Esta es una pregunta muy interesante, con una respuesta compleja.

Menciona una base de datos de ciudades con latitud/lon, pero las ciudades no son puntos únicos y esto puede marcar una gran diferencia en áreas densamente pobladas donde grandes partes de la ciudad A podrían estar más cerca del "centro" de la ciudad B que al centro de la ciudad A. Tome una gran ciudad rodeada de suburbios más pequeños. Las partes periféricas de la gran ciudad podrían estar más cerca de los centros de los suburbios que del centro mismo de la gran ciudad. Ajustar al centro de la ciudad más cercano implica un mapa que es el diagrama de Voronoi de los puntos del centro de la ciudad. Tal mapa no se parecería en nada a un mapa real de áreas urbanas.

Si desea conocer la ciudad y el estado para un latitud/longitud determinado, necesita consultar un mapa adecuado y hacer un punto en las pruebas de polígonos para averiguar cuál es. Esto parece computacionalmente costoso, pero es en realidad no está mal si usa un índice espacial apropiado y tiene cuidado en su codificación. Dirijo un sitio web que vende acceso API a esta y otras consultas geográficas, y nuestro motor subyacente (escrito en Java) puede devolver la ciudad que lo contiene o la más cercana en los EE. UU. Con un tiempo promedio de consulta de 3e-4 segundos (más de 3.000 consultas) por segundo).

A pesar de que lo estamos vendiendo, estoy feliz de explicar cómo funciona, ya que sería mucho más barato que comprarlo de nosotros que para construir por sí mismo, incluso con instrucciones. Así que aquí están:

• Encuentra el mapa que deseas. Para ubicaciones en los Estados Unidos, el Censo de los Estados Unidos ofrece mapas extremadamente precisos en: http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html. No he encontrado mapas globales que sean tan buenos como los mapas del censo de EE. UU., Pero pueden existir.
• Busque o escriba un analizador para el formato de archivo de formas ESRI. No tengo un enlace específico para esto, ya que es altamente dependiente del idioma, pero hay numerosos analizadores, tanto gratuitos como comerciales disponibles en la web. Simplemente haga una búsqueda de "parser de shapefile" junto con su lenguaje de programación.
• Cargue el mapa en la memoria. Un mapa digital consiste en una lista de polígonos representados por una lista de pares lat/lon, típicamente ordenados en sentido contrario a las agujas del reloj. La mayoría de los mapas permiten recortes (por ejemplo, Lesotho en Sudáfrica), que se acaban de enumerar como polígonos donde los pares lat/lon se enumeran en el sentido de las agujas del reloj. Por razones de rendimiento y consumo de memoria, querrá utilizar matrices flotantes sin procesar (evite la doble precisión, ya que desperdicia memoria y usa matrices nativas donde sea posible, para evitar el boxeo).
• A continuación, necesitará un código para responder si un punto de consulta dado está contenido en un polígono determinado. Aquí es una excelente discusión del problema de punto en el polígono: How can I determine whether a 2D Point is within a Polygon?
• En mi experiencia, la técnica de fuerza bruta sugirió en otra respuesta (comprobando cada entidad) no funciona bien en los mapas nacionales o mundiales. En cambio, sugiero fuertemente un índice espacial rápido que devuelva una lista de polígonos candidatos para un lat/lon determinado. Aquí hay muchas opciones. Mucha gente sugeriría índices basados ​​en árboles, pero prefiero los índices de grillas, ya que son más rápidos y los servidores modernos tienden a tener mucha memoria. Escribí el único índice con el que he trabajado. Sé que existen en las bibliotecas GIS, pero creo que la mayoría del código GIS es demasiado complejo, lento y difícil de usar. Entonces, dada una consulta lat/lon, se obtiene una lista de polígonos candidatos del índice espacial y se usa la función punto en el polígono para encontrar cuál de los candidatos contiene el punto de consulta.
• También es importante manejar los casos donde el punto de consulta no está contenido en ningún polígono. En tal caso, presumiblemente querrá encontrar el polígono más cercano hasta una distancia máxima especificada. Para hacer esto, debe asegurarse de que su índice espacial pueda devolver una lista de polígonos cercanos, y no solo una lista de polígonos que contengan candidatos. También necesitará un código para calcular la distancia entre un punto de consulta y un segmento de línea lat/lon (esto es difícil porque lat/lon no es un espacio euclidiano). No encontré ninguna buena discusión sobre cómo hacer esto en línea, así que ideé mi propio método.Funciona creando un espacio linealizado alrededor del punto de consulta (que se convierte en (0, 0) en el nuevo espacio) en el que longitud relativa se vuelve a escalar de modo que un grado de la longitud modificada sea la misma distancia que un grado de latitud (implica multiplicar la longitud relativa por el coseno de la latitud). En este espacio linealizado, encontrará el punto más cercano en el segmento de línea utilizando métodos estándar (consulte Shortest distance between a point and a line segment) y luego convierta ese punto nuevamente en lat/lon y utilice la fórmula Haversine para calcular la distancia entre los dos puntos (consulte Calculate distance between two latitude-longitude points? (Haversine formula)).

Y eso es todo. Construí un sistema así de forma intermitente durante aproximadamente medio año. Mi estimación es que hay al menos tres meses hombre de codificación seria, y esa es una persona familiarizada con el tema (así que ten cuidado si estás tomando una decisión de comprar o construir).