Intersection geometry refactor

[dabreegster]

There are a few ideas rumbling around for improving intersection geometry code. The current thing is quite a scary mess. In some first attempts to detangle it, I think I've found some smaller cleanup steps that should happen in some order first.

• Work in-place, instead of taking InputRoad and returning Results. Every road should have start and end trim distances, which can both be passed in (the results from the previous round) and modified by the algorithm.
• Remove intersection.point; it's a meaningless field after the first transformation. We can set the initial intersection polygon guess to be a circle there, maybe.
• Get rid of trim_roads_for_merging and instead store start/end trim distance on every road
• Dedupe RoadLine, Piece, and maybe Edge from Start rendering sidewalk corners. #130.

I think some/all of the above should happen before we attempt to remove the intersection geom transformation and instead always keep things updated as we make mutations elsewhere in the codebase.

More dramatic ideas:

• Radically simplify generalized_trim_back. We should only look for collisions between adjacent pairs of road edges.
• Revisit the whole second_half mess and the problems with two polylines hitting each other at multiple points
• Get rid of the deduped.sort_by_key stuff at the end if possible. See what tests break without it. We should be able to produce the polygon points in the correct order, if our input roads are sorted correctly.
• Make the pretrimmed_geometry case less weird. Maybe take the main algorithm and first go update trim_start and trim_end everywhere. Then have a second method that just produces the polygon from that.
• Reconsider what we do for deadend intersections in general and simplify that method
• Think through on_off_ramp from scratch. Maybe this is triggered by IntersectionKind now and has nothing to do with highway type. Maybe there are better ideas to generate the geometry here.

[BudgieInWA]

Without knowing the details of the current algorithm, I am heartened to read these individual points, because a lot of them make sense to me! That first list of steps all sound great to me (though I can't comment on RoadLine, Piece, or Edge) and iterating within the current transformation structure sounds sensible too.

I'm imagining one PR that adds trim_start and trim_end to Road, calculates it for the full network before any Intersections are merged, (by only considering adjacent Roads) and having the intersection geometry just use trim_start and trim_end. Transformations should only ever increase trim distance for now - Intersections will draw lane markings to compensate for some overly large trim distances.

I like the idea of different IntersectionKinds having different geometry algorithms.

I'm viewing the on_off_ramp as a special case of intersections drawing major movements: there are only major movements! Connection is the simplest case because all movements are guaranteed to be major. True Forks should be similar (but note that we currently classify some intersections with minor movements as Fork because we're not looking at individual lanes or yield signs to tell if someone gives way). In order to determine major movements we need to determine the lane connectivity, which is a whole journey to go on, but necessary.

[dabreegster]

and having the intersection geometry just use trim_start and trim_end

It's maybe a minor point, but as we keep trim_start and trim_end updated, should we recalcuate trimmed_center_line and the intersection polygon? In the spirit of keeping data synchronized, probably so, but just clarifying the idea

we need to determine the lane connectivity, which is a whole journey to go on, but necessary.

I think we'll want to do this anyway for #67. I certainly need lane-level routing even in non traffic sim applications. If we didn't care about it, all the lane-level turn restrictions wouldn't even be necessary to track! The big complication here in my mind is about lane-changing, but likely this is one of those weird legacy traffic sim-centered assumptions that we'll revisit and come up with a much simpler idea.

[BudgieInWA]

It's maybe a minor point, but as we keep trim_start and trim_end updated, should we recalcuate trimmed_center_line and the intersection polygon? In the spirit of keeping data synchronized, probably so, but just clarifying the idea

I think so, yeah. I'm conceptualising the derived data as being updated immediately, but am constantly thinking about ways to delay the actual calculation too. So anything in the public API should cause derived data to be updated straight away, but there should be some other mechanism for transformations to use that is more efficient. The idea of doing an entire transformation all at once is powerful I think:

1. Detect all the changes that should take place
2. Perform all the modifying operations without updating derived data
   • mark all modified roads and intersections as "dirty" as you go
3. Recalculate derived data for all dirty objects, (in the same way that it is calculated when StreetNetwork is being constructed).

[dabreegster]

I have a few branches going with some big cleanups here! Hoping to have a PR out by end of Friday. I started from scratch with the intersection trimming algorithm and arrived at something a bit simpler than the current mess, but only by a little. Some of the complexity there seems to be inherent. But lots goes away if we just trust that roads are coming in already sorted clockwise.

[dabreegster]

#140 is an uncontroversial start. I have a handful of experiments that I wanted to rubber-duck talk through...

simplify_intersection_geom

https://github.com/a-b-street/osm2streets/tree/simplify_intersection_geom starts deduping the code that generates the final polygon after something else trims back roads.

osm2streets/osm2streets/src/geometry/algorithm.rs

Line 467 in 20f36f4

fn finalize_intersection_polygon(

is hopefully easy to follow. This gets rid of lots of previous code that existed before sorting roads clockwise was stable. The complication comes from trying to keep intersection polygons "minimal". If we just use the endpoints of every road edge:

The corners are too bulky. Instead we want to use all of those places where two road edges were meeting at a point. Because of how I've refactored the code so far, holding onto those points in order is kind of complex. So this branch instead uses the trimmed road lines, continues the last line off to infinity, and looks for the collision point. Because of some cases I don't entirely understand yet, that collision can happen far away, so we restrict it to existing inside the thick first-pass polygon. The result is nicer:

But this corner-handling code breaks in a few places I need to work on more. Any thoughts about this strategy generally?

simplify_intersection_geom_trust_ordering

https://github.com/a-b-street/osm2streets/tree/simplify_intersection_geom_trust_ordering rewrites generalized trim from first principles.

osm2streets/osm2streets/src/geometry/algorithm.rs

Line 232 in 8e8eedb

fn generalized_trim_back_v2(mut results: Results, sorted_road_ids: Vec<RoadID>) -> Result<Results> {

is way simpler. We only need to look at adjacent sides of roads, find the collision point, project perpendicularly back to each road's center, and trim back the road accordingly.

maintain_trim_dist

https://github.com/a-b-street/osm2streets/tree/maintain_trim_dist gets rid of trim_roads_for_merging and adds fields to Road instead. The two complications with actually doing this so far are...

1. in some cases, we actually lengthen the center line! For handling short roads near the map edge, and for the on/off highway ramp case
2. Consistency. The intersection geom code has just been modifying the PolyLine. I'm not sure whether to calculate the changes to trim_start and trim_end later and update them, or to calculate those in the first place and always derive the PolyLine from it.

[BudgieInWA]

holding onto those [road edge intersection] points in order is kind of complex. So this branch instead uses the trimmed road lines, continues the last line off to infinity, and looks for the collision point. Because of some cases I don't entirely understand yet, that collision can happen far away, so we restrict it to existing inside the thick first-pass polygon.

That sounds like a sensible enough approach, though there are cases where it is not sufficient. Ideally, the generated section would follow the original edge geometry of the trimmed road until it meets the neighbouring road. Maybe that means the geometry should in fact be calculated at the same time as the trim distances are calculated, or that center_line needs remain untrimmed (even if it is shifted or otherwise modified).

On the other hand, it might be worth continuing with this approach, and allowing some intersections to have incorrect geometry at that stage. The smaller intersection area is useful as a conservative estimate of the are covered. I think we want to generate actual curb lines at a later stage, taking into account traffic paths, and generating curves.

maintain_trim_dist

Extending center lines past their original extent is a powerful ability, and pretty desirable in the long term, I think. This is the kind of thing that makes me want to treat center_line as the source or truth (at lease after some point in the transformation process), and not recalculate it from reference_line. Any subsequent transformations would need to update center_line appropriately, as well as reference_line (as long as that's still actually useful).

One approach to start with would be to not extend center lines and instead prioritise implementing the ability for intersections to draw lanes going them. Even when that is working, high on/off ramps will still result in huge intersections, but with lanes drawn appropriately through the whole thing, which might still be problematic for A/B Street.

[dabreegster]

I'm still puzzling through some of the changes from the placements PR. An example is bristol_sausage_links, where roads no longer meet the intersection polygon:

I've confirmed the problem isn't failing to maintain center_line state anywhere. The problem seems to be that the semantics of untrimmed_road_geometry have changed -- probably intentionally! If I force center_line back to the old definition, things are good again:

I'm fairly sure the problem is this:

The algorithm works by finding intersections between the corners of road edges. In the left case (good output, old code), the cyan line does intersect the horizontal road marked by green... just barely. In the right (bad output, new code), the cyan line is farther to the left and no longer hits that horizontal road. So we don't trim back for that corner at all, and the result is pretty broken.

One explanation is that previously we were just getting lucky. If our center_line is now closer to the true physical center, we need to deal with cases like this properly. I think in this case, a fix might be to use ignore the trim on the other side of each road. Aka, the ordering here happens to bite us. The green road happens to get trimmed on the left side first. If it didn't, when we looked for corners, the blue line would have a better chance of hitting something.

Unfortunately this means the multiple ideas for refactoring code will get a bit more complicated, but I'll try this idea out, see if it gets better results, and try to put all of the refactoring ideas together in a sensible order for reviewing.

[dabreegster]

Indeed this idea works. The complication is now that we mutate the center_line on each side, but lose one of the sides. In other words, this is a perfect argument to handling trim_start and trim_end and updating those independently. I'll try and do that now.

[dabreegster]

I rewrote the handling for dead-ends and map edges from scratch. It's much simpler now, and the square intersection shapes look nice. See https://github.com/a-b-street/osm2streets/blob/3f41273ab3a7a1ba079614f778c0b36dd113e732/osm2streets/src/geometry/terminus.rs for caveats. An example of winding up with too-short roads is:

I'm going to rewrite the degenerate handling from scratch now too, then tackle the harder generalized + pretrimmed cases. Will open a PR for anything non-trivial

[dabreegster]

I'm trying recent changes in A/B Street outside our test coverage area, and noticing some massive improvements! Before, some tiny roads have such broken geometry that they manage to disappear details of a cycle bypass:

After is much better:

I'm looking into why bus lanes disappeared; lane parsing hasn't changed recently.

[dabreegster]

https://github.com/a-b-street/osm2streets/tree/op_not_transform is an attempt to wrap up the hard remaining piece of this issue -- updating trims and geometry constantly, not as one big transformation pass at the end. It introduces regressions like...

seattle_slip_lane:

tempe_split:

But also makes some improvements, like no longer shrinking overlapping roads in perth_peanut_roundabout, because it merges a short road earlier:

The root problem is a big change in ordering of operations. Now we set internal_junction_road at the very beginning when roads get trimmed into oblivion. Previously, we had a chance to do some other transformations, like shrinking overlapping geometry, first, and so we detected a different set of short roads. Maybe now we need to consider undoing internal_junction_road = true if we no longer detect trim-into-oblivion after some transformations.

The new thing may be "correct" -- the regressions are in places where the current main behavior is OK, but still nowhere near correct. But the question about what order of running transformations and how to decide when to retry some transformations gets much bigger. Not sure what to do.