Map-Navigation Project, How is road data generally stored/represented?
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
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.