Intersection geometry refactor about osm2streets HOT 15 OPEN

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.

from osm2streets.

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.

from osm2streets.

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).

from osm2streets.

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.

from osm2streets.

#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.

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.

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.

from osm2streets.

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.

from osm2streets.

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.

from osm2streets.

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.

from osm2streets.

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

from osm2streets.

I hope the barrage of changes isn't hard to follow and that the resulting code is much simpler. My next steps are roughly:

• to fix a few tests that've regressed since placements -- northgate, tempe, and all the loop road cases. Hopefully the fix will illuminate some important aspect of this process that's missing
• try a few experimental ideas (like extending road edges if they don't originally collide)
• more refactoring without behavioral changes
• and finally, removing the transformation and instead always updating the center line when relevant

from osm2streets.

@BudgieInWA, I started figuring out how to finally achieve the goal of always maintaining trimmed roads and real intersection polygons, from the start. At a high level, I imagine we would:

1. Give StreetNetwork a method fn regenerate_geometry(&mut self, i: IntersectionID). It would trim all roads attached to this intersection (updating center_line) and recalculate the intersection polygon.
2. We decide where to call this. Maybe we don't call from insert_road to make the initial construction case less crazy, but call for everything at the end of streets_reader/src/split_ways.rs. Then everywhere that we modify reference_line or lanes_ltr or otherwise create/modify/delete stuff, we call this method to keep things consistent. We can play around with the exact API to make it low-effort to figure out when to recalculate stuff.
3. We get rid of transform/intersection_geometry.rs entirely. Current hacks to call this to render debug steps go away, as do methods like estimate_trimmed_geometry and untrimmed_road_geometry. A transformation can always use the reference line or the current trimmed road to decide stuff like length.

The complication is how to implement regenerate_geometry(intersection). The input into the algorithms right now must be the untrimmed road centers. That's why we call update_center_line at the top of the transformation, to reset everything. The complication is that we trim every road twice, once for each intersection. In other words, we can't call update_center_line before calling intersection_polygon -- that would erase the work from one side of every road. That leaves us with some options...

1. Relax the requirement that the geometry algorithms receive untrimmed input. I think this would make writing them harder, because sometimes nice corners between adjacent road edges will happen, but we also have to handle when roads have already been trimmed back.
2. Don't reset and call update_center_line. Remember whatever the previous trimmed line is. But do pass in untrimmed road centers to every intersection_polygon call. When we get the result, it's only trimmed on one side. We have to then use the previously trimmed center and change one side of it (the side of the intersection we just calculated). I think it's mostly easy, except for cases where we lengthen a road.
3. Use untrimmed centers as input. Instead of producing trimmed PolyLines, change all the algorithms to produce trim_start and trim_end distances. This complicates the algorithms substantially (they've now all been rewritten and simplified, and I still think this is true). Alternatively we could try to calculate the distances after getting back the polyline. I think this is kind of logically equivalent to idea 2.

The "glue two versions of a trimmed center together" logic is kind of started in main...geom_use_untrimmed_line_for_algorithm, but I hit problems there. It was before simplifying all the algorithms, so I'll have another go.

Any feedback/ideas about any of this?

from osm2streets.

Argh, there's a subtlety to passing in totally untrimmed (on both sides) centers. We were getting lucky sometimes near clipped borders. When we happen to clip a road and make it way too tiny, we were extending it. That often helped geometry for the other side.

I'm reconsidering whether extending a road's center line is a good idea at all now. Maybe we need to do #127 first and clip roads more carefully. There's a decision about how we represent roads that're MapEdges at one end. When they happen to wind up super super tiny like this, they mess up the other intersection they're attached to.

from osm2streets.

Ideas from the call:

• clip roads exactly to the boundary. then extend by width (to make the square) for map edges. Drawing the borders outside the clip will be more clear, and it'll break the other end less often
• for terminii: extend by half-width, make the square centered on that. like an endcap.
• do try to explicitly use trim_start and trim_end
  • the algorithm takes in untrimmed polylines, trims one end. the outer piece calculates the length change.
  • the outer piece can detect when a road gets totally destroyed. keep both polygons, untrim that short road entirely, mark it for merging

from osm2streets.

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.

from osm2streets.

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.

from osm2streets.