Difference between revisions of "Modèle:;/doc"

From Wazeopedia
(fixed links to transclusions)
m (fixed links)
Line 5: Line 5:
 
The original text provided by Waze staff which inspired this page was proven slightly inaccurate, and was difficult to comprehend it was replaced on 06/22/2014.
 
The original text provided by Waze staff which inspired this page was proven slightly inaccurate, and was difficult to comprehend it was replaced on 06/22/2014.
  
A simplified easy to understand interactive version of this page is [[User:PesachZ/Interactive junction instruction algorithm|available here]].
+
A simplified easy to understand interactive version of this page is [[Interactive junction instruction algorithm|available here]].
  
 
== Definitions ==
 
== Definitions ==
Line 35: Line 35:
 
*#Four (4) or less exits,
 
*#Four (4) or less exits,
 
*#All exits leave the roundabout ''(from the perspective of s-in)'' at a normal angle.
 
*#All exits leave the roundabout ''(from the perspective of s-in)'' at a normal angle.
*#*A '''Normal Angle''' is 0° or 90° to either side, ±15°. (See [[User:PesachZ/Interactive_junction_instruction_algorithm#roundabout_angle|roundabout angle]] for more information)
+
*#*A '''Normal Angle''' is 0° or 90° to either side, ±15°. (See [[Interactive_junction_instruction_algorithm#roundabout_angle|roundabout angle]] for more information)
 
*An '''[[Roundabout#Understanding_navigation_instructions|Abnormal Roundabout]]''' is one which has
 
*An '''[[Roundabout#Understanding_navigation_instructions|Abnormal Roundabout]]''' is one which has
 
*#Five (5) or more exits,
 
*#Five (5) or more exits,
 
*#At least one exit leaves the roundabout ''(from the perspective of s-in)'' at an abnormal angle.
 
*#At least one exit leaves the roundabout ''(from the perspective of s-in)'' at an abnormal angle.
*#*A '''Abnormal Angle''' is anything other than; 0° or 90° to either side, ±15°. (See [[User:PesachZ/Interactive_junction_instruction_algorithm#roundabout_angle|roundabout angle]] for more information)
+
*#*A '''Abnormal Angle''' is anything other than; 0° or 90° to either side, ±15°. (See [[Interactive_junction_instruction_algorithm#roundabout_angle|roundabout angle]] for more information)
 
<br/>
 
<br/>
 
[[File:S-in s-out definition.jpg|border|center|Visualize how segments are subjectively named in the 'Best Continuation' Algorithm]]
 
[[File:S-in s-out definition.jpg|border|center|Visualize how segments are subjectively named in the 'Best Continuation' Algorithm]]
Line 79: Line 79:
  
 
=== Graphic flowchart ===
 
=== Graphic flowchart ===
This is a static graphic flowchart starting from a junction point and flowing through (all) the possible configuration options, to hopefully cover any scenario. It culminates in all the possible navigation instructions. This chart includes [[Roundabout#Understanding_navigation_instructions|roundabouts]], [[LHT|Left Hand Traffic]], and [[RHT|Right Hand Traffic]]. For an interactive version with mite descriptions and illustrations are the [[User:PesachZ/Interactive junction instruction algorithm|interactive page]].
+
This is a static graphic flowchart starting from a junction point and flowing through (all) the possible configuration options, to hopefully cover any scenario. It culminates in all the possible navigation instructions. This chart includes [[Roundabout#Understanding_navigation_instructions|roundabouts]], [[LHT|Left Hand Traffic]], and [[RHT|Right Hand Traffic]]. For an interactive version with mite descriptions and illustrations are the [[Interactive junction instruction algorithm|interactive page]].
 
[[File:Turn algorithm flowchart.png|700px|thumb|center|Graphic flowchart for algorithm how waze determines turn, keep, and exit instructions. For Junctions, and roundabouts. ''(click to enlarge)'']]
 
[[File:Turn algorithm flowchart.png|700px|thumb|center|Graphic flowchart for algorithm how waze determines turn, keep, and exit instructions. For Junctions, and roundabouts. ''(click to enlarge)'']]
  

Revision as of 18:15, 22 June 2014

Modèle:Construction

A somewhat simplified description of this is covered in the Junction Style Guide. Additional routing information is covered in the article Routing server.

The original text provided by Waze staff which inspired this page was proven slightly inaccurate, and was difficult to comprehend it was replaced on 06/22/2014.

A simplified easy to understand interactive version of this page is available here.

Definitions

To better be able to put the algorithm into words, we have to name each of the road segments that connect to a junction. These are subjective names, they are relative to which segment the junction is being approached from, and which segment the routing server wants to navigate to after passing through the junction.

Start with the junction in the middle.

  • s-in: The segment the vehicle is on as it approaches the junction will be called s-in.
  • s-out: The segment the vehicle is being routed onto after it passes through the junction will be called s-out. This can be any of the other segments connected to the junction, which will also be one of the segments named below as s1, s2, ... etc..
  • s1, s2, s3, s4, etc.: All the segments connected to the same junction, (including s-out) will each be named consecutively as s1, s2, etc., for as many segments as there are… sN. One of these numbered segments will also be s-out.
  • Best Continuation: One of the segments leaving the junction will be considered the 'Best Continuation'. This is the segment that Waze determines is what drivers would consider the "no turning path" or "going straight" through the intersection. This segment will get a 'continue' instruction, which is ignored by the client app. The criteria Waze uses to determine which segment is the 'Best Continuation' is explained below.
  • Primary road: refers to a highway segment ( Freeway ,  Major Highway , or  Minor Highway ), not a  Primary Street .
  • The angle is the angle from the origin to the destination. A perfectly straight road with a junction in the middle would have a turn angle is 0°. The angle then gets wider as you turn to either side. A perfect left or right turn would be 90°. A U-turn at a junction between two segments would represent a 180° turn.
    (A turn less than How Waze determines turn / keep / exit maneuvers/Stay threshold will give a keep/stay instruction, vs. a turn more than How Waze determines turn / keep / exit maneuvers/Turn threshold which gives a turn instruction.)
    • In technical terms: The angle between the linear segment between the last geometry node of s-in and the junction and the linear segment between the junction and the first geometry node of sN is the supplementary angle to the angle of sN.
Angles
Turn angle.png
Turn angle 37.png
Turn angle geo line.png
Standard Angles 37° Angle 90° Dogleg Geometry Node
  • A Normal Roundabout is one which has
    1. Four (4) or less exits,
    2. All exits leave the roundabout (from the perspective of s-in) at a normal angle.
      • A Normal Angle is 0° or 90° to either side, ±15°. (See roundabout angle for more information)
  • An Abnormal Roundabout is one which has
    1. Five (5) or more exits,
    2. At least one exit leaves the roundabout (from the perspective of s-in) at an abnormal angle.
      • A Abnormal Angle is anything other than; 0° or 90° to either side, ±15°. (See roundabout angle for more information)


Visualize how segments are subjectively named in the 'Best Continuation' Algorithm

Best Continuation

In order to determine if s-out is the 'real' continuation of s-in, Waze does the following:

If the angle between s-in and s-out is less than How Waze determines turn / keep / exit maneuvers/Stay threshold, it is selected as the real continuation, unless one of the following are present.

If a 'best continuation' is determined, Waze will not give an instruction going onto that segment.

Flowchart defining the steps the algorithm runs through.

Special Considerations

The algorithm

The description below fits a right turn in a Right-hand traffic country (e.g. the USA). Left turns are symmetrical to right turns.

The algorithm iterates over a list of conditions. As soon as a condition is met, the relevant instruction is determined, and the algorithm terminates.

The list of conditions

  1. If the junction has only 2 segments, the instruction is: 'CONTINUE'.
    By design the client does not give this instruction.
  2. If s-out is determined to be the best continuation of s-in (see explanation on 'best continuation' above), the instruction is: 'CONTINUE', which implies that the driver is not turning (i.e., going straight through the junction).
    By design the client does not give this instruction.
  3. If the angle between s-out and a straight line is larger than 45 degrees, the instruction is: 'TURN RIGHT'.
    • This is because we assume that on primary roads ( freeways ,  major highways , and  minor highways ), turn angles are less than 45 degrees (no sharp turns on higher-throughput roads). Therefore, you never have something called an "exit" that has such an angle, and the instruction should be TURN, not EXIT.
  4. If s-in is a primary road ( FW ,  MH ,  mH ) and s-out is not a primary road ( FW ,  MH ,  mH ), the instruction is: 'EXIT RIGHT'.
  5. If s-in is a  ramp/exit  and s-out is neither a primary road ( FW ,  MH ,  mH ), nor a  ramp/exit , the instruction is: 'EXIT RIGHT'.
  6. If none of the above conditions are met, the instruction is: 'KEEP RIGHT'.

Graphic flowchart

This is a static graphic flowchart starting from a junction point and flowing through (all) the possible configuration options, to hopefully cover any scenario. It culminates in all the possible navigation instructions. This chart includes roundabouts, Left Hand Traffic, and Right Hand Traffic. For an interactive version with mite descriptions and illustrations are the interactive page.

Graphic flowchart for algorithm how waze determines turn, keep, and exit instructions. For Junctions, and roundabouts. (click to enlarge)

Special considerations

  • In some cases, a junction node could have more than two segments, but the routing server will only consider two of them as valid and therefore, the maneuver will be 'Continue straight'. This happens when turns into some of the segments are restricted, the routing server then skips those segments and ingores them when determining the 'Best Continuation'.
  • Turns can be restricted or unrestricted. In specific scenarios you may not be able to see this in WME - see RevCons for more information. There are external scripts which show this information (and some allow it to be easily corrected).
  • The original text mentions special behavior for locked nodes. For example, in this case (image below) - assuming the node is locked - heading south, the right turn will be considered 'Continue straight' as the routing server has no other option and there's only one possible segment to be s-out.
    • If the node was not locked, it is most likely that Waze would tell you to turn right. Driving against the direction is a high penalty, and so is a left turn where a turn is not allowed. However, it would still have been an option, which is why the routing server would have called it 'turn right'.

Right turn 1.png

    • This could be confusing, especially since there's no external indication on whether or not a node is locked at the moment.
    • The author and those involved in the discussion have never experienced a locked node which didn't follow the algorithm for determining the instruction.