[Routing] comparison of navigation-apps

Nic Roets nroets at gmail.com
Fri Mar 20 15:27:30 GMT 2009

On Fri, Mar 20, 2009 at 3:30 PM, <marcus.wolschon at googlemail.com> wrote:
> "a user who simply looks for a navigation or routing- application to USE"

Note that a user does not need to know what algorithm the program uses.

> Can you give some more details about how you did it?

Give numbers to all your segments (gosmore uses "double half segments" but
the idea is the same)

Then you have an array of Dijstra nodes :
struct DijkstraNode {
  int segnumber;
  boot forwards; /* Are we traveling forwards or backwards ? */
  float distance;
  boot unprocessed;
  /* For A* you may have an additional variable for the heuristic */

Each (segnumber, forwards) pair may only occur once.
So for each Dijkstra iteration you look in the array for the dijkstraNode d
with the lowest distance with unproceesed equal to TRUE.
* If forwards is true, you find the OSM node n to which the segment is
pointing to. Otherwise n is the OSM node that the segment is coming from.
* Now you look at all the segments s connected to n. (Gosmore will current
not consider s=d.segnumber, so u-turns back into the same way are not
allowed) Can I travel from d.segnumber to s ? If yes, add
(segnumber=s,unprocessed=TRUE) to the dijstraNode array. If it's already in
the array and the new distance is shorter, update it.

> I found some code in libgosm.cpp but it's hard to understand without
> more comments. Can you handle "no_u_turn"?
> > Gosmore can search for any tag value, nearest matches first. So if I want
> > to
> > search for "1 Main Road, Lynnwood Park", I start by searching for
> Lynnwood
> > Park, then I search for Main Road. Then search for 1. I know it's not
> > perfect, but it's not useless either.
> Ah, that explains why I could not find it. Thank you.
> Shall we label it "limited" then?

Well, you already changed it, so you're not asking !

AFAIK the house number data in OSM is still quite limited. So saying 'Yes'
is very misleading to a newbie.

Will you update your table when new versions of gosmore is released ? I
doubt it. So your table will just continue to mislead newbies.

> ... I was to try out how far navit has advanced this weekend...

I can't see how a smart guy like you can think it's acceptable to just make
up facts.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20090320/fb7d9bbb/attachment.html>

More information about the Routing mailing list