Post on 29-Jan-2016
description
transcript
Datenstrukturen und Algorithmen in
Open Street MapModul: Algorithmische GeometireVon: Elisabeth Lehmann 12INB-P
Inhalte1) Was ist
OpenStreetMap?2) Das Konzept3) Datenstrukturen in
OSMa) Nodeb) Wayc) Relationd) Tagse) OSM-Format
4) Algorithmena) Allgemeine
Vorgehensweiseb) Abstraktionsverfahrenc) Dijkstra-Algorithmus/
beidseitiger Dijkstrad) HISPA-Algorithmuse) A*-Algorithmusf) Contraction Hierarchies
5) Quellen
• ein 2004 gegründetes Projekt einer freien Weltkarte
• Sammlung von verschiedenen Daten, welche selbst erhoben werden
-> darf lizenzkostenfrei eigesetzt und beliebig weiterverarbeitet werden
1) Was ist OpenStreetMap?
• das Routing (Wegwahlfunktion) steht im Vordergrund
• optisches darstellen von Straßenattributen • Aufgabengebiete für die Funktionalität
◦ geografische Rohdaten◦ Anwendungsprogrammierung◦ Rendering
◦ Beispiel: OSMarelmon
2) Das Konzept
a) Node• kleinstes OSM-Objekt• bilden Gerüst der OSM-Karte
• Bestimmen zum Beispiel Verläufe von Straßen, Umrisse von Grundstücken, Ecken von Häusern
• repräsentieren GPS-Punkte• besitzen ID, Breitengrad und Längengrad,
Versionsnummer, Zeitstempel• Changeset-ID enthält letztes
Bearbeitungsdatum des Knoten (mit dazugehöriger User-ID)
3) Datenstrukturen in OSM
b) Way • ein Way besteht aus mindestens zwei
Knoten• verknüpft diese miteinander• stellen jegliche Arten von Verbindungen
zwischen Punkten her (in Array gespeichert)• zum Beispiel Uferverläufe oder Straßen
• mit gleichem Knoten als Start-und Endpunkt entstehen Flächen
• gleiche Metatags wie Nodes (ohne Breiten-und Längengrad)
• einzelnen Knoten als Referenztags eingebunden
<way id="9714974" version="16" timestamp="2012-06-28T23:41:09Z" changeset ="122312034" uid="1999074" user="perihel"><nd ref="304335953"/><nd ref="1563547869"/ ><nd ref="1396523373"/ ><nd ref="13878099"/></way>
c) Relation
• größter und umfassendster Datentyp in OSM
• erfassen komplexer und abstrakter Formen • Zum Beispiel Abbiegevorschriften Buslinien
• besitzt Referenzen (Member genannt)auf Konten, Wege und andere Relationen
<relation id="1239081" version="2" timestamp="2012-06-28T20:41:04Z" changeset ="122312034" uid="1999074" user="perihel"><member type="node" ref="867397262„ role="stop"/><member type="node" ref="213127" role="platform"/><member type="way" ref="19012912" role=""/><member type="relation" ref="09278124" role=""/></relation>
d) Tags
• Datenstrukturen bieten Metatags und vom Benutzer frei handhabbare Tags
• vor dem Endtag wird Benutzer die Möglichkeit geboten, selbst definierte Tags einzufügen
• bestehen aus key-value-Paaren• (wobei key angibt, was Relation beschreibt)
<tag k="maxspeed:winter" v="60">
e) OSM-Format
• Speicherung sämtlicher Daten in OSM XML• Minimal-und Maximalfunktionen können verwendet
werden• Reihenfolge der Objekte:
• Knoten• Wege• Relationen, deren Referenzen und Tags
• einfach lesbar, systemunabhängig, nur Parser muss vorhanden sein
• durch Größe der Dateien Kompression nötig• zum Beispiel planet.osm mit 400GB komprimiert,komprimeirt nur 29GB
• viele verschiedene Algorithmen, da unterschiedliche Funktionen angefragt werden
• Hauptteil bildet die Routen-Planung
• jedoch auch im Bereich der Geschwindigkeitsmessung oder von Höhenunterschieden
4) Algorithmen
a) allgemeines Vorgehen1. sammeln der Attribute zu jedem OSM-
Objekt2. Speichern der Koordinaten des Knoten3. Knoten beim Einlesen des Weges
gespeichert4. Bestimmen des geeignet Weges
I. ungeeignete Wege verwerfenII. zulässige Richtung und Geschwindigkeit
bestimmen III. Weg bestimmen
b) Abstraktionsverfahren
• graphen-ähnliche Darstellung bestehend aus Segment-Node (analog Knoten), Segment (gerichtete Verbindungen), Restriction (nicht nutzbare Verbindungen)
• Segment-Nodes und Segments können jedoch nicht einfach als Knoten bzw. Kanten des Graphen verwendet werden
-> Restrictions müssen berücksichtigt werden
c) Dijkstra-Algorithmus (1959)
• Bestimmung des kürzesten Weges unter Berücksichtigung des Kantengewichts (zum Beispiel der benötigten Zeit)
• Problem bei der Routenplanung: die kürzeste Strecke ist nicht unbedingt die schnellste ->mehrere Attribute pro Kante eingefügt (Entfernung [km], sondern auch Zeit [min])
• • О(E + V *log(V))
• V=Knotenmenge, E=Kantenmenge
d) HISPA-Heuristik
• Hierarchical shortest path
• sucht kürzesten Weg von zwei Endknoten zu Knoten der obersten Hierarchieebene im Umkreis mit gegebenen Radius
• Zum Beispiel von Stadt zu Autobahnkreuz
e) A*-Algorithmus Finde den kürzesten von Arad nach Buadpest
f) Contraction Hierarchies
• Routing-Algorithmus derzeitige Grundlage für mobile Navigation
• bei westeuropäischen Straßennetz etwa 20.000mal schneller als Dijkstra
• Suchanfragen in unter 1ms beantwortet• wenn nur Distanz und nicht Route abgefragt
wird, verbraucht sogar Datenstruktur weniger Speicherplatz
http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/sauer/geyer/BA_SebastianBrunner_-201308.pdf
ftp://ftp.informatik.uni-stuttgart.de/pub/library/medoc.ustuttgart_fi/DIP-3232/DIP-3232.pdf
http://tobias-knerr.de/bachelorarbeit/Bachelorarbeit.pdf
http://cvpr.uni-muenster.de/teaching/ws05/kiWS05/script/KI-Kap04-2.pdf
http://www.openstreetmap.de/faq.html#was_ist_osm
Quellen