On Fri, 20 Mar 2009 17:27:30 +0200, Nic Roets <[email protected]> wrote: >> 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.
Thanks a lot for the suggestion Nic! I was able to implement it and it seems to work fine. Other then your implementation I does allow u-turns (unless a no_u_turn -relation exists). As I already have a RoutingStep -class that is used to abstract between routing-engines and diving-instruction-plugins I could do away with the "bool forwards;" and segment-numbering. A RoutingStep contains a start-node, way and end-node. I do not mark them as "unprocessed" as I keep one sorted set of RoutingSteps to be processed and one map of the best step for each processed one. Announcement: http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=3&t=46 I'll update the Java Webstart -version of Traveling Salesman tonight in case anyone wants to play around with it. Marcus >> "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. I agree that many would not care and just skip that point. The ones who care would like to know and the others dont care. As most of them are free software I as a developer do care as it shows me where I can look for reference as I just did with your turn-restrictions. > AFAIK the house number data in OSM is still quite limited. So saying 'Yes' > is very misleading to a newbie. I don't think think so. It is an important feature to distinct between the capabilities of the different programs. That's what the table it about. > Will you update your table when new versions of gosmore is released ? I > doubt it. So your table will just continue to mislead newbies. If I notice such a change in http://wiki.openstreetmap.org/wiki/Gosmore yes, I will update it acordingly. > I can't see how a smart guy like you can think it's acceptable to just make > up facts. What factual errors remain in the table? Marcus _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
