RoadHog: Data Structures

This document describes the basic data structure used by the RoadHog software. It does not contain every nook and cranny but it should provide you with the grand picture.

Nodes and Edges

Firstly, RoadHog has to contain a model of the real road network. This network, as any graph, consists of vertices and edges. (I decided to use the term vertex in favour of node to avoid confusion with the XML Document Object Model term node).

A vertex in my model is any place where you can change the direction of travel. For simplicity, I assume that you can "turn around" only at vertices and not in between. In a city grid, each intersection would be a vertex, and in rural Scotland most villages are vertices. A vertex (and this is where I am leaving the well-trodden path of standard graphs) also has connectors, i.e. places where an edge can connect. Think of it like a construction set for children; a vertex is a little object to which you can attach a well-defined number of other objects into sockets.

This is how I describe the vertex for the village of Poolewe in Wester Ross:

<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>

This gives us three "sockets" for this vertex, with their approximate directions (90=East, 180=South and so on) to be used for automatic generation of direction information, like "you can turn left/right/...".

Next I'll have to define the edges that run between vertices. In my data model, an edge describes the basic fact that a road connects two vertices; it does not mean that I actually have any photos for it, and it doesn't have a direction either. (This assumes that any edge can be traveled in both directions.)

Here's the edge connecting Poolewe and Inverasdale:

<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>

It has exactly two vertex references, and does not assign them a direction (it is not "from" Poolewe "to" Inverasdale but just "between" the two). The rest ist just description - the name of the road, its length, the map on which it resides (more about maps later!) and some points along the way. These "via" descriptions can be used for searching later on, and thay save us the hassle of making every little hamlet along the way into a full-blown vertex with only two connectors.

Journeys

When I travel along an edge and take photos, the resulting data is stored in a journey. There can be any number of journeys on a given edge, but normally there should be two - one in each direction.

Here's an excerpt of the journey from Poolewe to 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>

	  ... (more <photo>...</photo> elements) ...

  <waypoint>
    <latitude>57.75508403</latitude>
    <longitude>-5.5969119</longitude>
    <time>986222144000</time>
    <speed>54</speed>
    <heading>2</heading>
  </waypoint>
	  
	  ... (more <waypoint>...</waypoint> elements) ...

</journey>

There's a number of "photo" objects, each pointing to an image file on my hard disk. Each photo has its own "waypoint" object which is synthesized - it is a weighted average of the two real waypoints that surround this photo in time. As you can see, the timestamp in the photo's waypoint is different from the photo's own timestamp. The photo's own timestamp is read directly from the JPEG file header where it is stored by the camera, but during the creation of the journey I have to make manual adjustments because the camera and the GPS are usually not synchronized. In this example, the adjustment is (986222240000 - 986222144000) / 1000, or 96 seconds.

After the list of "photo" objects, the real waypoints (or, more precisely, the track data) from the GPS is included. This it really just a safety measure that will allow me to change the time adjustment later on even if I have thrown away the original GPS track file.

Vertices revisited

There are a few things about vertices that I haven't told you right away in order to keep things simple. Vertices can also have extra information, like this:

<vertex>
   ... standard stuff as before ...

  <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>

The "detail" info is required for the RoadHog application to tell the user where he is. The "description" and "illustration" are used for generating the place overview; if a vertex doesn't have these, it will not show up there, and no place index page will be generated by the compiler.

The "passthrough" field controls the automatic onward travel; if the user comes into this vertex from one of the two connectors mentioned in the "passthrough", he will automatically continue on a journey that uses the other connector. If a vertex does not have a "passthrough" field, the user will be forced to stop and make a decision where to go.

The "weight" determines whether this vertex will show up as directional information. The mechanism is a bit complex and not perfect but if Poolewe was given a weight of 0, then somebody travelling north from Gairloch would not be told that he is travelling towards Poolewe, but instead towards the next vertex en route that has a greater weight.

Alternatives

There are two special cases I will just mention briefly: Alternative edges and alternative journeys. An alternative edge is an edge connecting two vertices which are already connected by another edge. Think of a fast road that runs through a village, and then someone builds a bypass. Now there will be a "vertex" to each side of the village, and when you reach the first one, you will have a choice of two edges - one via the village, the other being the bypass - to reach the second vertex. This is dealt with by qualifying edges and journeys with an "alternative" tag.

Alternative journeys are two or more journeys on the same edge in the same direction, say, one in rainy weather, one in sunshine and one at night. This is handled by adding a "detail" and a "priority" tag to the journey description; the user will normally only see the journey with the highest priority but in some situations he will be able to choose the other ones as well.

Decent XML

The XML structures I am using are quite a mess in parts. That's because the whole thing was cobbled together or, as people tend to say, it "grew organically", i.e. without having a well laid-out structure from the beginning. At some time in the future, if I contine to work on this, I'll sort the XML out and use more attributes instead of tags to make it less clumsy. Having an <id> tag is really not the way to go.

Back to the index


  Frederik Ramm, 2001-05-24