> I have a 1 GB flash drive in my pocket. It cost me £2. How much space do 
> you think they have to play with in a satnav device?

My SatNav comes on a DVD, so max 9GB (for all roads in western Europe). 
IIRC TomTom etc the map data comes on a memory card, perhaps 1-4GB depending 
on which map data set you get?

Post a reply to this message

> Depends on your definition of "optimal". (E.g., total distance, verses 
> estimated travel time, any tolls that have to be paid for certain routes, 
> traffic volume, etc.)

On most systems I think you get to choose whether you want the shortest or 
fastest route, the option to enable/disable motorways, tolls, ferries, 
tunnels etc.  Some systems even self-adjust the road weightings based on 
your driving style.  eg if you always drive at 220 km/hr on the autobahns it 
will take this into account when calculating the routing.

The other thing that is cool, is that when it tells you to turn right in 1 
km, it knows exactly which place names will be written on the roadsign, so 
you can easy double-check that you are taking the correct turning.

Post a reply to this message

scott wrote:
>> I have a 1 GB flash drive in my pocket. It cost me £2. How much space 
>> do you think they have to play with in a satnav device?
> 
> My SatNav comes on a DVD, so max 9GB (for all roads in western Europe). 
> IIRC TomTom etc the map data comes on a memory card, perhaps 1-4GB 
> depending on which map data set you get?

Indeed. So it can't be *that* hard to fit all the map into the space; 
it's pretty cavernous. ;-)

Post a reply to this message

Invisible wrote:
> I have a 1 GB flash drive in my pocket. It cost me £2. How much sp
ace do 
> you think they have to play with in a satnav device?

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 et
c, 
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 a
re 
exit-only, drawing the picture and telling me to keep to one side or the 
other.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Darren New wrote:

> 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. ;-)

Actually the video data for displaying the map and the topological data 
for route planning are probably seperate. I would guess.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> > This approach often may *not* give you the optimal route. However, given that it
> > will only very rarely be significantly worse than the optimal one, it is
> > definitely good enough.
>
> Depends on your definition of "optimal". (E.g., total distance, verses
> estimated travel time, any tolls that have to be paid for certain
> routes, traffic volume, etc.)

Well, it actually depends on *your* definition of "optimal": You as the user
assign a certain abstract "cost" to any of these parameters (typically by
choosing from a limited set of predefined factors), e.g.: A km of distance = 7
points, a minute estimated travel time = 10 points, a dollar of toll = 30
points, 40 miles of bad road = 80 points, ...

These abstract "cost" factors are then used to assign a cost to each road
section. The algorithm will then try to come up with a "cheap" route according
to these factors.

So from this perspective, the "optimum" is always well-defined: Lowest abstract
"cost". But even to these standards, the algorithm will only very seldom pick
the optimal route - because it would by any means not be efficient to do so.
After all, it doesn't make much sense to have your navigator spend 3 days
finding the optimal route, if within 30 seconds it can come up with one that is
at most 5 minutes longer :P

Post a reply to this message

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

clipka wrote:
> Invisible <voi### [at] devnull> wrote:
>>> This approach often may *not* give you the optimal route. However, given that it
>>> will only very rarely be significantly worse than the optimal one, it is
>>> definitely good enough.
>> Depends on your definition of "optimal". (E.g., total distance, verses
>> estimated travel time, any tolls that have to be paid for certain
>> routes, traffic volume, etc.)
> 
> Well, it actually depends on *your* definition of "optimal": You as the user
> assign a certain abstract "cost" to any of these parameters.

That's kind of my point, yes. :-)

> So from this perspective, the "optimum" is always well-defined: Lowest abstract
> "cost". But even to these standards, the algorithm will only very seldom pick
> the optimal route - because it would by any means not be efficient to do so.
> After all, it doesn't make much sense to have your navigator spend 3 days
> finding the optimal route, if within 30 seconds it can come up with one that is
> at most 5 minutes longer :P

Indeed. And if I make a wrong turn somewhere, it would be far more 
"optimal" for the device to quickly find a new route before I become 
*hopelessly* lost in a one-way system or something.

I'm looking at you, NAVMAN! >:-[

Post a reply to this message