Geo Distanz-Berechnung über MySQL

Wir haben in den vergangenen Jahren viel Webseiten und Webanwendungen mit integrierter Kartendarstellung (vorzugsweise Google Maps) realisiert. Egal ob „Store-Finder“, Liefergebiet-Ermittlung oder ausgefallene Werbekampagnen die Entfernungs-Berechnung von Koordinaten ist immer wieder eine essenzielle Anforderung.

In diesem Beitrag soll es, um die verschiedenen Möglichkeiten gehen seine Ergebnisse auf Basis eines Radius zu filtern bzw. eine Entfernung zwischen zwei Punkten berechnen zu können.

Geht es um die Radius-Berechnung, mag der erste Gedankengang sein, den Längen- und Breitengraden eines 1 km entfernten Punkts zu ermitteln, um dann einen Faktor zu haben, der sich je nach gewünschtem Umkreis addieren bzw. subtrahieren und so ein Quadrat um den Zielpunkt zu erstellen. Eine Abfrage, ob sich ein anderer Längen- und Breitengrad darin befindet, ist aufgrund der Erdkrümmung dermaßen ungenau, dass ich der Versuch erst überhaupt nicht lohnt.

Zum Glück gibt es einige mathematische Formeln, welche dieses Problem lösen. Eine davon heißt „Haversine Formel“ und definiert sich wie folgt:

R = Erdradius (ca. unterschiedliche Quellen nennen zwischen 6336 und 6399 km)
dlon = B_lon - A_lon
dlat = B_lat - A_lat

distance = R * (2 * arcsin(min(1,sqrt((sin(dlat/2))^2 + cos(A_lat) * cos(B_lat) * (sin(dlon/2))^2))))

In diesem Artikel soll es nicht um die mathematische Erklärung der Entfernungs-Berechnung gehen. Wer sich tiefergehend darüber informieren möchte, sollte einen Blick auf den Beitrag im OpenGeoDB Wiki werfen.

Im Folgenden sollen viel mehr einige Praxisanwendungen beschrieben werden.

Berechnung über die Google Maps API

Für die einfache Darstellung von Entfernungsangaben ist die Client-seitige Berechnung über den Browser die erste Wahl. Google Maps bietet für diesen Zweck die Funktion „computeDistanceBetween“. Im folgenden Beispiel wird die Entfernung zweier Punkte in Metern berechnet:

const latLng1 = new google.maps.LatLng(50.7271351,7.0725076);
const latLng2 = new google.maps.LatLng(50.9392606,6.9584879);

const distance = google.maps.geometry.spherical.computeDistanceBetween(latLng1, latLng2);

Um diese Funktion nutzen zu können sollte sichergestellt sein, dass die „Geometry“-Bibliothek geladen werden. Dies erfolgt über den entsprechenden Parameter „libraries=geometry“ bei der „Google Map“-Initialisierung wie in dem folgenden Beispiel zusehen:

<script src="https://maps.googleapis.com/maps/api/js?key=YOUR_KEY&libraries=geometry" async="" defer=""></script>

Berechnung über PHP

Ist es notwendig die Entfernungs-Berechnung serverseitig durchzuführen? In diesem Fall würden wir als PHP Entwickler als Nächstes daran denken, die „Haversine Formel“ oder eine Alternative in PHP zu implementieren. Glücklicherweise gibt es dafür bereits mehrere Pakete wie z. B. phayes/geoPHP, die sich diesem Problem schon angenommen haben.

Soll zu einer kleinen Auswahl (bis ca. 100 Einträge) eine Distanz berechnet werden, ist dieser Lösungsansatz absolut legitim. Geht es jedoch eher um das Filtern eines großen Datensatzes z. B. bei der Radius-Suche in einem Store-Finder mit 100.000 oder mehr Einträgen ist diese Methode nicht zu empfehlen. Die Daten müssten zunächst in der Gesamtheit aus der Datenbank geladen und anschließend mit einer Filterfunktion iteriert werden. Die würde eine enorm lange Ladezeit zur Folge haben.

In einem solchen Anwendungsfall sollte eher auf eine datenbankbasierte Kalkulation zurückgegriffen werden.

Berechnung über MySQL 5.7+

In den neueren MySQL Versionen ist eine Funktion zur Entfernungsberechnung bereits von Haus aus verfügbar. Gemeint ist die Funktion „ST_Distance_Sphere“ damit lassen sich diese Berechnungen bereits auf Datenbankebene durchführen. Das folgende MySQL-Query kann verwendet werden um die Entfernung in Metern zwischen zwei Längen- und Breitengraden zu berechnen:

select ST_Distance_Sphere(
    point(50.7271351,7.0725076),
    point(50.9392606,6.9584879)
)

Beispiel in Laravel mit MySQL 5.7+

Dieser Ansatz kann bspw. in Laravel als Scope auf ein Model angewendet werden:

public function scopeAppendDistanceTo(Builder $query, $latitude, $longitude): Builder
{
    return $query->selectRaw("
       *, ST_Distance_Sphere(
            point(longitude, latitude),
            point(?, ?)
        ) as distance
    ", [
        $longitude,
        $latitude,
    ]);
}

// Verwendung des neu angelegten Scopes:
return Store::appendDistanceTo($latitude, $longitude)->get(); 

Wobei der erste „point(longitude, latitude)“ direkt aus die Längen- und Breitengrad auf dem Model zurückgreift.

Beispiel in Laravel mit MySQL < 5.7

Ist Laravel mit einer älteren MySQL Version im Einsatz, so gibt es dennoch Abhilfe. Dabei kann auf die manuelle Kalkulation zurückgegriffen werden. Diese ließe sich ebenfalls als Query-Scope wie folgt auf einem Model implementieren:

protected function scopeAppendDistanceTo(Builder $query, $latitude, $longitude): Builder
{
    return $query->selectRaw("
        *, ROUND(
            3959 * acos( cos( radians(?) ) 
            * cos( radians( latitude ) ) 
            * cos( radians( longitude ) - radians(?) ) 
            + sin( radians(?) ) 
            * sin( radians( latitude ) ) )
        , 2) AS distance", [
            $latitude,
            $longitude,
            $latitude
        ]
    );    
}

// Verwendung des neu angelegten Scopes:
return Store::appendDistanceTo($latitude, $longitude)->get(); 

Limitationen und mögliche Probleme

Alle der oben genannten Ansätze unterliegen gewissen Limitationen. Auf diese möchten wir nun eingehen:

• Es wird lediglich die Luftlinie zwischen zwei Standorten berechnet. Die Erreichbarkeit eines Standorts unterliegt u.U. gewissen Einschränkungen, sodass die Entfernung über die Straße oder den Fußweg deutlich länger sein könnte. Sie möchten auch diesem Umstand Abhilfe schaffen? Dann sollten Sie einen Blick auf die Distance Matrix API von Google werfen.
• Zudem sind die oben genannten Methoden nicht 100 % genau. Die Erde ist keine perfekte Kugel, daher unterliegt die Entfernungs-Berechnung gewissen Schwankungen. Dies sollte für die meisten Anwendungsfälle jedoch keine Rolle spielen.

Was bedeutet eigentlich SRID?

SRID ist ein Akronym und steht für „Spatial Reference Identifier“ und ist eine Raumbezugskennung. Diese wird verwendet um von einer geografischen Ansicht (3D-Darstellung) der Welt zu einer projizierten Ansicht der Welt (2D-Kartendarstellung) zu wechseln.

Das Open Geospatial Consortium (OGC), eine nicht staatliche Freiwilligenorganisation, ist für die Definition und Verwaltung des SRIDs zuständig. Zu den Mitgliedern der Organisation zählen u. a. die Unternehmen wie Oracle, Google, Airbus, SAP und FedEx sowie 100+ Universitäten und viel mehr.

In der folgenden Tabelle haben wir zusammengefasst welche SRIDs derzeit von den verschiedenen Anbietern verwendet werden:

Über folgendes MySQL Select-Query können die in MySQL zur Verfügung stehenden SRID angezeigt werden:

SELECT COUNT(*) FROM INFORMATION_SCHEMA.ST_SPATIAL_REFERENCE_SYSTEMS;

Wer mehr zu dem Thema wissen möchte, sollte einfach mal nach den SRIDs in Bezug auf MySQL im Netz suchen.

Fazit

Die Entfernungs-Berechnung kann sehr komplex sein, gerade wenn es um die exakte mathematische Berechnung geht. Mit den oben aufgeführten Lösungsansätzen lassen sich aber für die meisten Anwendungsfälle völlig ausreichend genaue Berechnungen durchführen.

Sie benötigen Unterstützung rund um dieses Thema? Dann nehmen Sie doch gerne unverbindlich Kontakt mit uns auf.