Line voronoi diagram and network voronoi diagram features

[ResidentMario]

By way of background, this feature request was spawned by work I am doing on analyzing a dataset of trash pickup locations in San Francisco. The fundamental problem with this dataset is that GPS coordinates are inaccurate, so the point data needs to be snapped to nearby linear features (streets, blockfaces) and polygonal features (buildings, blocks) for analysis. I started a discussion in the PySAL Gitter regarding the best way to approach a specific problem in this projection:

I wanted to assign each slice of street to a nearby building (within a certain tolerance), the idea being that this would allow me to map trash > street point > building, and say stuff like "cigarettes are 200% more likely to show up in front of a liquor store!". I was wondering if there was anything in the PySAL gamut that could help with this operation.

@jGaboardi helpfully replied with the following comment:

[...] please open an issue in spaghetti with this information and we can continue the discussion there.

My initial thoughts are that you may try:

• A line voronoi diagram derived from street segments as generators. When a building intersects a LVD cell it is assigned to the generator street. Or,
• A network voronoi diagram derived from building points (snapped to the network) as generators. All locations within a NVD cell (along the network partition) are assigned to its generator building.

[...]

Becasue there was no “easy access” LVD generator in python I build my own method for doing it which I am implementing in my dissertation. Happy share the method and details via libpysal/spaghetti once I get my dissertation finished.

This issue is that feature request for the following additional types of Voronoi diagram generation and point-snapping algorithms (in addition to the existing):

• Line voronoi diagrams
• Network voronoi diagrams.

[ResidentMario]

(apologies that this take so long to log to GitHub)

[jGaboardi]

@ResidentMario Thanks for logging this. Hopefully this will be something I can get started on in the next several months. It will be super exciting to have this functionality included in libpysal/spaghetti. In the meantime, if you have any ideas or contributions feel free to start a PR or post more thoughts in here.

@ljwolf @sjsrey @weikang9009 @knaaptime @renanxcortes @slumnitz In terms of network allocation methods, would having something like Line Voronoi Diagram generation make more sense in libpysal.cg or directly in spaghetti? My thought is probably in libpysal.cg. However, once I am graduated I want to also add the method for allocating populations to networks I propose in my dissertation. Whether this makes more sense in its own package or as part of spaghetti is something I would like to discuss/get other's opinions on. Any input is welcome.

[renanxcortes]

@ResidentMario Thanks for logging this. Hopefully this will be something I can get started on in the next several months. It will be super exciting to have this functionality included in libpysal/spaghetti. In the meantime, if you have any ideas or contributions feel free to start a PR or post more thoughts in here.

@ljwolf @sjsrey @weikang9009 @knaaptime @renanxcortes @slumnitz In terms of network allocation methods, would having something like Line Voronoi Diagram generation make more sense in libpysal.cg or directly in spaghetti? My thought is probably in libpysal.cg. However, once I am graduated I want to also add the method for allocating populations to networks I propose in my dissertation. Whether this makes more sense in its own package or as part of spaghetti is something I would like to discuss/get other's opinions on. Any input is welcome.

Yes, @jGaboardi, I think too that it probably makes more sense on libpysal.cg, since it already has the Voronoi polygon generation in https://github.com/pysal/libpysal/blob/master/libpysal/cg/voronoi.py

I mean... we could add voronoi_lines, for example in this script.

[ResidentMario]

If it's any incentive, I wrote a hacky single-use package called streetmapper to solve the problems that came up in this project for me. Once these features land in spaghetti, I'd love to rework that code to use these algorithms instead, and write an expository blog post on the subject in the style of Eli's "Neighborhood Segregation Dynamics" blog post. 🙂

[jGaboardi]

@ResidentMario streetmapper looks very interesting. Would you be able to include a rudimentary notebook demonstrating functionality?

[ResidentMario]

I could upload something to the notebooks/ directory, yes.

[jGaboardi]

Yeah, or even just a link to something (this is something for my own curiosity). The explanation and docstrings of streetmapper are super interesting. I would love to see a use case.

[ResidentMario]

Hi @jGaboardi, you weren't the only person to ask me this question, so I figured it was worth the time to write up a short blog post explaining how the streetmapper module works and my motivation for writing it: "Bringing together building, block, street, and point data".

This post links to the polished blog post with the analysis I used this library for as well as the repo with all of the raw code I wrote. Some of the use cases of having this point-to-line-to-adjacent-polygon algorithm on hand included:

• Does street trash volume vary significantly between businesses?
• Does street trash volume vary significantly with business type?
• Is street trash volume correlated with Yelp! ratings?
• Is street trash volume correlated with Yelp! stars?

[jGaboardi]

openvoronoi

[jGaboardi]

We may want to explore:

• migrating this to pysal/libpysal for inclusion in cg/voronoi
• implementing higher-order Voronoi diagrams with
  • momepy
  • geonetworkx

[jGaboardi]

380

[martinfleis]

I think that this is already implemented in momepy. Or at least most of it.

import momepy
import geopandas
from shapely.geometry import box
from mapclassify import greedy
from libpysal import examples

path = examples.get_path("streets.shp")
gdf = geopandas.read_file(path)

# fill study area with tessellation
study_area = box(*gdf.total_bounds).buffer(50)

tess = momepy.Tessellation(gdf, 'ID', limit=study_area)
ax = tess.tessellation.plot(figsize=(12, 12), edgecolor='w')
gdf.plot(greedy(gdf, strategy="largest_first"), ax=ax, categorical=True, cmap='Set2')

# limit to 150 feet from network geometry
tess = momepy.Tessellation(gdf, 'ID', limit=momepy.buffered_limit(gdf, 150), segment=10)

ax = tess.tessellation.plot(figsize=(12, 12))
gdf.plot(greedy(gdf, strategy="largest_first"), ax=ax, categorical=True, cmap='Set2')

It is not properly documented, but it should do what you are looking for.

[jGaboardi]

@martinfleis this is another great example for your push to standardize the network instances.

[martinfleis]

Which reminds me that on one end of the conversion pipeline should be non-graph geodataframe. Since the example above is using gdf, not graph.

[jGaboardi]

@martinfleis let's revisit this in the not-to-distant future.

[martinfleis]

My proposal is to move generic voronoi algos from momepy to libpysal.cg and document it all there. Those could potentially also take a graph as an input, but we first need the standard of storing edge geometries in a graph.