HGVision
GAMES DESIGN DEVELOPMENT

Umkreissuche mit MySQL und Geo-Koordinaten

Blogbild

Vor kurzem brauchte ich für ein geplantes Projekt mal eine Umkreissuche mit welcher man bestimmte Punkte im Umkreis um seinen eigenen Standort ermitteln kann. Die Punkte waren als Breiten und Längengrad in einer MySQL Datenbank abgelegt und der eigene Standort war der Referenzpunkt der Suche.

Nach ein wenig Recherche im Netz bin ich auf folgendes Query gestoßen:


SELECT *,
        (
            6371 * acos
            (
                cos(
                    radians( :lat )
                ) 
                * cos(
                    radians( lat)
                ) * cos(
                    radians( lng) - radians( :lng )
                ) + sin(
                    radians( :lat )
                ) * sin(
                    radians( lat)
                )
            )
        ) AS distance
FROM location
HAVING distance <= :radius
ORDER BY distance ASC;

Dieser Query ist alles was man braucht um im Umkreis eines zentralen Punktes andere Punkte zu finden welche im angegeben Radius vorhanden sind.

Dabei muss man nur :lat durch den Breitengrad und :lng durch den Längengrad des Ausgnagspunkts ersetzten. Mit :radius kann man den Radius in Kilometern angeben in welchem gesucht werden soll.

Nun sieht die Formel mit der man hier die Distanz ermittelt sehr komplex aus, daher ein paar Eckdaten zu der Formel.

  • 6371 ist der Radius der Erde in Kilometern
  • radians() ist eine SQL-Funktion die aus einem Winkel in Grad einen Winkel in Radiant macht.
  • acos ist die Umkehrfunktion von Kosinus
  • cos ist die Kosinusfunktion
  • sin ist die Sinusfunktion

Nun wollte ich wissen wie perfomant dieses Query ist. Ich habe dafür zwei Tabellen erstellt der Aufbau ist dabei recht einfach für den Test.

  • Feld id als integer auto-increment
  • Feld lat als varchar(30)
  • Feld lng als varchar(30)

Die Tabellen habe ich mit zufälligen Daten gefüllt, einmal mit 10.000 Einträgen und einmal 50.000 Einträgen. Dann habe ich das Query mit den Koordinaten von Warendorf und einem Radius von 1000 Kilometern ausgeführt.


SELECT *,
        (
            6371 * acos
            (
                cos(
                    radians( 51.9538685 )
                ) 
                * cos(
                    radians( lat)
                ) * cos(
                    radians( lng) - radians( 7.9908987 )
                ) + sin(
                    radians( 51.9538685 )
                ) * sin(
                    radians( lat)
                )
            )
        ) AS distance
FROM location
HAVING distance <= 1000
ORDER BY distance ASC;

Ergebnis war bei der Tabelle mit 10.000 Einträgen eine Ausführungszeit von gerade mal 0.0067 Sekunden. Bei der Tabelle mit 50.000 Einträgen lag die Ausführungszeit bei 0.0320 Sekunden.

Obwohl das Query recht komplex ist und viel gerechnet wird und auch noch ein HAVING mit im Spiel ist liegt man deutlich unter einer Sekunde.