My city has huge blocks. One of them is 6km of perimeter! I want to make a map with the block polygons (and their sizes). One suggestion was to take the city boundary polygon and subtract a buffered version of the road network. So far more or less good.
The missing piece would be an algorithm to remove dead end streets, which are pervasive here, to the point you can find branches of several interconnected such streets in a tree like structure (no loops). I could do an algorithm that slowly removes them (for each highway section, take the end nodes; find other highways with the same nodes; if none, remove the section; if no new section was removed, stop; else repeat).
Notice I already have a rendering DB for this area, so reusing that data is why I propose that algo.
What I’m wondering if there is something that could already do this. I also accept alternative algorithms.
I also accept tags to use for this kind of queries :)
A couple of years ago, I had the task to generate a “city blocks” dataset. My solution was the same as yours: Use polygon and subtract buffers of the road network. I generated “builtup” area polygons derived from both buildings and landuse instead of using administrative boundaries because the latter includes unpopulated countryside.
You could use any routing engine to import OSM data into their internal graph storage and use their (likely non-public API) to remove dead-ends. For example, with GraphHopper’s Java API you can iterate over all nodes and look for nodes with are connected to one edge only. That would be brute-force but it is basically the entry point into working with the graph.
The backend of OSMI Routing uses GraphHopper to iterate over all nodes in order to test for all dead ends if they are close to other edges. OSMI Routing uses GraphHopper’s internal Java API for that purpose (we use a fork of GraphHopper with extended visibility for some methods). The EdgeExplorer and EdgeIterator interfaces of GraphHopper haven’t changed a lot between the GraphHopper version used by OSMI and current GraphHopper.
After removing all dead-ends, you can dump the graph as a GeoJSON (could be implemented without additional dependencies because it is plain text) or any other format (requires additional libraries).
You could use any routing engine to import OSM data into their internal graph storage
I forgot to mention I already have a rendering database of the area in particular. That’s why my proposed algo. But yeah, this is a good alternative because the routing DBs already make them 2 point vectors, not N point lines.
You can do this with a rendering database. Write a recursive CTE that selects all linestrings in a set that have two or more points where they intersect a geometry, including self-intersections. It should be reasonably fast as all the geometry calculations are trivial compared to modifying geometries. Figuring out the right DE-9IM conditions and handling self-intersections is left as an exercise to the reader.
Thinking about it a bit more you’d also have to turn the ways into segments with something like ST_DumpSegments. In the DE-9IM model the boundary of the segment linestring is the endpoints so you want to find how many segments each segment touches and filter out any which touch less than two other segments.
This will fail if you have an overpass as it will consider it a connection between the two ways.
It will also fail in some other conditions. If you have a way that looks like |--+--+-- where the left-right branch is all one way and the up-down branches go off to something that makes it unprunable, then the bit of the left-right way on the far right won’t get pruned.
You need to be able to prune parts of a way without pruning all of it.
Yeah, there are many corner cases. In the diagram above we have 4 segments of 3 roads (or they could be 4 if the N-S segments are roads with different names, but I don’t care about names).
If I’m counting how many roads a roads touches, 1 is not a good threshold because the northernmost road E-W touches two segments/roads; and
the southernmost road should have the segment bb-c eliminated but it’s all a single segment.
This process of elimination will take ages unless I find a heuristic, maybe looking at the segments within an area slightly bigger than the segment.
Thanks for the link :)