[mkgmap-dev] Sharp angles in cycle ways
From Gerd Petermann gpetermann_muenchen at hotmail.com on Tue Apr 8 14:24:15 BST 2014
Hi Felix, please check: I think sharp angles (or angles at all) do only matter at junctions of (different) roads. The RoadMerger should already join similar roads, and the routing algo doesn't care about angles in roads. The reason is quite simple: The NOD file contains no information about the angles within arcs. It only contains information about - position of nodes (in garmin map units) - arcs between these nodes (information: oneway or not, throughrouting or not, allowed vehicles, road class and speed, ratio between way on road and direct connection, and the so called initial heading. For each arc between two nodes n1 and n2 there exists a reverse arc from n2 to n1. So, the routing algo can calculate in which direction a road is going that arrives at a node, and at which direction another road is leaving. The sharper the angle between them, the more likely you see a time penalty when the algo decides to take that way. AFAIK the routing algo only uses the data in RGN (or NET) to determine the overall length of the way, and it seems to calculate that only once for the final result, not for the alternatives. The interesting point is that a sharp angle in the way doesn't matter as long as there is no connection to another road. I don't know yet how to find the initial headings which have to be changed, but for now it looks much easier to me to manipulate these values instead of adding new nodes and new arcs. Also, this will not change the size of the img file very much. Anyway, also the latter could be done. I've create a small test file to find out under what circumstances the routing algo avoids the shorter route, see attachment. Gerd Date: Tue, 8 Apr 2014 11:42:02 +0200 From: extremecarver at gmail.com To: mkgmap-dev at lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Sharp angles in cycle ways Oh yeah - just to give an example: The very sharp angle at road_speed=2 is already enough to add 2 minutes to the time vs the same distance on ~15° angle!!!! (which is completly unrealstic to lose 2min for one single turn if you are only at 40km/h (road_speed=2) anyhow...) On 08.04.2014 11:38, Felix Hartmann wrote: Well I used rather my own data for tests - and not OSM.... The only problem is that - while I can see that sharp angles add an tremendous amount of time to the route calculation, and are usually avoided, I cannot really see the influence on long distance routing. Because there are 3 factors to consider: 1. Sharp turns in angles 2. Preference for straight roads even if no intersection (doesn't seem to be too strong) 3. Overall turns (also doesn't seem to matter that much - though it ends up being about 100 to 150 turns limit between actual route points given by the user). There is some sort of cut off angle. I think any angle over 170° actually creates routing mistakes. They need to be angled lower in any case anyhow... You can play around a bit here: ftp://ftp5.gwdg.de/pub/misc/openstreetmap/openmtbmap/odbl/mtblegend.exe data: ftp://ftp5.gwdg.de/pub/misc/openstreetmap/openmtbmap/legend.osm The main importance regarding this is road_speed. (for above example). Have a look at the top roads which sometimes have supershort angles While on the top left the Roundabout is roadspeed 0 - the sharp turn doesn't matter. For the top middle track roads - which have roadspeed=2 - the sharp turns create far too big penalties. Actually the penalty for a 170° turn on intersection with roadspeed=7 is 5 minutes or so. That's absolutely unrealistic (because in real life at such an intersection everyone would be slowed down reasonably, so also cars going straight would need to go slower)... So no - I would not like to have 90° everywhere - but actually additional very short insible arc ways for very sharp turns. Say every intersection over 110° should be arced to get it down (creating two intersections that are both small angle)... For places where there is no actual intersection - but only two roads meeting at sharp angle (e.g. a hairpin turn where in osm there are two lines meeting at the hairpin - which is actually quite common) best would be of course to join the two roads and maybe additionally make the hairpin a bit rounder. If joining is not possible then just make it rounder... As I don't know if some of my proposals are easy or easier than others, it would be nice to give any of them a try to see if it improves routing... So concluding: 1.V shaped unreal intersection or just very tight V turn: smooth it out. Join if possible 2. Y shaped intersection. Add additional invisible arc way to smoothen the sharp angle out. 3. X shaped intersection or intersections with even more routable lines meeting - same as 2. would be great (in cities that would even reflect reality better as usually turns are not so sharp - but often due to simplicity in mapping - the ways meet at one point in OSM - however due to micro mapping theese become less common anyhow). If the style adds multiple routable ways for one OSM way, the corresponding multiple arcs between nodes on that way should be counted like one . - Yep, only one additional arc should be created. The roadspeed/roadclass should be highest minus 1. Actually I think if 1-3 could all be handled by mkgmap - I could skip most of my additional routable ways (save differing speed depending on direction) - as they only exist to increase chances that curvy/turny routes are calculated - as the main problem is: If you create a highway with road_class=4 and road_speed=7 (road_speed being the main problem) - and it's turny/curvy it simply won't be used by Garmin (the first assumption that you would use to make a cycle route into the most preferred way). If it is road_class=4 and road_speed=2 or 1 - it is much more attractive to the algo - albeit loosing out on long distance. Hence creating multiple routable lines of the same way, increases the chance that one of it fits... And while it's actually still quite easy to build the map in such a way that relation=route / route=cycleway has high preference - it currently is more or less impossible to create a map that has highest preference for highway=path (because pathes don't form any network). On 08.04.2014 10:16, Gerd Petermann wrote: Hi all, a few days ago Felix suggested to add code to improve routing for bicycles: http://gis.19327.n5.nabble.com/r3165-in-via-ways-branch-tp5802056p5802063.html If I got that right, mkgmap should detect cases where two arcs meet at with a sharp angle and the arcs are only accessible by bicycle or foot. In such a case, mkgmap should "manipulate" the angle so that the routing algo doesn't add too much time penalty, as we can assume that the real angle is not that sharp. Or mkgmap should assume that the created map is for cyclists only, so that car access means something like racing bike. Optimization would work like this: 1) at an y-shaped node, find the two arcs which are closer to a straight line and modify the initial heading of the other arc so that Garmin sees a right angle (90°) . 2) at an x -shaped node, try to make all angles 90° 3) at nodes with more than 4 arcs, do nothing. If the style adds multiple routable ways for one OSM way, the corresponding multiple arcs between nodes on that way should be counted like one . If that can be coded, it has only to be done if a new option like --optimize-cycle-ways is given. Did I get that right? @Felix: Please provide a test case (the OSM id of a node ) Gerd _______________________________________________ mkgmap-dev mailing list mkgmap-dev at lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev -- keep on biking and discovering new trails Felix openmtbmap.org & www.velomap.org -- keep on biking and discovering new trails Felix openmtbmap.org & www.velomap.org _______________________________________________ mkgmap-dev mailing list mkgmap-dev at lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140408/969e8830/attachment-0001.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: speed1.osm Type: application/octet-stream Size: 8091 bytes Desc: not available URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140408/969e8830/attachment-0001.obj>
- Previous message: [mkgmap-dev] Sharp angles in cycle ways
- Next message: [mkgmap-dev] improvements installer template
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list