[Roadster] Anyone working on routing / directions?

[Ian McIntosh]

To my knowledge, no one is working on routing.  All yours, if you want
it.

FYI, I am working with Jeremy Cole now to redesign the map data storage
(to make it faster & smaller on disk), and this will obviously affect
the routing code.  It might make sense for you to join in that dialog.
If you want to be involved, send me your IM details.

-Ian

El mar, 23-08-2005 a las 14:44 -0400, Noel Flicken escribió:
> Has anyone started on implementing the driving directions component of
> Roadster?  If so, i'd like to help.  If not, i'd like to start the
> implementation.
> 
> Before finding Roadster, i investigated the current state of driving
> directions in the open source community.  Currently, i have found two
> other open source mapping programs that already implement driving
> directions generation.   The directions produced aren't very good, 
> probably at least partially due to insuffient data available (such as
> one-way streets, road speeds, exit numbers, etc). Still, we may be
> able to learn from their implementations to produce a decent set of
> directions.
> 
> RoadNav - C++
> http://roadnav.sourceforge.net/
> Uses Dijkstra's algorithm [1] to find the shortest path.  This
> algorithm works, but is inefficient for this domain--the algorithm
> will search outward in a radius away from the starting point, visiting
> nodes upto 2X distance from the end location, where X is the distance
> from the start node to end node.
> 
> GMap - C#
> http://gmap.sourceforge.net/
> Uses a naive A-star algorithm [2].  This algorithm is well-suited for
> the domain, but GMap's implementation has no estimated cost heuristic
> function, so it is effectively the same algorithm as Dijkstra's and
> will perform similarly.
> 
> 
> Suggestions for Roadster's implemantion:
> The A-star algorithm is a simple and powerful algorithm for shortest
> path finding.  With the right heuristic function (see [3]), it can
> perform amazingly well.  Look at the number of node searched in [4].
> 
> I'd be willing to start implementing an A-star algorithm for Roadster
> (as soon as i can get the thing to compile (-; ).  Later, we can tweak
> the heuristic and distance calculation functions to allow for the
> generation of directions based on factors other than time required.
> 
> Cheers,
>   Noel
> 
> Footnotes:
> [1] http://www.nist.gov/dads/HTML/dijkstraalgo.html
> [2] http://en.wikipedia.org/wiki/A-star_search_algorithm
> [3] http://citeseer.ist.psu.edu/goldberg04computing.html
> [4] http://citeseer.ist.psu.edu/cachedpage/679638/3
> _______________________________________________
> roadster mailing list
> roadster at cairographics.org
> http://lists.freedesktop.org/mailman/listinfo/roadster
>