[Routing] [OSM-talk] www.OpenRouteService.org now supports Bicycle Routing with OSM Data

[Alex Wilson]

For the boost astar search algo:

So you must
> 1. Pack the data in yourself esp. if you want to avoid cache misses /
> paging.


Yes: although presumably you have to do this anyway.

>
> 2. hook a callback for testing to see if a segment may be traversed
> and at what speed.

Effectively, yes.

>
> 3. How do you prevent a bad routing query on a large map from eating
> all the memory on your WinCE device causing a crash ?

There are a variety of callback hooks you can implement to allow you to
check on the algo's progress and make sure it's not eating all your memory.

>
> 4. If the query is impossible (split network), can you modify the
> algorithm to at least return some useful route to the user ?

This is an interesting question. but the brief answer is: I suspect it
wouldn't be easy in the routing algo. However I would have approached this
as a graph pre-processing step: find the disconnected sub-graphs and attempt
to joint them before getting on to routing.

>
>
> > Finally: why would you want a library that combined routing and
> rendering?
> > They're two separate tasks: what advantage is there to combining them?
>
> Well you want to use the same data for rendering and routing on an
> embedded device with little memory. For rendering you want to be able
> to find all nodes in a given region (rectangle) and for routing you
> want to be able to take one node of a segment and find all the other
> segments at that  node.
>
> So the two operations are independent except for performing different
> queries on the same data structures.


Good point. Although I think it could be quite easily implemented using two
different views onto the same datastructure.

I've been playing with the BGL for routing, and I think that you can use it
trivially as-is (including the graph datastructures) for routing on a
desktop. The code is concise and the implementation fast and robust. For an
embedded device you would almost certainly want to implement your own graph
datastructures (although I'm certain that you can use at least some of the
boost framework)  - but then that doesn't preclude using boost for the
algos. And there is a lot more good stuff in there than just astar. For
instance the strongly connected component algo will quickly find you all
disconnected sub-graphs - including taking into account the fact that some
ways are one-way only. So pre-processing to connect disjoint sections is
already half-done for you just by using an extra library function.

Anyway: I didn't want to give the impression that I think the BGL should be
used by everyone, or that it's the perfect solution: I just wanted to make
the point that it is fit for purpose,  it could be used, and it might well
add some value. Not all libraries are rubbish for this task...


>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20080708/d38bd84c/attachment.html>