Map-Navigation Project, How is road data generally stored/represented?

Question

Navigation systems like the Garmin and TomTom have always fascinated me. I've wanted to implement small map/navigation applications to try out various pathing algorithms and expand on my knowledge of them.

This is a two part question:

1.) How is Map data stored? - When you have a network of roads, how is this data generally stored? What parts of the data are retained inorder to reproduce a map later? Is each road stored as a series of points where it changes direction? What kind of file formats is this data stored in? Are there publically available libraries for easily parsing these files? Does anyone have specifics on how map/road data is stored/represented it would be very helpful.

2.) Navigation/Pathing - When doing basic pathing on this map data (a la Garmin) is my assumption correct that it is converted to a directed graph? Is each road intersection a vertex with the edge weights the distance between vertexes? This is what I was thinking about doing so I could try some basic well known pathing algorithms and see what I get.

I've seen this publically available map data on the US but I'm not sure how it is represented and if it is detailed enough for me to be able to build my directed graph out of it.

If anyone has any information I would appreciate it. The more detailed knowledge you have the better.

Answer 1

I don't know specifics about navigation system units, but in the standard GIS world, map data is stored basically as a collection of polygons, lines and points, each described by its coordinates (and the projection used and some other parameters). For instance, one of the most common formats, shapefiles, is described here, and the database based format standard is here.

I've successfully used this storage model for roads display and route calculation, using PostgreSQL, PostGIS and PGRouting. Calculations are done using the usual graph algorithms and the data stored in the common format is stored also as a graph to allow for their application. I can't extrapolate that experience to an embedded device as they likely do it very differently given their limited computing capacity. They very probably precalculate lots of stuff.

For a somewhat different approach to storage, check OpenStreetMap

Answer 2

For improved drawing speed at the cost of more storage and limited resolution, many applications will use a georeferenced raster format such as GeoTiff.

Answer 3

The exact way it's stored depends on the format; there are heaps of different GIS formats. GDAL is an excellent free library for reading (almost) all of them.

Typically roads will be stored in the file as a "lines layer", that is a set of polylines with attached metadata. So each road will have a series of vertices, and depending on the quality of your data it will hopefully have information such as whether they're one-way or not, speed estimates and some sort of connection id.

Yes, they're normally converted to a directed graph for solving. Edge weights may be distance or, more usefully, the time taken to travel that edge.

Solving quickly is a tradeoff between precomputation and storage space (an embedded device may necessitate a different choice here to a PC). There are some very interesting algorithms out there for doing that.

Answer 4

I have been working on the navigator project for a while now as part of my final year project. @ Peter, i am a bit confused when you say that "they are normally converted to a directed graph for solving" Could you explain further. I was working on the projects with ArcGIS 9.2. My idea was to generate the co-ordinates of the road vertices and export all relevant data to a database. It doesn't seem to be working. Can anyone help with ideas? It would o a long way.

Answer 5

Mohammed: Okay, I didn't go into much detail there because the original question seemed pretty comfortable on that aspect. If you aren't familiar with graph theory, it's probably a good idea to do a bit of reading on it now - Wikipedia is fine for an introduction.

What typically happens is that in the GIS data the roads are stored as polylines with attached metadata. That's fine for displaying them onscreen etc, but to be able to navigate them you need to know which ones are connected to one another. So in the metadata there's normally a node id for each end of the road, so you can say "this is road segment 457, it goes from node 332 to node 667". So when you read in the GIS data you build up a representation of it as a set of nodes connected by arcs (ie. a graph).

If that metadata's not available you could infer it from which roads have the same start/end coordinates (this is the case with some not-so-wonderful GIS data). The "directed" bit just means that roads have direction - some of them can be travelled along in either direction, but others are only one-way.

The typical algorithm for finding a path through a digraph is Dijkstra's algorithm; various derivatives are used in practice. Basically that involves moving from node to node along the arcs of the graph, so you need the appropriate data structures to support that.

Hope that helps...

Answer 6

The previous responses all refer to GIS sytems. This is not how PNDs (Portable Navigation Devices) work. They're far too simple to run desktop/workstattion level GIS software.

Instead, PNDs store information pretty much as Simucal presumed. Roads are broken down into segments. This keeps the model a lot simpler. Within a segment, attributes like maximum speed don't change.

For planning purposes, road segments act as the edges in a graph. For each nodes, incoming and outgoing nodes are both stored. Planning is then done using a modified A* algorithm. Edge weights are typically not distances, but estimated travel time (or in TomToms case, actual, measured time).

Road networks are typically hiearchical, though, and normal A* is a slow starter. When travelling from one town to another, A* will spend excessive amounts of time crawling through the start town. However, we humans know it's best to use highways when travelling longer distances. That's what they're built for. PNDs likewise prefer highways. And as highways are a lot rarer, this saves a lot of memory.

Another optimization is forward and backward search; you plan from both sides towards some middle point. The big advantage of this is that if you take a wrong turn, you can search again from a new start point. The backwards search tree is unchanged as your destination didn't move.

Answer 7

If you want some code to look at to get some idea about how routing applications work, try having a look at some of the routing applications linked from the openstreetmap.org wiki. Navit and Gosmore are both open source and fairly easy to set up in particular.

Nic Roets, the developer of the Gosmore application wrote an interesting post about his choices for representing the road-vector data that may be of interest to you as well.

If you want to have a look at Gosmore in action, it is the backend of the yournavigation.org routing website based on openstreetmap data.