RoadHog: Datenstrukturen

Diese Seite beschreibt die grundlegenden Datenstrukturen, die ich für die RoadHog-Software verwende. Ich habe ein paar Details ausgelassen, aber für eine Übersicht sollte es reichen.

Knoten und Kanten

Natürlich muß RoadHog eine Abbildung des Straßennetzes enthalten. Dieses Netz, wie jeder Graph, besteht aus Knoten und Kanten. Ich benutze die englischen Ausdrücke vertex und edge (denn node wird schon im XML Document Object Model verwendet).

Ein Vertex ist im Prinzip jeder Ort, an dem man seine Richtung ändern kann. (Der Einfachheit halber nehme ich an, daß man nicht mitten zwischen zwei Knoten umdrehen kann.) In einer Stadt wäre jede Straßenkreuzung ein Knoten, doch in Schottland ist es im Prinzip einfach jedes Dorf. Ein Knoten hat außerdem (und hier verlasse ich ein wenig die Standard-Graphentheorie) Anschlüsse (connectors), an denen eine Kante "angesteckt" werden kann. (Man muß sich das so ein bißchen wie einen Baukasten vorstellen.)

So sieht die Beschreibung für den Ort Poolewe in Wester Ross aus:

<vertex> <id>Poolewe</id> <connector> <id>Inverasdale</id> <direction>315</direction> </connector> <connector> <id>Aultbea</id> <direction>45</direction> </connector> <connector> <id>Gairloch</id> <direction>180</direction> </connector> </vertex>

Das gibt uns also drei "Steckplätze" für Kanten, und jeder hat die ungefähre Richtung (in Grad - 90=Ost, 180=Süd usw.) angegeben, so daß man später automatisch Aussagen wie "links abbiegen nach ..." erzeugen kann.

Als nächstes muß ich die Kanten definieren, die zwischen den Knoten verlaufen. In meinem Datenmodell beschreibt eine solche Kante einfach die Tatsache, daß es eine Straße zwischen den zwei Knoten gibt - egal, ob ich jetzt tatsächlich Fotos davon gemacht habe. Die Kante hat keine Richtung (und ich nehme an, daß jede Kante in beiden Richtungen befahrbar ist).

So sieht die Kante aus, die Poolewe mit Inverasdale verbindet:

<edge> <road>B8057</road> <length>4</length> <vertex-id> <id>Inverasdale</id> <connector-id>Poolewe</connector-id> </vertex-id> <vertex-id> <id>Poolewe</id> <connector-id>Inverasdale</connector-id> </vertex-id> <map-id>mm</map-id> <via>Naast (Inverasdale)</via> <via>Brae (Inverasdale)</via> <via>Boor (Poolewe)</via> <via type="Island">Boor Rocks</via> <via type="Loch">Loch Ewe</via> </edge>

Sie hat genau zwei Vertex-Verweise und keine Richtung - es ist nicht "von" Poolewe "nach" Inverasdale, sondern einfach "zwischen" den beiden. Alles andere ist nur Beschreibung: Der Name der Straße, ihre Länge, die Karte, auf der sie abgebildet ist, und ein paar Punkte, an denen sie vorbeiläuft. Diese "via"-Orte können später zum Suchen benutzt werden, und ersparen uns die Mühe, jedes kleine Dorf entlang der Straße zu einem vollwertigen "Vertex" aufzubauschen, der dann genau zwei Anschlüsse hätte.

Fahrten

Wenn ich eine Kante entlangfahre und Fotos mache, speichere ich die entstehenden Daten in einem Reise-Objekt (journey). Es kann beliebig viele Journeys auf einer Kante geben, aber normal sind zwei - eine in jeder Richtung.

Dies ist ein Auszug aus der Reise von Poolewe nach Inverasdale:

<journey> <from>Poolewe</from> <to>Inverasdale</to> <photo> <filename>/home/photos/2001-04-02/RIMG0222.JPG</filename> <time>986222670000</time> <waypoint> <latitude>57.76617765</latitude> <longitude>-5.604954958</longitude> <time>986222240000</time> <speed>25</speed> <heading>344</heading> </waypoint> </photo> ... (weitere <photo>...</photo> Elemente) ... <waypoint> <latitude>57.75508403</latitude> <longitude>-5.5969119</longitude> <time>986222144000</time> <speed>54</speed> <heading>2</heading> </waypoint> ... (weitere <waypoint>...</waypoint> Elemente) ... </journey>

Es gibt eine Anzahl von "photo"-Objekten, jedes mit einem Verweise auf eine Bilddatei auf meiner Festplatte. Jedes Foto hat außerdem ein "waypoint"-Objekt mit Koordinaten; dies ist ein synthetisches Objekt, entstanden aus einem gewichteten Mittel der zwei "echten" GPS-Punkte, die unmittelbar vor und unmittelbar nach dem Foto aufgezeichnet wurden. Wie man sehen kann, ist die Zeitangabe im Foto selbst anders als die im zugeordneten "waypoint". Erstere wird nämlich direkt aus dem JPEG-Header gelesen (wo die Kamera die Zeit einträgt), letztere enthält eine Korrektur, die ich manuell beim Erzeugen des Journey-Objekts vornehmen mußte, weil die Kamera-Uhr normalerweise nicht mit dem GPS synchron läuft. Hier ist die Korrektur (986222240000 - 986222144000) / 1000, oder 96 Sekunden.

Nach der Liste der "photo"-Objekte kommen noch die "waypoint"-Objekte so, wie sie vom GPS aufgezeichnet wurden. Sie werden eigentlich nicht mehr gebraucht, es sei denn, ich möchte später noch einmal die Zeitkorrektur verstellen; vorsichtshalber speichere ich sie mal mit.

Mehr über Knoten

Ich habe noch ein paar Details über Knoten verschwiegen, um es nicht zu kompliziert zu machen. Knoten können noch die folgenden Zusatzdaten haben:

<vertex> ... Standard-Kram wie vorher ... <detail language="en">You are at the post office and shop in Poolewe.</detail> <passthrough> <id>Aultbea</id><id>Gairloch</id> </passthrough> <weight>1</weight> <description language="en">A picturesque village in Wester Ross, situated on the banks of the River Ewe, ... </description> <illustration> <filename>/home/photos/poolewe/riverewe.jpg</filename> <width>400</width> <height>300</height> <text language="en">River Ewe at Poolewe</text> </illustration> </vertex>

Die "detail"-Information ist notwendig, um dem Web-Benutzer später sagen zu können, wo er sich gerade befindet. "description" und "illustration" sind optional; wenn diese Felder angegeben sind, wird dieser Knoten mit einer eigenen Ortsseite in die Ortsliste aufgenommen.

Das "passthrough"-Feld bestimmt, ob ein Benutzer, der in einen Knoten "hineinfährt", automatisch weitergeleitet wird. Falls ein "passthrough"-Feld existiert, das den Anschluß, auf dem der Benutzer hineingekommen ist, mit einem anderen verbindet, dann wird er dorthin weitergeschickt; ansonsten hält die Reise an, und er muß entscheiden, wo er hinwill.

Mit dem "weight"-Feld kann ich steuern, ob ein Knoten in einer Richtungsangabe auftaucht. Den Mechanismus genau zu beschreiben, würde etwas zu weit führen, aber wenn Poolewe hier ein Gewicht von 0 zugeordnet würde, dann würde jemand, der von Gairloch aus nordwärts fährt, nicht gesagt bekommen, daß er nach Poolewe fährt, sondern stattdessen zum nächsten Knoten mit einem höheren Gewicht.

Alternativen

Es gibt noch zwei Spezialfälle, die ich nur kurz erwähnen möchte: Alternative Kanten und alternative Reisen. Eine alternative Kante liegt vor, wenn zwei Kanten dieselben zwei Knoten verbinden. Man stelle sich eine vielbefahrene Straße durch einen Ort vor; nun wird eine Umgehungsstraße gebaut. Dadurch entstehen zwei Knoten zu jeder Seite des Ortes, und man hat an jedem Knoten zwei Möglichkeiten, zum jeweils anderen Knoten zu kommen. Das löse ich durch ein "alternative"-Tag bei den "edge"- und "journey"-Objekten.

Alternative Reisen gibt es dann, wenn ich dieselbe Kante in der gleichen Richtung mehrmals befahre - einmal im Winter, einmal im Sommer, einmal bei Regen, einmal bei Nacht (oder so). In diesem Fall werden die "journey"-Objekte mit einem "detail"-Tag versehen (um die Randbedingungen der Reise zu beschreiben) und erhalten außerdem eine Priorität ("priority"), so daß der Benutzer im automatischen Betrieb nur die Reise mit der höchsten Priorität angezeigt bekommt.

Vernünftiges XML

Die XML-Strukturen, die ich benutze, sind teilweise recht chaotisch. Das kommt daher, daß das ganze halt "gewachsen" ist, ohne daß ich ihm von vornherein eine feste Struktur gegeben habe. Irgendwann, wenn ich hieran weiterarbeite, mache ich das mal alles richtig, mit mehr Attributen statt Tags, so daß ein bißchen Ordnung hineinkommt - ein <id>-Tag zu haben, ist wirklich sehr unelegant.

Zurück zum Index

[deutsch] [english] [about] [contact]

Frederik Ramm, 2001-05-24