Placement of intermediate points into an existing route

[Petra aus Aachen]

Hello @all,

I love to design my motor bike tours with kurviger. The typical method is: to define start and end point, and then iterate between automatic route generation and forcing the route to defined sections I'd like to ride by introducing additional intermediate points, by shoving them to respective positions.In the end of the planning process I am used to put supporting intermediate route points to force the actual route on the navaid (Tomtom Rider V4) that puts it's own "intelligence" to work during re-routing.

I'm aware of the possibility of automatic intermediate point insertion, but that proved suboptimal in many cases still, so I prefer to do that manually.

So far, so good.

The problem in manual intermediate point insertion is that the new point, although immediately derived from an existing shown route, is placed only near the track, not by default on the existing track / visited road. Could that be changed?

Of course it does make sense to take the "exact" mouse cursor map position as new route point if I happen to place the click just "somewhere" on the map. But if I click obviously on to the shown route line I'd expect the placement at a respective on-route position nearest to the mouse pointer.

This behaviour is especially important if I am in "overview" planning mode, in rather strong zoomed-out modes: Even though on that scale the inserted route point seems to lie on the road visually, a strong zoom-in shows that it frequently happens to effectively lie somewhere "in the fields" in the more harmless cases, or on a parallel road a hundred meters away from the intended route course. In the 2nd case this leads to silly departures from the intended course that is really a show-stopper for a tour with some followers.  :-)

So my suggestion is: to put a new intermediate point distinctly to a position on an existing route if the mouse click visually went on to a shown route course. I guess everything should be available to the algorithm to determine / derive the respective information, or isn't it?

Cheers,

Petra

[Robin]

Hi Petra,

interesting proposal. In this case it would be indeed better to place the waypoint exactly on the route.

What issues do you usually see with automatic point generation? We have added quite some nice features there.

Let me see if it's easily possible to further improve this.

Cheers,

Robin

[Emux]

Hi Petra,

Thanks for the kind words!

> So my suggestion is: to put a new intermediate point distinctly to a position on an existing route if the mouse click visually went on to a shown route course. I guess everything should be available to the algorithm to determine / derive the respective information, or isn't it?

When placing waypoints on map, cannot know beforehand their exact snapped coordinates on near streets, unless perform actual route calculations. :)

There is the "Place waypoints on street" button in Advanced Options which works after route is calculated, in order to snap the waypoints on road.

Does it help?

BTW some users find useful to have their via points placed on the requested places, e.g. on top of a parking at the side of the street, not in the middle of the street.

--
Emux

[Robin]

Hi Emux,

> When placing waypoints on map, cannot know beforehand their exact snapped coordinates on near streets, unless perform actual route calculations. :)

I think this is about clicking on the route. On the website it generates a waypoint on the route at this position. So it could improve the workflow to place it exactly on the route and not on the clicked coordinates.

> There is the "Place waypoints on street" button in Advanced Options which works after route is calculated, in order to snap the waypoints on road.

ah good point, Petra you can have a look at the option to place waypoints exactly on a road (advanced options). Maybe this fixes the issue already?

Cheers,

Robin

[Emux]

> I think this is about clicking on the route.

It's very abstract, depending the zoom, the map style's street stroke width, if the map follows exactly the actual street geometry, etc.

> On the website it generates a waypoint on the route at this position. So it could improve the workflow to place it exactly on the route and not on the clicked coordinates.

That can work only in cases of the calculations are considered "local", i.e. the frontend and the backend work in "close" or same servers.

--
Emux

[Petra aus Aachen]

Robin and Emux,

first, thanks for the very fast response to my question!  *thumb up*

I was, indeed, not aware of this option "put points to street". if it worked correctly it would help a lot w/r/to my objective - but it doesn't. Just look at:

  

I introduced the route point 2 into the route in zoom level of 2nd image, after the option was enabled and the mouse pointer changed from hand to arrow. Zooming in you immediately observe the point being placed into the field. (proceeding in a next posting as the editor seems to go crazy on my just now ....)

[Robin]

The button is a action, press it and the waypoints will be moved. It's not an option that works over time.

[Petra aus Aachen]

In the shown case this would typically not matter, as the navaid gracefully accepts the point even if passed by in the vicinity on the road.

A bit more problematic are the cases where there are adjacent roads, like in the following case for route point 4, with my introduction being done in the same way as described above for the other situation:

yielding in zoomed in mode:

Here the pure "snap to road" is not helpful as the algo did snap to a road - but one that was not on the course of the former route.

I guess you all know what the usual navaids make from such a setting ...   :-/

Please let me stress the fact that the mouse pointer changed from "hand" to "arrow" in both cases. So at least the respective active drawing procedure must have been aware that I clicked the route course. And I'd say that this is the hook to put a new jacket on.  :-)

Cheers,

Petra

[Emux]

Hi Petra,

Since you split your post, did you retest it according to Robin's explanation?

The "Place waypoints on street" button is not a toggle to stay firmly in pressed position.
You need to press it "each" time "after" the routing, for the "already" placed waypoints to be snapped on near streets.

--
Emux

[Petra aus Aachen]

Hi Emux,

> Since you split your post, did you retest it according to Robin's explanation?

No, I didn't because of my 2nd example in which I detailed out that "snap to road" would not help in the really critical situations (i.e.: point is placed on the wrong road).

But upon your post I now did the test - it ran as anticipated: For my first case the route point went indeed on to the rural lane. For the 2nd, more critical one the misplaced point stayed on the side road. So the function helps in the uncritical cases whereas the critical ones remain unchanged.

To show you another example of situations I was already tripped frequently in: Introduce an intermediate route point to secure the route to be taken - in the following example take road via Grötzingen instead of potentially via Ennahofen due to a differing algo in the later navaid. The point is placed in a zoom level rather typical for route refinement. Knowing the traps of placing intermediate points in populated areas it is obviously positioned on a rural part of the route, so nothing mean is to be anticipated, as discussed before.

When we zoom in, though, we see the mess:

"Snap to road" would just move the point to the very end of the dead end.

Once again, the pragmatic planning support would require a true detection of the mouse pointer as being pressed over the already existing course of the route. (I discuss the necessity of manually introducing intermediate points in another parallel thread.)

Anyhow - thank you for your continued interest in my critical remarks (which are definitely meant to be constructive, as I love to plan with Kurviger!)

Petra

[Robin]

Hi Petra,

as mentioned earlier, I will have a look if we can improve the placement of waypoints for the left-click scenario on the website. 

I understand the issue and I can see that this might create problems for users.

Cheers,

Robin

[Robin]

Hi Petra,

sorry that it took so long :). I hope you had many great rides with Kurviger in the meantime.

We just improved the waypoint placement on left-click. Please let us know if this fixes your issue.

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

indeed I made a few trips, and of course I planned them with Kurviger!  :-) At the moment the weather is so hot, tough, that the motorbike riding is brought to a rest even though I planned to have a nice tour on this weekend. Maybe I'm just too weakened.

I just checked your work on a theoretical basis and I'm glad to confirm that the placement of the left-click intermediates has definitely improved. I had some critical placements, though, where the produced intermediate was placed directly on a (very near) crossing of the formerly calculated route. This is an absolute no-go, as I teach my navaid adepts almost every time we talk about manual route creation for arbitrary navaids: Depending on the origin of the underlying map information of the respective navaid the route is placed upon, this is prone to lead you into the side road with the subsequent suggestion to make a full turn.

Same observation on an automatically generated round trip, exported with lots of intermediates for study purposes (see attachment): Most of them were placed intelligently (thumps up!!), but some landed directly on crossings: 3, 26, 28

Intermediate 5 needs a special mention: I didn't know Kurviger honors impressively decorated roundabouts by a lap of honor!    *rotfl*

Executive summary: Good work!   :-)

Petra

[Robin]

Hi Petra,

indeed it's too hot for a ride :). I am probably too weak as well ;).

> I had some critical placements, though, where the produced intermediate was placed directly on a (very near) crossing of the formerly calculated route.

Clicking is a manual process, don't click close to a crossing :). Sorry but someone might want to place a waypoint on an intersection or very close to it, for example because there might be a POI or a meeting point, so I think this should not be changed.

> but some landed directly on crossings: 3, 26, 28

3 and 28, shouldn't be an issue, since the other roads are not accessible for motorcycles, right?

26 and 5 are a different story. Were they created as one of the initial roundtrip waypoints?

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

> I had some critical placements, though, where the produced intermediate was placed directly on a (very near) crossing of the formerly calculated route.

Clicking is a manual process, don't click close to a crossing :). Sorry but someone might want to place a waypoint on an intersection or very close to it, for example because there might be a POI or a meeting point, so I think this should not be changed.

Of course a deliberate placement on a crossing should be obeyed. But in the demonstrated case the placements were performed automagically by Kurviger (see procedure below).

 

> 3 and 28, shouldn't be an issue, since the other roads are not accessible for motorcycles, right?

Almost: IIRC these crossings are at least ones with paved (although most probably forbidden) roads. Depending on the navaid these roads may or may not be declared accessible. Especially these higher category roads differ quite often in their categorization. As long as you stay in the Kurviger universe you are right, of course.

26 and 5 are a different story. Were they created as one of the initial roundtrip waypoints?

Way of creation:

i) Make Kurviger design a round trip of some 100 km, ii) fill resultant route with (lots of) intermediates during export, iii) re-import created route with intermediates back into Kurviger for scrutiny.

So any intermediate in the given example was created without any human intervention.

Kind regards,

Petra

[Robin]

Hi Petra,

> IIRC these crossings are at least ones with paved (although most probably forbidden) roads.

Yes but if these roads are not accessible to Kurviger they are not an intersection Kurviger knows about, so there is nothing we can avoid :).

I will have another look at the automatic generation. Cannot promise anything though ;).

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

just today I found another example of potentially problematic intermediates generation that I would like to discuss along example images.

After designing a small round trip I exported the route via "add lots of intermediates", resulting in the revamped route definition shown in "createdintermediates.png".

Zooming to the area of Rp 4 - Rp 5 we see that there are alternatives: There is a comparable route via "Schöffelding" that might be taken as well.

About the same holds for Rp 5 - Rp 6 where even more alternatives are possible due to a quite dense road coverage.

Finally, see excerpt for Rp 7 - Rp 8: I would expect several navaids to take a road selection nearer to the Ammersee instead of the one Kurviger has chosen.

In order not just to criticize let me suggest a potential algorithm that should be readily implementable in Kurviger, even though it would result in a slightly higher server load I assume:

#1: Create curvy road with user-defined hard intermediates (as before) and remember trip lengths between intermediates

#2: Create fast route for same hard intermediates and calculate trip lengths between intermediates

#3: Compare distances of intermediates calculated in #1 and #2

DO

  #4: Put additional intermediates coarsely to the middle of the actual route sections where distances differ by more than x meters (to be adjusted)

  #5: Recalculate "fast trip" lengths between affected intermediates (and potentially the lengths for the curvy alternative as well)

WHILE Results of #5 differ for curvy and fast

And just another issue (once again, IIRC): Do not limit the number of route points when importing a route into Kurviger, as long as the number is not lethal to the system. There is absolutely no sense in defining an import limit as low as 25 route points. It will just result in irritation of the user who sees that the formerly worked-out route is not taken as anticipated.

But now I'll rather hit the road than continue writing here ....  :-)

Cheers,

Petra

[Robin]

Hi Petra,

thanks for the detailed discussion and sorry for the late reply.

Have you tried what happens when using instead of the setting a lot, to simply input 200 in the custom input? This should improve the situation quite a bit.

Regarding your proposed algorithm, this sounds nice, but I fear it's not a practical approach as this would lead to a massively increased server load. Instead of doing just one route calculation, we might do 100 or even more. Then there is still the possibility that the device used for calculating the routes still deviates from the planned route. 

> And just another issue (once again, IIRC): Do not limit the number of route points when importing a route into Kurviger, as long as the number is not lethal to the system. There is absolutely no sense in defining an import limit as low as 25 route points. It will just result in irritation of the user who sees that the formerly worked-out route is not taken as anticipated.

Yes I remember talking about this as well ;). There is a good reason why we limit this to 25. Everyone that knows what's happening can increase this number, but new users struggled with this regularly if the number is too high. We received an incredible amount of complaints in the beginning with people importing too many waypoints and suffering from the issues.

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

> Have you tried what happens when using instead of the setting a lot, to simply input 200 in the custom input? This should improve the situation quite a bit.

I didn't, due to former experiences with abundant route point settings: the more superfluous rp there are the larger the danger of some of them lying only near the road and producing misleading turn suggestions. Apart from that, my Tomtom only likes 48 route points in its routes therefore a more  intelligent approach is highly desirable.

Regarding your proposed algorithm, this sounds nice, but I fear it's not a practical approach as this would lead to a massively increased server load. Instead of doing just one route calculation, we might do 100 or even more. Then there is still the possibility that the device used for calculating the routes still deviates from the planned route.

 There is no guarantee in a strict mathematical sense, indeed, that the proposed algorithm converges earlier. But practical experience indicates that this worst case scenario will happen in only very rare cases: The mesh density of the road net is a rather severe limiting factor on the required practical route point density.

I have just made a practical experiment: I took a route of some 220 km, only defined by start and end point, switched between fastest and most curvy planning variant, and inserted additional waypoints roughly in the middle of optically differing route segments between existing route points. I needed 14 insertions until I did not observe a (major) deviation between those variants any more. As the proposed algo would introduce supporting route points in every route section in need simultaneously this result would have required about 8 re-iterations of route calculation - which is way less than the horror scenario you envisioned!  :-)

 

> And just another issue (once again, IIRC): Do not limit the number of route points when importing a route into Kurviger, ...

There is a good reason why we limit this to 25. ... We received an incredible amount of complaints in the beginning with people importing too many waypoints and suffering from the issues.

Well, as I wrote: I suggest to do such things "within reason", i.e.: allow only a certain mean density (with regard to air distance of points) before automatically asking the importer what to do with the superfluous ones. I agree that a sensible limit on automatic imports should be set, derived from various classification numbers perhaps. But if the route point list is cut automatically on import there should at least be a warning on that behalf.

Cheers,

Petra (who works down her communication backlog on a rainy day ....  :-))

[Robin]

Hi Petra,

> But practical experience indicates that this worst case scenario will happen in only very rare cases

I have a different experience here :). Often the issues in Germany are not that big, but I have seen quite some cases all over the world. While your proposed algorithm sounds really nice, it is not practical, because it could lead to a server overload.

> inserted additional waypoints roughly in the middle of optically differing route segments between existing route points

That is another point, humans are really good at finding optically differing route segments. Computers are not. While this is possible, it is quite computational expensive, because you need to calculate distances, between thousands of points to find the biggest differing route segments.

> As the proposed algo would introduce supporting route points in every route section in need simultaneously this result would have required about 8 re-iterations of route calculation - which is way less than the horror scenario you envisioned!  :-)

There will be easy and complicated cases. Feel free to try this for a longer route > 200km that uses extra curvy and a couple of more advanced avoidances like "avoid main roads" and try to match this with the fastest route without using any avoidances (because most navis don't support "avoid main roads"). Hint: it's easier to do this when exporting one route as GPX track and show this as overlay and creating via points like this.

For the sake of argument, I did this for a random route here, I stopped after adding 15 additional waypoints and the route still doesn't come close to the originally planned route (see the attached files). My best guess would be that we would need >50 waypoints to get a 95% match of the route.

BTW: this is no special route, I just picked it at random.

> Well, as I wrote: I suggest to do such things "within reason", i.e.: allow only a certain mean density (with regard to air distance of points) before automatically asking the importer what to do with the superfluous ones. I agree that a sensible limit on automatic imports should be set, derived from various classification numbers perhaps. But if the route point list is cut automatically on import there should at least be a warning on that behalf.

I will think about this, maybe if we add a couple of sanity checks, this could work out :).

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

> That is another point, humans are really good at finding optically differing route segments. Computers are not. While this is possible, it is quite computational expensive, because you need to calculate distances, between thousands of points to find the biggest differing route segments.

No, wait: This is not the approach I was faking manually in lieu of calculational data from inside the router!

I was suggesting to insert a supporting route point in the middle of the curvy road partition if the lengths of "curvy" and "fast" do not match exactly. This should be an easy comparison for a computer. So for each insertion set (consisting of potential insertions in disjunct route parts) it is only (n-1) scalar numerical comparisons, and two further route calculations in one iteration step. And I would expect the distances between already defined route points (none else!) to be available within the router.

This only to bar misunderstanding of the suggested procedure. If you still claim server overload I am defeated!  :-)

Cheers,

Petra

[Robin]

Ah, now I understand your proposed algorithm. But how would you handle a minor route distinction that is for example in the beginning of the Route between A and B. Now you would put waypoints halfway between A,B, then halfway between A WP1 and B, and so on until you reach the small distinction?

Otherwise you need to calculate the distance of every route segment to every other route segment, which would be the better approach IMHO.

Anyway, the biggest issue is to recalculate the route multiple times, that's just not feasible. Partial recalculations are not possible due to technical reasons.

> If you still claim server overload I am defeated!  :-)

Yes. This algorithm could increase route calculation time from for example 1s to 100s, if you need to recalculate the route 100 times. These things don't matter on your own computer, but they matter on a shared resource. We are not as crazy about server overload as other route planners, but we cannot introduce an option that can slow down calculation by factor 10 or more.

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

> Ah, now I understand your proposed algorithm. But how would you handle a minor route distinction that is for example in the beginning of the Route between A and B. Now you would put waypoints halfway between A,B, then halfway between A WP1 and B, and so on until you reach the small distinction?

If the small and only distinction would be very near to A, WP1 would be put half way. Upon recalculation you would find that the distance A-WP1 is different, WP1-B is not. So put another WP2 between A and WP1 and recalculate the whole route. As there was no difference before on section WP1-B, you only have to check the new distances between A-WP2 and WP2-WP1. And so on. I assume that the routing strategy related distances between defined waypoints are available within the algorithm, so you can access those numbers readily.

These things don't matter on your own computer, but they matter on a shared resource. We are not as crazy about server overload as other route planners, but we cannot introduce an option that can slow down calculation by factor 10 or more.

Okay, defeated! :-)  I am pretty sure you would not need to recalculate the route 100 times, but if your pain limit is already at 10 times, this is a value that I expect to be frequently surpassed.

I hope I didn't distract too much of your valuable time from coding by this discussion ...   :-)

Cheers,

Petra

[Robin]

Hi Petra,

> I assume that the routing strategy related distances between defined waypoints are available within the algorithm, so you can access those numbers readily.

Yes sure, these numbers are available, but recalculating the route is the part that takes the most time.

> Okay, defeated! :-)  I am pretty sure you would not need to recalculate the route 100 times,

Please feel free to try with the route I send in my last post ;). This always depends on the route.

>  but if your pain limit is already at 10 times, this is a value that I expect to be frequently surpassed.

Actually the pain limit is a lot lower ;). 10% is already quite a lot. For example if we would have 100% utilization of our servers, by adding 10% to requests, we would need 10% more servers. The calculation doesn't work like that, but I think it can help to understand the problem a bit better.

Cheers,

Robin

[Petra aus Aachen]

Hi Robin,

as I said: As soon as you consider 10 recalculations as too much, I regard this case as settled. But please keep in mind that there will be a number of users that will simulate quite exactly the algorithm I described, with some human variations, of course, due to remembering stack deficiencies of the human brain. And with incompletely available information to relate to when inserting assisting route points, compared to the inner routing procedure by itself..  :-)

In order not to overload your servers, I could imagine my proposed function as a kind of delayed response system, though: Do the route point optimization as a niced background task that only progresses if servers are idling?

Cheers,

Petra

[Robin]

Hi Petra,

> But please keep in mind that there will be a number of users that will simulate quite exactly the algorithm I described, with some human variations, of course, due to remembering stack deficiencies of the human brain

That's not a problem though ;). I know this sounds inconsistent, this has something to do with the way our infrastructure is built.

> In order not to overload your servers, I could imagine my proposed function as a kind of delayed response system, though: Do the route point optimization as a niced background task that only progresses if servers are idling?

Sure, these things are possible, but this overcomplicates things. I know people that built systems like that. It's not as straightforward or easy to build.

We are constantly trying to improve our export mechanism :)

Cheers,

Robin