Plus d'une fois, j'ai dû implémenter la fonction de calcul de la distance d'un certain point géographique à une zone sur la carte - par exemple, le périphérique de Moscou. En conséquence, j'ai trouvé deux façons de résoudre le problème qui a donné de bons résultats, et maintenant nous les utilisons régulièrement en production. Je les décrirai dans la première partie de l'article. Et dans la seconde, je montrerai comment vous pouvez mettre en cache les géodonnées pour utiliser moins le géocodeur.
Première partie Deux façons de trouver la distance d'un point à une zone sur une carte
Si votre application mobile est vraiment mobile, elle fonctionne avec les coordonnées de l'appareil. L'emplacement de l'utilisateur (et de l'appareil) affecte divers indicateurs commerciaux de l'application, tels que le coût de livraison, le facteur de complexité, etc.
Ci-dessous, je vais montrer des exemples d'implémentation d'algorithmes en python en utilisant les bibliothèques scipy et shapely.
Pour le géocodage, nous utilisons Google Maps. Il convient à la fois à la fonctionnalité et au coût d'utilisation. Au moment d'écrire ces lignes, Google vous permet d'effectuer gratuitement les 20 000 premières demandes de géocodage par mois.
Méthode 1. Nous calculons l'itinéraire en fonction des sommets du polygone
Supposons que nous devions trouver la distance d'un point quelque part dans la région de Moscou à la rocade de Moscou. Un vrai chemin est nécessaire, pas géométrique. Par conséquent, nous construisons d'abord une décharge à partir des points de sortie de la rocade de Moscou, et ils ne coïncident pas avec les sommets du contour de la route sur la carte.
exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float
Pour travailler avec la géométrie, nous utilisons la bibliothèque
bien faite. Avec son aide, il est facile de déterminer si le point d'intérêt pour nous se trouve à l'intérieur du polygone ou non. Si c'est le cas, la distance est évidemment 0.
from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude))
Nous nous intéressons au cas où le point est en dehors du polygone. La tâche de trouver les objets les plus proches (sorties du MKAD) au point de départ est assez typique en mathématiques. Habituellement, il est résolu en utilisant un arbre KD. Alors faisons-le. En python, l'arborescence est implémentée dans la bibliothèque
scipy. Nous trouverons les sommets les plus proches des sorties de la rocade de Moscou jusqu'à notre point.
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])
Le nombre
k - le nombre de pics - ne doit pas être trop petit, car la sortie la plus proche de la rocade de Moscou peut être temporairement bloquée. Ou il peut être quelque part au-delà de la rivière et ne pas avoir un chemin direct vers notre point. Un
k trop grand
est également inutile pour nous, car une sortie appropriée est située dans plusieurs sommets voisins. Passons maintenant au service Google Maps. Il a déjà une fonctionnalité pour trouver des distances d'un tableau de points à un point spécifique - l'API Distance Matrix.
Mise à jour: le service d'API Distance Matrix facture séparément l'itinéraire vers chaque pic le plus proche. Ainsi, cette méthode est plus coûteuse que la seconde, décrite ci-dessous. Merci
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', )
Nous pouvons seulement analyser la réponse. Il comporte généralement plusieurs itinéraires et le tout premier n'est pas toujours le plus court. Par conséquent, nous choisissons la valeur appropriée.
Méthode 2. Nous calculons l'itinéraire à partir du centre de la décharge
Maintenant, en plus des sommets du polygone, nous définissons un point à l'intérieur, à partir duquel nous allons construire tous les itinéraires de Google Maps. Nous utiliserons l'API Directions, qui créera pour nous des itinéraires, et choisirons les plus courts.
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)
Nous commençons de manière itérative à partir de la fin pour ajouter les longueurs des segments de chemin jusqu'à ce que la coordonnée du début du segment soit à l'intérieur du polygone (l'analyse syntaxique est omise):
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']
Nous ne pouvons ajouter qu'une partie du segment en dehors du polygone. Pour ce faire, en utilisant la bibliothèque bien faite, nous construisons une ligne géométrique entre les coordonnées du début et de la fin du chemin et trouvons quelle partie de sa longueur se trouve en dehors du polygone. Le même pourcentage de la longueur est calculé pour le segment obtenu du chemin.
Un chemin est un itinéraire de terrain sur de vraies routes avec une courbure naturelle. S'il s'agit d'une longue ligne droite (avenue ou autoroute), notre approximation nous permettra de calculer l'itinéraire exactement en pourcentage.
Si la route traversant la décharge est suffisamment incurvée, une telle approximation sera incorrecte. Mais les parties courbes de l'itinéraire Google Maps lui-même sont généralement courtes et les erreurs de calcul n'affecteront pas le résultat.
from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length)
Pour être honnête, je n'ai pas comparé ces deux méthodes. Je les utilise depuis plus d'un an, les deux fonctionnent sans échec. J'ai décidé de ne pas peindre leur mise en œuvre en détail. Au lieu de cela, il a ouvert l'accès à sa
géothèque. Liba peut également utiliser un géocodage régulier, y compris avec une mise en cache efficace. Les problèmes et demandes de tirage sont les bienvenus!
Deuxième partie Enregistrer les demandes de géocodage inversé
Souvent, nous devons déterminer les adresses de points proches et correspondant à un objet dans le monde réel. Chaque fois, faire une demande à un système de géocodage externe n'est pas cool, et ici la question de la mise en cache se pose raisonnablement.
En règle générale, le client envoie les coordonnées avec une précision excessive, par exemple 59.80447691, 30.39570337. Mais combien de signes dans la partie fractionnaire seront importants pour nous?
Pour les paresseux et pressés, la réponse est quatre. Pour tout le monde, voir l'explication ci-dessous.
D'abord, un peu de géographie.
- L'équateur mesure 40 075,696 km de long et est à latitude zéro.
- Les méridiens sont des lignes de longitude, perpendiculaires aux lignes de latitude. La longueur de tout méridien est de 40 008,55 km
- Degré de latitude - 40000,55 km / 360 = 111,134861111 km. Ainsi, un centième donne un changement d'environ un kilomètre, et un dix millième donne un changement de 10 mètres.
- La circonférence de la ligne de latitude diminue à partir de l'équateur et est multipliée par le cosinus de l'angle de latitude.Par conséquent, pour 60 degrés de latitude (latitude de Saint-Pétersbourg), la longueur est inférieure à exactement 2 fois moins. Ensuite, le degré de longitude est de 40 075,696 * 0,5 / 360 = 55,66066888 km, soit un dix millième pour 5 mètres.
Une erreur de 1/10000 degrés donne un rectangle d'erreur de 5-10 sur 10 mètres. Cela nous permettra de «pénétrer» exactement dans le bâtiment, le bâtiment est beaucoup plus grand que le point. Et si, en raison d'une erreur, le point ne tombe pas dans le bâtiment, Google déterminera toujours le plus proche de lui.
Arrondir jusqu'à trois caractères est risqué, la précision est déjà considérablement réduite. Et jusqu'à cinq - cela n'a aucun sens, car la précision des émetteurs GPS ne dépasse pas quelques mètres.
Ainsi, s'il existe une valeur dans le cache avec la clé «adresse: 59.8045,30.3957», alors toutes les coordonnées, lorsqu'elles sont arrondies à 4 caractères, la même clé est obtenue, correspondent à une adresse géocodée. Nous faisons moins de demandes - nous travaillons plus rapidement et payons moins pour l'utilisation du service de géocodage. Profit!