User:Mvglasow/Roundabouts

From Navit's Wiki
Jump to: navigation, search

Navit's maneuver icons for roundabouts give an approximate direction (straight, sharply left, slightly right, turn around and others). Getting that information from the map data, however, is tricky.

The Naïve Approach[edit]

The naïve approach is to simply compare bearings of the last way segment before and the first way segment after the roundabout. This works well for cases like this:

This maneuver will be correctly announced as "go straight"

However, the approach fails when the roads leading to the roundabout split just before it, as shown below:

This maneuver will be incorrectly identified as a left turn

This is the approach Navit used before r2017. Cases like the one above were probably the reason it was abandoned.

The obvious solution to the above is to compare not the way segments before and after the roundabout, but the ones before and after the splits. This may sound like a solution to the case above, but it will not work for cases like the next one:

The roads connecting to this roundabout have separate carriageways

The Navit Approach Since r2017[edit]

In r2017, Navit switched to a different algorithm to calculate the angle between entry and exit. Since the approach segments essentially smoothen the turns one has to make when entering or leaving the roundabout, Navit simply pretends they enter the roundabout at a 90° angle and calculates the difference between those angles. (In reality, Navit simplifies calculations by comparing the tangents of the roundabout at the entry and exit points, which results in the same angles.) Compare the results:

Prior to r2017 After r2017

This works fairly well, albeit with a minor error, as long as the approach segments connect to the roundabout within a relatively short distance, compared to the circumference of the roundabout. Otherwise this approach will produce incorrect results, as shown in the next examples:

Prior to r2017 After r2017

Since the distance between the two approach carriageways is quite considerable compared to the size of the roundabout, the error is getting quite massive. A maneuver that drivers would likely perceive as going straight looks like a 90° turn to Navit.

Possible Solutions[edit]

Averaging Between Entry and Exit[edit]

In the above examples entry and exit ways always come in pairs: When following the roundabout, each exit is immediately followed by an entry. We could average between the points at which they connect to the roundabout and use that as the basis for our calculations, as in the following example:

Averaging between the two approach roads gives the correct angle in this example

Alas, this will not work in all cases: Sometimes there are true one-way roads connecting to a roundabout. We need to identify these cases and treat them specially.

Another limitation has to do with the internals of Navit:

  • A way in OSM may correspond to more than one way in Navit: Wherever a node is shared by two or more ways, Navit splits all of these ways in two. Thus, as far as Navit is concerned, no way extends beyond a junction.
  • Roundabouts are evaluated using the route map. The route map contains only a few items – namely those which are important for navigation. These are the ways that are part of the route, and all ways that share nodes with them.

Because of this, the route map for a roundabout would look something like this:

Roundabout 2 route.svg Roundabout 4 route.svg

As you can see, the route map does not hold the full roundabout. Things may be even worse than shown in the drawings – namely, when ways which are not part of the route are split into segments or share nodes with another feature. In such cases, some of the elements we need in order to average between an entry and its corresponding exit would be missing. So this approach will not work unless we add more items to the route map.

Averaging Between Previous Approaches[edit]

If you look closely at the earlier examples, you will see that the first two approaches introduce different kinds of errors: Given the same straight path, one approach interprets it as a left turn while the other one interprets it as a right turn. Averaging over the two would cancel the error out at least in part.

There is one caveat, though: a "turn around" maneuver together with approach roads will have a delta in excess of +/-180°. Simply comparing the bearings of the approach roads may incorrectly give us an angle in the opposite direction – we have to detect and handle these cases.

A simple unweighted average already improves the result, but since the two errors differ, this will overcompensate for the smaller of the two errors – or compensate insufficiently for the bigger one. We could do better with a weighted average if we manage to provide a confidence range, i.e. an estimate of the error.

The error of the first approach (using the bearings of the approach roads) is greatest when the bearing of the approach road diverges significantly from that of the road leading towards it. We can approximate this by analyzing the roads before and after the roundabout, assuming the approach section begins where either the one-way section begins or (in the case of separate carriageways) a certain distance from the roundabout (which should correspond to the length of the roundabout) is reached. The angle difference between the beginning and the end of this section is the confidence.

The error of the second approach (using bearings of tangents) is greatest when the approach ways are spaced far apart – or, more precisely: when the bearings of the corresponding tangents differ. These can be derived from the segments of the roundabout which are not part of the route. While this is not 100% reliable, it should be OK for confidence.

A propos: if these two segments have the same entry and exit angles, it means both are identical, which is only the case if we are going full-circle (thus roundabout delta is +/-180°).

Having established two estimates delta1 and delta2, along with their confidence levels c1 and c2, we can calculate a final estimate as:

delta = (delta1 * c2 + delta2 * c1) / (c1 + c2)

In other words, the weight for each delta estimate is the confidence of the other estimate.