Más de una vez tuve que implementar la funcionalidad de calcular la distancia desde cierto punto geográfico a un área en el mapa, por ejemplo, a la carretera de circunvalación de Moscú. Como resultado, encontré dos formas de resolver el problema que mostró buenos resultados, y ahora los usamos regularmente en la producción. Los describiré en la primera parte del artículo. Y en el segundo, mostraré cómo puede almacenar en caché los geodatos para usar menos el geocodificador.
Primera parte Dos formas de encontrar la distancia de un punto a un área en un mapa
Si su aplicación móvil es verdaderamente móvil, funciona con las coordenadas del dispositivo. La ubicación del usuario (y dispositivo) afecta a varios indicadores comerciales de la aplicación, como el costo de entrega, el factor de complejidad, etc.
A continuación, mostraré ejemplos de implementación de algoritmos en Python usando las bibliotecas scipy y shapely.
Para la geocodificación usamos Google Maps. Se adapta tanto a la funcionalidad como al costo de uso. Al momento de escribir este artículo, Google le permite realizar las primeras 20,000 solicitudes de geocodificación por mes de forma gratuita.
Método 1. Calculamos la ruta en función de los vértices del polígono.
Supongamos que necesitamos encontrar la distancia desde un punto en algún lugar de la región de Moscú hasta la carretera de circunvalación de Moscú. Se necesita un camino real, no geométrico. Por lo tanto, primero construimos un vertedero desde los puntos de salida de la carretera de circunvalación de Moscú, y no coinciden con los vértices del contorno de la carretera en el mapa.
exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float
Para trabajar con geometría, utilizamos la biblioteca
bien formada. Con su ayuda, es fácil determinar si el punto de interés para nosotros está dentro del polígono o no. Si es así, la distancia es obviamente 0.
from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude))
Estamos interesados en el caso cuando el punto está fuera del polígono. La tarea de encontrar los objetos más cercanos (salidas del MKAD) al punto de partida es bastante típica en matemáticas. Por lo general, se resuelve usando un árbol KD. Entonces hagámoslo. En python, el árbol se implementa en la biblioteca
scipy. Encontraremos los picos más cercanos desde las salidas de la carretera de circunvalación de Moscú hasta nuestro punto.
from scipy.spatial import KDTree kd_tree = KDTree(exits_coordinates) dists, indexes = kd_tree.query((latitude, longitude), k=3) nearest_coordinates = list() for _, index in zip(dists, indexes): nearest_coordinates.append(exits_coordinates[index])
El número
k , el número de picos, no debe ser demasiado pequeño, porque la salida más cercana de la carretera de circunvalación de Moscú puede estar bloqueada temporalmente. O puede estar en algún lugar más allá del río y no tener un camino directo a nuestro punto. Demasiado grande
k también
es inútil para nosotros, porque Una salida adecuada se encuentra en varios picos cercanos. Ahora pasemos al servicio de Google Maps. Ya tiene una funcionalidad para encontrar distancias desde una matriz de puntos a un punto específico: la API de matriz de distancia.
Upd: el servicio API de distancia de la matriz factura la ruta a cada pico más cercano por separado. Por lo tanto, este método es más costoso que el segundo, que se describe a continuación. Gracias
sovetnikov import googlemaps gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) gmaps_client.distance_matrix( origins=nearest_coordinates, destinations=(latitude, longitude), mode='driving', )
Solo podemos analizar la respuesta. Por lo general, tiene varias rutas, y la primera no siempre es la más corta. Por lo tanto, elegimos el valor apropiado.
Método 2. Calculamos la ruta desde el centro del vertedero
Ahora, además de los vértices del polígono, definimos algún punto dentro de él, desde el cual construiremos todas las rutas de Google Maps. Utilizaremos la API de indicaciones, que creará rutas para nosotros y elegiremos la más corta.
start_point: Tuple[float, float], destination: Tuple[float, float] polygon: shapely.geometry.Polygon gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) driving_path = gmaps_client.directions(start_point, destination)
Comenzamos iterativamente desde el final para agregar las longitudes de los segmentos de ruta hasta que la coordenada del comienzo del segmento esté dentro del polígono (se omite el análisis):
for step in reversed(driving_path): start_point = step['start_location']['lat'], step['start_location']['lng'] if is_inside_polygon(start_point, self.polygon): end_point = step['end_location']['lat'], step['end_location']['lng'] distance += get_part_outside_polygon( get_line(start_point, end_point), polygon ) * step['distance']['value'] break distance += step['distance']['value']
Solo podemos agregar parte del segmento fuera del polígono. Para hacer esto, usando la biblioteca bien formada, construimos una línea geométrica entre las coordenadas del principio y el final de la ruta y encontramos cuánto de su longitud se encuentra fuera del polígono. El mismo porcentaje de la longitud se calcula para el segmento obtenido de la ruta.
Una ruta es una ruta de terreno en carreteras reales con curvatura natural. Si se trata de una línea recta larga (avenida o autopista), nuestra aproximación nos permitirá calcular la ruta exactamente en términos porcentuales.
Si el camino que cruza el vertedero es lo suficientemente curvo, tal aproximación será incorrecta. Pero las partes curvas en la ruta de Google Maps en sí son generalmente cortas, y los errores en su cálculo no afectarán el resultado.
from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length)
Para ser sincero, no comparé estos dos métodos. Los he estado usando por más de un año, ambos funcionan sin fallas. Decidí no pintar su implementación en detalle. En cambio, abrió el acceso a su
geo biblioteca. Liba también puede usar geocodificación regular, incluso con almacenamiento en caché eficiente. ¡Problemas y solicitudes de extracción son bienvenidos!
Segunda parte Guardar solicitudes de geocodificación inversa
A menudo necesitamos determinar las direcciones de los puntos que están cerca y corresponden a un objeto en el mundo real. Cada vez, hacer una solicitud a un sistema de geocodificación externo no es bueno, y aquí surge la cuestión del almacenamiento en caché.
Normalmente, el cliente envía las coordenadas con una precisión excesiva, por ejemplo, 59.80447691, 30.39570337. Pero, ¿cuántos signos en la parte fraccionaria serán significativos para nosotros?
Para los flojos y apurados, la respuesta es cuatro. Para todos los demás, vea la explicación a continuación.
Primero, un poco de geografía.
- El ecuador tiene 40,075.696 km de largo y su latitud cero.
- Los meridianos son líneas de longitud, perpendiculares a las líneas de latitud. La longitud de cualquier meridiano es 40,008.55 km.
- Grado de latitud - 40,008.55 km / 360 = 111.134861111 km. Entonces, una centésima da un cambio de aproximadamente un kilómetro, y una décima parte da un cambio de 10 metros.
- La circunferencia de la línea de latitud disminuye desde el ecuador y se multiplica por el coseno del ángulo de latitud, por lo tanto, para 60 grados de latitud (latitud de San Petersburgo), la longitud es menor que exactamente 2 veces menos. Entonces el grado de longitud es 40,075.696 * 0.5 / 360 = 55.66066888 km, o una diezmilésima es 5 metros.
Un error de 1/10000 grados da un rectángulo de error de 5-10 por 10 metros. Esto nos permitirá "entrar" exactamente en el edificio, ya que El edificio es mucho más grande que el punto. Y si, debido a un error, el punto no cae dentro del edificio, Google aún determinará cuál es el más cercano.
Redondear hasta tres caracteres es arriesgado, la precisión ya se reduce significativamente. Y hasta cinco, no tiene sentido, porque la precisión de los transmisores GPS no supera los pocos metros.
Por lo tanto, si hay un valor en el caché con la clave "dirección: 59.8045,30.3957", entonces todas las coordenadas, cuando se redondea a 4 caracteres, se obtiene la misma clave, corresponde a una dirección geocodificada. Hacemos menos solicitudes: trabajamos más rápido y pagamos menos por usar el servicio de geocodificación. Beneficio!