Umkreissuche mit der OpenGeoDB

In vielen Fällen ist eine Suche nach Orten in der Umgebung (dem Umkreis) eines bestimmten Ortes hilfreich, zum Beispiel wenn aus einer Datenbank von Sportvereinen alle Vereine in der Nähe des Interessenten ermittelt werden sollen. Eine grobe Orientierung ist am einfachsten anhand der Postleitzahl (PLZ) zu realisieren.

Versuchsaufbau

Neben der OpenGeoDB (hier wird von den Daten in Version 0.2.5a ausgegangen) haben wir eine Datenbanktabelle vereine, in der in unserem Beispiel Sportvereine eingetragen sind. Die für uns wichtige Spalte heißt PLZ, in der die Postleitzahl des Vereins steht, sie ist vom Typ CHAR(5). Darüber hinaus gibt es natürlich noch weitere Spalten (z. B. Name des Vereins, Straße, Ortsname, Internetadresse) auf die wir nicht weiter eingehen müssen, weil sie für die eigentliche Umkreissuche keine Bedeutung haben.
Als Software nutzen wir neben der MySQL-Datenbank die Scriptsprache PHP.

Struktur der OpenGeoDB

Die zentrale Tabelle der OpenGeoDB heißt geodb_coordinates. Darin sind die Koordinaten verschiedener Orte (englisch: locations) als Länge lon (longitude) und Breite lat (latitude) gespeichert. Die Orte werden über eine ID loc_id identifiziert. In der Tabelle geodb_textdata sind unter anderem die deutschen Postleitzahlen eingetragen. Der zugehörige Ort ist auch hier über die loc_id zugeordnet. In allen Datenbankzeilen, bei der die Spalte text_type den Wert „500300000“ hat, stehen einzelne Postleitzahlen in der Spalte text_val. Mehr Daten benötigen wir für die Umkreissuche nach Postleitzahlen nicht.

Etwas Mathematik

Die Ortsangaben mit geographischer Länge und Breite basieren auf dem Kugelkoordinatensystem, in dem vom Äquator (0° N/S) bis zu ±90° und vom Nullmeridian (0° W/O / Greenwich-Line) bis ±180° abgetragen werden, um jeden beliebige Ort auf der Kugeloberfläche eindeutig zu bestimmen. Für die Bestimmung der Entfernung zweier Orte ist dieses Koordinatensystem nicht besonders gut geeignet, dies funktioniert im dreidimensionalen Raum (R³) mit x-, y- und z-Achse besser.

Da Computer im Bogenmaß (360° = 2π [π = PI]) rechnen, müssen wir das Gradmaß ins Bogenmaß umrechnen:


<?php
$lambda = $lon * pi() / 180;
$phi = $lat * pi() / 180; 
?>

Außerdem benötigen wir den Erdradius (in Kilometern):


<?php
$Erdradius = 6371;
?>

Die Umwandlung der Kugelkoordinaten ins kartesische (rechtwinklige) Koordinatensystem funktioniert wie folgt:


<?php
$geoKoordX = $Erdradius * cos($phi) * cos($lambda);
$geoKoordY = $Erdradius * cos($phi) * sin($lambda);
$geoKoordZ = $Erdradius * sin($phi); 
?>

Alle gesuchten Orte im Umkreis von r Kilometern (r für Radius) um den Ursprungsort herum haben die Eigenschaft, dass die Entfernung zwischen diesem und dem Ursprungsort kleiner als r ist. Also berechnen wir die die Entfernung zweier Orte mit den Koordinaten ($x1, $y1, $z1) und ($x2, $y2, $z2):


<?php
$Entfernung = 2 * $Erdradius *
                arcsin(
                  sqrt(
                      pow($x1 - $x2, 2)    // Hinweis: pow($Basis, $Exponent) berechnet 
                    + pow($y1 - $y2, 2)    // "$Basis hoch $Exponent".
                    + pow($z1 - $z2, 2)    // Hier also "($z1 - $z2)^2"
                  ) / (2 * $Erdradius)
                );
?>

Angewendet

In der Anwendung ermitteln wir zuerst die Koordinaten des Ursprungsorts / Mittelpunkts des Umkreises. Dafür nehmen wir an, dass dessen Postleitzahl in der PHP-Variablen $PLZ steht.


<?php
$Erdradius = 6371;

$sql = 'SELECT
            coo.lon,
            coo.lat
        FROM geodb_coordinates AS coo
        INNER JOIN geodb_textdata AS textdata
        ON textdata.loc_id = coo.loc_id
        WHERE
            textdata.text_val = "' . mysql_real_escape_string($PLZ) . '"
        AND textdata.text_type = "500300000"
        ';
$re = mysql_query($sql);
if (mysql_num_rows($re) != 1) {
    die($PLZ . ' wurde nicht gefunden.');
}
list($lon, $lat) = mysql_fetch_row($re);

$lambda = $lon * pi() / 180;
$phi = $lat * pi() / 180;
$UrsprungX = $Erdradius * cos($phi) * cos($lambda);
$UrsprungY = $Erdradius * cos($phi) * sin($lambda);
$UrsprungZ = $Erdradius * sin($phi);
?>

Jetzt suchen wir alle Orte, die weniger als r Kilometer von diesen Koordinaten entfernt sind, und erhalten so eine erste Form der Umkreissuche:


<?php
$r = 50; // 50 Kilometer

$sql = 'SELECT
            vereine.*,
            coo.loc_id,
            coo.lon,
            coo.lat    
        FROM vereine
        INNER JOIN geodb_textdata AS textdata
        ON 
            textdata.text_val = vereine.PLZ
        AND textdata.text_type = "500300000"
        INNER JOIN geodb_coordinates AS coo
        ON textdata.loc_id = coo.loc_id
        WHERE
            ' . (2 * $Erdradius) . ' *
                ASIN(
                  SQRT(
                      POWER(' . $UrsprungX .' - ' . $Erdradius . ' * COS(coo.lat * PI() / 180) * COS(coo.lon * PI() / 180), 2)
                    + POWER(' . $UrsprungY .' - ' . $Erdradius . ' * COS(coo.lat * PI() / 180) * SIN(coo.lon * PI() / 180), 2)
                    + POWER(' . $UrsprungZ .' - ' . $Erdradius . ' * SIN(coo.lat * PI() / 180), 2)
                  ) / ' . (2 * $Erdradius) . '
                ) <= ' . $r . '
        ';
?>

Dieser SQL-Query ist sehr aufwendig, weil bei jeder Abfrage zu jedem Verein die Koordinaten transformiert und die Entfernung berechnet werden muss – egal, ob ein Verein sehr weit vom Suchmittelpunkt entfernt ist, oder nicht.

Vereinfachung und Modifikation

Darum modifizieren wir die Tabelle vereine und fügen die Spalten Longitude, Latitude, KoordX, KoordY und KoordZ hinzu, darin werden geographische Länge und Breite (nur zur Datensicherung) und die Umrechnung dieser Kugelkoordinaten in die kartesischen gespeichert. Somit entfällt im SQL-Query die Abfrage über drei Tabellen und die Umrechnung der Koordinatensysteme:


<?php
$sql = 'SELECT *
        FROM vereine
        WHERE
            ' . (2 * $Erdradius) . ' *
                ASIN(
                  SQRT(
                      POWER(' . $UrsprungX .' - KoordX, 2)
                    + POWER(' . $UrsprungY .' - KoordY, 2)
                    + POWER(' . $UrsprungZ .' - KoordZ, 2)
                  ) / ' . (2 * $Erdradius) . '
                ) <= ' . $r . '
        ';
?>

Trotzdem muss auch hier die Entfernung zu jedem Verein berechnet werden, bevor der Verein ggf. ins Ergebnis aufgenommen werden kann.
Dies kann weiter vereinfacht werden, indem einige Rechenoperationen (genaue Einzelschritte im Abschnitt Fragen und Antworten) von einer Seite der Ungleichung auf die andere gebracht werden:


<?php
$sql = 'SELECT *
        FROM vereine
        WHERE
              POWER(' . $UrsprungX .' - KoordX, 2)
            + POWER(' . $UrsprungY .' - KoordY, 2)
            + POWER(' . $UrsprungZ .' - KoordZ, 2)
        <= ' . pow(2 * $Erdradius * sin($r / (2 * $Erdradius)), 2) . '
        ';
?>

So können die aufwendigen arcsin- und Wurzelfunktions-Auswertungen reduziert werden, sodass für jeden Datensatz „nur“ noch drei Subtraktionen und Quadrierungen und zwei Additionen durchgeführt werden müssen.

Dieser Aufwand lässt sich weiter reduzieren, indem wir eine große Cache-Tabelle erzeugen, in der die Entfernungen zwischen jeder (deutschen) Postleitzahl und jedem Verein zwischengespeichert werden. Wird darin ein Index über die entsprechenden Spalten (PLZ, Verein-ID, Entfernung) gelegt, kann eine recht schnelle SQL-Abfrage durchgeführt werden. Bei diesem Verfahren ist eine letzte Möglichkeit der Datenreduktion, nur solche Datensätze zwischenzuspeichern, bei denen die Entfernung unter einer festgelegten Grenze liegt: Sollen über die Suche sowieso nur Ergebnisse in einem Umkreis bis maximal 200 Kilometer geliefert werden, müssen weiter entfernte PLZ-Verein-Paare nicht in die Cache-Tabelle aufgenommen werden.

Konkreter PHP-Code für die Umkreissuche

Die vereine-Tabelle sieht so aus:

CREATE TABLE `vereine` (

    `ID` INT( 10 ) UNSIGNED NOT NULL AUTO_INCREMENT ,

    `Name` VARCHAR( 255 ) NOT NULL ,

    `PLZ` CHAR( 5 ) NOT NULL ,

    `Longitude` DOUBLE NOT NULL ,

    `Latitude` DOUBLE NOT NULL ,

    `KoordX` DOUBLE NOT NULL ,

    `KoordY` DOUBLE NOT NULL ,

    `KoordZ` DOUBLE NOT NULL ,

    PRIMARY KEY ( `ID` ),

    KEY `Koord` (`KoordX`,`KoordY`,`KoordZ`)

) ENGINE = MYISAM

Die Zeile `Name`... ist ein Platzhalter für zusätzliche Einträge, wie Name des Vereins, Straße, Ortsname und Internetadresse.

Die folgende Klasse enthält alle notwendigen Funktionen:


<?php
/* * * * * * * * * * * * * * * * * * * * * * * * *
    Klasse Umkreissuche
    (c) 2008 Philipp Mamat
    http://www.mamat-online.de/
    http://www.mamat-online.de/umkreissuche/opengeodb.php
 * * * * * * * * * * * * * * * * * * * * * * * * */
 
class Umkreissuche {
    // Erdradius in Kilometern
    private $Erdradius = 6371;
    // mysql link identifier
    private $db;
    // Datentabelle
    private $table = false;
    // Fehler zeigen?
    public $zeigeFehler = true;

    public function __construct($db, $table = 'vereine') {
        if (!is_resource($db) || get_resource_type($db) != 'mysql link') {
            trigger_error('Keine MySQL-Ressource übergeben', E_USER_ERROR);
        }
        $this->db = $db;
        $this->table = $table;

        // leere Koordinaten in Tabelle füllen
        $sql = 'SELECT `ID`, `PLZ`
                FROM `' . $this->table . '`
                WHERE
                    `KoordX` = "0"
                AND `KoordY` = "0"
                AND `KoordZ` = "0"
                ';
        $re = mysql_query($sql, $this->db);
        while ($rd = mysql_fetch_object($re)) {
            if (!$this->Plz2Koord($rd->PLZ, $lon, $lat)) {
                if ($this->zeigeFehler) {
                    trigger_error('Postleitzahl ' . $rd->PLZ . ' konnte nicht zugeordnet werden', E_USER_NOTICE);
                }
                continue;
            }
            $this->Kugel2Kartesisch($lon, $lat, $x, $y, $z);
            $sql = 'UPDATE `' . $this->table . '`
                    SET
                        `Longitude` = "' . $lon . '",
                        `Latitude` = "' . $lat . '",
                        `KoordX` = "' . $x . '",
                        `KoordY` = "' . $y . '",
                        `KoordZ` = "' . $z . '"
                    WHERE
                        `ID` = "' . (int)$rd->ID . '"
                    LIMIT 1
                    ';
            mysql_query($sql, $this->db);
        }
    }
        
    public function Kugel2Kartesisch($lon, $lat, &$x, &$y, &$z) {
        $lambda = $lon * pi() / 180;
        $phi = $lat * pi() / 180; 
        $x = $this->Erdradius * cos($phi) * cos($lambda);
        $y = $this->Erdradius * cos($phi) * sin($lambda);
        $z = $this->Erdradius * sin($phi); 
        return true;
    }
    
    public function Plz2Koord($PLZ, &$lon, &$lat) {
        $sql = 'SELECT
                    coo.lon,
                    coo.lat
                FROM geodb_coordinates AS coo
                INNER JOIN geodb_textdata AS textdata
                ON textdata.loc_id = coo.loc_id
                WHERE
                    textdata.text_val = "' . mysql_real_escape_string($PLZ, $this->db) . '"
                AND textdata.text_type = "500300000"
                LIMIT 1';
        $re = mysql_query($sql, $this->db);
        if (mysql_num_rows($re) != 1) {
            return false;
        }
        list($lon, $lat) = mysql_fetch_row($re);
        return true;
    }
    
    public function Suche($PLZ, $Radius, $Spalten = array(), $Reihenfolge = false, $Richtung = 'ASC') {
        if (!is_array($Spalten) || count($Spalten) == 0) {
            $Spalten = '*';
        } else {
            $Spalten = '`' . implode('`, `', $Spalten) . '`';
        }

        if (!$this->Plz2Koord($PLZ, $lon, $lat)) {
            if ($this->zeigeFehler) {
                trigger_error('Postleitzahl ' . $PLZ . ' konnte nicht zugeordnet werden', E_USER_NOTICE);
            }
            return false;
        }
        $this->Kugel2Kartesisch($lon, $lat, $UrsprungX, $UrsprungY, $UrsprungZ);
        
        $sql = 'SELECT ' . $Spalten . '
                FROM `' . $this->table . '`
                WHERE
                    KoordX >= ' . ($UrsprungX - $Radius) . '
                AND KoordX <= ' . ($UrsprungX + $Radius) . '
                AND KoordY >= ' . ($UrsprungY - $Radius) . '
                AND KoordY <= ' . ($UrsprungY + $Radius) . '
                AND KoordZ >= ' . ($UrsprungZ - $Radius) . '
                AND KoordZ <= ' . ($UrsprungZ + $Radius) . '
                AND POWER(' . $UrsprungX .' - KoordX, 2)
                  + POWER(' . $UrsprungY .' - KoordY, 2)
                  + POWER(' . $UrsprungZ .' - KoordZ, 2)
                    <= "' . pow(2 * $this->Erdradius * sin($Radius / (2 * $this->Erdradius)), 2) . '"';
        if ($Reihenfolge && strpos($Spalten, $Reihenfolge) !== false) {
            $Richtung = (strtoupper($Richtung) == 'DESC') ? 'DESC' : 'ASC';
            $sql .= "\n" . 'ORDER BY `' . $Reihenfolge . '` ' . $Richtung;
        }
        $re = mysql_query($sql, $this->db);
        $result = array();
        while ($rd = mysql_fetch_object($re)) {
            $result[] = $rd;
        }
        return $result;
    }

}
?>

Der Übersichtlichkeit halber hier noch einmal die Funktionsdefinitionen:


<?php
function __construct($db, $table = 'vereine') { /* ... */ }
function Kugel2Kartesisch($lon, $lat, &$x, &$y, &$z)  { /* ... */ }
function Plz2Koord($PLZ, &$lon, &$lat) { /* ... */ }
function Suche($PLZ, $Radius, $Spalten = array(), $Reihenfolge = false, $Richtung = 'ASC') { /* ... */ }
?>

Der Constructor erwartet als einzigen Parameter eine gültige MySQL-Verbindungskennung, welche vorher mit der Funktion mysql_connect aufgebaut wurde. Außerdem sollte schon eine Datenbank mit mysql_select_db ausgewählt worden sein. Zweiter (optionaler) Parameter ist der Name der Datenbank-Tabelle (hier: vereine).
Mit der Funktion Kugel2Kartesisch werden die geographischen Kugelkoordinaten (Breite und Länge) in die passenden kartesischen Koordinaten umgerechnet. Statt das Ergebnis zurückzugeben, wird es in den Parametern $x, $y und $z gespeichert.
Die Funktion Plz2Koord ermittelt wie oben beschrieben die geographische Breite und Länge zu einer Postleitzahl. Wieder wird das Ergebnis in den Parametern gespeichert. Kann eine Postleitzahl nicht zugeordnet werden, gibt die Funktion false zurück.
Die zentrale Funktion heißt schlicht Suche. Erwartet werden als Parameter die Postleitzahl (PLZ) des Ursprungsorts und der Umkreis. Als drittes kann als optionaler Parameter ein Array angegeben werden, welches die zu ermittelnden Spalten der vereine-Tabelle enthält. Fehlt der Parameter, werden alle Spalten ins Ergebnis aufgenommen. Zurückgegeben wird ein Array mit den Ergebnisspalten. Außerdem können die Parameter Reihenfolge und Richtung angegeben werden. Das Ergebnis wird dann nach der als „Reihenfolge“ angegebenen Spalte sortiert – je nach dem „Richtungs“-Wert auf- oder absteigend.

Vor- & Nachteile

Beim Initialisieren der oben stehenden PHP-Klasse wird geprüft, ob es Einträge ohne Koordinaten gibt. Für diese Datensätze wird versucht, die fehlenden Koordinaten anhand der Postleitzahl zu ermitteln und nachzutragen.
Vorteil: Beim Füllen der Datenbank muss man sich noch keine Gedanken um die Koordinaten machen, das wird komplett von der PHP-Klasse erledigt.
Nachteil: Insbesondere bei großen und „jungfräulichen“ Datenbeständen braucht das Script sehr lange, um die passenden Koordinaten zu ermitteln. So wird der erste Aufruf für den Benutzer zur Qual – eventuell bricht der PHP-Parser sogar ab, weil die maximale Scriptlaufzeit überschritten wurde.
Lösung: Schon beim Anlegen oder Verändern eines Datensatzes wird die Funktion Plz2Koord aufgerufen. Nachdem so die geographischen Koordinaten ermittelt wurden, werden sie mit Hilfe von Kugel2Kartesisch in die kartesischen Koordinaten umgerechnet. Dann können alle 5 Koordinaten beim Datensatz gespeichert werden, die aufwendige Vorarbeit entfällt und die Umkreissuche ist sofort betriebsbereit. Wird dies sauber implementiert, kann der „leere Koordinaten in Tabelle füllen“-Teil im Constructor entfernt oder auskommentiert werden.

Kontakt, Copyright, Nutzung

Gerne dürfen Sie diese geistigen Ergüsse für eigene Projekte benutzen, auch die oben zitierte PHP-Klasse Umkreissuche. Bitte haben Sie Verständnis dafür, dass ich Korrektheit und Funktionsfähigkeit nicht garantieren kann. Darum schließe ich, soweit wie nach deutschem Recht möglich, jegliche Haftung für Schäden gleich welcher Art, die durch Nutzung oder Nichtnutzung dieses Dokuments oder Teilen davon (inkl. der dargestellten PHP-Klasse) entstehen, aus.

Ich freue mich über Kommentare, Fragen und Anregungen zur oben beschriebenen Umkreissuche. Wenn Sie einen Fehler finden, korrigiere ich diesen gerne! Schreiben Sie mir einfach eine E-Mail über das Kontaktformular meiner Homepage. Und wenn Sie einen Link auf diese Seite setzen wollen, bin ich Ihnen auch nicht böse.

Philipp Mamat, August 2008

Fragen und Antworten

Mir ist aufgefallen, dass ich zu verschiedenen Postleitzahlen die gleichen Daten bekommen:
Bei den drei Postleitzahlen 13156, 12099 und 14055 sind alle 5 Parameter (Longitude, Latitude, KoordX, KoordY, KoordZ) identisch.
Wie kann das kommen?

Ich habe einmal direkt in der Datenbank nachgeschaut:
Zur Postleitzahl 13156 ist die loc_id 14356 hinterlegt. Dieselbe Location-ID ist bei den Postleitzahlen 12099 und 14055 gespeichert. Von daher ist es kein Wunder, dass dieselben Daten herauskommen.

Alle Postleitzahlen sind Berliner Postleitzahlen. Für viel Großstädte gilt leider, dass die Geo-Daten nicht bis auf Stadtteilebene / Postleitzahlenbereiche genau gespeichert sind. Wer genauere Daten und Muße hat, sie in die OpenGeoDB einzutragen, erfährt genaueres über die Mailingliste der OpenGeoDB.
Mit diesem Aufruf rechne ich meinen km Radius ja in einen Wert um: pow(2 * $this->Erdradius * sin($Radius / (2 * $this->Erdradius)), 2)
In was genau rechne ich den Radius um? Und wie kann ich diesen Wert wieder in km bekommen?

Im Abschnitt Vereinfachung und Modifikation habe ich diskutiert, dass durch den obenstehenden Code die Entfernung zum Ursprung für jeden Datensatz berechnet wird. Dabei müssen für jeden Datensatz insbesondere die mathematischen Funktionen Wurzel ziehen und Arcus-Sinus (Umkehrfunktion der Sinus-Funktion) ausgewertet werden, was für den Webserver relativ aufwendig ist.

Durch einige Äquivalenzumformungen wird erreicht, dass stattdessen nur einmal (pro Aufruf der Umkreissuche, nicht pro Datensatz) die Funktionen Sinus und Quadrieren durchgeführt werden müssen.

Hier sind die Umformungen in Einzelschritten aufgeführt:

Dieser Wert hat in diesem Sinne keine Bedeutung, sondern dient nur der Vereinfachung innerhalb der Datenbankabfrage. Damit erübrigt sich die Frage, wie dieser Wert in Kilometer zurückgerechnet wird.
Wie kann ich das Suchergebnis um die berechnete Entfernung zum Ursprungsort ergänzen?

Entweder ergänzt man die Datenbankabfrage und lässt die Entfernung vom MySQL-Server berechnen: <?php $sql = 'SELECT ' . $Spalten . ', ' . (2 * $this->Erdradius) . ' * ASIN( SQRT( POWER(' . $UrsprungX .' - KoordX, 2) + POWER(' . $UrsprungY .' - KoordY, 2) + POWER(' . $UrsprungZ .' - KoordZ, 2) ) / ' . (2 * $this->Erdradius) . ' ) AS Entfernung FROM `' . $this->table . '` WHERE POWER(' . $UrsprungX .' - KoordX, 2) + POWER(' . $UrsprungY .' - KoordY, 2) + POWER(' . $UrsprungZ .' - KoordZ, 2) <= "' . pow(2 * $this->Erdradius * sin($Radius / (2 * $this->Erdradius)), 2) . '"'; ?> Oder sie wird von PHP innerhalb der while-Schleife berechnet: <?php while ($rd = mysql_fetch_object($re)) { $rd->Entfernung = 2* $this->Erdradius * asin( sqrt( pow($UrsprungX - $rd->KoordX, 2) + pow($UrsprungY - $rd->KoordY, 2) + pow($UrsprungZ - $rd->KoordZ, 2) ) / (2 * $this->Erdradius) ); $result[] = $rd; } ?> Dafür müssen die Datenbank-Felder KoordX, KoordZ und KoordZ zwingend in den abzufragenden Spalten aufgeführt sein! Das modifizierte SQL-Statement könnte so aussehen: <?php $sql = 'SELECT ' . $Spalten . ', KoordX, KoordY, KoordZ FROM `' . $this->table . '` WHERE POWER(' . $UrsprungX .' - KoordX, 2) + POWER(' . $UrsprungY .' - KoordY, 2) + POWER(' . $UrsprungZ .' - KoordZ, 2) <= "' . pow(2 * $this->Erdradius * sin($Radius / (2 * $this->Erdradius)), 2) . '"'; ?>
Gibt es ein Beispiel, an dem die Umkreissuche ausprobiert werden kann?

Ja, hier geht es zum Beispiel für eine Umkreissuche.
Das Beispiel verwendet die obenstehende PHP-Klasse und enthält einen Test-Datensatz. Es kann direkt online ausprobiert werden, steht aber auch zum Download und Installation auf dem eigenen Webspace zur Verfügung.
Woher kriege ich die OpenGeoDb? Wo kann ich die Datenbank herunterladen?

Die OpenGeoDb-Datenbank kann von der Sourceforge-Projekthomepage als „Package“ Data heruntergeladen werden. In diesem Text wird von der Datenstruktur der Version 0.2.5a ausgegangen.

Diese Seite bookmarken:

Diese Seite zu Social-Bookmarks hinzufügen

Auch interessant: Aufklappende Werbebanner mit JavaScript und CSS

Anzeige