dabreegster
commented
1 year ago Research on planar graphs:
- https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cycles.cycle_basis.html
- https://en.wikipedia.org/wiki/Cycle_basis
- https://github.com/ammanvedi/planar-face-discovery
- https://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf
- https://github.com/Hermann-SW/planar_graph_playground
- http://lin-ear-th-inking.blogspot.com/2023/03/simplifying-polygonal-coverages-with-jts.html
- http://lin-ear-th-inking.blogspot.com/2022/07/polygonal-coverages-and-operations-in.html aka polygonal coverages
https://user-images.githubusercontent.com/1664407/200342459-492e0fb0-2936-4a6c-9ed6-4f6794a1a775.mp4
This is a quick prototype in both https://github.com/a-b-street/abstreet/tree/snap_areas and https://github.com/a-b-street/osm2streets/tree/snap_area of turning a free-hand polygon into an LTN-like area boundary. The algorithm is simple: snap each point in the polygon to the nearest intersection, then find the shortest driveable path between each pair of intersections. The result has issues, but looks promising. (I started looking into the hidden markov model based snapping, but I think it's overkill right now.)
This has a few related uses...
1) As an optional tool to help authorities sketch area-based proposals in https://github.com/acteng/atip 2) As a simpler and less buggy UX for customizing boundaries in the LTN tool. #857 3) As a way to future-proof the LTN save file. We reference OSM IDs today, but roads can be split, breaking the format. Saving a polygon and re-snapping it later seems more robust. #995
Planar graph
Optionally, we could snap to water boundaries. In practice we needed to do this in Bristol already: #916. The perimeter of an LTN is not always driveable or connected/a loop in practice. (But when it's not, reasoning about displaced traffic is harder!)
Going further, half the headaches in #857 are caused by bridges/tunnels. What if we just... use the planar graph to snap. So bridge/tunnel crossing points would be vertices in that graph, and people could trace along things sanely. This'll require re-thinking the current
Perimeter/Blockabstraction. It's based on individual lanes right now, not even entire roads! IIRC, that was partly due to ambiguity in figuring out the interior vs exterior of a polygon. Why can't we just start flooding both directions from an intersection on the perimeter, do a point-in-polygon test, and halt the wrong side?Partitioning
I think in the LTN tool it's still confusing if two neighbourhoods physically overlap. So we probably need to keep the current partitioning mess. That has hard-to-solve bugs with holes and stuff, but maybe we can figure out a simpler workaround.