Move blockfinding algorithm to this library

[dabreegster]

Blockfinding = https://dabreegster.github.io/talks/aiuk_ltn/slides.html#/blockfinding, tracing around street-edges

This would have use in the urban morphology research community, and a simple API for them to grab polygons would be great. Just a reminder to myself to eventually do this.

[dabreegster]

I've been experimenting in https://github.com/a-b-street/osm2streets/tree/planar_graph_literally. It's a long way from working, and I think the resulting code belongs in a new repo, unrelated to osm2streets. Just want a place to vent frustration and share some progress. :)

screencast.mp4

How it works now:

• take all of the intersection polygons, thickened road polygons, and the boundary polygon
• turn those into each line segment
• find every pair of line segments that intersect, and split them (in a horrible brute force way)
• now we have a graph of nodes and edges. sort the edges around a node and track edges that have a left/right side and a forwards/backwards orientation
• it's fairly straightforward to then start tracing from every edge+side+direction and make a loop

There's a bunch of hacky UI code to do four-coloring, detect overlapping faces, nodes too close to each other, etc.

Current big problems:

• most maps wind up with one gigantic face covering everything. it's kind of valid/correct, maybe just tracing the boundary from the wrong side. I'm filtering it out just by checking for huge area
• most maps are missing some faces. we wind up with a bad Ring that doubles back on itself somehow
• borough by st george has a face that covers too much. there are very close nodes in there probably to blame.

I got very stuck for a while until I started aggressively reducing the resolution of points, 0.1m right now. Even now it doesn't work in some areas. The more funky geometry coming from osm2streets, the more points we wind up with very close together, and the harder it is to correctly trace faces in the planar graph

[dabreegster]

Alright, it turns out I've maybe been reinventing a wheel totally unnecessarily! MapShaper does practically all of the work:

1. Bring in road+intersection geometry and the boundary
2. Merge the two layers if needed (merge-layers target=Geometry,Boundary)
3. Turn line intersections into new polygons, handling all sorts of bridge/tunnel problems: mosaic
4. Four-coloring to visualize: classify non-adjacent save-as=fill colors=category10

Things to think about next:

• How can we use this from Rust? (Depending on the application of course. If I were to build a new version of the LTN tool that's web-native, for example, depending on the JS libraries would be fine.)
• Preserve properties per polygon or edge (so we know what a road, intersection, block spanning a bunch of roads, etc is)
• Figure out how to remove edges / dissolve adjacent polygons
• (More on the LTN side) Figure out what it means for a neighbourhood to not be bounded by roads necessarily. Still find the border intersections.

[dabreegster]

Preserving properties is taking some getting used to, but we can at least distinguish blocks from roads/intersections:
mapshaper lyon_geom.geojson -mosaic calc='overlap=count()' -colorizer name=showOrig colors='red,green,grey' breaks=0,1 -style fill='showOrig(overlap)' stroke=black -o format=geojson topo.json