Recently, I created an Edge Network Voronoi Diagram that partitions Chicago's walkable network into sets of street segments with a shorter walking distance to a particular 'L' station than any other. In other words, given a location along a street, alley, park pathway, etc. somewhere in Chicago, you can find the nearest 'L' station to that point by foot. Click here to view the final visualization over an interactive map of Chicago. Read the repository's README to learn more about the project, including issues and plans for future work. In this blog post, I will explain how I computed the Edge Network Voronoi Diagram using Python.

Gathering the data¶

First, I downloaded a list of CTA 'L' Stations, which can be found on the Chicago Open Data Portal, and loaded it into a pandas DataFrame. Stations serviced by multiple lines appear multiple times in the dataset, so I removed any duplicative records. The Location column provides the geographical coordinates of each station as a string formatted as "(lat, lon)".

I'm not sure precisely what part of a station the coordinates represent: perhaps its "average" location? Each station in the dataset includes only one location, so the points don't necessarily represent the locations of the station entrances. This is important to keep in mind during the analysis. Some stations have multiple spatially distributed entrances. The Damen and Paulina entrances to the Illinois Medical District station on the Blue Line are half a mile apart, for example. Having easy access to an auxiliary entrance could impact which 'L' station is nearest to you. I plan to address this issue in future versions of the map.

Next, I downloaded the walkable street network for Chicago and surrounding suburbs using OSMnx, a Python package for downloading street networks, political boundaries, and building footprints from OpenStreetMap's APIs. The package leverages NetworkX to allow you to easily model, visualize, and analyze complex street networks. The author, Geoff Boeing, provides a good introduction to using OSMnx in this blog post.

I downloaded the network for a rectangular region encompassing Chicago and all of the suburban 'L' stations. I also downloaded the networks for specific cities and villages in Cook County, including Chicago, Evanston, Skokie, Lincolnwood, Rosemont, Norridge, Harwood Heights, Forest Park, Oak Park, and Cicero. I computed the initial Voronoi diagram on the larger rectangular region first and then restricted the final network to Chicago and those suburbs. Had I computed the Voronoi diagram on just the municipalities of interest, then the Voronoi cells on the periphery of the network might not be true to life: sometimes the shortest path to the 'L' involves walking on streets outside of the restricted network. I chose to include each of the listed municipalities in my final analysis in order to avoid holes in the diagram (Norridge, Harwood Heights, Lincolnwood) or because it has at least one 'L' station and several nearby. I didn't include O'Hare Airport or Wilmette in the final diagram, even though both places have an 'L' station, since the Voronoi cells around each station would be large, and they wouldn't add much value to the analysis. Most people probably don't access the O'Hare station from the street and the Linden station is fairly isolated in Wilmette.

Downloading all of these networks and generating the corresponding Python objects could take 10-20 minutes, so make yourself a cup of coffee, do the dishes, and come back in a little bit.

Open Street Maps data is constantly being updated thanks to a dedicated community of contributors. The result of a query made now might not be the same in an hour. I saved the network data as a GraphML file, so I can extend or tweak my analysis later on a consistent set of data. Also, it helped not to need to download the data again in the event of a mistake.

Computing the Node Network Voronoi Diagram¶

Once I gathered all of the necessary data, I used the station coordinates to identify the nearest nodes in the network to each 'L' station. These nodes served as the seeds for the Voronoi partitioning. Since the seeds corresponded to the nodes nearest to the stations, and not the stations themselves, they were sometimes located in an alley or road off of the main street. On the map, this is most evident at the 35th-Bronzeville-IIT Green Line Station. The station's seed is in a nearby parking lot, which causes the cell for the (very nearby) Sox-35th Red Line Station to encroach on the Green Line station's actual entrance. I plan to improve the accuracy of seed selection in future versions of the map.

The NetworkX package comes with a number of algorithms, including one to compute the Voronoi cells of a graph! Given a graph and a set of center nodes (seeds), nx.voronoi_cells returns a dictionary mapping center nodes to the set of all nodes in the graph closer to that center node than to any other with respect to the shortest-path distance metric. Shortest paths are calculated using Dijkstra's algorithm. The values of the dictionary form a partition of the nodes of the graph called a Node Network Voronoi Diagram (NNVD).

I eventually want to partition the graph edges (street segments) by nearest 'L' station. That is, I want to compute the Edge Network Voronoi Diagram (ENVD) of my street network. I will explain how to do this in a moment. In anticipation of that goal, I modified the source for nx.voronoi_cells to also return the lengths of the shortest paths between each node and its corresponding center node. I also included the sequence of nodes constituting the shortest paths (geodesics) in the return statement, so I can plot them later.

So first, I computed the Voronoi diagram on the full network.

voronoi_cells stores the nodes that are unreachable from any of the given seeds in the cell dictionary under the key "unreachable". I deleted these nodes from the dictionary and the final network. I also filtered the Voronoi cells dictionary so the partitions only contain nodes that are in the final network.

In order to visualize the NNVD, I needed to plot the nodes and color them. To distinguish between cells, I wanted to color them such that all nodes in the same cell have the same color and that no two adjacent cells use the same color. I determined which cells are adjacent to each other by iterating the network edges and checking which cells the to- and from-nodes belonged to. If the nodes were partitioned into different cells, then those two cells are adjacent and should be colored differently. I kept track of cell adjacency by building an adjacency graph.

A successful graph coloring should use as few colors as possible, both for aesthetic and accessibility purposes. Thankfully, NetworkX also has an algorithm for generating graph colorings! The function nx.coloring.greedy_color attempts to color a given graph using as few colors as possible, such that neighboring nodes do not share the same color. The strategy argument determines the order in which the nodes are colored. By default, nx.coloring.greedy_color uses a "largest first" strategy, which colors the nodes with the most connections first.

nx.coloring.greedy_color returns a dictionary mapping nodes in the adjacency graph to integers (which can later be assigned colors). Next, I constructed a dictionary mapping each node in the street network to the integer/coloring assigned to its cell.

OSMnx's plot module has a number of useful functions to help you plot and style your street networks. For example, ox.get_colors returns an n-length list of colors from the given colormap, which I used to assign Hex color codes to integers. Here's a look at the NNVD restricted to just Evanston. The larger nodes correspond to stops along the Purple Line.

Creating the Edge Network Voronoi Diagram¶

Now comes the fun part! The previous steps partitioned and colored the network nodes (i.e. street and alley intersections) based on the nearest 'L' station. That's great, but the diagram would be even better if the street segments were partitioned into cells and colored too. The next steps outline a process for doing just that.

I iterated the edges in the network and inspected their to- and from-nodes. Nodes partitioned into the same cell—which have the same coloring—should have an edge between them also with the same coloring. If the nodes do not belong the same cell, then some fraction of the edge should be colored the same as the to-node, and the other part of the edge should be colored the same as the from-node.

In the latter case, I calculated the point along the edge where the center nodes are equidistant—i.e. where the two partitions meet. At this distance, I cut the edge into two segments. The Shapely docs provide a recipe for a function that cuts a LineString at a specified distance. In order to "cut" the edge in the network graph, I had to delete the original edge and insert two new edges and two new nodes in its place. I added both new nodes at the point at which the original edge was cut, and I added an edge from the original to-node to one of the new nodes, and the other edge from the second new node to the original from-node. As I deleted and added new geometries from the network, I updated the list of nodes in the corresponding Voronoi partition, the sequence of nodes in the geodesic, and the length of the shortest path in the cells, geodesics, and graph_distances dictionaries, respectively.

Finalizing the map¶

I removed the unwanted edges from the final network graph and added the new nodes and edges.

I did the same with the original network, as it is needed later to draw the geodesics between nodes and 'L' stations in some cases.

Here's an updated view of the Voronoi diagram! The large black dots are the center nodes of each partition (the 'L' stations). nx.coloring.greedy_color almost found a four-coloring of the graph! Unfortunately, one of the cells was assigned a renegade fifth color.

Finally, I saved a number of files. I removed unwanted attributes from the graphs to help reduce the file sizes and saved the edited street networks as GraphML files.

I saved the Voronoi diagram as a GeoJSON, first converting the graph to a GeoDataFrame and dissolving the individual edge geometries into a single feature for each color in order to reduce the file size. The finished visualization renders the GeoJSON with D3/Leaflet.

I also saved the Voronoi cell data as Python objects with Pickle, so that I can plot and analyze the geodesics later.

Hopefully the steps to create an Edge Network Voronoi Diagram are straightforward to follow. Designing an actual process that worked was fairly complicated and took some tinkering, especially determining the best way to color edges crossing between partitions.

I hope to improve this map in the future so that the Voronoi cells are more accurate. In particular, I plan to choose more accurate center nodes for each 'L' station, as well as to add center nodes corresponding to alternate station entrances. I also hope to analyze the size and shape of Voronoi cells to see who in Chicago lives the closest to and further from the L and to see the impact of adding new stations, such as those outlined in the CTA's Red Line Extension project, to transit accessibility.