Globus

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.

Inhalt

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 
$Erdradius *
                
arcsin(
                  
sqrt(
                      
pow($x1 $x22)    // Hinweis: pow($Basis, $Exponent) berechnet 
                    
pow($y1 $y22)    // "$Basis hoch $Exponent".
                    
pow($z1 $z22)    // Hier also "($z1 - $z2)^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
            ' 
. ($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)
                  ) / ' 
. ($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
            ' 
. ($Erdradius) . ' *
                ASIN(
                  SQRT(
                      POWER(' 
$UrsprungX .' - KoordX, 2)
                    + POWER(' 
$UrsprungY .' - KoordY, 2)
                    + POWER(' 
$UrsprungZ .' - KoordZ, 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($Erdradius sin($r / ($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.
Anzeige

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($this->Erdradius sin($Radius / ($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

Diese Seite bookmarken: Delicious Diese Seite zu Mister Wong hinzufügen oneview - das merk ich mir! Webnews Diese Seite zu Favoriten.de hinzufügen Diese Seite zu Social-Bookmarks hinzufügen
Auch interessant: Aufklappende Werbebanner mit JavaScript und CSS

Anzeige