Improve the detection of interior vs perimeter roads

[dabreegster]

ltn/backend/src/neighbourhood.rs

Line 48 in dd8ee47

let mut interior_roads = BTreeSet::new();

Given a polygon boundary, we need to find all of the roads inside that boundary, and all of the roads bordering it. This quasi-works today, but there are some issues:

• The line_in_polygon code is convoluted and should probably be re-thought from scratch, especially given new things like ioverlay
• The checks are noticeably slow for large areas (10s for Manchester centre)
• False positives and false negatives below

Two E/W streets are missing, but should be interior roads.

When perimeter roads are enabled for analysis, they should all appear and be clickable. There's some missing in this screenshot.

And some false positives here -- the highway shouldn't count. This is maybe a bit of a weird case, because the boundary was originally built using part of the highway.

[michaelkirk]

I'm looking into this - just posting my notes as I wrap up for the day.

assumption: to be editable, roads must be LineInPolygon::Inside - is that right?

I've verified that the missing roads (e.g. East Gwinn Place from your screenshot.) are missing because they are being classified as LineInPolygon::Cross { percent: 1.0 } rather LineInPolygon::Inside.

I can easily make that change to convert LineInPolygon::Cross { percent: 1.0 } to LineInPolygon::Inside. Interestingly that'd basically be a revert of 8bc4f2f

But when I do that, another problem appears: I start to see a bunch of spurious "border crossings" (what do you call those?). Maybe that's what 8bc4f2f was intended to fix?

e.g. along Harvard on the left border - I marked them with pink stars.

This stuff is pretty touchy, so I'm mostly gathering test cases to at this point to understand what we expect to happen. You can see them here: https://github.com/michaelkirk/ltn/pull/new/mkirk/improve-roads-in-boundary

[michaelkirk]

assumption: to be editable, roads must be LineInPolygon::Inside - is that right?

I was wrong!

    pub fn editable_roads(&self) -> Vec<RoadID> {
        if self.edit_perimeter_roads {
            self.interior_roads
                .iter()
                .chain(self.crosses.keys())
                .cloned()
                .collect()
        } else {
            self.interior_roads.iter().cloned().collect()
        }
    }

Ok, that explains some things. It looks like we're using crosses kind of as a synonym for perimeter, which doesn't make sense for a road like Gwinn. I have some ideas for how to improve this.

A radical question: what if we got rid of the "include perimeters" button and just always included the perimeter? Can't the user just choose to not edit it?

[dabreegster]

Ok, that explains some things. It looks like we're using crosses kind of as a synonym for perimeter, which doesn't make sense for a road like Gwinn. I have some ideas for how to improve this.

Correct. The goal is to detect 3 things:

1. border intersections right on the perimeter (shown by arrows, used for shortcut calculations)
2. strictly interior roads (always editable)
3. perimeter roads (should generally be parallel and close (perpendicularly) to the boundary polygon's exterior linestring

The crosses case was an early attempt at dealing with interior roads that cross the boundary very slightly. It wasn't really meant to handle perimeter roads, which should be parallel to the polygon and could physically be fully inside or fully outside or a mix. What's more important in distinguishing them, I think, is how closely the linestring is parallel.

what if we got rid of the "include perimeters" button and just always included the perimeter? Can't the user just choose to not edit it?

I don't think so. The shortcut algorithm looks for all entry/exit pairs (from border intersections), then calculates the shortest route between them restricted to the interior roads. If perimeter and interior roads were always treated the same, then we'd lose information about how somebody might try to cut through when the perimeter roads have traffic. The "include perimeter roads" is a bit of an experiment still, but the purpose is to let people add filters (often bus gates particularly, because main roads often have bus routes) and change one-ways right next to the neighbourhood they're working in. There are some issues I can dig up later with more context.

[michaelkirk]

Thank you for the clarifications - this mostly all makes sense.

The shortcut algorithm looks for all entry/exit pairs (from border intersections), then calculates the shortest route between them restricted to the interior roads.

In general interior vs. exterior and neighborhood building seems to work much better in the legacy app.

Does the legacy app have this "include perimeter" functionality? I can't seem to find it.

[dabreegster]

The legacy doesn't have the option to include perimeter or not. It works much better, because the neighbourhood definition works fundamentally different. In the old version, there was code to trace around one "city block" at a time and make a polygon out of it, tracking the road IDs involved on the way. Adjacent blocks could be merged together by lining up road IDs. By the end of the process, the road IDs on the perimeter of the block could be main roads or whatever else the user wants, and the blocks correctly tracked interior roads, intersections, and the perimeter. https://github.com/a-b-street/abstreet/tree/main/blockfinding

That approach worked fine for simple cases, but it had a bunch of bugs that I gave up on trying to fix. Non-planar graphs, with bridges/tunnels crossing but not having an intersection, broke. Brittle osm2streets-based geometry broke. It was also not future-proof to OSM data changes, because it was tied to particular road IDs. So in the new version (there were some intermediate steps leading to this), I started over with a tool just worried about drawing polygon boundaries that was already working well from other projects. And in theory, it ought to be easy to geometrically recover interior and perimeter roads just from the polygon shape

[michaelkirk]

Thanks for the explanation. It makes sense why the old approach is kind of a dead end.

However, the new approach puts us in the scary world of finite floating point topology calculations (👻), which is it's own can of worms. At least it seems like there's a way forward here, but I'm not sure yet how much work it'll be to "solve" this. I'll keep plugging away at it!

should generally be parallel and close (perpendicularly) to the boundary polygon's exterior linestring

I believe I have a good algorithm (theoretically) for this part now:

Essentially, we slice out a subset of the boundary's exterior (inserting new vertices as necessary) that are closest to the road, and take the frechet distance.

But I'm still not seeing the results I want. I'm going to continue debugging today.

[dabreegster]

we slice out a subset of the boundary's exterior (inserting new vertices as necessary) that are closest to the road, and take the frechet distance.

This sounds reasonable to me. I recently explored this in a different project and had somewhat good results by:

1. line-splitting the longer line (polygon boundary here) to match the two endpoints of the smaller line: https://github.com/nptscot/match_linestrings/blob/ca052f48f4775a5bd6376f80acc7fddc0a03da20/match_linestrings/src/lib.rs#L213, using a copy of LineSplit trait georust/geo#1050 that's in the utils crate
2. Checking distance between midpoints of the two linestrings and angle: https://github.com/nptscot/match_linestrings/blob/ca052f48f4775a5bd6376f80acc7fddc0a03da20/match_linestrings/src/lib.rs#L151

I played with Frechet distance in https://github.com/dabreegster/georust-tester a bit, but I still don't have an intuition what it does -- find the farthest distance between two linestrings?