Intersection consolidation: geometry

[dabreegster]

There are some other issues already for merging short roads, but I want to dump some recent notes about the geometry problem in particular.

Current approach

Code at https://github.com/a-b-street/abstreet/blob/master/map_model/src/make/merge_intersections.rs

The RawMap produced from OSM looks something like this. The pink segments have been manually tagged by me as junction=intersection in OSM, which often requires splitting the way. It's not too hard to auto-detect these segments and avoid the tagging. The problem is that the current algorithm for consolidating these intersections breaks in most cases, so I'm using the tagging as a way to manually opt in a few cases that I've worked on and verified turn out reasonably.

The current algorithm will take each pink segment in a pretty arbitrary order and do the following. It'll delete the segment and one of the intersections (arbitrarily), preserving the other intersection. It takes all of the roads connected to the deleted intersection, and reassigns them to be connected to the surviving intersection. It does some work to preserve the various types of OSM turn restrictions, some of which are implemented, some not. But then it also modifies the polyline geometry of some of the roads, to account for the deleted segment. The animation explains best:

The top intersection was deleted, so those 3 connecting roads have their polyline extended to roughly cover the deleted segment.

Then we proceed with map generation as usual, and the intersection geometry algorithm described elsewhere sometimes produces something half-reasonable:

But often it does not:

New idea

Do we always want to extend the geometry of surviving roads by that one new point? Maybe we don't need to extend any polylines at all, or maybe we should only extend the ones of non-pink segments, aka, normal roads that'll survive this process repeating. Maybe we should move the last point instead of adding, or add all of the points of the short road removed.

I added 2 new enums to quickly explore all of these combinations. One example worked much better for the case above:

But applying that policy everywhere broke another case that was previously working:

So is there a way to identify when we should AddOnePoint and when we should ModifyWhichRoads::None?

Wild alternative number 1

I've probably tried some form of this in the past. Often the original intersection geometries turn out reasonably:

What if we used these to decide how much to trim back the surviving roads, then deleted the pink segments, did the turn restriction fixing, but didn't modify any geometry? And mark that these intersections were "pre-trimmed" and skip part of the intersection geometry algorithm, and just construct the final polygon.

If this even works, would it blow up with road widening?

Wild alternative number 2

https://wiki.openstreetmap.org/wiki/Tag:junction%3Dyes#How_to_use_on_an_area

There are a few different proposals for tagging intersections as areas in OSM. I haven't checked Overpass yet, but I'm pretty sure I've seen a few of these mapped before. This particular scheme is purely additive; it shouldn't break any existing OSM software. Maybe in these really hard cases, it'd be much faster to just draw the polygon by hand in OSM from satellite imagery, and make the importer understand these as overrides. Haven't thought through how that import would work. Also not sure what to do if abst infers very different road width than reality and winds up disagreeing strongly with the human-mapped polygon.

[dabreegster]

Alright this is pretty exciting. I got "Wild alternative number 1" pretty much working in https://github.com/a-b-street/abstreet/tree/consolidate_differently. There are some rough edges, but I'm convinced this is the way forward. I'm focusing on consolidating all the intersections in the Tempe map first, while not breaking anything in Seattle.

My plan:

• Fix a few Tempe intersections upstream in OSM; no amount of code can work around some of the weird mapping there.
• Just import that using the old/current code. There should be some improvements, maybe even a full day without gridlock.
• Fix some more stuff with the consolidate_differently branch: restore U-turn handling, figure out how all of this interacts with road widening
• Locally opt in more/all junctions in Tempe and try the old/new code. If the new code does much better, proceed.
• Sanity check the new code doesn't badly break existing Seattle maps.
• Regenerate everything with the new code, commit it.
• Tag more junctions in Tempe in OSM, regenerate.

Then assuming everything's good, lots of exciting cleanup:

• Improve the intersection geometry for the consolidated intersections; I'll describe the problem more in the upcoming PR, but there are visual "gaps" and the polygon's exterior isn't a proper Ring.
• Make Tempe the "level 1" for the traffic signal challenge
• Manually try to consolidate lots of intersections in some of the tricky Seattle maps, particularly downtown
• Revive the effort to automatically consolidate intersections by looking for roads shorter than some threshold. Then we can stop manually tagging junctions in OSM, if indeed the new algorithm is robust enough.
• Very cautious optimism here: if we can robustly consolidate intersections, then it's worth auditing all open issues and reviewing some design decisions / hacks that've been trying to work around this problem. Particularly some of the core sim logic is overly complicated to try to deal with short roads.
• Do we need uber-turn logic in simulations anymore?

[dabreegster]

Making progress here. Approximate next steps:

• Skip false dog-legs at dual carriageways like https://www.openstreetmap.org/node/496331163 and https://www.openstreetmap.org/node/3391701869
• Figure out why https://www.openstreetmap.org/node/53198133 looks fine after forcing a fake road edit; it regenerates the intersection polygon in some way that's better than the first time
• The merge near https://www.openstreetmap.org/node/53211693 is causing the get_slice_starting_at crash -- easy to repro and focus there, figure it out finally
• Make the map_editor's geometry preview match what the real import process does. We need to modify the roads twice (for both intersections) and in a matching order. Maybe just call InitialMap in map_editor, but also correctly update individual intersections?
• Then gradually rollout to all maps. https://www.openstreetmap.org/node/1885807871, https://www.openstreetmap.org/node/9261013193 were particular motivations originally
• Can we move an intersection after merging it?
• Revisit https://github.com/a-b-street/abstreet/tree/shrink_roads

[Robinlovelace]

Just had a quick look at the issues and possible solutions above. No specific input but just wanted to say big general 👍 on progress. The hardest problems in software are often the last ones to be tackled but seems there could be benefits of 'grasping the nettle' on this one. If you want any input from me, or before/after tests, happy to help.

[dabreegster]

I'm now enabling it for map, and aiming to gradually rollout to more! Been working on merging "dog-leg" junctions. Before:

After:

Before:

After:

Treating this as a single 4-way intersection instead of two 3-way intersections with a vanishingly tiny road in between is a vast win for things downstream: rendering, LTN blockfinding logic, simulation for vehicles to not get stuck, editing the traffic signal as one logical object, etc. I've made so many attempts at this kind of fix before, but the problem is that the fix works in some areas, and breaks badly in others. The difference this time around is that I've got a much smoother development workflow using the map_editor (with ~3s recompilation in release mode!!!) and a clear separation of "find a problematic area" and "fix it"

[dabreegster]

The next problem:

The blue road is short, we should be able to merge it. But if we try, intersection geometry crashes:

Can't get_slice_starting_at: PolyLine::new(vec![     // length 193.1375m
  Pt2D::new(669.682, 2846.0703),
  Pt2D::new(668.5644, 3039.2046),    // -1.1176000000000386, 193.13430000000017 (+ 193.1375m @ Angle(90.33154622249592 degrees))
]) doesn't contain Pt2D(669.7136, 2843.3807)

If we first delete the yellow road, it works fine. If I make the PolyLine routine not panic when given a point not on that polyline and just skip the process of pre-trimming the road, it looks like it works:

The road that can't be pretrimmed is the long vertical one:

We're trying to pre-trim it to a point a few meters above where my cursor is. That point isn't on the polyline, so we can't pretrim there. What's going on here?

[Robinlovelace]

Treating this as a single 4-way intersection instead of two 3-way intersections with a vanishingly tiny road in between is a vast win for things downstream: rendering, LTN blockfinding logic, simulation for vehicles to not get stuck, editing the traffic signal as one logical object, etc.

Win-win-win-win solution!

[Robinlovelace]

We're trying to pre-trim it to a point a few meters above where my cursor is. That point isn't on the polyline, so we can't pretrim there. What's going on here?

Not sure, could spout some suggestions but don't feel well enough informed to do so at this point.

[dabreegster]

I don't understand the pre-trimming crash at all, but I think I'm going to take the easy way out for now, avoid crashing, not pre-trim, and just plow forward. It works in this case:

and we've been doing it all along for editing roads near merged intersections: https://github.com/a-b-street/abstreet/blob/efe5f76bbe0ee804fcbd31dbee8de146e8e05b35/map_model/src/edits/mod.rs#L622

Now attempting to roll out the de-dog-leggification to all maps...

Also, another good before:

After:

[dabreegster]

Not sure, could spout some suggestions but don't feel well enough informed to do so at this point.

Feel free to, but no pressure. https://a-b-street.github.io/docs/tech/map/geometry/index.html#a-solution-two-passes describes what's happening here. It takes me about 3 days of full concentration to shove all of this back into my head; I don't find it simple. :\ Which is partly why progress is so slow.

[Robinlovelace]

Also, another good before:

After:

So good to see!

[Robinlovelace]

It's pretty intense computational geometry going on here! Over my head and above my pay grade. Could help drum up interest in a call out to computational geometers interested in programming on Twitter and other platforms if that becomes appropriated at any point. As with many domains of human interest, there's a surprisingly large community of them, not least the 100s of people involved, directly and indirectly, to CGAL: https://www.cgal.org/people.html and the source code: https://github.com/CGAL/cgal People love a challenge.

[dabreegster]

More motivation why this has downstream effects. When the geometry is broken enough, the LTN tool can't trace blocks, and the whole idea just kind of keels over. This is a "base" problem I've been trying to solve more robustly since forever. Before:

After:

Note the line artifact exploding out.

Also, I declared victory too soon -- many map crashing trying to use this new code. I'll keep iterating...

Could help drum up interest in a call out to computational geometers interested in programming on Twitter and other platforms if that becomes appropriated at any point

That would be fantastic, but let me split out the code / problem first: #3. The first steps I took yesterday towards this were what let me make progress today.

[Robinlovelace]

Awesome. Interested to see what happens when a call out to the computational geometry community is made, will let you take the lead on that but of course happy to help out where I can.

[dabreegster]

Next thing to fix is merges near roads that loop, like https://www.openstreetmap.org/way/26815503 and https://www.openstreetmap.org/way/13868806