[mkgmap-dev] Add additional ways at junctions - extending "Merge similar lines and ways" concept.

Thu Sep 10 13:39:08 BST 2009

Thilo Hannemann wrote:
> Hi Mark,
>
> Am 09.09.2009 um 19:58 schrieb Mark Burton:
>
>   
>>> I will modify the code that the merging is applied even earlier.
>>> Shouldn't be too hard to do.
>>>       
>> Did you do that? I would be keen to try a version because I notice on
>> my first few trips with the Nuvi that sometimes it says "keep
>> right/left" when it should say "turn right/left". I think that is
>> because the way looks like this:
>>     
>
>   
Some remarks about the merge lines concept, and the reasoning why it 
will not help much and needs to be extended/changed.

*1.* There is absolutely no need to merge lines in case the way 
continues at 0° angle (no change in direction).
*2. *There is no time penalty in Mapsource for a way zig-zagging, as 
long as there is no junction/change of way. The more the angle 
approaches 180° , the bigger the time penalty.
*2a* 180° exact i.e. only change in direction of way in osm database 
without oneway attribute does not matter of course, On the other hand 
every single route viapoint you set additionally will give you a time 
penalty. So if you route along a completely straight line and you put 
additional via points, the calculated arrival time gets bigger. This of 
course is irrelevant to mkgmap. The effect of the time penalty for via 
points, is only around 5-20seconds, so should be irrelevant (maybe 
maximum 1-2% of added time) to total travel time of a route.
*3.* If two ways meet on a straight line:
*a)* no time penalty is added at all
*b)* no turn indication is given
This means that you can well turn around a whole circle without any turn 
indication and many way changes, as long as the junctions themselves lie 
on a straight line. There is not even an indication of streetname 
changes. So in the directions window of mapsource, or route window of 
GPS it will not tell you that you get on another street (meaning another 
streetname) as long as you continue straight.

*
Taking into account the above:*
Yes a merging lines patch will help for bicycle/pedestrian routing. 
Though much more effective would be a patch that actually changes the 
angle streets meet.

Let's first look at what happens when two streets meet at extreme angle. 
notice total time is 03:27min (with no junction at all it would be 01:28):
original

/

*Concept1*/
So if two ways meet:
       y
       y
       y
xxxxxxxx
       y
       y
       y

We should make additional ways like this (this will help a tiny bit, but 
not much). ("." means that 2 ways lie on top of each other, ";" means at 
this point there are four ways on top of each other, so the direction 
change is not at the junction but done on the intermediary way)
       y
       y
       .
xxx. . .xxxx
       .
       y
       y
concept1
So we notice now that the time is actually the same as if there was no 
junction 1:28min. Note, no junction/direction change is shown at all 
(the GPS will still warn however when approaching). This achieves the 
same effect as the merge line patch would do in case both streets have 
the same name.

*/Concept 2:/*
By having the turn on the intermediary way, instead of the junction 
itself) we completely avoid the time penalty (though we also miss the 
name change of the street in the route window, nor any indication in the 
route window about the turn). Therefore we have to change the above 
still a tiny bit. By playing around with changing the distance I have 
found out that we need to put nodes at least around 1m distance of each 
other (otherwise we get short arc problem), so while the /Concept1/ I 
chose to have a rather large distance for the straight part, I now 
reduce the distance to 1m between each node (this means that we need to 
have 2m additional width for the junction - /Concept1/ could be achieved 
on 1m), the even dirtier hack to get junctions back into the route 
window has to make the whole thing rounded. So assume you come from top 
(north) and want to continue to the right (east) we have to add a new 
way like this (only showing added ways, we should never remove the 
original ways of course, so that crossing straight is still possible). 
The new way is drawn as .
                            y
                            y
                            .
                            ..
                                             xxxxxxxxxxxxxxx
This distance          |               | being 5.4m, while distance from 
north to south should be made around 1m. By doing this we get the best 
possible. a) we are notified about the junction/street change, b) we are 
taking a time penalty for turning. This time penalty is however very 
small (5-10 seconds), and should be more or less  equal to what we need 
in real life to orientate here and change streets.

The proof in Mapsource of concept 2 (time penalty decreased to a mere 12 
seconds), reducing the distance between the two additional nodes to the 
junction of 1m makes this more or less invisible:
concept2

*
The much bigger advantage however is*, that the above concept would 
allow us on GPS to always route along the maximum of 100 direction 
changes (at least the old GPS can't route over more than 100 direction 
changes without via point) and over more or less indefinite distances in 
Mapsource (think Spain to Germany using small streets, cycleways and so 
on only). Transferring such a long route to GPS is even possible, using 
WinGDB to insert a via point every 99th direction change (Mapsource puts 
direction change points internally, but does not show them, they are 
saved in the .gdb file which is created if you save a calculated route. 
This way you could theoretically transfer a route going along 99.000 
junctions to your GPS which is still easily able to recalculate it (well 
I'm sure GPS runs out of memory long before, but we will be able to have 
as long routes as fit into the memory, I think routes over 1000-2000km 
should still work).

A closeup of the work shown in JOSM zoomed up very close looks like this 
(red is original way):
closeup josm

*Is there anyone* who thinks the above concept2 can be implemented into 
mkgmap? I don't have the skills to code this. But maybe someone has the 
skills, and feels motivated by knowing that shitty routing for 
bicycle/pedestrian use, can be easily adapted by changing junctions with 
the above concept. Without implementing the above, we will never have 
good routing in Mapsource or on GPS. Using concept2 would get splendid 
routing (and make the merge lines patch discussed before obsolete!). Off 
course the above would not be needed, if Garmin would make the penalty 
adjustable, but that day will probably not come......

Also as a benegit the keep left vs turn left could be solved this way 
(increasing the angle of the junction high enough to get turn instead of 
keep, or in contrast decrease angle of the road you want to stay on so 
that it reminds you to keep left/right).

See attached also screenshots of one more example (classic junction) and 
a osm testfile for you to play with.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: original.png
Type: image/png
Size: 15172 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: concept1.png
Type: image/png
Size: 13765 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0001.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: concept2.png
Type: image/png
Size: 14087 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0002.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: closeup.png
Type: image/png
Size: 3817 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0003.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example2 concept2.png
Type: image/png
Size: 17627 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0004.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example2 josm closeup.png
Type: image/png
Size: 2677 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0005.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example2 original.png
Type: image/png
Size: 17723 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0006.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mapsource 20m.png
Type: image/png
Size: 1668 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment-0007.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testfile.osm.gz
Type: application/gzip
Size: 1373 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090910/605531ad/attachment.bin 