Mehr als einmal musste ich die Funktion zum Berechnen der Entfernung von einem bestimmten geografischen Punkt zu einem Gebiet auf der Karte implementieren - zum Beispiel zur Moskauer Ringstraße. Als Ergebnis habe ich zwei Möglichkeiten gefunden, um das Problem zu lösen, bei dem gute Ergebnisse erzielt wurden, und jetzt verwenden wir sie regelmäßig in der Produktion. Ich werde sie im ersten Teil des Artikels beschreiben. Im zweiten Abschnitt werde ich zeigen, wie Sie Geodaten zwischenspeichern können, um weniger Geocoder zu verwenden.
Teil Eins Zwei Möglichkeiten zum Ermitteln der Entfernung von einem Punkt zu einem Gebiet auf einer Karte
Wenn Ihre mobile Anwendung wirklich mobil ist, funktioniert sie mit den Koordinaten des Geräts. Der Standort des Benutzers (und des Geräts) wirkt sich auf verschiedene Geschäftsindikatoren der Anwendung aus, z. B. Lieferkosten, Komplexitätsfaktor usw.
Im Folgenden werden Beispiele für die Implementierung von Algorithmen in Python unter Verwendung der scipy- und shapely-Bibliotheken gezeigt.
Für die Geokodierung verwenden wir Google Maps. Es eignet sich sowohl für die Funktionalität als auch für die Betriebskosten. Zum Zeitpunkt dieser Veröffentlichung können Sie mit Google die ersten 20.000 Geokodierungsanforderungen pro Monat kostenlos stellen.
Methode 1. Wir berechnen die Route anhand der Eckpunkte des Polygons
Angenommen, wir müssen die Entfernung zwischen einem Punkt in der Moskauer Region und der Moskauer Ringstraße ermitteln. Es wird ein realer Pfad benötigt, kein geometrischer. Deshalb bauen wir zuerst eine Deponie an den Ausgängen der Moskauer Ringstraße, die nicht mit den Scheitelpunkten des Straßenumrisses auf der Karte übereinstimmen.
exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float
Für die Arbeit mit Geometrie verwenden wir die
formschöne Bibliothek
. Mit seiner Hilfe ist es einfach festzustellen, ob der für uns interessante Punkt innerhalb des Polygons liegt oder nicht. Wenn dies der Fall ist, ist der Abstand offensichtlich 0.
from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude))
Wir interessieren uns für den Fall, dass der Punkt außerhalb des Polygons liegt. Die Aufgabe, die nächstgelegenen Objekte (Ausstiege aus dem MKAD) zum Ausgangspunkt zu finden, ist in der Mathematik recht typisch. Normalerweise wird es mit einem KD-Baum gelöst. Also lass es uns tun. In Python ist der Baum in der
Scipy- Bibliothek implementiert
. Wir werden die nächsten Gipfel von den Ausgängen der Moskauer Ringstraße zu unserem Punkt finden.
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])
Die Zahl
k - die Anzahl der Spitzen - sollte nicht zu klein sein, da die nächste Ausfahrt von der Moskauer Ringstraße vorübergehend gesperrt sein kann. Oder es liegt irgendwo jenseits des Flusses und hat keinen direkten Weg zu unserem Punkt. Ein zu großes
k ist auch für uns nutzlos, weil Ein geeigneter Ausgang befindet sich in mehreren nahe gelegenen Gipfeln. Wenden wir uns nun dem Google Maps-Dienst zu. Es verfügt bereits über eine Funktion zum Ermitteln von Entfernungen zwischen einer Reihe von Punkten und einem bestimmten Punkt - die Distance Matrix-API.
Aktualisierung: Der Distance Matrix API-Dienst stellt die Route zu jedem nächsten Gipfel separat in Rechnung. Somit ist dieses Verfahren teurer als das nachstehend beschriebene zweite. Vielen Dank
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', )
Wir können nur die Antwort analysieren. Normalerweise hat es mehrere Routen, und die allererste ist nicht immer die kürzeste. Deshalb wählen wir den passenden Wert.
Methode 2. Wir berechnen die Route von der Mitte der Deponie
Jetzt definieren wir zusätzlich zu den Eckpunkten des Polygons einen Punkt darin, aus dem wir alle Routen von Google Maps erstellen. Wir werden die Routen-API verwenden, die Routen für uns erstellt, und die kürzeste davon auswählen.
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)
Wir beginnen iterativ am Ende, um die Längen der Pfadsegmente hinzuzufügen, bis die Koordinate des Beginns des Segments innerhalb des Polygons liegt (Analyse wird weggelassen):
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']
Wir können nur einen Teil des Segments außerhalb des Polygons hinzufügen. Dazu erstellen wir mithilfe der formschönen Bibliothek eine geometrische Linie zwischen den Koordinaten von Anfang und Ende des Pfades und ermitteln, wie viel Länge außerhalb des Polygons liegt. Der gleiche Prozentsatz der Länge wird für das erhaltene Segment des Pfades berechnet.
Ein Pfad ist eine Geländestrecke auf realen Straßen mit natürlicher Krümmung. Wenn es sich um eine lange gerade Linie handelt (Straße oder Autobahn), können wir die Route nach unserer Näherung in Prozent genau berechnen.
Wenn die Straße, die die Deponie überquert, ausreichend gekrümmt ist, ist eine solche Annäherung falsch. Die gekrümmten Teile in der Google Maps-Route selbst sind jedoch in der Regel kurz und die Fehler bei der Berechnung wirken sich nicht auf das Ergebnis aus.
from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length)
Um ehrlich zu sein, habe ich diese beiden Methoden nicht verglichen. Ich benutze sie seit mehr als einem Jahr, beide arbeiten ohne Ausfälle. Ich habe beschlossen, ihre Umsetzung nicht im Detail zu malen. Stattdessen öffnete er den Zugang zu seiner
Geobibliothek. Liba kann auch reguläre Geokodierung verwenden, auch mit effizientem Caching. Probleme und Pull-Requests sind willkommen!
Zweiter Teil Reverse Geocoding-Anforderungen speichern
Oft müssen wir die Adressen von Punkten bestimmen, die sich in der Nähe befinden und einem Objekt in der realen Welt entsprechen. Jedes Mal, wenn eine Anfrage an ein externes Geocodierungssystem gestellt wird, ist das nicht cool, und hier stellt sich die Frage nach einem vernünftigen Caching.
Normalerweise sendet der Client die Koordinaten mit übermäßiger Genauigkeit, z. B. 59.80447691, 30.39570337. Aber wie viele Zeichen im Bruchteil werden für uns von Bedeutung sein?
Für die Faulen und Eiligen ist die Antwort vier. Für alle anderen siehe die Erklärung unten.
Zunächst ein bisschen Geographie.
- Der Äquator ist 40.075,696 km lang und der Breitengrad Null.
- Meridiane sind Längengrade, die senkrecht zu den Breitengraden verlaufen. Die Länge eines Meridians beträgt 40.008,55 km
- Breitengrad - 40.008,55 km / 360 = 111,134861111 km. Ein Hundertstel entspricht einer Änderung von etwa einem Kilometer, ein Zehntausendstel einer Änderung von 10 Metern.
- Der Umfang der Breitengradlinie nimmt vom Äquator ab und wird mit dem Kosinus des Breitengradwinkels multipliziert, daher ist die Länge für 60 Breitengrade (Breitengrad von St. Petersburg) weniger als genau das Zweifache. Dann ist der Längengrad 40.075.696 * 0,5 / 360 = 55.66066888 km, oder ein Zehntausendstel ist 5 Meter.
Ein Fehler von 1/10000 Grad ergibt ein Fehlerrechteck von 5-10 mal 10 Metern. Dies ermöglicht uns, genau in das Gebäude einzudringen Das Gebäude ist viel größer als die Spitze. Und wenn der Punkt aufgrund eines Fehlers nicht in das Gebäude fällt, ermittelt Google immer noch den nächstgelegenen Punkt.
Das Runden auf drei Zeichen ist riskant, die Genauigkeit ist bereits erheblich reduziert. Und bis zu fünf - das macht keinen Sinn, da die Genauigkeit von GPS-Sendern nur wenige Meter überschreitet.
Befindet sich also ein Wert im Cache mit dem Schlüssel "Adresse: 59.8045,30.3957", so entsprechen alle Koordinaten, auf 4 Zeichen gerundet, ein und demselben Schlüssel einer geocodierten Adresse. Wir stellen weniger Anfragen - wir arbeiten schneller und zahlen weniger für die Nutzung des Geokodierungsdienstes. Profit!