U-turns at splitter vertices

[mattwigway]

We need to support turn restrictions. This seems simple enough but it gets a little bit complex when you realize that it would require multiple states per vertex. For example, consider the following situation:

The intersection in the middle has two incomparable states. One solution is to allow multiple states per vertex, but as outlined in #43 that is undesirable. There's another way, which used to be in OTP, which was to use an edge-based graph of the street network, where every street segment becomes a node and every turn possibility becomes an edge, as described in this paper, which is incidentally also the source of the above image. @abyrd remarks in no uncertain terms that he never wants to do this for the whole graph again. However, we don't have to do it for the whole graph, just for intersections where there are turn restriction (of which there are only about 500,000 in the entire world). So those particular intersections would (topologically) look like this (of course all the vertices depicted below would be coincident):

Turn restrictions would then be encoded by changing permissions on the turn edges. Note that there is no vertex in the center, so the situation depicted above would not pass through the same vertex twice (it would traverse both straight-through edges as well as the approach vertices to each, but would not visit any vertex twice).

This approach is nice because it can be extended to more complex turn restrictions without huge messes of path dependence (a la path parsers). For example, consider the following (from the OSM wiki:

In this location, you cannot turn right (slight right) from the main freeway (b) if you have come from the left entrance (a) (because they don't want people cutting quickly across many lanes). This is very difficult to represent with the standard graph structure as it basically requires a state machine. However, it can be simply represented with the edge based structure, by treating the entire intersection as a single unit and just connecting up all the possible entrances and exits:

So the main roadway becomes two edges because there are two possible states on it, the state where you have come from the main roadway and that where you have come from the left entrance. I think the code would just take more complex restrictions, find all of the edges that enter and exit the restriction, and create a node for each, then connect up edges based on what is legal.

It gets messy though when we have to make a split in a complex intersection like this, with duplicated edges (for the simple case it doesn't matter because the edges are infinitely short, we can just omit them from the spatial index and they won't be split, but these more complex intersections may take up significant area.

[mattwigway]

The below is the result of extensive discussion between @abyrd, @demory, @buma, and myself. The approach described above is problematic, because we would need to create a vertex not for every edge pair, but indeed for every edge, in order to be able to disallow U-turns. Edges in R5 come only in pairs, so this would require creating two edge pairs for every incoming edge, with all permissions removed from the back edge. Of course this is even more messy when two adjacent vertices have turn restrictions.

Instead we will just take the approach used in OTP of having multiple states per vertex. Initially this seems fairly simple; at vertices with turn restrictions, we simply store one state per incoming edge. Unfortunately, this won't work either, because it cannot handle the case where the via member of the turn restriction is a way rather than a node. This is fairly common any place there is a no-U-turn restriction on a dual carriageway; the via would be whatever crossing street you are not allowed to turn at. Making this even more interesting, consider that the via is a way, which may become 1...n edges in the graph. Currently, OTP does not handle via ways, nor does OSRM: Project-OSRM/osrm-backend#483.

However, as always, there is a solution to this problem as well. What we'll do is create partial turn restrictions. When you enter a partial turn restriction, a flag is set in the state, which is carried forward until you exit the turn restriction. If you exit the turn restriction in a way that is not allowed, that branch of the tree is terminated. This seems like a resource-limiting problem that would make the algorithm invalid, and, as formulated above, it is. However, we solve this by simply not allowing states that are in a partial turn restriction to dominate any other state. Since there are relatively few turn restrictions (about 1 million in the entire world), this should not cause the search to explode. In someplace like Lower Manhattan, we might need to make an optimization to handle the fact that most intersections have turn restrictions (I assume), but we can exploit the fact that almost all of them have a node as a via.

[mattwigway]

Turn restrictions are all working at this point, including ugly cases involving via ways (and even multiple via ways). Put that in your pipe and smoke it.

However, having working turn restrictions is creating a number of problems.

Exhibit A, in Pikesville, MD, at the intersection of the Baltimore Beltway and Reiserstown Road:

There is a no-U-turn restriction here, which r5 is honoring (confirmed by turning off turn restrictions and seeing that it makes the U-turn. This is a messy restriction because it has two via ways, but works as expected. However, the planner decides to take a shortcut through some nearby driveways. This is not completely unexpected, and indeed is something that @mattwigway would consider doing had he accidentally exited here. However, it's probably not something we should be suggesting.

Exhibit B, in Washington, DC, at Ward Circle (intersection of Nebraska and Massachusetts Aves NW):

You can't turn left from the inner circle onto Massachusetts from Nebraska (restriction), so the planner is obediently driving straight on. However, shortly past the intersection, there is a splitter vertex for a bus stop, which the planner is using to make a U-turn and come back at the circle. This is definitely super-illegal, as it's not an intersection and there's a double yellow line in the middle of the road.

It would seem like one option would be to prevent exiting a splitter vertex on the back edge to the edge you arrived on, but we can't actually apply costs/cutoffs at vertices like that. Suppose the right answer is to drive straight on Nebraska, go around the block, and come back at the circle:

Then the first state at the bus stop will dominate the second state coming back at it. The only way to do it right would be to create a bona fide no U turn restriction at every splitter vertex (actually two restrictions, one in each direction). This will create a ton of incomparable states, and may slow down routing (then again, it might not, and could be worth a try).

Finally, some good news. The planner has figured out that to turn left on Massachusetts, you need to use the outer circle, which is more than can be said for @mattwigway the first time he drove through this particular circle:

[mattwigway]

We need to add a large cost to a U-turn to prevent it from happening unless absolutely necessary, and an infinite cost to a U-turn at a splitter vertex. However, we cannot add costs to vertices in standard Dijkstra, so we need to switch to something akin to an edge-based graph, which we're doing in #84.

[mattwigway]

So turn restrictions are working in master. Currently they're only being applied to cars, but I suppose they should also apply to bikes. Although I'm not sure, since (for example for left turns) bikes have the option to make a pedestrian left instead of a vehicular left (and many riders always make pedestrian lefts anyhow).

[mattwigway]

I believe we still do not forbid U-turns at splitter vertices.