[OSM-talk] 'Distance to feature' maps?

[Gora Mohanty]

On Wed, 15 Jul 2009 13:30:44 -0400 (EDT)
simon at mungewell.org wrote:

> >> only needs an dijkstra algorithm and some more lines of code.
> >
> > sounds so simple... ;-)
> >
> > I had a look at the wikipedia page
> > (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and that
> > would look to make sense.

Actually, an implementation of the Dijkstra algorithm is not
difficult at all. When we were trying to do this with Python
and Django, we came across a couple of sample implementations.
Better yet, there is the Boost graph library which already
implements the Dijkstra shortest path algorithm. The library
is in C++, but there are various bindings to it.

To push our own work, one can take a look at an implementation 
at http://citybyroad.com/ (Log in with user/password testuser/
gpstrack). This actually was a more ambitious attempt to get
shortest paths based on actual travel time from GPS traces.
However, ignore that for the moment, and also ignore the half-
completed state of the application. Leave all the drop-down
boxes as Unspecified, enter a from/to address via the auto-
complete boxes (try "Raja Puri" and "Srijan Technologies",
allowing the auto-complete to take over after typing a few
letters), and click on the blue "FIND ROUTE" button. The result
shown on the map is from the Dijkstra shortest-path algorithm,
based on distance. The distance is calculated by integrating along
known routes, which is a fairly tedious, manual process, but OSM
routes should already have that information. For someone familiar
with Delhi, the application will be unable to find some routes, as
the database is not completely populated.

> As you may have noticed I've actually had a relatively amount of
> success with this, but my brain is off on the 'multiple targets'
> question.
> 
> Is it valid to repeat the dijkstra algorithm with multiple
> 'target' nodes, so you could find the shortest path to (say) any
> playground? Target nodes could auto-magically be extracted from
> OSM file based on tags.
[...]
> Does this sound correct?

Your description covers the gist of the issue. The Dijkstra
algorithm actually visits every node in the network, and thus
running it once between two points should find all shortest
paths. In practice, it seems that the Boost implementation prunes
unlikely paths, so that one has to start with two extreme points,
and maybe rerun the algorithm a couple more times with other
extreme points in order to get full coverage.

Came into this conversation a little late, but if you had a
definite purpose in mind, we would be glad to share the code,
and maybe even put in some work on a reimplementation. What
language are you planning on using?

Regards,
Gora