> > I wasn't talking about the size. I was talking about the format.  As in,
> > how do you represent the paths of the road, the locations of services,
> > etc etc, in such a way that the machine can tell you "make the second
> > left in X miles".  My machine even tells me if I'm on a 5-lane road and
> > two lanes are exit-only, drawing the picture and telling me to keep to
> > one side or the other.
>
> I would imagine it's some kind of space partitioning method, similar to
> how a game engine figures out with world polygons are "near to" where
> you're currently standing. ;-)

Just a wild guess:

- For route finding, a (multiply) weighted, directed graph representing the
roads and junctions (pick your favorite data structure serving this purpose;
make sure it's space efficient, so probably no 2d array adjacency matrix), with
the weights representing the associated time, distance and other "costs"

- For navigation and display, some type of spline curve attached to each edge of
the graph, representing the road in real world

- For precise directions at junctions, additional data attached to each node
detailing the precise junction geometry, lane designation etc.

- For address finding, additional data attached to each edge indicating the
first and last house number, as well as lookup tables linking city names to
streets, and streets to street sections (= graph edges)

- For places of interest, a list of places with their respective co-ordinates
and reference to the graph edge they are adjacent to, with a spatial
sub-division tree for efficient look-up of nearby POIs.

That should get you started for typical applications.

Post a reply to this message