logo separator

[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>


More information about the mkgmap-dev mailing list