Opened 11 years ago

Closed 7 years ago

Last modified 7 years ago

#46 closed enhancement/feature request (fixed)

It'd be nice to have several waypoints, not only a destination

Reported by: hafting Owned by: tryagain
Priority: major Milestone: want patch / contribution
Component: core Version:
Severity: Keywords:
Cc: http://wiki.navit-project.org/index.php/user:sanderd17, https://wiki.navit-project.org/index.php/user:rdorsch

Description

It is nice to have several waypoints, when you reach one, go on to the next. Hopefully not hard to add. Useful for vacation planning, enter the locations of all the hotels in advance.

In some cases it is also useful to have unordered waypoints. When you reach one, proceed to the nearest unvisited one. Or even better - have navit calculate the best order. (Yes, that in the NP-complete travelling salesman problem, but not hopeless for 4-5 points. :-)

Either case of unordered waypoints is useful when making several deliveries.

Attachments (4)

multipoint.diff (4.6 KB) - added by tegzed 8 years ago.
multi waypoint routing lead out to internal gui
patch4.txt (22.5 KB) - added by heiko wegeler 7 years ago.
fixes and changes
waypoints.diff (22.1 KB) - added by heiko wegeler 7 years ago.
patch from ticket 750 removed (home=/sdcard/navit)
waypoints.patch (9.0 KB) - added by pini 7 years ago.
Keep ongoing waypoint when restarting Navit

Download all attachments as: .zip

Change History (26)

comment:1 Changed 11 years ago by Jason Antman <jason@…>

This would be a major plus for me. Seems like it would be possible to implement by essentially just calculating multiple routes, and then summing up the time and distance.

comment:2 in reply to: ↑ description Changed 10 years ago by latouche@…

Replying to hafting:

It is nice to have several waypoints, when you reach one, go on to the next. Hopefully not hard to add. Useful for vacation planning, enter the locations of all the hotels in advance.

It could also be useful to avoid well known traffic jams, to take shortcuts or to avoid a road which is dangerous

comment:3 Changed 10 years ago by KaZeR

  • Milestone set to want patch / contribution

comment:4 Changed 8 years ago by tegzed

Hello All,

I have played a bit with multi waypoint routing. I found that the functionality is largely implemented in the source already, but it is not lead out to the gui. According to my tests the saving and loading of destination list is also not solved yet. I attach a patch here that leads out multi waypoint routing functionality to the internal gui. This only gives basic usage. After clicking somewhere on the map at "Actions -> <position> -> Add destination several destinations can be added. I did only very limited testing but it seems to work. To enable this menu item the patch should be applied and compiled and the html like section for gui internal should be changed in the following way: replace line:

<img cond='click_coord_geo' src='gui_map' onclick='position(click_coord_geo,_("Map Point"),8|16|32|64|256)'><script>write(click_coord_geo)</script></img>

with

<img cond='click_coord_geo' src='gui_map' onclick='position(click_coord_geo,_("Map Point"),8|16|32|64|256|1024)'><script>write(click_coord_geo)</script></img>

This patch is not intended to be the final sulution it only allows testing the functionality. The add destination gui entries should be created also in search dialogs vehicle position dialogs and perhaps several other places.

Changed 8 years ago by tegzed

multi waypoint routing lead out to internal gui

comment:5 Changed 8 years ago by sanderd17

  • Cc http://wiki.navit-project.org/index.php/user:sanderd17 added

would gpx backtracking be possible with this?

comment:6 Changed 8 years ago by rdorsch

  • Cc https://wiki.navit-project.org/index.php/user:rdorsch added

comment:7 Changed 7 years ago by donnatrackme

Thanks for this patch, tegzed.

Can't believe after all this time that it hasn't been incorporated into the trunk. (!) When might it be?

comment:8 Changed 7 years ago by blablabloblo bb

Is anyone working on a solution that will make it into the trunk? I would really like to see this in navit.

At least having a list of ordered destinations would be great.

comment:9 Changed 7 years ago by heiko wegeler

and save list of destinations to bookmark folder, load bookmarks from folder as route, delete bookmark folder, remove last waypoint from route for easier route planning.

I made a solution for my next bike season, works for me. Wait some days for patches. A toogle button for enable/disable waypoint routing is also needed (todo). Android test package (based on r4888) is here: http://heiko.ploinger.de/Navit-debug.apk

add this somewhere to the html for internal gui for remove last waypoint:

<img cond='navit.route.route_status&amp;52'src='gui_stop' onclick='route_remove_last_waypoint()'><text>Remove 
Waypoint</text></img>

comment:10 Changed 7 years ago by heiko wegeler

added waypoints.diff, based on r4923

workflow is:

  1. Enable Settings->Rules->"Plan with waypoints" to switch "Set destination" to add next waypoints.
  2. Add waypoints. If the last routing is not nice, use Route->"Drop last waypoint" to remove last waypoint.
  3. Add a new bookmark folder eg. "Route xy".
  4. Go into bookmark folder and press "Save waypoints". The bookmark labels are named as (street-systematic or type) + (label or osmwayid) + WP[waypoint number]
  5. To drive the route go into bookmark folder and press "Bookmarks as Waypoints".
  6. To cancel the next waypoint while driving use Route->"Drop next Waypoint".

Empty folders can also deleted. The last waypoint from the route goes into "Former Destinations" list, labeled with bookmark label. Android test package is updated.

Last edited 7 years ago by heiko wegeler (previous) (diff)

comment:11 Changed 7 years ago by heiko wegeler

some bugfixes: *former destination list works as it should. At first the route folder name is shown. After reaching a waypoint the name of the waypoint is shown in the former destination list as (street-systematic or type) + (label or WayID[osmwayid])

*after switching route only the route to 1st waypoint was shown. fixed with reloading route completly.

*add waypoint 10-20% faster and delete last waypoint without lags.

comment:12 Changed 7 years ago by tryagain

Hi!

Seems to work fine for me. Hope we will have this quite useful feature added soon.

I even tried adding waypoints_flag="1" attribute to <navit tag of navit.xml and got new semantics of set_destination to be default. That behavior seems to me so intuitive that I see no need to support the old one.

Unfortunately, code has to be worked on before commit.

1.Worst news are we have memleaks. I did not investigated it too deep neither used some automated tool. So list is incomplete:

1.1. In route_get_destination_description, after type=g_strdup_printf(..., type should be freed somewhere. But it's just reassigned at type=attr_to_text(...

1.2. In gui_internal_cmd_load_bookmarks_as_waypoints, prefix won't be freed if navit_get_attr(this->nav, attr_bookmarks, &mattr, NULL) will return false. I know it will most probably never happen. Also, an empty string like char *s=g_strdup(""); should be freed too, so your code

if (plen) { 
   g_free(prefix);
}

should be looking as

if (prefix)
   g_free(prefix);

or even just as g_free(prefix) because g_free checks for NULLs internally.

  1. Code like
if (strcmp(attr_to_name(attr.type), "street_name_systematic")==0)

is better written as

if (attr.type==attr_street_name_systematic)
  1. gui_internal_cmd2_route_remove_last_waypoint and gui_internal_cmd2_route_remove_next_waypoint are not depend on gui_internal module. So they are better to be placed in navit.c just like navit_cmd_set_destination to be reused by other modules when some alternative gui is used.

Good luck!

Last edited 7 years ago by tryagain (previous) (diff)

comment:13 Changed 7 years ago by tryagain

Hi!

Please use g_list_next to iterate in bookmarks_get_bookmark_count. Both g_list_length and g_list_nth_data are too cpu-hungry to use them to iterate through all list elements. You get quadric algorithm complexity if you go your way. For example, g_list_length() will be iterating through all elements on each for() loop condition evaluation, i.e. g_list_length() times.

And memleaks again:

  • In route_get_destination_description. What if an item will have both attr_label and attr_osm_wayid defined, and attr_osm_wayid will be returned by item_attr_get before attr_label? Right, label will be assigned with g_strdup_printf("WayID %s", attr_to_text(&attr, item->map, 1)) and then reassigned with g_strdup_printf("%s", attr_to_text(&attr, item->map, 1)) without freeing former value.
  • Code
    1117        if (strlen(label)>0) { 
    1118	           g_free(label); 
    1119	        } 
    

is very similar to example I gave you in previous post.

strcmp(type, label)==0 is going to crash if type or label is NULL. This probably may happen only if bookmark file is corrupt. But good practice is not to crash on any input data.

Again, in gui_internal_cmd_save_bookmarks_from_waypoints you're using plen to check if prefix should be freed on exit. What if data parameter is pointer to empty string ("")? Right, prefix will point to newly allocated one byte memory area, and it will never be freed.

label=g_strdup_printf("%s", attr_to_text(&attr, item->map, 1)) is leaking on pointer returned by attr_to_text(&attr, item->map, 1).

This again is only partial review. Please do your own review to find at least errors similar to described.

And I stay on moving route_remove_next_waypoint and route_remove_last_waypoint to navit.c.

Changed 7 years ago by heiko wegeler

fixes and changes

comment:14 Changed 7 years ago by heiko wegeler

Hello,

it seems my next timeout is comeing, her is the current state: everything fixed i hope, exept:

  1. "prefix/plen": not fixed because its copy/paste from gui_internal_cmd_bookmarks. prefix is foldername which cannot string.empty. there is nothing to fix.
  1. "label=g_strdup_printf("%s", attr_to_text(&attr, item->map, 1)) is leaking on pointer returned by attr_to_text(&attr, item->map, 1)": not fixed because its copy/paste from gui_internal_cmd_view_attributes. there is nothing to fix.
  1. "move route_remove_last/next_waypoint to navit.c": copied to navit.c, but not removed from gui_internal.c because navit.c calls cannot used within osm->route. But osm->route is the only route context and the waypoint remove buttons should stay there.

sorry, i'm not a C developer. If a C developer mean that there is something to fix then fix your code and i copy it back to my copy/paste patch. but there is nothing to fix.

for waypoint routing as default the "Plan with waypoints" menu point in osm->settings should removed or save settings fixed. But navit is labeled as car navigation and car drivers normally don't need waypoints, therefore i made it off as default. Waypoints are mostly used for sport navigation and they will find the "Plan with waypoints". Its only needed to plan a tour, not for load/drive a tour.

changes:

  1. for not empty folders the "save waypoints" is replaced with "replace waypoints"
  2. bugfix for trunk: set bike in maps and vehicle, set 1 destination to a cycleway near street, change vehicle to car -> bug

for bookmarks=waypoints as bubbles on map add this to mapset in xml:

<map type="textfile" enabled="yes" data="/data/data/org.navitproject.navit/home/bookmark.txt" />

and this to a map under <layer name="Internal">

<itemgra item_types="bookmark" order="5-">
     <icon src="cursor_still_32_32.png" />
</itemgra>

because i am waiting since last summer for a simple binary, others asking http://sourceforge.net/projects/navit/forums/forum/512959/topic/4792675 https://sourceforge.net/projects/navit/forums/forum/512960/topic/5122516
but no navit developer is willing to do and i dont know how long is this going here, a sometimes updated android package with cycling stuff is here:

http://heiko.ploinger.de/navi/index.html

cheers

comment:15 Changed 7 years ago by tryagain

  • Owner changed from somebody to tryagain
  • Status changed from new to assigned

Hi!

The patch looks much better now.

I'm going to fix the rest myself and commit it as soon as I have time (probably within a week).

I'd like to see any comments on usability of this feature as it is implemented in this patch.

comment:16 Changed 7 years ago by heiko wegeler

Hello,

because plen/prefix stuff, which was pasted from gui_internal_cmd_bookmarks and goes into a folder. Its not needed in gui_internal_cmd_replace_bookmarks_from_waypoints and gui_internal_cmd_load_bookmarks_from_waypoints (called from gui_internal_cmd_bookmarks) to go again in the folder. removed completely.

someone fixed attr_to_text: pasted back

updated waypoints.diff

cheers

Changed 7 years ago by heiko wegeler

patch from ticket 750 removed (home=/sdcard/navit)

comment:17 Changed 7 years ago by tryagain

  • Resolution set to fixed
  • Status changed from assigned to closed

I have committed patch4.txt with fixes applied and gui_internal_cmd_replace_bookmarks_from_waypoints and gui_internal_cmd_load_bookmarks_from_waypoints backported from waypoints.diff.

The only interface change is that I got rid of route_remove_*_waypoint commands of gui_internal object and used only ones from the navit object. So in navit_shipped.xml we have now onclick='navit.route_remove_last_waypoint()' and onclick='navit.route_remove_next_waypoint()'.

Please note, to have waypoints routing enabled by default you may set waypoints_flag attribute of navit object to 1. We have to document this on the wiki.

Applied in r5004

comment:18 Changed 7 years ago by tryagain

If you're updating your own layout to use this feature, please consider the following.

In r5004, there was no direct way to clean up the planned waypoints while "Plan with Waypoints" is active and some of the Waypoints are unreachable from the Position.

To fix that, condition to display buttons "Stop navigation" and "Drop [next|last] waypoint" is changed to navit.route.route_status & 1 since r5012.

comment:19 Changed 7 years ago by pini

Hi,

Here is a patch proposal (attachment 'waypoints.patch') to keep ongoing waypoints when restarting navit. Please review and comment :)

Thanks,

_g.

Last edited 7 years ago by pini (previous) (diff)

Changed 7 years ago by pini

Keep ongoing waypoint when restarting Navit

comment:20 Changed 7 years ago by sleske

@pini:

This bug has been closed. Please open a new ticket for your proposal/patch.

comment:21 Changed 7 years ago by pini

Oops! Sorry, I didn't notice the ticket status.

comment:22 Changed 7 years ago by pini

New ticket #1040 created. Thanks.

Note: See TracTickets for help on using tickets.