Ein webbasierter Routenplaner für Motorradfahrer

Transcrição

Universität des Saarlandes
Naturwissenschaftlich-Technische Fakultät I
Fachrichtung Informatik
Diplom-Studiengang Informatik
Diplomarbeit
Ein webbasierter Routenplaner für
Motorradfahrer
vorgelegt von
Rainer Jochem
am 17. März 2008
angefertigt unter der Leitung von
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
betreut von Dr.-Ing. Jörg Baus
begutachtet von
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
Prof. Dr.-Ing. Philipp Slusallek
Erklärung
Hiermit erkläre ich, dass ich die vorliegende Arbeit selbständig verfasst
und alle verwendeten Quellen angegeben habe.
Saarbrücken, den 17. März 2008.
Einverständniserklärung
Hiermit erkläre ich mich einverstanden, dass meine Arbeit in den Bestand der Bibliothek der Fachrichtung Informatik aufgenommen wird.
Saarbrücken, den 17. März 2008.
Inhaltsverzeichnis
1
2
3
4
5
Einleitung
3
1.1
Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . .
4
Grundlagen webbasierter Routenplaner
6
2.1
Standards . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
Geographische Daten . . . . . . . . . . . . . . . . . . . . . .
11
2.3
GIS Überblick . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.4
Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.5
Berechnung benachbarter Orte . . . . . . . . . . . . . . . . .
18
2.6
Benutzen existierender Mapserver . . . . . . . . . . . . . . .
19
Übersicht existierender Routenplaner
20
3.1
Map24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2
Google Maps . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.3
Mapquest / AOL Routenplaner . . . . . . . . . . . . . . . . .
23
3.4
Yahoo Routenplaner . . . . . . . . . . . . . . . . . . . . . .
24
3.5
MSN Routenplaner . . . . . . . . . . . . . . . . . . . . . . .
25
3.6
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . .
26
Softwareevaluation
27
4.1
Geodatenserver . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2
Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.3
Desktopanwendungen . . . . . . . . . . . . . . . . . . . . . .
34
4.4
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . .
34
Konzeption des Webservices
35
5.1
Analyse des Kartenmaterials . . . . . . . . . . . . . . . . . .
35
5.2
Vorüberlegungen zur Routenplanung . . . . . . . . . . . . . .
43
1
INHALTSVERZEICHNIS
6
2
Erstellen des Webservices
51
6.1
Überblick über das CartoWeb-Framework . . . . . . . . . . .
51
6.2
Implementation in CartoWeb . . . . . . . . . . . . . . . . . .
54
7
Anwendungsbeispiel
60
8
Zusammenfassung und Ausblick
64
A Importieren des Kartenmaterials
66
B Installation von UMN Mapserver und Cartoweb
69
C Berechnung des Voronoidiagrammes
72
Kapitel 1
Einleitung
1.1
Motivation
Ziel der Arbeit ist die Entwicklung eines Routenplaners für Motorradfahrer,
welcher sich in den an ihn gestellten Ansprüchen von denen für Autofahrer unterscheidet. Hierzu soll ein internetbasierter Routenplaner entwickelt
und implementiert werden. Routenplaner stellen inzwischen im Internet einen
weit verbreiteten Dienst dar. Bekannte Vertreter sind www.mapquest.com,
www.map24.de oder maps.google.com. Diese bieten seit geraumer Zeit Webdienste an, mit deren Hilfe sich beispielsweise die schnellsten oder kürzesten
Routen von A nach B finden lassen. Diese Funktion ist für den üblichen Einsatzzweck, dem Finden einer Reiseroute zwischen verschiedenen Orten, auch
vollkommen ausreichend.
Für das Motorradfahren im Freizeitbereich ist diese Art der Routenplanung jedoch uninteressant. Hier geht es weniger darum, die kürzesten oder schnellsten
Routen zwischen zwei Orten finden, sondern das Motto lautet vielmehr ”Der
Weg ist das Ziel”. Dies bedeutet, dass die Wegstrecke selbst den eigentlichen
Reiz ausmacht. Im Gegensatz zur allseits bekannten Routenplanung werden
auch bewusst Umwege in Kauf genommen.
Es ist also zunächst zu klären, welche Kriterien eine Strecke für Motorradfahrer interessant machen. Hierzu gibt es eine Vielzahl an möglichen Parametern,
die auch teilweise stark von den persönlichen Interessen des potentiellen Benutzers abhängen. Betrachtet man Reiseberichte und Diskussionen der Motorradfahrer im Internet, z.B. www.jokko.de oder de.rec.motorrad im Usenet, so
3
KAPITEL 1. Einleitung
kann man den folgenden Kriterien eine zentrale Bedeutung beimessen:
• Anzahl und Art der Kurven
• Lage in landschaftlich reizvoller Umgebung
• Nähe zu interessanten Points of Interest (POIs), z.B. Sehenswürdigkeiten, aber auch Restaurants etc.
Ein weiterer Unterschied zur üblichen Routenplanung besteht darin, dass bei
Motorradtouren Start- und Zielpunkt in vielen Fällen identisch sind, beispielsweise bei einer Wochenendtour ausgehend vom eigenen Wohnort. Des Weiteren sollte der Routenplaner in der Lage sein, auf Wunsch auch alternative Routen zwischen zwei Orten anbieten zu können. Das Kernziel dieser Anwendung
ist also das automatisierte Auffinden neuer und unbekannter Motorradrouten
für den Freizeitbereich.
Zu guter Letzt sollte es dem Benutzer möglich sein, die berechneten Routen
exportieren zu können, um ihre Verwendung in Navigationssystemen zu ermöglichen.
Um einen solchen Webservice zu erstellen bieten sich zwei Alternativen an:
zum einen kann auf bestehende Webservices aufgebaut werden, beispielsweise
mit der frei zugänglichen API von Map24. Der zweite Ansatz besteht darin,
einen eigenen Webservice unter Verwendung hierfür geeigneter Software zu
implementieren.
1.2
Aufbau der Arbeit
Kapitel 2 beschreibt die für diese Arbeit wichtigen Grundlagen. So wird zunächst die grundlegende Architektur eines webbasierten Routenplaners beschrieben und die damit verbundenen Standards und Datenformate aus der
Geoinformatik vorgestellt. Weiterhin werden verschiedene Routingalgorithmen und Optimierungsmöglichkeiten für die Routenplanung auf großen Graphen kurz vorgestellt.
In Kapitel 3 wird eine Übersicht und Bewertung des Funktionsumfangs der
derzeit am Markt befindlichen webbasierten Routenplaner gegeben.
4
1.2. Aufbau der Arbeit
Ausgehend von den in den vorherigen Kapiteln definierten Anforderungen beschäftigt sich Kapitel 4 mit der Evaluation der für die Implementation in Frage
kommenden Software.
Anschließend erfolgt in Kapitel 5 eine Analyse des Kartenmaterials auf deren
Grundlage die Methoden zur automatisierten Routenberechnung für Motorradfahrer entwickelt werden.
Kapitel 6 beschreibt die Implementation der gewonnenen Ergebnisse in Form
eines Prototyps eines webbasierten Routenplaners für Motorradfahrer, welcher
in Kapitel 7 mit einem Anwendungsbeispiel vorgestellt wird.
Ein Ausblick schließt die Arbeit ab. Im Anhang werden schließlich Quellcodebeispiele der relevanten Funktionen und Konfigurationsdateien aufgeführt.
5
Kapitel 2
Grundlagen webbasierter
Routenplaner
Bevor wir uns mit der Implementation befassen, wollen wir den Aufbau eines
solchen Webservices ausgehend vom Endbenutzer untersuchen. Der Endbenutzer verwendet als Client-Software für den Webservice einen Internetbrowser. Dieser hat die Aufgabe das komplette Benutzerinterface darzustellen, Anfragen an den Webservice zu leiten und die daraus resultierenden Karten zu
visualisieren. Für den Endbenutzer verhält sich dieser Webservice wie jede andere Webseite, bei der eine Anfrage an einen Server gestellt und von diesem
mit einer entsprechenden Ausgabe beantwortet wird. Die Unterschiede werden erst auf Seiten des Webservers deutlich. Hier müssen nicht nur die HTTPAnfragen des Clients, sondern auch die geographischen Anfragen und Veränderungen der Kartendarstellung verarbeitet werden. Hierzu kommen neben
einem gewöhnlichen Webserver für die HTTP-Anfragen spezielle Kartendienste zum Einsatz. Ihre Aufgabe ist es, anhand der jeweiligen Anfrage diverse
Berechnungen auf Grundlage des Kartenmaterials durchzuführen und aus dem
Ergebnis dieser Anfragen und Berechnungen eine im Webbrowser darstellbare Karte zu erzeugen. Anfragen können u.a. das Verschieben oder Vergrößern
eines Kartenausschnittes sein. Eine Berechnung ist beispielsweise das Finden
einer Route zwischen zwei Punkten. Als Basis für all diese Operationen wird
schließlich noch Kartenmaterial benötigt, welches üblicherweise als vektorbasierte Geometrie zusammen mit weiteren Informationen in einer Datenbank
vorliegt (siehe Abb. 2.1). Diese Kartendienste werden auch als Web GIS oder
Web Mapping bezeichnet. Man unterscheidet statische, dynamische und verteilte Kartendienste. Statische Kartendienste liefern feste, vordefinierte Kar-
6
GIS-Server
Webserver
Geographische
Berechnungen
Benutzer
HTTP-Request
Datenbank
HTTP-Response
Kartenbild
Web-GIS
WMS
Abbildung 2.1: Aufbau eines Web GIS. Der Benutzer stellt eine HTTPAnfrage an einen Webserver, welcher mit Hilfe eines GIS-Systemes ein dynamisch generiertes Kartenbild zurückliefert.
tenausschnitte in Form von Bildateien (JPEG, PNG, GIF, ...) an den Benutzer.
Dies bietet jedoch keine Form von Interaktivität für den Endbenutzer, da er
nur zwischen vorbestimmten Ansichten wählen kann. Das Gegenteil hiervon
stellen die dynamischen Kartendienste dar, welche erst aufgrund einer Anfrage
eines Benutzers eine entsprechende Karte mit den gewünschten Details erzeugen und diese dann als Bilddatei an den Benutzer senden. Das Erzeugen der
Bilddatei obliegt hierbei einem sogenannten Web Map Server (WMS), welcher
hierfür auf entsprechende Datenquellen mit Kartenmaterial, meist in Form einer Datenbank, zugreift. Ähnlich arbeiten die verteilten Kartendienste, wobei
hier Webserver, WMS und Datenquellen auf beliebig viele Server verteilt sein
können. Damit in beiden Fällen ein Datenaustausch der einzelnen Bestandteile
untereinander möglich ist, werden entsprechende Standards benötigt.
7
KAPITEL 2. Grundlagen webbasierter Routenplaner
2.1
Standards
Für diese Geoinformationssysteme (GIS) und deren Schnittstellen existieren
offene Standards, welche durch das Open Geospatial Consortium (OGC) [1]
festgeschrieben werden. Etliche dieser Standards sind auch ISO-Standards.
Das OGC ist eine gemeinnützige Organisation, die aus einem internationalen
Zusammenschluss verschiedener Unternehmen, Universitäten und Behörden
(347, Stand Dez 2007) besteht und deren Ziel in der Erarbeitung allgemeiner Standards für die Interoperabilität von GIS-Systemen liegt. Im Folgenden
werden die wichtigsten Standards kurz vorgestellt.
WMS - Web Map Service
Aufgabe des WMS ist es, aus ihm zu Grunde liegenden geographischen Rasteroder Vektorgeometrien eine Karte zu visualisieren, welche dann als Rastergrafik oder auch als Vektorgrafik wie SVG ausgegeben wird. WMS-Anfragen
können mit jedem Internetbrowser durch den Aufruf von entsprechenden
URLs gestellt werden. Der OGC-Standard spezifiziert hierbei drei Typen von
Anfragen, die per HTTP an den WMS gestellt werden können:
GetMap liefert das angeforderte Kartenbild als Rastergrafik vom WMS zurück. Hierbei können die gewünschten Details des Kartenausschnitts als
Optionen in der Anfrage spezifiziert werden.
GetFeatureInfo kann Informationen zum Inhalt eines Kartenausschnitts, wie
die Eigenschaften eines Objekts an einer bestimmten Position, liefern.
GetCapabilities gibt die Fähigkeiten des WMS, welche Art von Kartentypen
verarbeitet werden können, zurück.
GML - Geography Markup Language
GML ist eine XML-Sprache zur Kodierung von Geodaten sowie ein Austauschformat für geographische Daten in Netzwerken. Zu den Basiselementen
von GML, auf welchen weitere Schemata und Profile aufbauen, gehören die
sogenannten Merkmale (Features), Geometrien und Koordinatenreferenzsysteme. Geometrien beschreiben hierbei geographische Objekte wie beispielswei-
8
2.1. Standards
se Straßen und unterstützen dabei als Geometrieobjekte Punkte, Linien und
Polygone. Merkmale sind hingegen Objekte, welche Elemente der realen Welt
beschreiben und nicht notwendigerweise einen geometrischen Bezug haben
müssen. Ein Merkmal kann allerdings auch mehrere geometrische Eigenschaften besitzen. Beispielsweise kann ein Merkmal “Sendeturm” als Standort eine
Punktgeometrie besitzen, eine weitere Geometrie welche die Größe des Bauwerks beinhaltet und eine dritte, welche den Empfangsbereich darstellt.
<complexType name="RadioTowerType">
<complexContent>
<extension base="gml:AbstractFeatureType">
<sequence>
<element name="location" type="gml:PointPropertyType"/>
<element name="floorSpace" type="gml:SurfacePropertyType"/>
<element name="serviceArea" type="gml:SurfacePropertyType"/>
</sequence>
</extension>
</complexContent>
</complexType>
Mittels eines Koordinatenreferenzsystems wird schließlich die genaue geometrische Position einer Geometrie definiert. Unterstützte Referenzsysteme sind
beispielsweise die durch die European Petroleum Survey Group definierten
EPSG-Codes. Hierbei entspricht EPSG:4326 dem WGS84-Standard (World
Geodetic System), welcher das verbreitete Koordinatensystem aus Längenund Breitengraden ausgehend vom Nullmeridian in Greenwich beschreibt.
Weiterhin unterstützt GML verschiedene Profile, welche nur bestimmte Teilmengen der GML-Elemente beinhalten, um somit eine Vereinfachung für bestimmte Anwendungsgebiete zu erreichen. Beispielsweise wird das “GML
Simple Features profile”, welches nur einfache Vektorgeometrien beinhaltet,
für Abfragen in WFS-Systemen eingesetzt. Seit der Version 3.1.1 ist GML
auch eine ISO Norm (ISO 19136).
Verwandt mit GML ist die von Google verwendete Keyhole Markup Language (KML). Mit Version 2.2 wurde die KML-Spezifikation dem OGC zur
Standardisierung vorgelegt, um diese als offenen Standard festzuschreiben. Im
Unterschied zu GML, welches Objekte mit ihren Eigenschaften beschreibt,
dient KML jedoch dazu geographische Information zu visualisieren. Allerdings kann KML auch GML-Inhalte transportieren und GML-Ausgaben können auch in ein KML-Format gebracht werden.
9
SFS - Simple Feature Specification
Die Simple Feature Spezifikation beschreibt sowohl die verfügbaren Geometrien wie Punkt, Linie, Polygon, Multipolygon, uvm., als auch räumliche Operationen, um vorhandene Geometrien zu modifizieren oder neue zu erstellen.
Hierzu gehören beispielsweise Funktionen mit welchen sich die Distanz zwischen zwei Punkten oder die Fläche eines Polygons berechnen lassen. Um
einen systemübergreifenden Zugriff auf geographische Daten zu ermöglichen
existieren hierbei drei unterschiedliche Spezifikationen, je eine für OLE/COM,
CORBA und SQL.
WFS - Web Feature Service
Mittels der WFS-Schnittstelle kann ein Benutzer unter Verwendung von GML
geographische Informationen mit verschiedenen WFS-Systemen austauschen
und verändern. Der Standard umfasst die folgenden WFS-Operationen:
• Erstellen eines neuen Merkmals
• Löschen eines Merkmals
• Aktualisieren eines Merkmals
• Sperren eines Merkmals
• Abfragen eines Merkmals anhand räumlicher oder nichträumlicher Eigenschaften
Hierbei werden zwei Arten von WFS unterschieden: einfaches WFS, welches
nur die Abfrage von Merkmalen unterstützt, und WFS-T (transactional WFS),
welches alle der oben aufgeführten Operationen unterstützt. Zur Darstellung
der so angeforderten geographischen Informationen kann dann ein WMS benutzt werden.
Wie diese Standards zusammenwirken ist in Abbildung 2.2 dargestellt. Mittels des WFS kann auch schreibend auf die gespeicherten Daten zugegriffen
werden. Der WMS erlaubt die Ausgabe einer graphischen Repräsentation der
Geodaten.
10
2.2. Geographische Daten
GMLFormat
Kartengrafik
Web Feature Service
Web Map Service
Features
Simple Features Specification
Datenquelle
Abbildung 2.2: Zusammenspiel der verschiedenen OGC-Standards.
Bei der Umsetzung der Standards unterscheidet das OGC in OGCkonforme und OGC-implementierende Anwendungen. Dabei haben die OGCkonformen Anwendungen entsprechende Tests durch das OGC durchlaufen
und wurden vom OGC als konform zertifiziert. Anwendungen, welche die
Tests des OGC noch nicht bestanden haben, werden als OGC-implementierend
bezeichnet. Eine Liste der OGC-konformen und OGC-implementierenden Anwendungen kann auf der Webseite des OGC eingesehen werden.
2.2
Geographische Daten
Nachdem der Aufbau eines Web GIS und die zugehörigen Standards betrachtet wurden, fehlen noch die eigentlichen Inhalte, die sogenannten Geodaten,
welche in einem solchen System verarbeitet werden. Diese können dabei sowohl in Form einzelner Dateien als auch in einer Datenbank gespeichert werden. Für die Speicherung in Form von Dateien haben sich die ESRI-ShapefileFormate[2] (ein von der Firma Environmental Systems Research Institute entwickeltes Dateiformat) als quasi-Standard etabliert. Ein Shapefile besteht an
sich aus drei verschiedenen Dateien, welche das gleiche Prefix aber unterschiedliche Dateiendungen tragen.
11
Hierbei beinhalten Dateien mit der Endung
• *.shp die eigentliche Geometrie,
• *.dbf die sogenannten Sachdaten (Attribute) als dBASE-Tabelle und
• *.idx einen Index zur Verknüpfung von Geometrie und Sachdaten.
Die geographischen Daten werden hierbei auch als Basis- oder Primärdaten
bezeichnet, da sie in der Regel direkt auf physikalischen Messwerten beruhen,
wie beispielsweise die Art und Länge eines Straßenverlaufes. Diesen Daten
werden dann Sachdaten hinzugefügt, welche für sich betrachtet keinerlei geometrische Informationen beinhalten, sondern erst durch die Verknüpfung mit
den zugehörigen Basisdaten einen geographischen Bezug erhalten. Sachdaten
können bei einer Straße beispielsweise den
• Straßennamen,
• Straßentyp,
• Art des Straßenbelags uvm. beinhalten.
Im Zuge einer strukturierten Datenhaltung werden Daten, die sich mit den gleichen Objekten befassen relational zusammengefasst. So würden für Straßendaten die Dateien strassen.shp, strassen.dbf und strassen.idx entstehen. Während
die Sachdaten anhand der für ihren jeweiligen Datentyp verfügbaren Operationen miteinander verknüpft werden können, existieren für die geometrischen
Basisdaten topologische Verknüpfungen. So können topologische Relationen
zwischen verschiedenen Geometrien, wie beispielsweise A schneidet B, A liegt
innerhalb B, A ist disjunkt zu B, verwendet werden.
Als Alternative zur Datenhaltung in Form von Shapefiles besteht auch die
Möglichkeit diese Informationen in einer Datenbank zu speichern. Dies hat
den Vorteil, dass insbesondere in verteilten, netzwerkbasierten Umgebungen
effizient auf die Daten zugegriffen werden kann. Als Datenbank bieten sich
relationale SQL-Datenbanken an. Für diese existiert wie in Kapitel 2.1 beschrieben die SFS-Spezifikation des OGC, welche die Speicherung von Geometrien in SQL-Datenbanken definiert. Hierbei ist zu beachten, dass eine solche Datenbank auch in der Lage ist mit den notwendigen räumlichen Daten
12
2.2. Geographische Daten
umzugehen. So existieren beispielsweise für Oracle, MySQL und PostgreSQL entsprechende Erweiterungen, welche den OGC-Standard implementieren
und das Speichern von räumlichen Daten ermöglichen. Die Sachdaten werden
hierbei wie üblich in der Datenbank mit den jeweiligen Datentypen abgespeichert. Datenbanken, welche derartige geographische Informationen speichern
können werden auch als Geodatenbanken bezeichnet.
Sachdaten
Namen, IDs, Werte,
Zusatzinformationen, ...
Straßenname
PLZ
Hauptstraße
Rathausplatz
L 123
...
4711
4711
NULL
...
Geodaten
Punkte, Linien, Polygone
Straßentyp
Innerorts
42
42
7
...
Y
Y
N
...
geometry
0106000020E6100010300000003000000E3230...
0106000020E6104A5100D50000300000024230...
010600DA30013DE40026100010300000300042...
...
Abbildung 2.3: Sachdaten werden mit den jeweiligen Datentypen (Integer,
String, Boolean, ...) in der Tabelle gespeichert. Die Geometrien (Punk, Linie,
Polygon) werden in einer textuellen Repräsentation den jeweiligen Sachdaten
zugeordnet.
Wie bereits erwähnt, stellen Shapefiles einen quasi-Standard für das Speichern
von Geodaten dar. Um diese Daten in einer Geodatenbank abspeichern zu können existieren für viele Geodatenbanken entsprechende Importfilter, welche
die Basisdaten mit den Sachdaten verknüpfen und in einer jeweiligen Tabelle
in der Geodatenbank hinterlegen (siehe Abbildung 2.3). An dieser Stelle wird
ein weiterer Vorteil von Geodatenbanken gegenüber Shapefiles deutlich: Es ist
nun relativ leicht, mittels geeigneter SQL-Anfragen die Datensätze zu filtern,
zu durchsuchen oder zu modifizieren.
13
2.3
GIS Überblick
Waren Anfang des letzten Jahrhunderts gedruckte Landkarten das Werkzeug
schlechthin um mit raumbezogenen Informationen zu arbeiten, so haben seit
den 60er Jahren zusammen mit zunehmendem Aufkommen der Computertechnologie rechnergestützte Geoinformationssysteme an Bedeutung gewonnen.
Heute haben Geographische Informationssysteme (GIS) eine weite Verbreitung gefunden. Sei es als Landinformationssystem im Kataster- und Vermessungswesen, als Umweltinformationssystem zur Analyse und Visualisierung
von Hochwassergefahrenzonen oder bei der Verwaltung von Kundendaten in
global operierenden Unternehmen.
Bis in die Mitte der 90er Jahre bestanden GIS-Systeme meist aus entsprechend leistungsfähigen einzelplatzbasierten Desktop-Systemen. Mit zunehmender Vernetzung von Rechnersystemen hat auch der Datenaustausch via
Netzwerk Einzug gehalten und zur Entstehung verteilter Geoinformationssysteme mit entsprechenden gemeinsamen Schnittstellen geführt. Mit Web Mapping Diensten wie Google Maps haben Kartendienste geographische Informationen in das breite Licht der Öffentlichkeit gerückt, wenngleich klassische
GIS-Funktionalitäten in diesen Systemen erst im Entstehen sind.
Aktuelle Entwicklungen im GIS-Umfeld umfassen die Verbindung von Techniken des Semantic-Web mit Web GIS-Systemen. So wurden beispielsweise
vom World Wide Web Consortium (W3C) im Rahmen der W3C Geospatial
Incubator Group [3] grundlegende Ontologien für die Repräsentation geospatialer Eigenschaften im Internet erarbeitet. Sind beispielsweise Webseiten mit
entsprechenden geographischen Informationen versehen, so könnte eine Suchmaschine einem Benutzer bei einer Suchanfrage nach Einkaufsmöglichkeiten
nur die Webseiten zurückliefern, die sich auch in seiner Reichweite befinden.
Eine weitere Anwendung sind GeoRSS-Feeds, bei denen die Inhalte des Feeds
mit geographischen Positionen verknüpft sind. Anzeigen lassen sich die Inhalte solcher Feeds beispielsweise mit Google Maps.
Weiterhin arbeitet das OGC an der Integration von Sensorinformationen in
GIS-Systeme (Sensor Web Enablement). Auch die Erweiterung von Geoinformationssystemen für mobile Endgeräte insbesondere im Zusammenhang mit
Location Based Services wird derzeit weiter vorangetrieben.
14
2.4. Routing
2.4
Routing
Eine weitere zentrale Komponente des zu implementierenden Webservices ist
das Routing über das Straßennetz. Straßennetze können leicht in Form eines gewichteten Graphen G = (V, E, c) mit Knoten V , Kanten E und einem für den jeweiligen Anwendungszweck gewählten Kantengewicht c repräsentiert werden. Kreuzungen stellen hierbei Knoten und Straßensegmente
die Kanten dar. Für das Berechnen kürzester Wege bietet sich als Kantengewicht die Distanz zwischen Start- und Zielpunkt des Segments an. Auf diesem Graphen können nun mittels eines geeigneten Routingalgorithmus die gesuchten Strecken berechnet werden. Zur Lösung dieses Problems existieren
die folgenden Ansätze: Zum einen kann ein All Pairs Shortest Paths (APSP)Algorithmus zur Berechnung aller kürzesten Wege zwischen allen Knoten wie
etwa der Algorithmus von Floyd-Warshall [4] genutzt werden. Die Laufzeit
dieses Algorithmus liegt in O(|V |3 ). Der Nachteil einer solchen Lösung liegt
darin, dass alle möglichen Pfade vorberechnet werden müssen, was sehr zeitund insbesondere auch platzaufwändig ist. Des Weiteren zieht jede Änderung
im Straßengraphen eine aufwändige Neuberechnung nach sich.
Eine weitere Möglichkeit sind Single Source Shortest Paths (SSSP)Algorithmen. Hier wird ausgehend von einem Startknoten der kürzeste Weg
zu allen Zielknoten errechnet. Der bekannteste Algorithmus zur Lösung dieses Problems ist der Algorithmus von Dijkstra [5], welcher bei Verwendung
von Fibonacci heaps als Prioritätswarteschlange eine Laufzeit von O(|E| +
|V |log|V |) besitzt. Da das Interesse beim Routing in Straßennetzen allerdings
an einer Route zwischen einem Start und Ziel liegt, wird üblicherweise zusätzlich mit Abbruchkriterien gearbeitet die den SSSP-Algorithmus beenden,
sobald das Ziel erreicht ist. Man spricht in diesem Fall auch von Single Pair
Shortest Paths oder Source Target Shortest Paths, wobei die Laufzeit dieser
Algorithmen im Worst Case jedoch gleich einem SSSP-Algorithmus sind. Da
SSSP-Algorithmen allerdings auf großen Graphen, z.B. Straßennetzen, viel
Zeit zur Berechnung benötigen, ist es hilfreich einen Blick auf eine Reihe
möglicher Optimierungen zu werfen. Mit diesen sind Vorberechnungen auf
dem Graphen möglich, welche dann die spätere Ausführung der Suchanfrage,
insbesondere bei solch großen Graphen, teils erheblich beschleunigen können.
Hierbei lassen sich die verschiedenen Optimierungsmöglichkeiten auch teilweise miteinander kombinieren. Mögliche Optimierungen sind:
15
Bidirektionale Suche: Bei der bidirektionalen Suche wird nicht nur vom
Start- sondern auch gleichzeitig vom Zielknoten aus eine Suche gestartet. Die Suche kann beendet werden, sobald sich die beiden Suchräume
treffen. Somit lässt sich die Suchzeit halbieren. Dies erfordert lediglich
eine Anpassung des Suchalgorithmus und benötigt keinerlei Vorberechnungen [6].
A*: Der A*-Suchalgorithmus ist eine informierte Suche, welche sich einer
Heuristik bedient, um zielgerichtet zu suchen [7]. Hierbei werden vorrangig die Knoten betrachtet, welche am wahrscheinlichsten zum Ziel
führen. Dabei darf die Heuristik die tatsächlichen Kosten zum Ziel nicht
überschätzen. Für die Berechnung von kürzesten Wegen bietet sich die
euklidische Distanz zwischen den jeweils betrachteten Knoten an, da
dies die bestmöglichste Entfernung ist, welche nicht unterschritten werden kann. Hierzu wird jedem Knoten ein Funktionswert
f (x) = g(x) + h(x)
zugeordnet, der die Länge vom Start zum Ziel für den günstigsten Fall
angibt. Der Funktionswert setzt sich hierbei aus der tatsächlichen Distanz g(x) vom Start bis zum aktuellen Knoten und der durch die Heuristik geschätzten Distanz h(x) bis zum Ziel zusammen. Die Laufzeit des
Algorithmus hängt dabei von einer geeigneten Heuristik ab.
Reach-based routing: Hier wird für jeden Knoten ein sogenannter ReachWert ermittelt, welcher von der Länge des kürzesten Pfades abhängt auf
dem er sich befindet [8]. Der Wert ist umso höher, je größer die Länge des kürzesten Pfades ist. Sucht man über diesen Graphen, werden
Knoten die nicht auf einem solchen Pfad liegen nicht berücksichtigt. Allerdings wird hierfür eine zeitaufwändige Vorberechnung benötigt.
Highway Hierarchien: Dieses Verfahren nutzt eine Vorberechnung auf dem
Straßengraphen, welche sich die Hierarchien im Straßennetz zunutze
macht [9]. Hierzu werden im Straßengraphen wichtige Kanten bestimmt
und die so entstehenden Teilgraphen können vereinfacht werden. Die
nun rekursiv entstandenen Ebenen bilden eine hierarchische Darstellung
des Straßennetzes, auf der dann mittels einer angepassten Version einer bidirektionalen Suche mit dem Algorithmus von Dijkstra gearbeitet
werden kann.
16
2.4. Routing
Weitere Optimierungsmöglichkeiten sind zum einen das Verwenden von Kantenmarkierungen (edge labels) welche zu jeder Kante den Knoten mit dem kürzesten Weg zum Startknoten der Kante speichern [10]. Des weiteren kann die
Geometrie des Graphen verwendet werden: so lässt sich mit Hilfe von Bounding Boxes der Suchraum ebenfalls verkleinern.
Eine weitere Besonderheit von Straßennetzen ist, dass es sich um einen gerichteten Graphen handelt, da beispielsweise Einbahnstraßen und Autobahnen nur
in eine Richtung befahrbar sind. Darüberhinaus bestehen auch aus verkehrstechnischen Gründen lokale Abbiegeverbote, wodurch der Graph je nachdem
aus welcher Richtung man sich einer Kante nähert unterschiedlich gerichtet
sein kann. Eine Lösung für diese Problematik findet sich in beispielsweise in
[11].
Da das für diese Arbeit zu Grunde liegende Straßennetz jedoch über keinerlei
Informationen zu erlaubten Richtungen verfügt, wurde das gesamte Straßennetz als ungerichteter Graph betrachtet, bei dem alle Abbiegemanöver erlaubt
sind. Es wurde weiterhin auf die Anwendung von zeitund platzaufwändigen
Vorberechnungen zur Optimierung der Suchanfragen verzichtet, da dies insbesondere bei der Evaluation verschiedener Lösungsmöglichkeiten den Rahmen
dieser Arbeit gesprengt hätte.
17
2.5
Berechnung benachbarter Orte
Eine weitere Komponente eines Kartendienstes stellt das Auffinden benachbarter Orte dar. Hier soll zu einem gegebenen Suchpunkt aus einer Menge
von möglichen Zielen jenes gefunden werden, welches dem Suchpunkt am
nächsten liegt. Die naive Methode würde darin bestehen, den Suchpunkt mit
allen in Frage kommenden Zielen zu vergleichen, um von jedem die kürzeste
Distanz zu berechnen. Dieser Ansatz verbietet sich jedoch bei großen Datenmengen. Eine Lösung stellt hier im zweidimensionalen Raum die Verwendung
sogenannter Voronoi-Diagramme dar. Diese werden über der zu betrachtenden Menge der Zielpunkte erstellt und teilen die Ebene in eine Vielzahl von
Polygone auf, welche jeweils genau einen Zielpunkt enthalten. Dabei ist jedes
Polygon derart geformt, dass sich in seinem Inneren exakt die Punkte befinden,
welche dem jeweiligen Zielpunkt am nächsten sind.
Abbildung 2.4: Ausschnitt eines Voronoi-Diagramms. Gelb dargestellt die
Punktmenge um die die Voronoi-Polygone berechnet wurden.
Existiert eine solche Menge an Zielpunkten, beispielsweise eine Liste verschiedener Sehenswürdigkeiten, so kann man über diese Ziele ein VoronoiDiagramm vorberechnen. Soll nun zu einer beliebigen Suchposition die
nächstgelegene Sehenswürdigkeit ermittelt werden, so muss lediglich überprüfet werden, in welchem Polygon sich die Suchposition befindet. Da jedem
Polygon exakt eine Sehenswürdigkeit zugeordnet ist erhält man direkt das gewünschte Ergebnis. Diese Operationen können insbesondere unter Verwendung von geometrischen Indizes in einem GIS-System sehr effizient erfolgen.
18
2.6. Benutzen existierender Mapserver
2.6
Benutzen existierender Mapserver
Wie in Kapitel 2 erwähnt gibt es für das Erstellen eines Navigationswebservices zwei Möglichkeiten. Zum einen soll das Aufsetzen auf bereits existierende Webservices mittels frei zugänglicher Schnittstellen betrachtet werden.
Im ersten Ansatz sollte daher die frei zugängliche API von Map24 [12] verwendet werden. Allerdings erfüllte die Map24-API (Stand Okt. 2006, API <
1.2.8) die in Kapitel 1 erwähnten Anforderungen nur bedingt. Anforderungen
die nicht erfüllt wurden, waren:
• Zugriff auf die Sachdaten, um über die Attraktivität einer Strecke zu
entscheiden
• Zugriff auf die Geometriedaten, um Berechnungen zur Relation einzelner Orte zueinander durchzuführen
• Möglichkeit, auf den zu Grunde liegenden Straßengraphen zuzugreifen, um die Kantengewichte für den Routingalgorithmus beeinflussen
zu können
Dadurch bietet die API keine Möglichkeit auf die zu Grunde liegenden Sachund Geometriedaten zuzugreifen, um beispielsweise die Anzahl der Kurven
zu ermitteln. Auch gibt es keine Möglichkeiten gezielt bestimmte Points of
Interest (POI) abzufragen. Ausserdem kann nur der von Map24 bereitgestellte
Routingalgorithmus mit einer vorgegebenen Parametermenge verwendet werden. Es besteht keine Möglichkeit einen eigenen Routingalgorithmus einzubinden oder den Bestehenden zu modifizieren, um beispielsweise andere Kantengewichte zu verwenden.
Da sich dieser erste Ansatz aus genannten Gründen als ungeeignet erwies, fiel
die Entscheidung einen eigenen Webservice mit Hilfe eines Geodatensatzes
der Bundesrepublik Deutschland zu erstellen, obwohl dies bedeutet, dass zusätzlich ein Web GIS benötigt wird, um diese Daten verarbeiten und in einem
Browser darstellen zu können.
19
Kapitel 3
Übersicht existierender
Routenplaner
Nach der Betrachtung der Grundlagen eines WebGIS Systemes sollen im
Folgenden verschiedene bestehende Routenplaner im Internet vorgestellt und
deren Funktionsumfang untersucht werden. Zu den großen und bekannten
Diensten, welche schon seit vielen Jahren bestehen, zählen Map24, Mapquest,
Google Maps, Yahoo Routenplaner sowie MSN Routenplaner.
3.1
Map24
Seit dem Jahr 2000 bietet die Mapsolute GmbH mit Map24 einen interaktiven
Routenplaner im Internet an. Zu den verfügbaren Routingoptionen zählen das
Berechnen einer kürzesten und schnellsten Route. Der Benutzer hat weiterhin
die Möglichkeit verschiedene Straßentypen wie Autobahnen, kostenpflichtige
Straßen, Fährverbindungen oder Autozüge von der Suche auszuschließen. Darüberhinaus kann eine zu verwendende Fahrzeugart gewählt werden, wobei sich
dies lediglich auf die ebenfalls durch den Nutzer wählbare Höchstgeschwindigkeit für verschiedene Straßentypen auswirkt. Jedoch hat eine Änderung der
Geschwindigkeiten für die verschiedenen Straßentypen keinerlei Einfluss auf
die Berechnung der Route sondern wirkt sich lediglich auf die Berechnung der
Fahrtdauer aus. Zu den besonderen Funktionen von Map24 zählt das Auffinden von Sonderzielen wie Sehenswürdigkeiten, Restaurants usw. entlang einer
berechneten Route.
20
3.2. Google Maps
Abbildung 3.1: Darstellung einer Route im Webinterface von Map24
(Quelle: Mapsolute GmbH, www.map24.de)
Zur Navigation durch das Kartenmaterial stehen dem Benutzer verschiedene
Operationen wie Verschieben des Kartenauschnittes, Zoom, Messen von Distanzen und Hervorheben von Kartenelementen zur Verfügung. Die Kartenlayer beinhalten das Straßen- und Schienennetz, Gewässer sowie bebaute Gebiete. Die Farbgebung ist hier komplett in verschiedenen Orangetönen gehalten. Neben der reinen Darstellung der Vektordaten wird auch eine Ansicht mit
Satellitenphotos im Hintergrund angeboten. Ab einem bestimmten Zoomlevel
werden weiterhin POIs in die Kartenanzeige eingebettet. Eine weitere Besonderheit ist die Anzeige von Informationen zu den Kartenelementen die sich
gerade unter dem Mauszeiger befinden. So lassen sich beispielsweise leicht
weitere Informationen zu angezeigten POIs darstellen. Map24 stellt ebenfalls
aktuelle Verkehrsinformationen zu Staus, Baustellen usw. im Straßennetz dar.
3.2
Google Maps
Google bietet mit Google Maps ebenfalls einen webbasierten Kartendienst
an. Hauptfunktionen sind hier das Suchen von Orten, Branchen sowie Routenplanung zwischen zwei Orten. Standardmäßig berechnet Google Maps die
schnellste Verbindung zwischen zwei Orten. Eine explizite Option zur Berechnung einer kürzesten Route existiert hier nicht, einzig lässt sich über eine
21
KAPITEL 3. Übersicht existierender Routenplaner
Checkbox die Option “Autobahnen vermeiden” auswählen. Es besteht für den
Benutzer jedoch auch bei Google Maps keine Möglichkeit das Ergebnis des
Routings zu beeinflussen. Auch eine Funktion zur Suche von POIs entlang der
Route wie es Map24 bietet, besteht hier nicht.
Die verfügbaren Kartenlayer beinhalten das Straßennetz, Schienennetz, besiedelte Flächen, Waldgebiete und Gewässer, welche mit gut erkennbaren Farben
dargestellt werden. Eine Navigation im Kartenausschnitt erfolgt intuitiv durch
Hin- und Herbewegen mit der Maus, Zoomen ist mit dem Mausrad möglich.
Alternativ stehen auch entsprechende Schaltflächen zur Verfügung. Berechneten Routen kann durch Mausklick leicht ein Zwischenziel hinzugefügt werden,
welches sich dann frei auf eine beliebige andere Straße positionieren lässt, was
zu einer sofortigen Neuberechnung der Route führt.
Abbildung 3.2: Darstellung einer Route im Webinterface von maps.google.de
(Quelle: Google, maps.google.de)
Neben der Kartenansicht bietet Google Maps ebenfalls das Einblenden von Satellitenphotos an, über welche dann das Straßennetz projiziert wird. Eine weitere Funktion ist die Anzeige von GeoRSS-Feeds. Hierzu wird als Suchbegriff
einfach die URL des GeoRSS-Feeds angegeben, woraufhin die entsprechenden
Einträge mit ihrem Inhalt als Punkte in der Karte markiert werden. Weiterhin
sind für einige Regionen, derzeit lediglich in den USA, auch Verkehrsinformationen, sowie eine “Straßenansicht” verfügbar. Letztere besteht aus qualitativ
22
3.3. Mapquest / AOL Routenplaner
hochwertigen Fotos welche von einem durch die Straßen fahrenden Fahrzeug
aus aufgenommen wurden.
3.3
Mapquest / AOL Routenplaner
Mapquest, das im Jahr 2000 von AOL übernommen wurde, bietet seit 1996
Kartendienste im Internet an. Dem Benutzer stehen Funktionen wie die Berechnung einer schnellsten oder kürzesten Route zum Ziel zur Verfügung. Weiterhin können Autobahnen oder gebührenpflichtige Straßen, ähnlich wie bei
Map24, von der Berechnung ausgeschlossen werden.
Abbildung 3.3: Darstellung einer Route im Webinterface von Mapquest
(Quelle: MapQuest Inc., www.mapquest.com)
Das Kartenmaterial zeigt die Straßen- und Schienenverbindungen, sowie bebaute Flächen, Parks, Wälder und Gewässer. Die Navigation erfolgt fast vollständig über Schaltflächen, lediglich in die Karte hereinzoomen lässt sich auch
mit Mausklicks an die entsprechende Position innerhalb der Karte.
23
3.4
Yahoo Routenplaner
Der Yahoo Routenplaner bietet ein einfaches Interface zur Berechnung der
schnellsten Route zwischen zwei Orten. Optionen zum Individualisieren des
Routings fehlen komplett. In der Kartenanzeige bietet auch Yahoo sowohl die
Darstellung des reinen Kartenmaterials aus Straßen, Wäldern, Parks, bebauten
Flächen und Gewässern als auch eine Hybriddarstellung mit Satellitenphotos.
Die Farbgestaltung ist sehr übersichtlich und gut erkennbar.
Abbildung 3.4: Darstellung einer Route im Webinterface von Yahoo
(Quelle: Yahoo Deutschland GmbH, de.routenplaner.yahoo.com)
Die Navigation durch das Kartenmaterial erfolgt zum einen durch Verschieben
des Kartenausschnittes mit der Maus, sowie der Auswahl einer von mehreren
fest definierten Zoomstufen mittels entsprechender Schaltflächen. Eine besondere Funktion des Yahoo Routenplaners ist die Suche von bestimmten POIs im
gerade angezeigten Kartenausschnitt. Hier kann aus verschiedenen Kategorien
wie Restaurants, Kaufhäuser, Hotels etc. gewählt werden.
24
3.5. MSN Routenplaner
3.5
MSN Routenplaner
Auch der MSN Routenplaner von Microsoft bietet die üblichen Routingoptionen wie schnellste und kürzeste Route. Sonstige Funktionalität ist jedoch keine vorhanden. Die Kartenlayer beinhalten neben dem Straßen- und Schiennetz
noch Gewässer und einige wenige Parkanlagen. Wälder oder bebaute Flächen
werden nicht gesondert dargestellt. Die Navigation im Kartenausschnitt erfolgt
über Schaltflächen zum Zoomen und Verschieben, lediglich Hineinzoomen ist
durch Mausklicks möglich.
Abbildung 3.5: Darstellung einer Route im Webinterface von MSN
(Quelle: Microsoft Corporation, auto.de.msn.com/routenplaner)
25
3.6
Zusammenfassung
Alle betrachteten Routenplaner erfüllen die grundlegende Anforderung des
Auffindens einer schnellsten Verbindung zwischen zwei Orten. Allerdings ist
bereits die Berechnung von kürzesten Strecken nicht immer selbstverständlich.
Das Kartenmaterial wird bei allen in einer für den Anwendungszweck ausreichenden Form dargestellt, wobei sich hier Yahoo und Google Maps durch eine
gut erkennbare Farbwahl abheben. Hilfreiche Zusatzfunktionen wie das Auffinden von POIs an einem Ort können sowohl Yahoo als auch Map24 bieten.
Letzteres verfügt mit seiner interaktiven Kartendarstellung, welche zu den unter dem Mauszeiger befindlichen Elementen automatisch Zusatzinformationen
einblendet, über ein besonders informatives Benutzerinterface.
Jedoch fehlt allen vorgestellten Diensten die Möglichkeit, dass der Benutzer
das Routing durch die Auswahl individueller Parameter beeinflussen kann.
Aus diesem Grund wollen wir im folgenden Kapitel das verfügbare Kartenmaterial einer genaueren Betrachtung unterziehen und feststellen, welche Möglichkeiten es gibt, um einen Navigationsdienst für Motorradfahrer zu erstellen,
welcher neben der Berechnung von kürzesten und schnellsten Strecken auch
für Motorradfahrer interessante Strecken finden kann.
26
Kapitel 4
Softwareevaluation
Im Folgenden werden verschiedene Geodatenserver und die entsprechenden
Client-Programme beschrieben und daraufhin untersucht, ob sie für den Aufbau eines Web GIS als geeignet erscheinen.
4.1
Geodatenserver
Zentraler Bestandteil eines Web GIS ist eine Geodatenbank, welche die gesamten Informationen speichert. Hier bietet sich eine Vielzahl von möglichen
Datenbanken an, beispielsweise Oracle, MySQL oder PostgreSQL. Da wir
uns aus Kostengründen auf Opensource-Software beschränken wollen, fällt
Oracle aus der weiteren Betrachtung heraus. MySQL bietet seit Version 4.1
eine grundlegende Unterstützung von räumlichen Objekten gemäß der Spezifikation des OGC. Allerdings ist diese noch nicht vollständig ([13], [14]).
PostgreSQL mit der Erweiterung PostGIS bietet eine von der OGC als Standardkonform zertifizierte Implementation geospatialer Funktionen und wird
daher nicht nur von einer Vielzahl von Anwendungen unterstützt, sondern findet auch in kommerziellen Produkten Verwendung.
PostGIS ist eine OpenSource-Erweiterung für PostgreSQL und wird von der
kanadischen Firma Refractions Research [15] entwickelt. Mit PostGIS wird
PostgreSQL um Funktionen zur Bearbeitung und Speicherung von Geometriedaten erweitert. Die Datenbank ist somit zugleich Speicherort der geographischen Daten und Schnittstelle um Mittels SQL-Abfragen Berechnungen auf
den gespeicherten Daten durchführen zu können.
27
KAPITEL 4. Softwareevaluation
Damit die gespeicherte Geometrie effizient durchsucht werden kann, bedient
sich PostGIS eines R-Baum [16] basierten Index. Bei derart großen Datenmengen wie sie bei Straßennetzen auftreten können, ist es wichtig, dass effizient
auf die gewünschten Teile zugegriffen werden kann, ohne dabei die im Augenblick uninteressanten, da beispielsweise weiter weg liegenden, Teile ebenfalls
betrachten zu müssen. An dieser Stelle kommen R-Bäume zum Einsatz. Ein
R-Baum speichert die zu indizierenden Daten in seinen Blättern während die
Knoten Verweise in Form n-dimensionaler Rechtecke (Bounding Boxes) auf
die in diesem Rechteck enthaltenen Unter-Rechtecke dieses Teilbaumes beinhalten. Die Suche nach einem Element im R-Baum erfolgt rekursiv mittels ei-
1
2
3
a
b
c
6
7
8
4
5
b
6
a
1
8
7
3
c
2
4
5
Abbildung 4.1: Beispiel eines R-Baumes. Die Knoten a, b und c umfassen mit
einer Boundingbox die jeweiligen Daten der in ihnen gespeicherten Kinder.
nes Suchrechteckes, mit welchem ausgehend von der Wurzel des Baumes die
in den Knoten gespeicherten Rechtecke auf Überlappung mit dem Suchrechteck geprüft werden. Ebenso wird beim Einfügen eines Elementes ausgehend
von der Wurzel rekursiv die Geometrie jedes Knotens mit der Bounding-Box
des einzufügenden Elements verglichen. Hierbei wird der Knoten ausgewählt,
dessen Geometrie am wenigsten verändert werden muss, um das neue Element aufzunehmen. Sollte im Blatt kein Platz mehr vorhanden sein, um das
neue Element aufzunehmen, so muss ein Aufteilen (split) erfolgen. Um einen
R-Baum über die für die Benutzung notwendigen Operationen möglichst op-
28
4.1. Geodatenserver
timal zu halten, existieren verschiedene Variationen von R-Bäumen, darunter
R-Baum mit quadratischem Split [16], R-Baum mit linearem Split [16], R∗ Baum [17] und R+ -Baum [18], auf die jedoch hier nicht näher eingegangen
werden soll. Eine Untersuchung verschiedener Indexstrukturen für die Visualisierung sehr großer Graphen kann in [19] nachgelesen werden.
PostgreSQL
SQL-Funktionen
(PostgreSQL)
Tabellen
(Sachdaten)
Räumliche Funktionen
(PostGIS)
Tabellen
(Geometriedaten)
Routingfunktionen
(pgRouting)
Graph des
Straßennetzes
Abbildung 4.2: Schematische Darstellung der Komponenten des Geodatenservers
PostGIS verwendet jedoch nicht die native R-Baum-Unterstützung von PostgreSQL sondern verwendet die von PostgreSQL seit Version 8 unterstützten
GiST-Indizes [20], die als Basis für eine eigene R-Baum-Implementation dient.
GiST steht für “Generalized Search Tree” und wurde vom GiST Indexing
Project der Universität Berkeley entwickelt. GiST ist ein balancierter Suchbaum der als Template für eigene Ordnungsschemata dient. Auch hier werden
<Schlüssel, Wert>-Paare gespeichert, wobei der Schlüssel in diesem Fall ein
benutzerdefiniertes Objekt mit entsprechenden Zugriffsmethoden sein kann.
Der Grund für die Verwendung von GiST anstelle der bereits vorhandenen RBaum-Implementation liegt darin, dass auf R-Bäumen basierende Indizes in
PostgreSQL keine Elemente größer als 8K und keine Indizes auf leeren Geometrien (NULL) unterstützen.
Weiterhin stellt PostGIS Funktionen zum Import verschiedener GIS-Formate
wie beispielsweise von ESRI Shapefiles zur Verfügung, so dass sehr leicht
29
ein eigener Datenbestand aufgebaut werden kann. Erweitert man PostGIS nun
noch um das Modul pgRouting [21] so lassen sich leicht Graphtopologien erstellen, auf welchen eine Routenplanung durchgeführt werden kann. pgRouting ist Bestandteil der GPL-lizenzierten Datenbankerweiterung PostLBS, deren Ziel es ist zentrale Schnittstellen für Location Based Services zur Verfügung zu stellen. pgRouting wird vom japanischen GIS-Unternehmen Orkney
[22] entwickelt.
4.2
Client
Als Gegenstück zum Geodatenserver wird noch ein passender Client benötigt.
Zu seiner Aufgabe gehört die Kommunikation mit dem Benutzer, indem er
es ermöglicht Suchanfragen oder Anfragen zur Veränderung des Kartenausschnittes in entsprechende Anfragen an das GIS-System zu formulieren. Des
Weiteren muss er als WMS die resultierenden Ergebnisse der Anfrage wieder
als rasterisierte Karte dem Benutzer zur Verfügung stellen.
Es besteht die Möglichkeit diese einzelnen Komponenten zum Bereitstellen
eines Benutzerinterfaces, Verarbeitung der Anfragen und Aufruf eines WMS
zur Kartenerzeugung mit Hilfe verschiedener getrennter Programme durchzuführen. Es ist jedoch aus Gründen der Vereinfachung sinnvoller auf ein geeignetes bestehendes Framework zurückzugreifen, welches diese Komponenten
vereint.
Für den Rahmen dieser Arbeit bieten sich die Systeme Geoserver [23] mit
Openlayers [24] und UMN MapServer [25] mit CartoWeb [26] als Framework
an.
Das System Geoserver ist ein auf JAVA basierender, OGC-konformer Opensource Server und basiert auf dem Geotools-Toolkit, einem Open Source JAVA
GIS Toolkit [27]. Dabei kann Geoserver sowohl als WMS als auch als WFS
arbeiten und bietet mit der WFS-T Unterstützung auch einem Benutzer die
Möglichkeit Daten zu verändern. Weiterhin verfügt Geoserver über ein webbasiertes Benutzerinterface über das alle Einstellungen konfiguriert werden.
Openlayers würde hier sowohl als WMS für die Darstellung der Karte als auch
als Framework zur Benutzerinteraktion dienen. Allerdings war die Entwicklung von Openlayers zum Beginn der Arbeit noch in einem frühen Stadium.
Eine Alternative wäre der Einsatz des UMN Mapservers als WMS gewesen.
30
4.2. Client
Da dieser jedoch nicht auf Geoserver angewiesen ist, sondern auch direkt mit
der PostgreSQL-Datenbank kommunizieren kann, wurde beschlossen auf die
Verwendung von Geoserver zu verzichten. Statt dessen wird das CartowebFramework zusammen mit dem UMN Mapserver verwendet.
CartoWeb wird vom Schweizer Unternehmen Camptocamp SA [28] entwickelt und unter der GPL vertrieben. Basierend auf PHP5 bietet es ein modulares, objektorientiertes Framework mit dessen Hilfe sich leicht eigene Anwendungen umsetzen lassen. Zur Darstellung des Kartenmaterials bedient es
sich des UMN Mapservers als WMS unter Verwendung der PHP/MapscriptSchnittstelle des Mapservers. Als Geodatenserver wird PostgreSQL mit PostGIS unterstützt.
Cartoclient
cartoclient
core
MapRequest
kmlExport
csvExport
pdfExport
export
html Output
plugins
template
layers
location
images
SOAP
...
extendable
PDA Output
Cartoserver
ext. Data int.
services
MapResult
config mgmt
File Output
(pdf, kml, ...)
messaging
i18n
...
WMS server (WFS server)
external
Data
Abbildung 4.3: Architektur von CartoWeb, Clientseite.
Die Architektur von CartoWeb erlaubt es diesen auch als SOAP Web Service
einzusetzen, so dass zum einen das Frontend für den Benutzer sowie zum anderen die Datenverarbeitung und Kartenerstellung auf getrennten Servern be-
31
trieben werden. Des Weiteren ist CartoWeb modular aufgebaut, d.h. einzelne Funktionen sind in Form von Plugins gekapselt, welche leicht angepasst
werden können. Das Erzeugen und Anpassen der HTML-Ausgabe geschieht
mittels Templates, welche die Smarty template engine benutzen [29].
Smarty ist ein Template-Framework für PHP mit dessen Hilfe sich sehr leicht
Programmcode von Seiteninhalt und Design mittels Templates trennen lässt.
Durch Setzen entsprechender Smarty-Variablen in PHP werden diese dann im
zugehörigen Template mit dem jeweiligen Inhalt aufgelöst. Smarty bietet zudem weitere Funktionen und Plugins die das Erzeugen von HTML-Code vereinfachen und somit auch Quelltext und Templates übersichtlicher gestalten.
Cartoserver
cartoserver
core
MapRequest
geospatial
data
plugins
layers
mapfiles
location
images
SOAP
mapserver
mapscript
...
extendable
Cartoclient
geospatial
database
ext. Data int.
services
config mgmt
MapResult
messaging
highlighting
query
...
WMS/WFS
data sources
WMS server (WFS server)
external
Data
Abbildung 4.4: Architektur von CartoWeb, Serverseite.
Das CartoWeb-Framework ist des Weiteren in einen Client- und einen Serverteil gegliedert. Abbildung 4.3 zeigt den Aufbau des Cartoclient. Dieser stellt
alle Funktionen zur Kommunikation mit dem Benutzer zur Verfügung. Über
verschiedene Templates kann die Ausgabe auf das Endgerät des Benutzers an-
32
4.2. Client
gepasst werden, während Plugins das Einbinden unterschiedlichster Funktionen für den Benutzer ermöglichen. Mittels SOAP werden die Anfragen und
Antworten mit dem Cartoserver ausgetauscht.
Die per SOAP empfangenen Anfragen werden wie in Abbildung 4.4 gezeigt
von den jeweiligen Plugins im Cartoserver verarbeitet, wobei die zur Berechnung nötigen Daten aus unterschiedlichen Datenquellen stammen können. Das
Erzeugen des Kartenbildes für den Benutzer geschieht extern durch den UMN
Mapserver, welcher vom Cartoserver über die Mapscript-Schnittstelle angesprochen wird.
Darüberhinaus trennt CartoWeb die eigentliche Implementation eines Webservices vom restlichen Framework. Implementationen werden als Projekte in
einem getrennten Verzeichnis gespeichert, wodurch eine einzige CartoWebInstallation mehrere unterschiedliche Projekte mit unterschiedlichem Layout,
Kartenmaterial und Funktionalität beinhalten kann und ein Upgrade auf eine
neuere Version recht einfach vollzogen werden kann. Darüberhinaus verfügt
CartoWeb über eine sehr ausführliche Dokumentation sowohl für Benutzer,
als auch für Entwickler.
Zum Darstellen des Kartenmaterials greift CartoWeb auf den UMN Mapserver
zurück. MapServer wurde von der Universität Minnesota (UMN) in Kooperation mit der NASA und dem Minnesota Department of Natural Resources
entwickelt und gehört zu den am weitest verbreiteten freien Mapservern.
Anwendungsbeispiele finden sich beispielsweise unter folgenden Webseiten:
http://www.flaechennutzung.nrw.de/ und http://www.gefahrenatlas-mosel.de/.
Der UMN MapServer ist jedoch kein Server im eigentlichen Sinn und auch
keine vollständige GIS-Anwendung, sondern dient dazu geospatiale Daten in
eine für das Internet verwendbare Form aufzubereiten. Dabei kann MapServer seine Daten sowohl aus lokalen Dateien als auch von OGC-konformen
Geodatenservern in allen gängigen Formaten beziehen und daraus Karten in
verschiedenen Bildformaten generieren. Neben Programmierschnittstellen in
PHP, Python, Perl, Ruby, Java und C# bietet MapServer auch die Möglichkeit
als CGI-Anwendung über einen Webserver angesprochen zu werden. UMN
Mapserver implementiert ebenfalls die Web-Spezifikationen des OGC.
33
4.3
Desktopanwendungen
Um die in der Datenbank gespeicherten geographischen Daten auch unabhängig vom zu entwickelnden System betrachten und analysieren zu können, bietet sich die Verwendung einer desktopbasierten Anwendung an. Hier gibt es
eine große Auswahl an Software welche in der Lage ist auf die im PostgreSQLServer gespeicherten Daten zuzugreifen. Unter Linux bietet sich beispielsweise Quantum GIS [30] an. Eine weitere Alternative, welche sowohl für Windows, Linux als auch Mac OS zur Verfügung steht ist das JAVA-basierte uDig
(User-friendly Desktop Internet GIS) [31]. uDig wird ebenfalls von Refractions Research entwickelt.
4.4
Zusammenfassung
Von den zur Verfügung stehenden Geodatenservern hat sich PostgreSQL mit
der OGC-konformen Erweiterung postGIS und der Routingerweiterung pgRouting als sehr gut geeignet herausgestellt. Durch die guten Importfunktionen für Shapefiles ist es sehr leicht möglich einen Datenbestand aufzubauen
und durch die Unterstützung der von der OGC spezifizierten räumlichen Operationen auf diesen Daten Berechnungen durchzuführen.
CartoWeb bietet mit seinem modularen, leicht erweiterbaren Aufbau, der guten Dokumentation und der Integration von etablierten GIS-Anwendungen wie
UMN Mapserver und PostgreSQL mit postGIS eine gute Ausgangsbasis für
die Entwicklung eigener Webservices.
34
Kapitel 5
Konzeption des Webservices
Der entwickelte Webservice beschränkt sich auf das Straßennetz der Bundesländer Hessen, Rheinland-Pfalz und Saarland. Dies hat mehrere Gründe: zum
einen beträgt bereits die Datenmenge aller Informationen dieser Bundesländer
in der Datenbank 700MB. Zum anderen ist mir das Straßennetz in Teilen bekannt und es bestand somit die Möglichkeit gefundene Routen auf ihre Tauglichkeit zu überprüfen.
Dieser Datensatz liegt ursprünglich im ESRI-Shapefileformat vor. Um diesen
nun für einen Webservice nutzen zu können, muss dieser zunächst in die Datenbank eingelesen werden. Bevor dies jedoch geschehen kann, muss die Datenbank erst einmal installiert und konfiguriert werden. Details hierzu können
in Anhang A nachgelesen werden.
5.1
Analyse des Kartenmaterials
Um eine automatische Auswahl an interessanten Strecken treffen zu können,
ist es notwendig geeignete Indikatoren für eine solche Strecke zu bestimmen.
Wie in Kapitel 1 erwähnt ist das Vorhandensein von Kurven ein solcher Indikator für eine interessante Strecke. Es stellt sich nun die Frage, ab wann
eine Strecke als kurvenreich zu betrachten ist. Betrachtet man eine Visualisierung des Kartenmaterials, so ist dies für das menschliche Auge relativ leicht zu
entscheiden. Will man jedoch mittels automatisierter Abfragen aus dem Kartenmaterial geeignete Strecken herausfinden, so ist eine eingehendere Analyse
des vorhandenen Materials unabdingbar. Zu den in der Datenbank verfügbaren
35
KAPITEL 5. Konzeption des Webservices
Informationen zum Straßennetz gehören
• Eindeutige ID des Segmentes
• Straßenname
• ID des vorherigen Segmentes
• ID des nachfolgenden Segmentes
• Anzahl der Punkte die diese Geometrie aufspannt, also die Kurven des
Segmentes
• Zusatzinformationen zum Segment, z.B. Privatstraße, gebührenpflichtige Straße
• Straßenkategorie
• Geometrie des Straßensegmentes
Die hier aufgeführten Informationen sind nur der für diese Arbeit relevante
Teil. Tatsächlich befinden sich in der Tabelle für das Straßennetz insgesamt
57 mögliche Informationen. Das Straßennetz ist dabei in einzelne Segmente
unterteilt, wobei ein Segment jeweils von Einmündung zu Einmündung reicht.
Der benutzte Datensatz enthielt in der Strassentabelle über 870.000 Segmente.
Ein weiterer Gesichtspunkt stellt die zu betrachtende Straßenhierarchie dar,
dies bedeutet, welche Klassen von Straßen sollen überhaupt vom Algorithmus
später betrachtet werden. In der Bundesrepublik Deutschland gibt es derzeit
die folgenden Hierarchien von Straßen
1. Bundesautobahnen
2. Bundesstraßen
3. Landesstraßen/Staatsstraßen
4. Kreisstraßen
5. Gemeindestraßen/Ortsstraßen
6. Feld- und Forstwege
36
5.1. Analyse des Kartenmaterials
Im Kartenmaterial abgebildet, d.h. anhand von entsprechenden Kennziffern
unterscheidbar, sind die ersten fünf Typen. Dies bedeutet, dass leider Feld- und
Forstwege im Kartenmaterial nicht von innerörtlichen Straßen unterschieden
werden können. Dies kann insbesondere bei der Berechnung von kürzesten
Wegen zu in der Praxis nicht befahrbaren Routen führen. Dies ließe sich jedoch
ohne Probleme mit geeigneterem Kartenmaterial beheben.
Als nächstes gilt es eine Klassifizierung, d.h. Gewichtung, für diese Straßen
zu bestimmen. Um nicht erreichbare Knoten im Straßengraph zu vermeiden
werden die Straßen welche vom Routingalgorithmus nicht primär betrachtet
werden sollen lediglich mit einem hohen Gewicht versehen. Für alle übrigen erwünschten Straßen sind entsprechend geringere Gewichte zu ermitteln.
Da kurvenreiche Strecken ein wesentliches Merkmal für die zu berechnenden
Routen darstellen, wollen wir mit der Berechnung dieser Gewichte beginnen.
Privatwege oder sonstige für den öffentlichen Verkehr nicht freigegebene Straßen fallen von Vorneherein aus der Betrachtung heraus. Innerörtliche Straßen,
d.h. alle Straßen die sich innerhalb von bebautem Gebiet befinden, wurden auf
Grund der dort üblicherweise vorherrschenden Verkehrsdichte ebenfalls von
der Betrachtung ausgenommen. Autobahnauffahrten sind zwar in der Regel
relativ kurvig aber an sich wenig reizvoll. Sie wurden daher ebenfalls nicht
betrachtet.
Autobahnen selbst werden von einigen wenigen Motorradfahrern bevorzugt,
da diese jedoch üblicherweise relativ kurvenarm sind wurden sie im Vergleich
zur den folgenden Straßengattungen etwas schlechter bewertet, um den Anteil
der Autobahnen an der Gesamtstrecke relativ niedrig zu halten.
Bundes- Land- und Kreisstrassen hingegen stellen das eigentliche Revier der
überwiegenden Mehrheit der Motorradfahrer dar. Dies liegt darin, dass sich
diese Straßen oftmals sehr kurvenreich durch die Landschaft schlängeln, meist
eine schöne Aussicht bieten und zudem ein zügiges Vorankommen ermöglichen.
Auf diese Weise entsteht nun eine erste Klassifizierung des Straßennetzes welche als Ausgangspunkt für weitere Betrachtungen dient und daher in einer eigenen Tabelle gespeichert wird.
Um nun die bereits angesprochene Gewichtung von kurvenreichen Strecken zu
erhalten, wurden zwei verschiedene Ansätze entwickelt. Die erste Möglichkeit
37
um zu einer Aussage über die Kurvenzahl eines Segmentes zu kommen, falls
keine explizite Information über die Kurvenzahl gegeben ist, bestehet darin
das Verhältnis aus der Gesamtlänge des Segmentes und der Luftlinie zwischen
Start- und Endpunkt des Segmentes zu berechnen. Hier muss dann allerdings
ein anderer Maßstab zur Gewichtung angelegt werden, da beispielsweise Segmente die einem mäandrierenden Flusslauf folgen möglicherweise eine sehr
kurze Distanz zwischen Start- und Endpunkt des Segments und eine große
Segmentlänge haben, vom Kurvenverlauf her allerdings lediglich aus einer
einzigen sehr weit gestreckten Kurve bestehen. Aufgrund dieser nur schwer
auszuschliessenden Fehlerquellen und der Tatsache, dass die weitaus genaueren Informationen zur Kurvenanzahl im Kartenmaterial vorhanden ist wurde
darauf verzichtet, dies als Maß zur Gewichtung zu verwenden.
Die im Kartenmaterial vorhandenen Straßensegmente verfügen über ein Feld,
welches die Anzahl der Kurvenpunkte enthält. Somit können nun sehr einfach interessante Teilsegmente betrachtet werden, insbesondere interessieren
hier die Segmente die viele Kurven beinhalten. Eine Analyse des vorliegenden Kartenmaterials hat gezeigt, dass für das soeben erstellte Straßennetz ein
Faktor von mehr als 10 Shapepoints pro Segment ein kurviges und für den
Motorradfahrer potentiell interessantes Segment markiert. Betrachtet man alle
vorhandenen Straßensegmente und deren Kurvenanzahl, so besitzen 95% der
Segmente weniger als 10 Kurvenpunkten. Die restlichen 5% verteilen sich auf
die kurvenreichen Segmente mit mehr als 10 Kurvenpunkte. Berechnet man
weiterhin die durchschnittliche Länge der Segmente, so kann festgestellt werden, dass Segmente mit wenigen Kurven auch relativ kurz sind und von daher
recht wenig zu einer attraktiven Route beitragen.
Kurvenpunkte
0 - 10
11- 100
> 100
Segmente
832504
38123
79
Durchschnittliche Länge
0.32km
2.08km
4.55km
Tabelle 5.1: Analyse der Kurvenpunkte
Abbildungen 5.1 und 5.2 zeigen eine grafische Repräsentation des verwendeten Straßennetzes in Bezug auf die verschiedenen Klassifizierungen.
Mittels dieser Informationen kann nun eine Gewichtung des Straßennetzes durchgeführt werden. Zunächst werden alle interessanten Straßen, d.h.
Segmente die mehr als 10 Kurvenpunkte besitzen, mit einem Gewicht von
38
(a) Gesamtes Straßennetz
(b) Beschränkung des Straßennetzes auf Segmente mit mindestens 11 Kurvenpunkten
Abbildung 5.1: Grafische Darstellung des verwendeten Straßennetzes (1)
39
1/<Anzahl der Kurvenpunkte> versehen. Somit werden Segmente mit sehr vielen Kurven entsprechend günstig bewertet und bevorzugt. Alle übrigen interessanten Landstraßen, welche diese kurvenreiche Teilstücke verbinden werden
mit einem Gewicht von 1 bewertet. Dies führt nun dazu, dass bei der Berechnung einer Route ausschließlich die Kurvenzahl für die Streckenwahl entscheidend ist und alle anderen Segmente unabhängig von ihrer Länge zum Verbinden dieser Kurvenpassagen genutzt werden. Somit wird der Benutzer von einer
kurvenreichen Teilstrecke zur nächsten geleitet. Zuletzt müssen noch alle übrigen Straßen mit einem Gewicht versehen werden, damit der Straßengraph
vollständig ist. Da die verbleibenden Straßen lediglich dazu dienen sollen, eine Route zu den interessanten Straßen zu finden und ansonsten nicht in die
Berechnung einfließen sollen, wird diesen Straßen ein noch höheres Gewicht
als den interessanten Landstraßen zugeteilt. Hier bieten sich nun Gewichte an,
welche größer als 1 sind. Versuche mit verschiedenen Gewichtungen haben gezeigt, dass erst ab einem Wert von 4 auch bei längeren Strecken von mehreren
hundert Kilometern keine unerwünschte Straßen hinzugenommen werden. Ansonsten tritt beispielsweise auch in innerörtlichen Gebieten der Fall ein, dass
der Algorithmus störende “Abkürzungen” beispielsweise durch Wohngebiete
oder sonstige Seitenstraßen wählt und nicht auf der durch den Ort führenden
interessanten Landstraße bleibt. Dies kann mit einem entsprechend gewählten
Gewicht vermieden werden, sodass dies auch die spätere Navigation erleichtert, da unnötige Abbiegemanöver vermieden werden.
Ein weiteres Klassifikationsmerkmal für eine interessante Strecke kann die Nähe eines Straßensegmentes zu bestimmten POIs darstellen. Umsr diese Information in die Routenberechnung einfließen zu lassen, muss auch in diesem Fall
für das Straßennetz eine geeignete Gewichtung erstellt werden. Hierzu wird
für jede Gruppe von POIs ein Voronoi-Diagramm berechnet, mit dessen Hilfe
eine Verschneidung mit dem Straßennetz durchgeführt werden kann. Mittels
einer Nearest-Neighbour-Suche lässt sich so eine entfernungsabhängige Gewichtung eines Straßensegmentes zum jeweiligen nächsten POI der betreffenden Gruppe berechnen. Diese zusätzlichen Gewichte können dann nach Bedarf
auf Wunsch des Benutzers zur Berechnung der Route hinzugefügt werden.
Um die Straßeninformationen in einem Routingalgorithmus verwenden zu
können, müssen entsprechende Tabellen mit den Graphinformationen über die
Knoten und Kanten, sowie deren Gewichtung erzeugt werden. Hierzu gibt es
nach der Installation von PostGIS bereits Funktionen die das Anlegen der Tabellen übernehmen:
40
(a) Alle als für Motorradfahrer interessant klassifizierten Landstraßen
(b) Segmente des als für Motorradfahrer interessant klassifizierten Straßennetzes mit mindestens 11 Kurvenpunkten
Abbildung 5.2: Grafische Darstellung des Straßennetzes (2)
41
SELECT create_graph_tables(’streets’, ’int4’);
Dies generiert die Tabellen streets_edges und streets_vertices, welche die Kanten und die Knoten des Straßengraphen enthalten. Im nächsten Schritt können
dann den einzelnen Kanten ihre jeweiligen Gewichte für die einzelnen Modi
des Routenplaners zugewiesen werden. Hierzu wird eine modifizierte Version
der Funktion update_cost_from_distance verwendet. Für das Routing werden
verschiedene Gewichtungen benötigt:
cost0 Kosten abhängig von der Länge des Segmentes um die kürzesten Wege
berechnen zu können.
cost1 Kosten eines Segmentes in Bezug der Fahrtzeit, um die schnellste Route
finden zu können.
cost2 Kosten in Abhängigkeit der Kurvenanzahl und der Interessantheit des
Straßentypes für das Auffinden interessanter Motorradstrecken.
cost3 und weitere Kosten in Abhängigkeit der Entfernung eines Straßensegments zu einem bestimmten POI, beispielsweise Sehenswürdigkeiten,
Parkanlagen, Museen, ...
SELECT update_cost_from_distance(’streets’);
DECLARE
BEGIN
BEGIN
EXECUTE ’CREATE INDEX ’ || quote_ident(geom_table) ||
’_edge_id_idx ON ’ || quote_ident(geom_table) ||
’ (edge_id)’;
EXCEPTION
WHEN DUPLICATE_TABLE THEN
RAISE NOTICE ’Not creating index, already there’;
END;
EXECUTE ’UPDATE ’ || quote_ident(geom_table) ||
’_edges SET cost0 = (SELECT sum( length( g.the_geom ) ) FROM ’
|| quote_ident(geom_table) ||
’ g WHERE g.edge_id = id GROUP BY id)’;
EXECUTE ’UPDATE ’ || quote_ident(geom_table)
|| ’_edges SET cost1=cost0*60/50’;
|| ’_edges SET cost1=cost0*60/130 FROM ’
|| quote_ident(geom_table) ||
’ g WHERE g.edge_id=id AND (g.route_type =1 OR g.route_type = 2)’;
EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_edges SET cost1=cost0*60/80 FROM ’
|| quote_ident(geom_table) || ’ g, sechwys
WHERE g.edge_id=id AND (g.the_geom ~= sechwys.the_geom)’;
EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_edges SET cost2=4’;
EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_edges set cost2=1 FROM ’
42
5.2. Vorüberlegungen zur Routenplanung
|| quote_ident(geom_table)
|| ’ g, interessante_strassen h WHERE (g.edge_id=id)
AND g.the_geom && h.the_geom AND equals(g.the_geom,h.the_geom)’;
|| ’_edges SET cost2=(1::real/(SELECT g.n_shapepnt FROM ’
|| quote_ident(geom_table) || ’ g WHERE (g.edge_id=id) )::real)::real FROM ’
|| quote_ident(geom_table)
|| ’ g, interessante_strassen h WHERE (g.edge_id = id)
AND (g.the_geom && h.the_geom)
AND equals(g.the_geom, h.the_geom)
AND (g.n_shapepnt > 10)’;
|| ’_edges SET cost8 = (SELECT distance(s.the_geom, t.the_geom) FROM ’
|| quote_ident(geom_table) ’ s, poi_type r, travdest t WHERE
s.the_geom && r.the_geom AND t.the_geom && r.the_geom AND
id = s.edge_id AND t.fac_type = 7999 LIMIT 1 ) FROM strassen s
WHERE id = s.edge_id’;
RETURN;
END;
5.2
Vorüberlegungen zur Routenplanung
Für den klassischen Fall von kürzester bzw. schnellster Strecke von A nach B
werden einfach die Kosten in Abhänigkeit der Segmentlänge bzw. in Abhängigkeit der Fahrzeit für das jeweilige Segment berechnet.
Wie bereits erwähnt gibt es für die Berechnung von Motorradrouten zwei verschiedene Betriebsmodi. Der einfachste Fall stellt das Routing von A nach B
dar, in welchem der Benutzer eine anhand der für Motorradfahrer interessanten
Kriterien gewichtete Route zwischen diesen beiden Punkten erhalten möchte.
Dies kann relativ einfach unter Verwendung der im vorherigen Abschnitt erzeugten Gewichte geschehen.
Der zweite besondere Fall des Motorradroutings besteht im Erzeugen von
Rundtouren, d.h. Start und Ziel sind identisch. Es gibt zwei Ansätze diesem
Problem zu begegnen: entweder bestimmt der Benutzer explizit Via-Punkte,
d.h. Zwischenziele die der Algorithmus verwendet. Alternativ kann der Algorithmus selbst ein Zwischenziel suchen lassen. Ein solcher Punkt ist zwingend
notwendig, da kein Routingalgorithmus mit gleichem Start und Ziel arbeiten
kann. Allerdings ist auch für das automatische Auswählen eines solchen Hilfszieles eine Information des Benutzers notwendig, nämlich eine Angabe zur
ungefähren maximalen Länge der Tour. Diese Information ist auch aus Sicht
des Benutzers sinnvoll, denn somit hat dieser eine Möglichkeit die Tourlänge
seinen individuellen Wünschen anzupassen. Da das Festlegen von Via-Punkten
durch den Benutzer keine besonderen Fähigkeiten des Routenplaners erfordert,
43
wurde beschlossen eine Lösung für das automatisierte Bestimmen von Hilfszielen zu erarbeiten.
t'
(d/2) * 0.6
S
Abbildung 5.3: Schema der Umkreisberechnung. Der Suchraum für das Zwischenziel ist orange hervorgehoben.
Diese Auswahl des Zwischenzieles erfolgt wie folgt: Mittels des Startpunktes
und der gewünschten maximalen Entfernung d werden ein äußerer Umkreis
mit Radius (d/2) · 0.6 und ein innerer Umkreis, dessen Radius einen Kilometer kleiner als der äußere ist um den Startpunkt gezogen. Die Differenz dieser
beiden Kreise definiert einen Ring von einem Kilometer Breite, der als Suchraum für ein zufällig zu wählendes Zwischenziel dient (siehe Abbildung 5.3).
Die Größe des zu wählenden Radius hängt hierbei von der Beschaffenheit des
zu Grunde liegenden Straßengraphen und der Größe der Voronoizellen ab. Je
dichter das Straßennetz ist, desto näher liegt die tatsächliche Länge der berechneten Route an dem vom Benutzer gewählten Soll-Wert. Eine Analyse des
vorliegenden Kartenmaterials haben einen Wert des 0.6fachen des Radius als
geeignetes Maß ergeben (siehe Abbildungen 5.4 und 5.5). In diesem Fall liegt
die mittlere prozentuale Abweichung von der gewünschten Routenlänge bei
2%, während Faktoren von 0.5, 0.7 oder 0.8 zu Abweichungen von 17 - 28 %
des Soll-Werts führen. Untersucht wurden jeweils 40 verschiedene Routen mit
Längen zwischen 80 und 200km.
Bei der Berechnung dieser Umkreise ist des Weiteren zu beachten, dass die gesamten hierfür notwendigen geometrischen Berechnungen möglichst effizient
durchgeführt werden können. Ebenso muss dafür gesorgt sein, dass in grenznahen Regionen kein Ort gewählt werden kann, der ausserhalb des verfügbaren
Kartenmaterials liegt. Als Lösung für diese Probleme wurde der folgende An-
44
(a) Faktor 0.5, 17% Abweichung
(b) Faktor 0.6, 2% Abweichung
Abbildung 5.4: Verschiedene Radien für die Umkreisberechnung und deren
mittlere Abweichung. Grün die Soll-Werte, rot die tatsächliche Länge der automatisch generierten Rundtouren.
satz verwendet: In der Datenbank sind alle Ortsnamen in einer separaten Tabelle mit der jeweiligen geographischen Position des Ortskerns gespeichert. Mittels dieser Punkte wurde nun ein Voronoi-Diagramm berechnet, dessen Zellen
das gesamte Kartengebiet überdecken. Details zur Berechnung des VoronoiDiagrammes finden sich in Anhang C.
Die Geometrie des Voronoi-Diagrammes ist in einer eigenen Tabelle gespeichert, so dass es nun möglich ist, diese effizient mit dem Straßenlayer zu verschneiden, wodurch nur Straßen gefunden werden, die in einer bestimmten
Voronoizelle liegen. Will man nun einen zufälligen Ort als Zwischenziel auswählen, wird wie folgt vorgegangen: Mit den oben berechneten Radien wählt
man die Voronoizellen aus, welche sich zwischen dem inneren und dem äuße-
45
(a) Faktor 0.7, 23% Abweichung
(b) Faktor 0.8, 28% Abweichung
Abbildung 5.5: Verschiedene Radien für die Umkreisberechnung und deren
mittlere Abweichung. Grün die Soll-Werte, rot die tatsächliche Länge der automatisch generierten Rundtouren.
ren Kreis um den Startpunkt herum befinden. Von dem Ergebnis dieser SQLAbfrage liefert die Datenbank nun zufällig ein Ergebnis zurück und man erhält
eine Voronoizelle mit dem entsprechenden Ortsnamen (siehe Abbildung 5.7).
Dieser lässt sich nun für den Routingalgorithmus als Zwischenziel verwenden.
Da das Voronoidiagramm auch über Ländergrenzen herausragt kann auch bei
grenznahen Orten oder durch den Benutzer zu groß gewählten Radien sichergestellt werden, dass immer ein Ort als Zwischenziel gefunden werden kann.
Sollte dieser zufällig gewählte Ort nun im Falle eines grenznahen Startpunktes
deutlich zu nahe an diesem liegen, was sich mit einer einfachen Distanzberechnung schnell feststellen lässt, so kann das Verfahren einfach erneut durchgeführt werden. Mit relativ hoher Wahrscheinlichkeit findet sich im nächsten
46
Radius (d/2) * 0.6
Startpunkt
Tabelle der
Ortsnamen
Berechnung des
äußeren und inneren
Umkreises,
Bilden der Differenz
Verschneiden der
Geometrien
Abfrage der
Geokoordinaten des
Startpunktes (x,y)
Tabelle des
VoronoiDiagramms
Auswahl eines
Ortes
Zwischenziel
Abbildung 5.6: Funktionsweise der Bestimmung von Zwischenzielen
Durchlauf ein geeigneterer Ort als Zwischenziel.
Um eine Rundtour zu berechnen, muss allerdings noch mehr beachtet werden.
So lässt sich zwar mittels des Zwischenzieles wie im einfachen Routing von
A nach B eine interessante Route berechnen, allerdings soll für den Rückweg
eine andere Route zwischen diesen Punkten gewählt werden. Daher wird die
bereits berechnete Route mit erhöhten Kantengewichten in einer eigenen Tabelle temporär zwischengespeichert. Der Faktor mit dem die Kantengewichte
zu erhöhen sind, muss dabei höher als der vorher gesetzte Wert für die teuersten Straßen sein. Eine Erhöhung um den Faktor 10 hat sich hier als geeignet
herausgestellt. Bei der Berechnung des Rückweges wird nun die Tabelle mit
den normalerweise benutzten Kantengewichten mit den erhöhten Gewichten
der vorangegangenen Routenberechnung vereint. Somit wird die bereits gewählte Route zwischen Start und Zwischenziel vermieden (siehe Abbildung
5.8). Ausnahmen bilden natürlich Orte in deren Umgebung das Straßennetz so
dünn ist, dass es für Teilstrecken keine andere Möglichkeit gibt.
Das Ausschließen bereits berechneter Routen von einer weiteren Suchanfra-
47
Abbildung 5.7: Voronoidiagramm aller Ortsnamen, sowie die durch einen Umkreis um einen Startpunkt ausgewählten Voronoizellen (blau)
Abbildung 5.8: Eine anhand eines zufällig gewählten Zwischenziels generierte
Rundtour
ge lässt sich selbstverständlich auch für das normale Routing von A nach B
verwenden. Somit hat der Benutzer die Möglichkeit auf Wunsch auch alternative Routen zwischen diesen Orten finden zu können. Um dem Benutzer die
Möglichkeit zu geben, die gefundenen Routen sowohl speichern, als auch einer
genaueren Betrachtung unterziehen zu können, lässt sich jede Route im KMLFormat exportieren. Dadurch lässt sich das Ergebnis beispielsweise in Google
Earth betrachten. Die so gefundenen und exportierten Routen lassen sich auch
in andere Anwendungen einbinden oder in ein Navigationsgerät laden.
48
(a) Kürzeste Route
(b) Schnellste Route
Abbildung 5.9: Berechnung einer Route zwischen Illingen/Saar und Koblenz.
Dargestellt ist das Ergebnis (blau), das Straßennetz der interessanten Landstraßen (gelb), kurvige Teilstrecken (rot), sowie POIs (gelbe quadrate) und deren
Voronoizellen (violette Linien).
49
(a) Route mit vielen Kurven
(b) Route mit vielen Kurven entlang verschiedener POIs
Abbildung 5.10: Berechnung einer Route für Motorradfahrer zwischen Illingen/Saar und Koblenz. Dargestellt ist das Ergebnis (blau), das Straßennetz der
interessanten Landstraßen (gelb), kurvige Teilstrecken (rot), sowie POIs (gelbe
quadrate) und deren Voronoizellen (violette Linien).
50
Kapitel 6
Erstellen des Webservices
Nachdem im vorherigen Kapitel die Konzepte der Routenplanung für Motorradfahrer vorgestellt wurden, sollen diese Ergebnisse nun in Form eines
Webservices umgesetzt werden. Hierzu wird wie in Kapitel 4.2 beschrieben
das CartoWeb-Frameworks in Verbindung mit dem UMN Mapserver verwendet. Die Installation und Konfiguration von UMN Mapserver und CartoWeb
ist in Anhang B beschrieben. Bevor wir mit dem Erstellen des Webservices
beginnen, soll zunächst der Aufbau von CartoWeb erläutert werden.
6.1
Überblick über das CartoWeb-Framework
CartoWeb teilt den Webservice in Client- und Serverseite auf. Aufgabe des
Clients ist die Interaktion mit dem Benutzer und die Darstellung der Inhalte. Serverseitige Skripte stellen die Verbindung mit den Datenquellen her und
beantworten die Anfragen des Clients. Die einzelnen Funktionen sind dabei
modular in Plugins gekapselt, welche ihrerseits wiederum Client- und Serverspezifische Skripte beinhalten können. Darüber hinaus existieren zwei Arten
von Plugins, sogenannte Coreplugins welche obligatorische Funktionen beinhalten sowie optionale Plugins die bei Bedarf geladen werden können. Auf der
Clientseite erfolgt das Erzeugen der Ausgabe mit Hilfe von Templates, wodurch sich zum einen Quellcode und Design trennen lassen und zum anderen
eine endgerätespezifische Ausgabe ermöglicht wird. Als Programmiersprache
des Frameworks wird PHP in Verbindung mit der Smarty Template Engine
verwendet.
51
KAPITEL 6. Erstellen des Webservices
Zunächst soll die allgemeine Arbeitsweise und Verzeichnisstruktur von CartoWeb betrachtet werden. Im Installationsverzeichnis existieren alle mitgelieferten Plugins und Templates wie in der unten aufgeführten Verzeichnisstruktur
mit ihren entsprechenden Voreinstellungen. Alle im projects-Verzeichnis existierenden Projekte bedienen sich der gleichen Verzeichnisstruktur und erben
alle Dateien und Voreinstellungen, können jedoch auch diese Voreinstellungen durch Anlegen gleichnamiger Dateien überschreiben oder durch Anlegen
neuer Dateien erweitern. Auf der obersten Ebene existieren
client Clientspezifische Programmdateien
client_conf Dies sind alle Konfigurationsdateien, die das Verhalten des Benutzerinterfaces betreffen.
common Programmdateien für Server und Client
coreplugins Grundlegende, für den Betrieb notwendige Plugins
htdocs Hier liegen Stylesheets, JavaScript-Dateien und Grafiken
include Von CartoWeb verwendete Libraries
locale Dateien zur Internationalisierung
log Speicherort für Logfiles
plugins Hier befinden sich alle zusätzlichen Plugins
po Dateien zur Internationalisierung im gettext-Format
projects Enthält die Projekte
scripts Skripte zur Wartung
server Serverspezifische Programmdateien
server_conf Dieses Verzeichnis enthält alle Konfigurationsdateien für die serverseitigen Skripte sowie für den WMS
templates Enthält die Smarty-Templates für das Benutzerinterface
templates_c Cache-Verzeichnis für die Smarty-Templates
www-data Für den Webserver schreibbares Verzeichnis für dynamisch generierte Inhalte
52
6.1. Überblick über das CartoWeb-Framework
Um nun einen eigenen Webservice zu erstellen, wird im projectsVerzeichnis eine Kopie des demoCW3-Projektes erzeugt. Enthalten ist wieder
ein Teil der oben aufgeführten Verzeichnisse, welche nun die projektspezifischen Anpassungen beinhalten. Dies sind die Verzeichnisse client_conf,
coreplugins, plugins, server_conf und templates.
Um nun die Kartendarstellung einzurichten, müssen die entsprechenden Dateien im Verzeichnis server_conf angepasst werden, welche sich dort im Unterverzeichnis <mapId>, also beispielsweise demoCW3, befinden. Die zentrale Datei stellt hier <mapID>.map dar, welche die Mapscript-Konfiguration des
UMN Mapservers beinhaltet. Hier werden das Ausgabeformat der Karte sowie
die einzelnen Layer mit den darzustellenden Features definiert. Die Hierarchie
dieser Layer sowie die Bezeichnungen für die Legende in der Kartenanzeige
werden in der Datei layers.ini definiert. CartoWeb unterstützt hierbei auch die
Gruppierung einzelner Layer und bietet dem Benutzer die Möglichkeit, einzelne Layer individuell an- und abzuwählen. In der Konfigurationsdatei <mapID>.ini werden zuletzt alle benötigten Plugins sowie das initiale Layout der
Karte definiert.
Abbildung 6.1: Die aus der layers.ini resultierende Legende. Die zur besseren
Übersichtlichkeit in der aktuellen Zoomstufe nicht verfügbaren Optionen sind
hellgrau dargestellt.
Sind diese Schritte durchgeführt, so kann das Kartenmaterial im Webbrowser
53
angezeigt werden. Dem Benutzer werden durch das Framework auch direkt
die üblichen Manipulationswerkzeuge zum Vergrößern bzw. Verkleinern oder
Verschieben des Kartenausschnittes zur Verfügung gestellt.
Abbildung 6.2: Darstellung des Kartenmaterials im fertigen Webinterface.
6.2
Implementation in CartoWeb
Aufbauend auf dieser Basisinstallation wird CartoWeb um die benötigte Funktionalität erweitert. Zunächst werden die einfachen Fälle des Berechnens kürzester bzw. schnellster Wege implementiert. Hierzu müssen in der Datei <mapID>.ini das Routing-Plugin geladen und in der Datei routing.ini die Parameter für die Datenbankanbindung gesetzt werden.
Im nächsten Schritt muss das Eingabeformular des Routing-Templates um die
benötigten Parameter von Start, Ziel, Routingmodus (schnellste Route, kürzeste Route, Motorradroute), ungefähre Distanz einer Rundtour, einer Option um alternative Routen zu berechnen, Berücksichtigung von POIs, sowie
der Möglichkeit die berechnete Route im KML-Format zu exportieren angepasst werden. Die benötigte Template-Datei befindet sich dem CartoWebVerzeichnisschema folgend in routing\plugins\templates. Nachfolgend sind der Inhalt des Templates sowie in Abbildung 6.3 die daraus resultierende Ansicht im Webinterface dargestellt.
54
6.2. Implementation in CartoWeb
<table border="0">
<tr>
<td>{t}Von{/t}</td>
<td><input type="text" id="routing_from" name="routing_from"
value="{$routing_from}" size="12" maxlength="20" /></td>
</tr>
<tr>
<td>{t}Nach{/t}</td>
<td><input type="text" id="routing_to" name="routing_to"
value="{$routing_to}" size="12" maxlength="20" /></td>
</tr>
<tr>
<td>{t}Tourlänge in km (ca.){/t}</td>
<td><input type="text" id="tourlength" name="tourlength"
value="{$tourlength}" size="8" maxlength="10" /></td>
</tr>
<tr>
<td>{t}Modus{/t}</td>
<td>
<select name="routing_options" id="routing_options">
{html_options values=$routing_options_values output=$routing_options_labels selected=$routing_options}
</select>
</td>
</tr>
{if $exportKml != ’’}
<tr>
<td><input type="checkbox" name="alternative" value="1"></td>
<td>Alternative Route berechnen</td>
</tr>
{/if}
<tr><td colspan="2">Routing mit POIs:</td></tr>
<tr>
<td align="right">
<font color="#00cf31" size="4pt">•</font>
<input type="checkbox" name="pois[]" value="cost7"
</td>
<td>Parks</td>
</tr>
<tr>
<td align="right">
<font color="#0f00d0" size="4pt">•</font>
</td>
<td>Museum</td>
</tr>
<tr>
<td align="right">
<font color="#ff6e0d" size="4pt">•</font>
</td>
<td>Attraktion</td>
</tr>
<tr>
<td align="right">
<font color="#000000" size="4pt">•</font>
</td>
<td>Monumente</td>
</tr>
</table>
{if $cost7} checked="checked"{/if}>
<p>
<input type="submit" name="routing_submit" value="Route berechnen" class="form_button"/>
<input type="submit" name="routing_reset" value="Reset" class="form_button"/>
</p>
{if $exportKml != ’’}
<br />
Länge der Route: {$length}km.
<br />
<a href="{$exportKml}">In Google Earth betrachten</a>
{/if}
55
Abbildung 6.3: Aus dem Template resultierende Benutzerschnittstelle für die
Routingparameter
Die hier gesetzten Parameter müssen als nächstes vom Client ausgewertet und in einer Routinganfrage an den Server versandt werden. Dies geschieht in der Datei ClientRouting.php, welche sich im Verzeichnis
plugins\routing\client befindet. Die erforderlichen Modifikationen
in ClientRouting.php bestehen hierbei im Wesentlichen aus dem Einführen neuer Variablen und Datenstrukturen welche die Ein- und Ausgabe von
Werten im Benutzerinterface steuern und die KML-Datei mit den Routingergebnissen erzeugen. Die hier erzeugte Anfrage wird anschließend serverseitig
von der Datei ServerRouting.php verarbeitet, in der die im Folgenden
aufgeführten Veränderungen notwendig sind.
Veränderungen der Datei ServerRouting.php sind nur für den Fall relevant, wenn vom Benutzer als Routingoption “Motorrad” ausgewählt wurde.
Zum einen muss in der Funktion getNodes das soeben berechnete Routingergebnis in einer gesonderten Tabelle zwischengespeichert werden. Dies dient
dazu, in späteren Suchanfragen auf Wunsch die bereits erzeugten Routen ausschließen zu können um alternative Routen zu berechnen. Dabei wird bei allen
Kanten des Ergebnisses das Gewicht erhöht, damit diese Kanten in späteren
Berechnungen eine niedrigere Relevanz haben. Des Weiteren wird zusätzlich
zu den erforderlichen Straßeninformationen die ID des Routingergebnisses gespeichert, damit bei weiteren Anfragen eine eindeutige Zuordnung der gespei-
56
cherten Routingergebnisse zur vorherigen Anfrage möglich ist.
// insert already visited edges in temporary table for calculating alternative routes
if ( ($options == 2) || ($options == 4) ) {
$temp = $db->query("INSERT INTO temp_edges SELECT r.id, r.source, r.target, ".
"r.cost2+10, $timestamp, $resultsId, r.x1, r.y1, r.x2, r.y2 ".
"r.cost5, r.cost6, r.cost7, r.cost8, r.cost9 ".
"FROM {$table}_edges r WHERE r.id= $edgeId ;");
Utils::checkDbError($temp);
}
Die Funktion ShortestPathQuery wird als nächstes um diesen Fall des Ausschließens bereits erzeugter Strecken erweitert. Hierzu wird in der SQLAnfrage die Tabelle mit den regulär verwendeten Graphinformationen mit den
soeben zwischengespeicherten Ergebnissen verknüpft, so dass ein neues Straßennetz entsteht, welches für die bereits verwendeten Segmente die erhöhten
Gewichte verwendet.
SELECT edge_id, x(the_geom), y(the_geom) FROM shortest_path(
’SELECT id, source, target, $cost AS cost FROM {$table}_edges WHERE id NOT IN
(SELECT id FROM temp_edges WHERE sessionid IN ({$resId}) )
UNION
SELECT id, source, target, $cost AS cost FROM temp_edges WHERE sessionid IN ({$resId})’,
?, ?, false, false) LEFT JOIN {$table}_vertices ON vertex_id = id;
Für den Fall der Berechnung einer Rundtour muss die Funktion computeRoutingResult um die Berechnung eines Zwischenziels erweitert werden. Mit dem
so gewonnenen Zwischenziel kann nun eine ShortestPathQuery vom Start zu
mZiel und anschließend vom Ziel zum Start durchgeführt werden, wobei im
letzten Fall die für den Hinweg berechnete Route, wie oben beschrieben, ausgeschlossen wird. Die so entstandenen zwei Routen werden danach durch die
Funktion mergeRoutingResult zu einer zusammengefügt und an den Benutzer
zurückgegeben.
--- Wählt die ID des Ortes aus, welcher in der gewählten Voronoizelle liegt
SELECT id FROM {$table}_vertices WHERE the_geom &&
--- Wählt zufällig eine Voronoizelle aus, welche innerhalb der Differenz der beiden Kreise liegt
(SELECT the_geom FROM rvoronoi r,
--- Berechnet die Differenz des inneren und äußeren Umkreises
(SELECT difference(innen.innen_geom,aussen.aussen_geom) FROM
--- Erzeugt den inneren Umkreis, indem erst vom Startpunkt ($node1) die Koordinaten gewählt
--- werden um dann mittels "buffer" einen Kreis mit Durchmesser $umkreis um die
--- Punktkoordinaten vom Startpunkt x(the_geom), y(the_geom) zu ziehen.
(SELECT setsrid(buffer(makepoint(x(the_geom), y(the_geom)), {$umkreis}),4326) as innen_geom FROM
(SELECT the_geom FROM {$table}_vertices WHERE id={$node1} ) as foo) as innen,
--- Erzeugt den äußeren Umkreis analog zu oben.
(SELECT setsrid(buffer(makepoint(x(the_geom), y(the_geom)),{$umkreis2}),4326) as aussen_geom FROM
(SELECT the_geom FROM {$table}_vertices WHERE id={$node1} ) as bar) as aussen
) as geom
WHERE r.the_geom && geom.difference AND intersects(r.the_geom, geom.difference) ORDER by random() LIMIT 1)
LIMIT 1;
57
ServerRouting
initializeRequest
+request
computeRoutingResult
+stops
+parameters
computePath
+node1
+node2
+parameters
+oldResultsId
getNodes
+result
+resultsId
+timestamp
+parameters
buildKML
+graph
mergeRoutingResultGraph
+routingResult
+newRoutingResult
shortestPathQuery
+node1
+node2
+parameters
+oldResultsId
Abbildung 6.4: Zusammenhang der serverseitigen Funktionen
Mit der neu erstellten Funktion buildKML wird die Geometrie des
Routingergebnisses in das KML-Format überführt und kann später in
ClientRouting.php in ein dynamisch erzeugtes KML-Dokument eingefügt werden.
protected function buildKML($graph) {
$routingResultsTable = $this->getRoutingResultsTable();
$ids = ’(’ . implode(’,’, $graph->resultsIds) . ’)’;
$db = $this->getDb();
$thegeom = $this->db->query("SELECT geomunion(the_geom) ".
"FROM $routingResultsTable where results_id IN $ids ;") ;
Utils::checkDbError($thegeom, ’Error receiving KML geometry’);
$thegeom = $thegeom->fetchRow(DB_FETCHMODE_ASSOC);
$thegeom = $thegeom[’geomunion’];
$kmlData = $this->db->query("SELECT askml(’$thegeom’) ;") ;
Utils::checkDbError($kmlData, ’Error building KML’);
$kmlData = $kmlData->fetchRow(DB_FETCHMODE_ASSOC);
return array($kmlData[’askml’], $this->getLength($thegeom));
}
58

<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://earth.google.com/kml/2.1">
<Document>
<name>{$fromto}</name>
<description>{$description}</description>
<Style id="the_route">
<LineStyle>
<color>ffed00e5</color>
<width>4</width>
</LineStyle>
<PolyStyle>
<color>07ed00e5</color>
</PolyStyle>
</Style>
<Placemark>
<name>Route</name>
<description></description>
<styleUrl>#the_route</styleUrl>
{$kmloutput}
</Placemark>
</Document>
</kml>
Alle berechneten Ergebnisse werden über die Funktion initializeRequest,
welche um die benötigten Rückgabeparameter erweitert wurde, wieder an
ClientRouting.php übergeben, so dass die Ergebnisse dem Benutzer,
wie in Abbildung 6.5 gezeigt, dargestellt werden können.
Abbildung 6.5: Darstellung einer Route im Webinterface
59
Kapitel 7
Anwendungsbeispiel
Abschließend wird noch ein exemplarischer Ablauf der Benutzung des entwickelten Webservices vorgestellt. Abbildung 7.1 zeigt das Benutzerinterface
des Webservices direkt nach dem Start. Mit den in Abbildung 7.2 dargestellten
Werkzeuge ist es dem Benutzer möglich den Kartenausschnitt zu vergrößern,
zu verkleinern, zu verschieben oder wieder in die ursprüngliche Ansicht zurückzusetzen, wie in Abbildung 7.3 gezeigt.
Abbildung 7.1: Ansicht des Webservice
Abbildung 7.2: Werkzeuge zum Verändern des Kartenausschnitts
60
Über die Legende wird dem Benutzer die Möglichkeit gegeben die Kartenansicht an seine Bedürfnisse anzupassen. So lassen sich, wie in Abbildung 7.4 zu
sehen, bestimmte Kartenlayer individuell anzeigen oder verbergen.
Abbildung 7.3: Änderung der Kartenansicht
Abbildung 7.4: Anpassen der Kartenansicht
Auf die Routingfunktionen kann über die Registerkarte “Routing” im Menu
zugegriffen werden. Hier können die üblichen Parameter wie Start und Ziel,
sowie der zu verwendende Modus ausgewählt werden. Zur Verfügung stehende Modi sind die Berechnung einer kürzesten, schnellsten und einer für Motorradfahrer geeigneten Route. Als weitere Optionen stehen die Angabe einer
61
KAPITEL 7. Anwendungsbeispiel
ungefähren Maximallänge für Rundtouren sowie die Auswahl verschiedener
Gruppen von POIs, welche in die Routenberechnung einfließen sollen, zur Verfügung. Zur Berechnung einer Rundtour ist, wie in Abbildung 7.5 gezeigt, ein
identischer Start- und Zielpunkt, sowie eine Kilometerangabe für die Länge
der Rundtour anzugeben.
Abbildung 7.5: Berechnung einer Rundtour
Abbildung 7.6: Berechnen einer alternativen Route
Sollte der Benutzer einen weiteren Tourenvorschlag mit den gesetzten Parametern und unter Ausschluss der bereits berechneten Route wünschen, so kann er
wie in Abbildung 7.6 gezeigt mittels der Option “Alternative Route berechnen”
eine neue Suchanfrage stellen.
62
Abbildung 7.7: Export einer berechneten Route(Quelle: Google Earth)
Über den Link “In Google Earth betrachten” kann die berechnete Route im
KML-Format heruntergeladen und in weitere Anwendungen, beispielsweise
Google Earth, geladen werden (siehe Abbildung 7.7).
Zu guter Letzt kann der Benutzer noch die Berücksichtigung verschiedener
POIs bei der Routenplanung auswählen. Hierzu existieren entsprechende Optionen, z.B. für Parks, Museen, Attraktionen und Monumente. Die berechnete
Route führt dann, wie in Abbildung 7.8 zu sehen, direkt oder relativ nah an
POIs der ausgewählten Kategorien vorbei.
Abbildung 7.8: Berechnung einer Route unter Berücksichtigung von POIs
63
Kapitel 8
Zusammenfassung und
Ausblick
Ausgehend vom allgemeinen Aufbau eines WebGIS-Systems, den damit verbundenen Standards und einer Analyse des Funktionsumfangs von derzeit auf
dem Markt befindlichen webbasierten Routenplanern wurde eine für diese Diplomarbeit geeignete Softwareumgebung ausgewählt und vorgestellt.
Anschließend wurde eine eingehende Analyse des Kartenmaterials mit dem
Ziel einen webbasierten Routenplaner für Motorradfahrer zu entwickeln
durchgeführt. Es wurden Kriterien erarbeitet, welche eine automatisierte,
computergestützte Routengenerierung ermöglichen. Hier konnte insbesondere
durch die Vorberechnung von Voronoi-Diagrammen über geeignete Geometrien eine effiziente Möglichkeit zur automatischen Erzeugung von Rundtouren
geschaffen werden. Die so gewonnenen Erkenntnisse wurden abschließend unter Verwendung der Eingangs ausgewählten Software in Form eines Webservices implementiert.
Um das hier vorgestellte System zu einem produktiv einsetzbaren Routenplaner zu erweitern ist die Verwendung eines geeigneten Datensatzes, insbesondere mit genauen Straßeninformationen notwendig. Hierzu zählen eine genaue
Unterscheidung in Straßen und Forst- und Feldwirtschaftswege, Einbahnstraßen, Abbiegeverbote und sonstige Streckenverbote im Sinne der StVO. In diesem Fall muss dann auch ein geeigneter Suchalgorithmus, wie beispielsweise
in [11] vorgestellt, verwendet werden. Weiterhin bietet es sich aus Gründen
der Performanz an, verschiedene Optimierungsmöglichkeiten für die Suche zu
64
implementieren (z.B. [9], [8], [10]).
Als weitere Klassifikationsmöglichkeiten für das Straßennetz könnte außerdem die Lage in landschaftlich reizvollen Gebieten betrachtet werden. So können Strecken die durch Wälder führen entsprechend günstiger gewichtet werden. Des Weiteren bietet es sich an, nach Flüssen in der Nähe der Straße zu
suchen, da dies zum einen meist ein Indikator für optisch schöne Gegenden
darstellt, zum anderen sich auch Straßen oftmals an einem kurvigen Flusslauf
orientieren.
Darüberhinaus verfügt die zugrundeliegende Software noch über das Potential
dem Benutzer weitere Funktionen anzubieten. So wäre es denkbar das System
zu einem Communityportal auszubauen, in dem es nicht nur möglich ist nach
neuen Routen zu suchen, sondern mittels WFS-T Funktionen auch eigene Routen für andere Motorradfahrer zu hinterlegen.
65
Anhang A
Importieren des
Kartenmaterials
Nachfolgend wird nun die Installation der erforderlichen Umgebung auf einem Linuxsystem mit Debian Etch beschrieben. Die folgenden Pakete werden
benötigt:
apt-get install postgresql-8.1
postgresql-client-8.1
postgresql-client-common postgresql-common
postgresql-server-dev-8.1 phppgadmin apache2
Abbildung A.1: Benötigte Debian-Pakete
gaul-devel-0.1849-0 [32]
geos-3.0.0rc3 [33]
proj-4.5.0 [34]
postgis-1.2.1 [15]
pgRouting-1.0.0a [21]
Abbildung A.2: Benötigte Quellpakete
Da die bei Debian Etch mitgelieferten Versionen dieser Pakete nicht dem aktuellen Entwicklungsstand entsprachen, welcher etliche Funktionen mehr zu
bieten hatte, wurden die Pakete in der jeweils aktuellen Version heruntergeladen und aus dem Quelltext kompiliert und installiert. Die Installation erfolgt
66
mit dem bei Linux üblichen Trio configure, make und make install und wird
daher nicht weiter betrachtet.
GAUL (Genetic Algorithm Utility Library), GEOS (Geometry Engine - Open
Source) und PROJ (Cartographic Projections Library) dienen dazu, PostGIS
und pgRouting verschiedene Geometriemodelle zur Verfügung zu stellen und
eine effiziente Berechnung dieser zu ermöglichen.
pgRouting erweitert PostGIS um verschiedene Routingalgorithmen. Dies sind
im Einzelnen:
Shortest Path Dijkstra Normales Routing ohne Heuristik
Shortest Path A* Routing mit Heuristik für große Datenmengen
Shortest Path Shooting Star Routing unter Beachtung von Abbiegeverboten
Nach der Installation der Pakete kann nun eine Postgres-Datenbank für die
Benutzung der Geodaten angelegt werden. Hierzu werden zunächst Benutzer
und Datenbank erzeugt:
su postgres
createuser -s -d -l -P rainer
createdb -O rainer navigation
Abbildung A.3: Anlegen der Datenbank
Danach können die benötigten PostGIS-Erweiterungen in die Datenbank geladen werden. Die benötigten SQL-Dateien befinden sich im Quellverzeichnis
des PostGIS-Paketes.
su postgres
createlang plpgsql navigation
psql -d navigation -f lwpostgis.sql
psql -d navigation -f spatial_ref_sys.sql
Abbildung A.4: PostGIS-Erweiterungen installieren
67
ANHANG A. Importieren des Kartenmaterials
Nun können im nächsten Schritt die Shapefiles mittels des bei PostGIS mitgelieferten Tools shp2pgsql in die Datenbank importiert werden:
shp2pgsql -s 4326 -W LATIN1 -Id streets streets
navigation | psql -d navigation
In diesem Beispiel wird das Shapefile streets.shp als Tabelle streets in
die Datenbank navigation eingefügt.
Die so importierten Daten können nun mit einer Desktop-GIS-Anwendung wie
uDig betrachtet und einer ersten Analyse unterzogen werden.
68
Anhang B
Installation von UMN
Mapserver und Cartoweb
Wie in Kapitel 4.2 erwähnt, verwendet CartoWeb den UMN Mapserver zur
Erzeugung der Karten. Die Steuerung von Mapserver zum Erzeugen der Karte
erfolgt über ein sogenanntes Mapfile, welches mit einer eigenen Syntax die
darzustellenden Kartenlayer definiert. Ein Beispielmapfile, welches eine Verbindung zur PostgreSQL-Datenbank herstellt und die Geometrie der Bundesländer Hessen, Rheinland-Pfalz und Saarland darstellt, sieht wie folgt aus:
MAP
NAME Kartendemo
SIZE 640 480
#
EXTENT 6 49 11 52
#
UNITS DD
#
Imagecolor 255 255 255 #
IMAGETYPE png
#
PROJECTION
"init=epsg:4326"
END
Bildgroesse
Darzustellender Kartenbereich minx, miny, maxx, maxy
Einheit des Koordinatensystem fuer EXTENT (hier Gradangaben)
Hintergrunfarbe
Dateiformat
# Koordinatensystem in dem die Daten vorliegen
LAYER
# Definition eines Kartenlayers
NAME "bundesland"
# Name
TYPE POLYGON
# Typ der Geometrie (Punkt, Linie, Polygon)
CONNECTIONTYPE postgis # Quelle der Daten
CONNECTION "user=username password=secret host=localhost dbname=navigation"
DATA "geometry FROM table" # Spaltenname der Tabelle welche die Geometrie enthaelt
CLASSITEM ’laendername’
# Spaltename der die Sachdaten klassifiziert
CLASS
# Detaillierte Definitionen zu den jeweiligen Inhalten
# der Spalte laendername
NAME ’SAARLAND’
EXPRESSION ’SAARLAND’
COLOR 255 255 0
END
CLASS
NAME ’RHEINLAND-PFALZ’
EXPRESSION ’RHEINLAND-PFALZ’
COLOR 255 0 3
END
69
ANHANG B. Installation von UMN Mapserver und Cartoweb
CLASS
NAME ’HESSEN’
EXPRESSION ’HESSEN’
COLOR 0 0 0
END
END # Layer
END # Map File
Damit dies in einem Browser angezeigt werden kann, ist noch ein “Client”
in Form einer HTML-Seite nötig, welche eine Verbindung zum UMN Mapserver herstellt, die im Mapfile spezifizierte Karte anfordert und das Ergebnis
wiederum im Browser anzeigt. In diesem Fall bedienen wir uns der MapserverSchnittstelle von PHP, die hierfür einfache Funktionen bereitstellt:
<?php
$map_file="./mapfile.map";
$map = ms_newMapObj($map_file);
$image=$map->draw();
$image_url=$image->saveWebImage();
?>
<html>
<head>
<title>Mapserver Demo</title>
</head>
<body>
<img SRC="<?php echo $image_url?>">
</body>
</html>
Abbildung B.1: Das Ergebnis
70
Die Installation des CartoWeb-Frameworks ist in relativ wenigen Schritten
vollzogen. Das Framework ist auf der CartoWeb-Homepage [26] erhältlich
und wird auf dem Server nach /var/www/ entpackt. Anschließend kann mittels dem Kommando ./php5 cw3setup.php -install -base-url
http://www.domain.com/cartoweb das Installationsskript von CartoWeb aufgerufen werden. Danach können die mitgelieferten Templates den
eigenen Bedürfnissen angepasst werden.
71
Anhang C
Berechnung des
Voronoidiagrammes
PostGIS bietet zwar auch eine interne Funktion zur Berechnung von Voronoidiagrammen, jedoch ist diese nicht sehr performant. Eine wesentlich bessere
Möglichkeit zur Berechnung von Voronoidiagrammen besteht in der Verwendung von R (http://www.r-project.org).
Die folgende Anleitung wurde der PostGIS-Mailingliste entnommen, siehe
http://postgis.refractions.net/pipermail/postgis-users/2006-April/011732.html
[postgis-users] Voronoi / Dalaunay function with R
Jan Hartmann j.l.h.hartmann at uva.nl
Wed Apr 5 11:04:32 PDT 2006
Previous message: [postgis-users] Voronoi / Dalaunay function (solved)
Next message: [postgis-users] Voronoi / Dalaunay function with R
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
As an alternative to Mike Leahy’s and Mark Fenber’s Voronoi postings:
There is an easy way to generate Voronoi polygons for PostGIS using R
(wwww.r-project.org). In its simplest form you generate a text file with
x-y coordinates from PostGIS, read these into R, compute the Voronoi
diagram, and write the resulting polygons out as a text file with SQL
insert commands:
- write out x-y-values to "points.txt"
psql <database>
\o points.txt
\t
select x,y from table
\o
- The Voronoi package "deldir"
(http://cran.r-project.org/src/contrib/Descriptions/deldir.html) is
not part of the standard R distribution, so you have to install it
with:
"R CMD INSTALL deldir" (for Windows, install from the "packages" menu)
- R
72
library(deldir)
points = scan(file="points.txt",what=list(x=0.0,y=0.0),sep="|")
voro = deldir(points$x,points$y)
# generate voronoi edges
tiles = tile.list(voro)
# combine edges into polygons
sink("voronoi.sql")
# redirect output to file
for (i in 1:length(tiles)) {
# write out polygons
tile = tiles[[i]]
cat("insert into mytable (the_geom) values(geomfromtext(’POLYGON((")
for (j in 1:length(tile$x)) {
cat (tile$x[[j]],’ ’,tile$y[[j]],",")
}
cat (tile$x[[1]],’ ’,tile$y[[1]]) #close polygon
cat ("))’,4326));\n")
# add SRID and newline
}
sink()
# output to terminal
- In psql create a table "mytable" with a geometrycolumn "the_geom" and
insert "voronoi.sql" (\i voronoi.sql). If you want additional
information for each polygon, add variables to "points.txt" and adapt
the "scan" statement accordingly. An additional variable (e.g. "id") can
be accessed in the loop as points$id[[i]]
If you have PL/R installed, you can access everything from within
PostgreSQL. In that case there is no need for intermediate ascii-files:
data can be read and written directly with "pg.spi.exec(SQL-statement)".
PostgreSQL data can also be read directly into R by means of the Rdbi
and Rdbi.PgSQL packages
(http://www.bioconductor.org/repository/release1.5/package/html/Rdbi.html
and
http://www.bioconductor.org/repository/release1.5/package/html/RdbiPgSQL.html)
They are only available for Unix and can be somewhat tricky to install.
Alternatively, you can use the RODBC package.
Whatever method you choose, text-files, Pl/R or Rdbi/RODBC, the
combination of PostgreSQL and R will give a huge usability boost to your
PostGIS applications.
Jan
Jan Hartmann
Department of Geography
University of Amsterdam
In diesem Falle wurden die X und Y-Koordinaten aus der Tabelle aller Ortsnamen verwendet um hierüber ein Voronoidiagramm zu bilden, welches dann
wieder mit den zugehörigen Ortsnamen verknüpft wurde, so dass die resultierende PostGIS-Tabelle aus den Spalten “Ortsname” und “Geometrie” besteht,
wobei letztere aus den Voronoizellen besteht.
73
Abbildungsverzeichnis
74
2.1
Aufbau eines Web GIS . . . . . . . . . . . . . . . . . . . . .
7
2.2
Zusammenspiel der OGC-Standards . . . . . . . . . . . . . .
11
2.3
Zusammenspiel Sachdaten, Geodaten . . . . . . . . . . . . .
13
2.4
Voronoi-Diagramm . . . . . . . . . . . . . . . . . . . . . . .
18
3.1
Webinterface Map24 . . . . . . . . . . . . . . . . . . . . . .
21
3.2
Webinterface maps.google.de . . . . . . . . . . . . . . . . . .
22
3.3
Webinterface Mapquest . . . . . . . . . . . . . . . . . . . . .
23
3.4
Webinterface Yahoo . . . . . . . . . . . . . . . . . . . . . . .
24
3.5
Webinterface MSN . . . . . . . . . . . . . . . . . . . . . . .
25
4.1
Beispiel eines R-Baumes . . . . . . . . . . . . . . . . . . . .
28
4.2
Schematische Darstellung des Geodatenservers . . . . . . . .
29
4.3
Architektur von CartoWeb, Client . . . . . . . . . . . . . . .
31
4.4
Architektur von CartoWeb, Server . . . . . . . . . . . . . . .
32
5.1
Analyse des Straßennetzes . . . . . . . . . . . . . . . . . . .
39
5.2
Analyse des Straßennetzes (2) . . . . . . . . . . . . . . . . .
41
5.3
Umkreisberechnung, Schema . . . . . . . . . . . . . . . . . .
44
ABBILDUNGSVERZEICHNIS
5.4
Verschiedene Radien und deren mittlere Abweichung (1) . . .
45
5.5
Verschiedene Radien und deren mittlere Abweichung (2) . . .
46
5.6
Umkreisberechnung, Datenbankschema . . . . . . . . . . . .
47
5.7
Voronoidiagramm der Orte . . . . . . . . . . . . . . . . . . .
48
5.8
Eine automatisch generierte Rundtour . . . . . . . . . . . . .
48
5.9
Ergebnisse der Routenplanung . . . . . . . . . . . . . . . . .
49
5.10 Ergebnisse der Routenplanung (2) . . . . . . . . . . . . . . .
50
6.1
Legende des Webinterfaces . . . . . . . . . . . . . . . . . . .
53
6.2
Darstellung des Kartenmaterials . . . . . . . . . . . . . . . .
54
6.3
Eingabemaske Routing . . . . . . . . . . . . . . . . . . . . .
56
6.4
Zusammenhang der serverseitigen Funktionen . . . . . . . . .
58
6.5
Darstellung einer Route im Webinterface . . . . . . . . . . . .
59
7.1
Ansicht des Webservice . . . . . . . . . . . . . . . . . . . . .
60
7.2
Werkzeuge zum Verändern des Kartenausschnitts . . . . . . .
60
7.3
Darstellung einer Route im Webinterface . . . . . . . . . . . .
61
7.4
Anpassen der Kartenansicht . . . . . . . . . . . . . . . . . .
61
7.5
Berechnung einer Rundtour . . . . . . . . . . . . . . . . . . .
62
7.6
Berechnen einer alternativen Route . . . . . . . . . . . . . . .
62
7.7
Export einer berechneten Route . . . . . . . . . . . . . . . . .
63
7.8
Berechung einer Route unter Berücksichtigung von POIs . . .
63
A.1 Benötigte Debian-Pakete . . . . . . . . . . . . . . . . . . . .
66
A.2 Benötigte Quellpakete . . . . . . . . . . . . . . . . . . . . .
66
75
ABBILDUNGSVERZEICHNIS
76
A.3 Anlegen der Datenbank . . . . . . . . . . . . . . . . . . . . .
67
A.4 PostGIS-Erweiterungen installieren . . . . . . . . . . . . . .
67
B.1 UMN Mapserver Demo . . . . . . . . . . . . . . . . . . . . .
70
Literaturverzeichnis
[1] Open Geospatial Consortium
http://www.opengeospatial.org/
Letzter Zugriff: Dezember 2007
[2] ESRI Shapefile Technical Description
http://www.esri.com/library/whitepapers/pdfs/shapefile.pdf
Letzter Zugriff: Oktober 2007
[3] W3C Geospatial Incubator Group
http://www.w3.org/2005/Incubator/geo/XGR-geo-20071023/
Letzter Zugriff: Januar 2008
[4] R. W. Floyd, Algorithm 97: Shortest Path, Communications of the ACM
5 (1962), Nr. 6, S. 345
[5] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1, S. 269-271, 1959
[6] I. Pohl, Bi-directional and heuristic search in path problems. Stanford
Linear Accelerator Center. Stanford, California, 1969 - Technical Report
104
[7] P.E. Hart, N. J. Nilsson, B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on System Science
and Cybernetics, 4(2), S. 100-107, 1968
[8] R. J. Gutman. Reach-Based Routing: A new approach to shortest path algorithms optimized for road networks. ALENEX/ANALC, 2004, S. 100111
[9] D. Schultes, Fast and Exact Shortest Path Queries Using Highway Hierarchies. Master-Arbeit, Universität des Saarlandes, 2005
77
LITERATURVERZEICHNIS
[10] R. H. Möhring, H. Schilling, B. Schütz, D. Wagner, T. Willhalm Partitioning graphs to speed up Dijkstra’s algorithm. 4th International Workshop
on Efficient and Experimental Algorithms, 2005
[11] K. Müller, Berechnung kürzester Pfade unter Beachtung von Abbiegeverboten. Studienarbeit, Universität Karlsruhe (TH), Fakultät für Informatik,
2005.
[12] Mapsolute Developer Network
http://devnet.map24.com/
Letzter Zugriff: Juli 2007
[13] GIS and Spatial Extensions with MySQL
http://dev.mysql.com/tech-resources/articles/4.1/gis-with-mysql.html
[14] OGC, All Registered Products
http://www.opengeospatial.org/resource/products
Letzter Zugriff: Februar 2008
[15] PostGIS
http://postgis.refractions.net/
[16] A. Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching.
In Proc. ACM SIGMOD, S. 47-57, 1984
[17] N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger The R∗ -Tree: An
efficient and robust access method for points and rectangles. In Proc.
ACM SIGMOD, S. 322-331, 1990
[18] T. Sellis, N. Roussopoulos, C. Falaoutsos: The R+ -Tree: A dynamic index
for multidimensional objects. In Proc. of VLDB, S. 3-11, 1987
[19] T. Bingmann, Visualisierung sehr großer Graphen, Studienarbeit, Universität Karlsruhe (TH), Fakultät für Informatik, 2006
[20] J. M. Hellerstein, J. F. Naughton, A. Pfeffer. Generalized Search Trees
for Database Systems. Proc. 21st Int’l Conf. on Very Large Data Bases,
Zürich, September 1995, 562-573.
[21] pgRouting Project
http://pgrouting.postlbs.org/wiki
78
[22] Orkney Inc.
http://www.orkney.co.jp/english/index.html
[23] Geoserver
http://www.geoserver.org/
[24] OpenLayers
http://www.openlayers.org/
[25] UMN Mapserver
http://mapserver.gis.umn.edu/
[26] CartoWeb
http://www.cartoweb.org/
[27] GeoTools - The Open Source Java GIS Toolkit
http://geotools.codehaus.org/
[28] Camptocamp SA
http://www.camptocamp.com/
[29] Smarty Template Engine
http://www.smarty.net/
[30] Quantum GIS
http://www.qgis.org/
[31] uDIG - User-friendly Desktop Internet GIS
http://udig.refractions.net
[32] Genetic Algorithm Utility Library
http://gaul.sourceforge.net/
79
[33] Geometry Engine - Open Source
http://geos.refractions.net/
[34] PROJ.4 - Cartographic Projections Library
http://proj.maptools.org/
80

Ein webbasierter Routenplaner für Motorradfahrer

Transcrição

Documentos relacionados

Inspektor Gadget

Liste anfordern - ADFC

Karte * - ESSEN.Neue Wege zum Wasser

Reiseverlauf herunterladen

Page 1 of 1 K+K Hotel George, London nach The Pembroke (ex

Probleme bei der Weitergabe von GPS-Routen

Köln Cologne

Online Routenplaner

Datei herunterladen

Die besten fünf kostenlosen Routenplaner