Just some Cincinnati-themed output from some work I’ve been doing recently… this is a map of the percent of streets, by length, which are dead-ends (for cars).
Data is from OpenStreetMap. The darker area on the map is defined by a street density of greater than 4km of roads per km2. The X and Y scales are in kilometers. Now a few other random cities for comparison. Smoothing was done with circular gaussian kernels with a standard deviation (bandwidth) of 2km.
Atlanta:Cleveland:Much more on this to be presented at the NACIS 2016 annual meeting this October!
931 miles that go nowhere, versus 2,761 that offer escape from either end.
For bikes at least, not that routing for other modes would change the figure much. Fun/disturbing fact of the day! Impress your friends with your amazing and mathematically informed knowledge of Cincinnati geography!
I talked about this geography of connectivity thing a little bit already, but since that post, I’ve switched to a better dead-end-finding algorithm. Where before I was looking for tree-like structures by recursing on nodes with only one edge, I’m now able to detect all nodes which could be removed from the graph‘s largest biconnected subcomponent by the elimination of just one edge. Or those which are already detached, of course.
In layman’s terms, this answers the question: “Where should we put no-exit signs?” Or for the purpose of defending our titular statement: “what portion of streets, measured by their length, would be behind such signs?”
Here is the PHP script I wrote to implement the algorithm. It connects to a PostgreSQL DB, and looks at a specified edge table with source and target fields. (These source and target fields are the IDs of the nodes on either end of the edges.) You can create an edge table, as I did, using OSM data processed with osm2po. Since I was routing for bikes, I excluded highways and most trunk roads. I also excluded dangling service roads from the measurement.
As the script runs through the graph, every time it isolates a subcomponent, it inserts the nodes of that subcomponent into a temporary table, along with a unique ID value for the component. Once all the nodes are in there(technically, they’re all part of some subcomponent), a GROUP BY statement gives us the ID of the biggest component. This component is the main street network itself. All edges that touch any node that is NOT part of this largest component are identified as dead-ending.
Before altogether too long, I’ll get around to doing some more interesting analysis and regional comparisons and mapping and stuff. But for now, I’m off to Europe with my little netbook, which is, to my honest delight, too puny for serious GIS.
I was trying to de-clutter a streetmap I’m making and I found some interesting patterns along the way :-)
Cool colors are areas with more dead-ending street segments and warm colors indicate more connected streets than otherwise. That big top blob is Dayton, the lower Cincinnati sitting on the Ohio River. Disconnected streets simply cancel out connecting streets, so you can sort of consider this corrected for density.
Here is the relative intensity of dead-ending streets by themselves:
Since most streets connect to others at both ends, the inverse of the above map doesn’t show much that the first one didn’t. It’s interesting to note the distinctly different patterns here. Clusters of connecting streets, many of their more intense appearances in gridded arrangements, form relatively distinct places. You can easily make out Hamilton, Middleton, Richmond or Oxford in the first map if you know where to look. The disconnected streets though seem to really blur recognizable places, totally changing the shape of Cincinnati and smearing it into Dayton, a visible connection not so apparent in the first map.
What’s going on in Kentucky? The rural area south of Cincinnati is a lot hillier than that to the North and there are a lot of long streets that branch out along the tops of hills and then end where the hills themselves do. In flatter places, such streets would pretty naturally just continue straight on until they met the next road.
Since you’re probably wondering if you made it this far just what counts as a connecting street, it’s a segment that connects to another at both ends. In fact, here they are below. You’re gonna want to click the image for the full resolution. Red is connecting, blue unconnected.
- Create a routable topology from OSM data using osm2po.
- Identify dead-ends recursively:
- Identify nodes(‘source’ & ‘target’ fields) that are connected to only one edge
- Identify the edges that are connected to those nodes
- Isolate those edges from the rest of the network and recurse until everything you have left is connected at both ends. This took me about 20 iterations for this dataset and identified ~81,000 segments out of ~300,000
- Create a centroid geometry from the linear geometry of the edges
- Calculate a weight for each edge as it’s distance in miles, signed negatively for the dead-ending segments identified in #2
- Compute a kernel density surface using the centroids and weight values. I used an 8KM radius, and tri-weight kernels with the QGIS raster plugin which I think is simply a GUI for GDAL.
And then I made it kind of pretty :-)
- Some very long dead-ending segments appeared around the edges as a result of clipping the original dataset out of it’s global context. Concentrating their weight in a centroid resulted in strongly negative spots which simply shouldn’t exist.
- Lines that turned back on themselves, or sub-networks of streets which where ultimately connected to the main network by only one edge, and which may thus reasonably be considered entirely dead ends were not identified at all.
- OSM data in the US is mainly derived from low-quality TIGER data that was imported several years ago. Many rural areas seem to have an enormous number of driveway type paths identified, many of them mislabelled as residential streets. There are also some places where actual suburban driveways have been identified as dead-ends, which may or may not be misleading to some degree. Most of these however are very short and so their weight shouldn’t be overwhelming. Though that huge negative area West of Dayton is Brookville, where someone seems to have added driveways for every house in town.