Wie lassen sich OSM-Daten zur Weiterverarbeitung aufbereiten?

Geodaten à la Carte

Oliver Schünemann

© Shutterstock / Vadim Georgiev

Das OpenStreetMap-Projekt stellt, neben der bekannten Webseite, auch die Rohdaten zur Verfügung. Diese werden von einer großen Gemeinschaft, ähnlich wie bei Wikipedia, zusammengetragen, stammen aber auch teilweise aus anderen freien Quellen. Das Rohdatenformat ist auf geringen Speicherbedarf hin optimiert, eignet sich jedoch nur bedingt zur weiteren Verarbeitung. Im Folgenden wird gezeigt, wie die Daten umgewandelt werden können, um sie für Routenberechnung, Kartenerstellung usw. verwenden zu können.

OSM-Daten werden im Wesentlichen in drei verschiedenen Formaten bereitgestellt. Das bekannteste ist das OSM-Format, ein XML-Dialekt. Daneben gibt es noch das PBF und das O5M-Format. Allen gemeinsam ist der prinzipielle Aufbau der Daten. Sie sind aufgeteilt in Knoten, Wege und Relationen. Die kleinste Einheit bilden die Knoten (Nodes, Listing 1). Diese enthalten die geografische Position eines Punkts in der Landschaft und können, so wie alle anderen Elemente der Karte auch, weitere Eigenschaften besitzen, die als Schlüssel-Wert-Paare abgelegt sind.

  <node visible="true" id="123456" lat="52.51627" lon="13.37773"> 
  <tag k="name" v="Brandenburger Tor"/> 
  <tag k="public_transport" v="stop_position"/> 
  <tag k="railway" v="tram_stop"/> 
  <tag k="tram" v="yes"/> 
 </node>

Mehrere Knoten zusammen bilden einen Weg (Way, Listing 2). Dieser enthält selbst keinerlei Positionsangaben, sondern referenziert lediglich die Knoten über deren ID.

  <way id="234567" visible="true"> 
    <nd ref="123456"/> 
    <nd ref="123457"/> 
    <nd ref="113456"/> 
    <tag k="highway" v="residential"/> 
    <tag k="name" v="Unter den Linden"/> 
  </way>

Aus einem Weg können dabei nicht nur Straßen, Pfade, Bahn- und Wasserlinien gebildet werden, sondern auch alle einfachen Flächen werden von Wegen umrandet. Kompliziertere Objekte werden dagegen als Relation beschrieben (Listing 3). Diese referenzieren wiederum Knoten und Wege, aber auch andere Relationen, um daraus lange Autobahnen, große Waldgebiete und mehr zu bilden.

<relation id="34567"> 
  <member type="way" ref="234567" role="outer"/> 
  <member type="way" ref="234568" role="outer"/> 
  <tag k="highway" v="pedestrian"/> 
  <tag k="name" v="Pariser Platz"/> 
  <tag k="type" v="multipolygon"/>
</relation>    

Jede dieser Referenzen hat einen Typ („node“, „way“, „relation“) und eine Rolle. Mehr dazu findet sich online.

Probleme bei der Verarbeitung

Die Daten könnten so, wie sie im XML abgelegt sind, direkt einer Datenbank entsprungen sein. Die einzelnen Tabellen für Knoten, Wege und Relationen mit ihren Zeigern auf die anderen Tabellen lassen sich deutlich erkennen. Der einfachste Ansatz zur Weiterverarbeitung der Daten wäre also, sie in eine Datenbank zurückzuspielen und anschließend die einzelnen Knoten für die Wege zu finden, um diese z. B. in einer Karte zu zeichnen. Bei aktuell 2,5 Milliarden Knoten in den OSM-Daten und 250 Millionen Wegen braucht es aber schon die Datenbank eines mittelgroßen Industrieunternehmens, um sämtliche Knoten-Weg-Beziehungen aufzulösen. Einen gut ausgestatteten Arbeitsplatzrechner zwingt man damit auf jeden Fall in die Knie. Grund dafür ist nicht einmal, dass der Ansatz grundlegend falsch ist. Vielmehr hat man es hier mit einem mechanischen Problem zu tun. Will man wahlfrei auf Daten eines rotierenden Massenspeichers zugreifen, bedeutet dies, dass der Lesekopf permanent umpositioniert werden muss, was eine sehr zeitraubende Operation ist. Dagegen lassen sich zusammenhängende Daten relativ schnell lesen. Ziel muss es also sein, den wahlfreien Zugriff in einen linearen Zugriff zu wandeln.

Beziehungen zwischen den einzelnen Elementen auflösen

Bei Datenbanken werden zum Abbilden von Beziehungen zwischen Elementen verschiedener Tabellen Relationstabellen eingesetzt, die in jeder Zeile die primären Schlüssel zweier Objekte beinhalten, die miteinander in Beziehung stehen. Ähnlich geht die hier vorgestellte Bibliothek vor, deren Lösungsansatz für dieses Problem beschrieben werden soll.

Zunächst werden alle Knoten, Wege und Relationen in eigenen Dateien gespeichert. Für jede ID, die die Referenz auf ein anderes Objekt abbildet, wird dabei den Objekten ein dem Referenztyp entsprechendes Objekt als Platzhalter übergeben, das, bis auf die ID, unkonfiguriert ist und später durch das entsprechende Objekt aus dem Datensatz ersetzt werden soll. Als Basisinterface für alle drei Typen dient java.io.Externalizable, was es erlaubt, sie ohne unnötigen Ballast zu speichern. Das weitere Vorgehen sei nun am Beispiel der Wege beschrieben (Listing 4).

 
public class Way implements Externalizable {
  protected long id = 0;
  protected List nodes = new ArrayList<>();
  protected final Map<String, String> props = new HashMap<String, String>();
  ...
}

Im ersten Schritt wird nun die Wegedatei mithilfe des oc.io.ExternalizableIterator (stellt den Inhalt einer Datei von Externalizable mit der Funktionalität eines java.util.Iterator zur Verfügung) einmal komplett eingelesen und dabei eine Datei mit allen benötigten Weg-Knoten-Beziehungen erstellt, ähnlich dem Datenbankansatz von oben. Der einzige Unterschied ist, dass auch hier gleich wieder ein Platzhalter für jeden gesuchten Knoten vorhanden ist.

Die Idee ist nun, die Datei mit allen Knoten-Weg-Beziehungen nach der Knoten-ID zu sortieren und anschließend die Knotendatei sowie die Beziehungsdatei parallel einzulesen, um so die Platzhalter durch die Knoten zu ersetzen und in einer weiteren Datei zu speichern. Ist dies geschehen, kann die neue Beziehungsdatei wieder nach den Wege-IDs sortiert werden, anschließend diese parallel zur Wegedatei durchgearbeitet und die Knoten an ihren endgültigen Bestimmungsort, nämlich den Weg, kopiert werden. Zum Sortieren der Beziehungen wird die Klasse oc.io.ExternalizableSorter verwendet, die einen leicht modifizierten Merge-Sort-Algorithmus implementiert.

Sortieren vieler Daten

Merge Sort ist ein Algorithmus aus den Anfängen der Datenverarbeitung, der hervorragend geeignet ist, Daten, die auf einem Massenspeicher ausgelagert sind, zu sortieren. Anstatt nun, wie beim klassischen Merge Sort, die Daten rekursiv in immer kleinere Einzeldateien aufzuspalten, unter Umständen, bis nur noch ein Element pro Datei enthalten ist, werden diese von vornherein in viele vorsortierte Dateien kopiert. Dazu wird der vorhandene Arbeitsspeicher ausgenutzt, und die Daten werden mittels eines TreeSet sortiert.

Danach werden so lange mehrere Dateien im Reißverschlussverfahren zusammengefasst, bis nur noch eine einzige sortierte Datei übrig bleibt. Dieser Algorithmus ist deswegen so vorteilhaft, weil die Quelldateien dabei immer nur sequenziell gelesen werden müssen.

In der beschriebenen Bibliothek werden alle diese Schritte von der Klasse oc.io.ReferenceResolver zusammengefasst. Diese ist generisch aufgebaut und stellt keinerlei Ansprüche an die verwendeten Klassen in Bezug auf Interfaces oder Basisklassen, die diese zu implementieren haben. Die einzige Annahme, die getroffen wird, ist, dass ein Long als Schlüssel für die Beschreibung der Beziehung verwendet wird. Diese Abstraktion erfordert allerdings einen etwas höheren Aufwand bei der Verwendung von ReferenceResolvern. Es müssen zwei Hilfsklassen implementiert werden, die die Zugriffe auf die Daten für den Algorithmus ermöglichen (Listing 5).

 
public class WayNodeReferer implements RefererHandler<Way, Node> {
  /**
   * @param one
   *            the way that needs to be inspected
   * @return the id of the Way instance
   */
  @Override
  public long getId(final Way one) {
    return one.getId();
  }

  /**
   * @param one
   *            the way that needs to be inspected
   * @return a list of all references to Nodes that the way needs
   */
  @Override
  public List getRefs(final Way one) {
    final List refs = new ArrayList<>();
    for (final Node node : one.getNodes()) {
      refs.add(Long.valueOf(node.getId()));
    }
    return refs;
  }

  /**
   * @param one
   *            way that shall be configured 
   * @param manies
   *            gives the resolved Node instances to the Way
   */
  @Override
  public void setResolvedRefs(final Way one, final Map<Long, Node> manies) {
    for (final Node node : one.getNodes()) {
      final Node resolvedNode = 
                         manies.get(Long.valueOf(node.getId()));
      if (resolvedNode == null) {
        logger.warn("Node not resolved : {}", node.getId());
      } else {
        node.setLat(resolvedNode.getLat());
        node.setLon(resolvedNode.getLon());
      }
    }
  }
};

Der RefererHandler wird von ReferenceResolver benutzt, um die ID eines Wegs sowie dessen referenzierte Knoten zu erhalten. Nach getaner Arbeit werden damit außerdem die gefundenen Knoten in das Wegobjekt kopiert. Einfacher ist dagegen der Handler für den Knoten (Listing 6).

 

public class ReferedNode implements ReferedHandler {
  /**
   * @param many
   *            instance of node the id is needed from
   * @return the id of the node instance
   */
  @Override
  public long getId(final Node many) {
    return many.getId();
  }

  /**
   * 
   * @param many
   *            Node that shall be configured
   * @param id
   *            id that shall be set to the instance
   */
  @Override
  public void setId(final Node many, final long id) {
    many.setId(id);
  }
};

Er muss nur die ID eines Knotens abfragen bzw. setzen können, wenn während des Sortiervorgangs neue Knotenobjekte erzeugt werden müssen.

Relationen

Ähnlich wie bei den Wegen werden die Beziehungen der Relationen zu Knoten und Wegen aufgelöst. Nur bei den Beziehungen von Relationen zu anderen Relationen gibt es einen kleinen Unterschied. Hier werden in einer Rekursion jeweils die referenzierten Relationen herausgefiltert, bis nur noch Relationen ohne Referenzen auf andere Relationen übrig sind oder eine zirkuläre Referenzierung erkannt wird. Beim Auflösen der Rekursion werden dann die bereits vollständigen Relationen in die referenzierenden kopiert, bis am Ende alle Beziehungen aufgelöst sind.

Das Programm

Werden die Sources mit Maven übersetzt, erhält man ein fertiges JAR (oc.resolve.jar) im Basisverzeichnis des Projekts. Das JAR ist ausführbar und kann mit

java -jar oc.resolve.jar

gestartet werden. Es unterstützt folgende Parameter:

-o [Ausgabeordner]
-i [Eingabedatei]
-t [temporärer Ordner] (optional)
–in-osm (Wenn Eingabedatei im osm.gz-Format)
–in-o5m (Wenn Eingabedatei im o5m-Format)

Nach dem Programmlauf erhält man folgende Ergebnisdateien im Ausgabeordner:

nodes.dat enthält alle Knoten der Eingangsdatei
resways.dat enthält alle aufgelösten Wege
resfiltways.dat enthält nur Wege, die nicht Teil einer Relation sind
resrelation.dat enthält alle aufgelösten Relationen

Eingelesen werden können sie mithilfe des oben beschriebenen ExternalizableIterator (Listing 7).

ExternalizableIterator<Way> iter = new ExternalizableIterator<>(new File("resways.dat"), new Way.WayFactory());
while (iter.hasNext()){
  Way nextWay = iter.next();
  [ ... ]
}

Fazit

Auch wenn die hier vorgestellte Bibliothek zur Auflösung von Referenzen in OSM-Daten keine Wunder vollbringen kann, zeigt sie doch sehr schön, dass auch Verfahren aus den Anfängen der Computertechnik heute noch ihre Berechtigung haben. Immerhin schafft sie es, die komplette Planetdatei in weniger als 24 Stunden zu verarbeiten, und liegt damit ziemlich weit vorne.

Aufmacherbild: Street Map with GPS Icons. Navigation von Shutterstock / Urheberrecht: Vadim Georgiev

Verwandte Themen:

Geschrieben von
Oliver Schünemann
Oliver Schünemann
Dipl.-Ing. Oliver Schünemann (46) ist verheiratet und hat zwei Kinder. Zurzeit arbeitet er als Softwareentwickler und Architekt bei einem mittelständischen Ingenieurbüro in Hildesheim. In seiner Freizeit beteiligt er sich aktiv beim OpenStreetMap-Projekt.
Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: