Wo ist die nächste Bar?

Mit MySQL und der neuen GIS-Erweiterung beantwortest Du diese Frage mit ein paar Kniffen trotz tausender Datensätze schnell und performant. In diesem Artikel zeigen wir Dir, wie Du MySQL zur Umkreissuche auf geographischen Daten einsetzen kannst.

Umkreissuche befasst sich – wie der Name bereits verrät – mit der Suche von Punkten innerhalb eines gewissen Umkreises. So können beispielsweise alle Orte berechnet werden, die sich in einem Umkreis von 200 km um Innsbruck befinden. Eine solche Suche lässt sich mit MySQL mit einfachen Mitteln realisieren. Grundlage dafür ist eine Tabelle, die die Koordinaten all jener Punkte enthält, die durchsucht werden sollen. MySQL stellt dazu im Rahmen der GIS-Erweiterung den Datentyp POINT zur Verfügung, der es erlaubt, Punkte die durch X- und Y-Koordinaten lokalisiert sind, zu speichern. Im folgenden Beispiel werden die Koordinaten stets durch Grad Länge und Breite definiert (WGS-Referenzsystem). In einem konkreten Beispiel erfolgt die Erzeugung einer solchen Tabelle bzw. Spalte wie folgt:

CREATE TABLE geodaten(
stadt VARCHAR(30) NOT NULL,
geolokation POINT NOT NULL,
SPATIAL INDEX (geolokation)
) ENGINE=MyISAM;

Die Spalte geolokation beinhaltet dabei Werte des POINT-Datentyps. Wichtig dabei ist, dass ein räumlicher (spatial) Index für die Spalte mit den Koordinaten angelegt wird. Dieser Index wird in MySQL als sogenannter R-Baum realisiert und erlaubt performante Abfragen auf räumliche Daten. Näheres zum R-Baum findest Du im Buch. Ein solcher R-Baum ist allerdings nur in der Storage Engine MyISAM verfügbar, daher musst Du die Tabelle basierend auf dieser Storage Engine erzeugen.

Beim Einfügen von Daten in die geodaten-Tabelle werden basierend auf den X- und Y-Koordinaten (in Grad Breite bzw. Länge angegeben) der jeweiligen Punkte POINT-Objekte erzeugt und eingefügt:

INSERT INTO geodaten(stadt, geolokation)
VALUES ('Innsbruck', POINT(47.26027800, 11.343889));

Vorausgesetzt Du hast die Tabelle nun mit ausreichend Daten gefüllt, kannst Du – wie folgt beschrieben – eine Umkreissuche realisieren und so beispielsweise alle Orte berechnen, die in einem Umkreis von 200 km zur Stadt Innsbruck liegen. Eine sehr einfache Berechnung der Distanz zweier Orte beruht auf dem Satz von Pythagoras (a² + b² = c²). Prinzipiell lässt sich die Vorgehensweise zur Umsetzung einer Umkreissuche in folgende Schritte gliedern:

  • Aufspannen eines Suchrechteckes um den Ausgangspunkt
  • Berechnung der Distanz zwischen Ausgangspunkt und allen im Suchrechteck liegenden Punkten
  • Verfeinerung des Ergebnisses

Diese Schritte werden im Folgenden durchgeführt und erklärt. Zu Beginn müssen der Ausgangspunkt der Umkreissuche und der gewünschte Umkreis (in Kilometern) festgelegt werden. Dazu werden die Variablen @ibk_laenge und @ibk_breite mit den Koordinaten von Innsbruck und die Variable @umkreis mit dem gewünschten Umkreis gefüllt. Im Anschluss werden die Eck-Koordinaten des Suchrechtecks festgelegt. Bei einem gewünschten Umkreis von 200 km soll das Rechteck dementsprechend 200 km nach Westen, Osten, Norden und Süden reichen. Das Suchrechteck wird in Grad berechnet, der Umkreis liegt in diesem Fall allerdings in Kilometern vor. Daher müssen diese Einheiten umgerechnet werden. Breitengrade lassen sich dabei ganz einfach umrechnen: 1 Grad entspricht 111 Kilometern. Die Umrechnung der Längengrad ist etwas kniffliger: diese hängt nämlich vom jeweiligen Breitengrad ab. So liegen zwei zwei Längengrade näher am Pol — in Kilometern gerechnet — weniger weiter auseinander als zwei Längengrade in der Nähe des Äquators. Dies wird berücksichtigt, indem zusätzlich durch den Cosinus des Radians der Breite (Absolutwert) dividiert wird.

Diese oben beschriebenen Schritte können in MySQL wie folgt realisiert werden:


SET @ibk_laenge = 11.343889;
SET @ibk_breite = 47.26027800;
SET @umkreis = 200;
SET @breite_nord = @ibk_breite + (@umkreis / 111);
SET @breite_sued = @ibk_breite - (@umkreis / 111);
SET @laenge_west = @ibk_laenge -
(@umkreis / (ABS(COS(RADIANS(@ibk_breite))) * 111));
SET @laenge_ost = @ibk_laenge +
(@umkreis / (ABS(COS(RADIANS (@ibk_breite))) * 111));

Der nächste Schritt ist das Erzeugen des Suchrechteckes, das mittels eines Multipoint-Objects (einem Kantenzug) definiert wird, der die vier bereits definierten Ecken beinhaltet. Dieses Multipoint-Objekt bildet die Grundlage für das Suchrechteck, das mittels des ENVELOPE-Befehls als minimal umspannendes Rechteck definiert wird. Dies ist notwendig, um dann wirklich basierend auf diesem Rechteck die Suche einschränken zu können:

SET @mp = CONCAT('MULTIPOINT(', @breite_sued , ' ',
@laenge_west, ', ',
@breite_nord, ' ',
@laenge_ost, ')');
SET @quadrat = ENVELOPE(GEOMFROMTEXT(@mp));

Der letzte Schritt ist dann die eigentliche Abfrage. Dabei wird das Suchrechteck verwendet und alle darin befindlichen Punkte selektiert (mithilfe des MBRCONTAINS-Befehls). Zusätzlich wird die Distanz aller im Suchrechteck liegenden Punkte berechnet. Dies geschieht – wie bereits erwähnt – über den Satz von Pythagoras. Beachte allerdings, dass bei dieser Formel die Erdkrümmung nicht in die Berechnung einfließt. Daher ergeben sich bei weiteren Strecken Abweichungen. Falls Du die Erdkrümmung auch berücksichtigen möchtest, sollten Du Dich an die Haversinsche Formel halten.

Wichtig bei der gezeigten Berechnung ist, dass wiederum die Umrechnung der Gradangaben in Kilometerangaben korrekt erfolgt. Dabei wird – wie bereits bei der Berechnung des Suchrechteckes – die Umrechnung der Längengrade von der jeweiligen Breite abhängig gemacht. Darauf basierend werden die Distanz in der Breite und die Distanz in der Länge (beides in km umgerechnet) quadriert (POW-Funktion) und aus der Summe dieser beiden Werte wird anschließend die Wurzel gezogen (SQRT-Funktion).

Durch die Verwendung eines Rechteckes (200 km lang und 200 km breit) als Grundlage für die Suche ist allerdings noch nicht sichergestellt, dass die Distanz zu jedem Punkt in diesem Rechteck kleiner als 200 km ist. So liegen die Eckpunkte beispielsweise weiter als 200 km vom Ausgangspunkt entfernt. Daher muss in einem letzten Schritt nochmals nachselektiert werden. Dazu machen wir uns die bereits berechnete Distanz zunutze und schränken diese mittels einer HAVING-Klausel nochmals ein.

Abschließend noch einmal das gesamte Beispiel:

SET @ibk_laenge = 11.343889;
SET @ibk_breite = 47.26027800;
SET @umkreis = 200;
SET @breite_nord = @ibk_breite + (@umkreis / 111);
SET @breite_sued = @ibk_breite - (@umkreis / 111);
SET @laenge_west = @ibk_laenge -
(@umkreis / ABS(COS(RADIANS(@ibk_breite))) * 111);
SET @laenge_ost = @ibk_laenge +
(@umkreis / ABS(COS(RADIANS(@ibk_breite))) * 111);

SET @mp = CONCAT('MULTIPOINT(', @breite_sued , ' ',
@laenge_west, ', ',
@breite_nord, ' ',
@laenge_ost, ')');
SET @quadrat = ENVELOPE(GEOMFROMTEXT(@mp));

SELECT (
FLOOR(
SQRT(
POW((@ibk_breite - sub.breite) * 111, 2) +
POW((@ibk_laenge - sub.laenge) * 111 *
ABS(COS(RADIANS(@ibk_breite))),2)
)
)
) AS distanz, sub.stadt
FROM
(
SELECT stadt, Y(geolokation) AS laenge,
X(geolokation) AS breite
FROM geodaten
WHERE MBRCONTAINS(@quadrat, geolokation)
) AS sub
HAVING distanz <= @umkreis
ORDER BY distanz;

2 Gedanken zu “Wo ist die nächste Bar?

  1. Ich erhalte falsche Werte für das Quadrat, denn im Ausdruck:
    SET @laenge_west = @ibk_laenge –
    (@umkreis / ABS(COS(RADIANS(@ibk_breite))) * 111);

    fehlt ein Klammerpaar. Es funktioniert mit:

    SET @laenge_west = @ibk_laenge –
    (@umkreis / (ABS(COS(RADIANS(@ibk_breite))) * 111));

    Das gleiche gilt für @laenge_ost.

    Getestet mit MySQL 5.5.42

Schreibe einen Kommentar