clever stuff.

Electrickery.

On a serious note, I don't know, but I suspect it involves nothing cleverer than massive number-crunching and a bit of stylish presentation.

Places and junctions are points held as co-ordinated, roads are lines connecting point (with data for each line saying things like one-way, A road, Motorway etc) then it's brute force to find a connection from A to B (via C, or avoiding D) and then optimise the start and end points.

It's very hit and miss compared to the much more methodical and consistent approach by the professionals though, and as I've said, even their own project leaders have said they're an awfully long way from competing with commercial systems. There's a reason there is only a small number of road database, it's basically bloody hard to make!

Routing metrics? Lane numbers? Traffic directions? Speed limits? Roundabouts? Junction priorities and so on? And that's just the obvious stuff ;-)

I've not said it can't be done, but it's so far away from being close to current commercial offerings that it's not really worth mentioning it in the same context. It's got possible uses, I'd like to see a sat-nav system that can take me green-laning for example, but the technology's not much use without proper data.

They haven't the power in the boxes or the time to do "massive" number crunching though, so I think there is something really clever going on.... I'd just like to understand what,

Steve

not yet.

yes

no

yes

no

I didn't say OSM could do it now; tell the Unix manufacturers ten years ago that some hobbyist was going to re-write a better operating system and they'd all have pissed themselves laughing. OSM will take time, it might never succeed, but it *is* feasible to make a better open mapping system.

Lines need lengths too, unless they work it out, which I don't see how they'd have time. Roads also show bends, and not straight lines, so do they store the whole europe map as a table of nodes, or is the map you see on screen not an the same as the things internal "visualisation"

Steve

If you know the co-ordinates of the points which the lines connect, you can work out the length of the line easily.

Dunno if commercial satnavs store spline curves, or just sufficient points so that the short segments of straight lines approximate the bends, OSM does the latter.

Andy Burns wrote: .

Well yes, but you need two squared terms, an addition and then a square root, unless you work in distance squared units - and that for all nodes in your test path. Seems a bit intense.

Steve

Well, here's an example, each system would be a variation on this basic technique, unless it's all changed dramatically in the last few years!

Each junction has a link to the next junction both ways, and a set of "costs" associated with it, including the distance and the likely speeds that might be possible on that stretch of road. What then happens is a variety of algorithms can be used to calculate the quickest path from one point to the next, a basic one being a "travelling wavefront" algorith, in which each map node around the destination is tagged with the relevant total of costs from that node to the destination then repeat this spreading out over the whole map like a ripple in a pond spreading outwards, then when the source node is reached, you just have to follow the smallest numbers at each step and you get the most efficient path. That's a very simple algorithm though for example only, and isn't practical for large data sets but that's the kind of principle they work on, with lots of more clever stuff being used to reduce the amount of tagging that needs doing.

I did have some software that did use the travelling wavefront approach, ViaMichelin early versions I think, when you changed destination it would chew over the tagging for about 2 minutes and eat lots of RAM, but once it was done, it could find the most efficient route to that destination instantly from anywhere on the map, great as long as you know exactly where you're going and don't change it ;-)

Note that the actual geometric data and the costing data aren't the same thing, which is why the openstreetmap stuff using GPS tracks has a major task on its hands, as the data used to draw the maps isn't particularly useful for calculating the routes, certainly very inefficient and not detailed enough. It's also why you get the situation where a satnav can draw a junction perfectly but for some odd reason won't route you through it, the geometric data and costing data don't match up at that point, there being an error in one but not the other.

Look up the "travelling salesman problem" for some info on routing calculations. The wikipedia link gets hairy very quickly, that's because it's quite a complicated thing, efficient routing algorithms are far more complicated than most people realise. It's one of the most studied problems in mathematics.

Routing calculations are a good illustration of the difference between digital and analogue computing, digital computers find routing calculations hugely complex, but an analogue computer for routing calculations consists of a set of beads connected by bits of string connecting each bead to its neighbours, the length of the string corresponds to the cost to get from one node to the next. To find the shortest path between any two nodes, pick up the analogue computer by the two nodes and pull them apart, and the optimal route is the one that goes tight ;-) Mind you, I don't fancy an analogue satnav for the whole of Britain, it'd fill Dorset!

Routing metrics are more important for sat nav than the geometric data, and the geometric data is all you get from GPS traces.

Possibly, but it's the size and quality of the dataset that's the issue, just look at the quality of the documentation for linux and then wonder ;-)

He's a clever chap is oor steve! A pretty good stab that. I waffle on in another post about it in a bit more detail, but essentially the map data that you download to it contains the data to draw the maps, and an associated "cost" map that is used to do the routing.

I love this newsgroup.

But with sufficient GPS plot points and throwing some computation horepower at it centrally, can't the routing data be "distilled out"? then this data is what the individual satnav units need to perform their routing.

Well, the Landie owners seem friendler than the bikers!

In theory it's possible, but you need good GPS data for each stretch of road in both directions at a good set of average speeds (remember you've got people on motorbikes, cars, sports cars, pinzgauers, lorries etc sending in these traces), and each junction needs to be travelled in all combinations a sufficient number of times to make it reliable, not perfect, just reliable, as you're having to bash data out of a dataset that's just not suited for the job.

Plus of course you've got the problem of a road being narrower than a satnav is accurate, the only reason a commercial satnav shows you're on the road is because it locks you to the road even if your satnav shows you as being 20ft off to the right. A *very* early satnav I had plotted the road position and the GPS position, showing this locking in action, it was quite pronounced. You've probably seen occasions when two roads are close together and the satnav thinks you've jumped from one to the other, this is down to the inaccuracy of the satnav, something that openstreetmap will have to tackle somehow but the commercial users don't as they use special spiffy satnavs and sensors on the vans. Looking at a junction as a set of lines drawn by GPS plots by different users in different vehicles with different satnavs must look like a fight at a spaghetti factory, trying to drag lane data out of that isn't going to work so it'll need user input.

Ooh don't get me started on bikers ;-)

You can ohl a set of road data from Ordnance Survey. It's made up of a series of line-segments with coordinates of the end-points. I'm not sure whether the AA have something similar now.

They do, don't they. A bit more polite, as well - though to be fair it's only lately the bikers have been troublesome. They always seemed to be fairly amiable, if a little free with 'language' in the past.

Hey - there's nothing wrong with (proper) bikers. I don't mean kids 'riding' around on toy scootery-type things, or mini-moto chamines. I've never been a Landi owner, but used to drive one for jbex purposes. It was ok, but my Bonneville was much more fun to play with.