Ein webbasierter Routenplaner für Motorradfahrer
Transcrição
Ein webbasierter Routenplaner für Motorradfahrer
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 KAPITEL 2. Grundlagen webbasierter Routenplaner 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 KAPITEL 2. Grundlagen webbasierter Routenplaner 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 KAPITEL 2. Grundlagen webbasierter Routenplaner 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 KAPITEL 2. Grundlagen webbasierter Routenplaner 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 zeit- und 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 KAPITEL 2. Grundlagen webbasierter Routenplaner 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 KAPITEL 3. Übersicht existierender Routenplaner 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 KAPITEL 3. Übersicht existierender Routenplaner 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 KAPITEL 4. Softwareevaluation 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 KAPITEL 4. Softwareevaluation 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 KAPITEL 4. Softwareevaluation 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 KAPITEL 5. Konzeption des Webservices 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 5.1. Analyse des Kartenmaterials (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 KAPITEL 5. Konzeption des Webservices 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 5.1. Analyse des Kartenmaterials (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 KAPITEL 5. Konzeption des Webservices 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’; EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_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)’; EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_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)’; EXECUTE ’UPDATE ’ || quote_ident(geom_table) || ’_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 KAPITEL 5. Konzeption des Webservices 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 5.2. Vorüberlegungen zur Routenplanung (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 KAPITEL 5. Konzeption des Webservices (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 5.2. Vorüberlegungen zur Routenplanung 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 KAPITEL 5. Konzeption des Webservices 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 5.2. Vorüberlegungen zur Routenplanung (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 KAPITEL 5. Konzeption des Webservices (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 KAPITEL 6. Erstellen des Webservices 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> <input type="checkbox" name="pois[]" value="cost6" </td> <td>Museum</td> </tr> <tr> <td align="right"> <font color="#ff6e0d" size="4pt">•</font> <input type="checkbox" name="pois[]" value="cost8" </td> <td>Attraktion</td> </tr> <tr> <td align="right"> <font color="#000000" size="4pt">•</font> <input type="checkbox" name="pois[]" value="cost9" </td> <td>Monumente</td> </tr> </table> {if $cost7} checked="checked"{/if}> {if $cost6} checked="checked"{/if}> {if $cost8} checked="checked"{/if}> {if $cost9} 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 KAPITEL 6. Erstellen des Webservices 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 6.2. Implementation in CartoWeb 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 KAPITEL 6. Erstellen des Webservices 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 6.2. Implementation in CartoWeb <!-- Template for KML Export --> <?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 Letzter Zugriff: Januar 2008 [14] OGC, All Registered Products http://www.opengeospatial.org/resource/products Letzter Zugriff: Februar 2008 [15] PostGIS http://postgis.refractions.net/ Letzter Zugriff: Februar 2008 [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 Letzter Zugriff: Februar 2008 78 LITERATURVERZEICHNIS [22] Orkney Inc. http://www.orkney.co.jp/english/index.html Letzter Zugriff: Februar 2008 [23] Geoserver http://www.geoserver.org/ Letzter Zugriff: Dezember 2007 [24] OpenLayers http://www.openlayers.org/ Letzter Zugriff: Dezember 2007 [25] UMN Mapserver http://mapserver.gis.umn.edu/ Letzter Zugriff: Februar 2008 [26] CartoWeb http://www.cartoweb.org/ Letzter Zugriff: Februar 2008 [27] GeoTools - The Open Source Java GIS Toolkit http://geotools.codehaus.org/ Letzter Zugriff: Januar 2008 [28] Camptocamp SA http://www.camptocamp.com/ Letzter Zugriff: Februar 2008 [29] Smarty Template Engine http://www.smarty.net/ Letzter Zugriff: Februar 2008 [30] Quantum GIS http://www.qgis.org/ Letzter Zugriff: Januar 2008 [31] uDIG - User-friendly Desktop Internet GIS http://udig.refractions.net Letzter Zugriff: Januar 2008 [32] Genetic Algorithm Utility Library http://gaul.sourceforge.net/ Letzter Zugriff: Dezember 2007 79 LITERATURVERZEICHNIS [33] Geometry Engine - Open Source http://geos.refractions.net/ Letzter Zugriff: Januar 2008 [34] PROJ.4 - Cartographic Projections Library http://proj.maptools.org/ Letzter Zugriff: Februar 2008 80