{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Delaunay graphs from geographic points\n\nThis example shows how to build a delaunay graph (plus its dual,\nthe set of Voronoi polygons) from a set of points.\nFor this, we will use the set of cholera cases at the Broad Street Pump, \nrecorded by John Snow in 1853. The methods shown here can also work \ndirectly with polygonal data using their centroids as representative points. \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from libpysal import weights, examples\nfrom libpysal.cg import voronoi_frames\nfrom contextily import add_basemap\nimport matplotlib.pyplot as plt\nimport networkx as nx\nimport numpy as np\nimport geopandas\n\n# read in example data from a geopackage file. Geopackages\n# are a format for storing geographic data that is backed\n# by sqlite. geopandas reads data relying on the fiona package,\n# providing a high-level pandas-style interface to geographic data.\n# Many different kinds of geographic data formats can be read by geopandas.\ncases = geopandas.read_file(\"cholera_cases.gpkg\")\n\n# In order for networkx to plot the nodes of our graph correctly, we\n# need to construct the array of coordinates for each point in our dataset.\n# To get this as a numpy array, we extract the x and y coordinates from the\n# geometry column.\ncoordinates = np.column_stack((cases.geometry.x, cases.geometry.y))\n\n# While we could simply present the Delaunay graph directly, it is useful to\n# visualize the Delaunay graph alongside the Voronoi diagram. This is because\n# the two are intrinsically linked: the adjacency graph of the Voronoi diagram\n# is the Delaunay graph for the set of generator points! Put simply, this means\n# we can build the Voronoi diagram (relying on scipy.spatial for the underlying\n# computations), and then convert these polygons quickly into the Delaunay graph.\n# Be careful, though; our algorithm, by default, will clip the voronoi diagram to\n# the bounding box of the point pattern. This is controlled by the \"clip\" argument.\ncells, generators = voronoi_frames(coordinates, clip=\"convex hull\")\n\n# With the voronoi polygons, we can construct the adjacency graph between them using\n# \"Rook\" contiguity. This represents voronoi cells as being adjacent if they share\n# an edge/face. This is an analogue to the \"von Neuman\" neighborhood, or the 4 cardinal\n# neighbors in a regular grid. The name comes from the directions a Rook piece can move\n# on a chessboard.\ndelaunay = weights.Rook.from_dataframe(cells)\n\n# Once the graph is built, we can convert the graphs to networkx objects using the\n# relevant method.\ndelaunay_graph = delaunay.to_networkx()\n\n# To plot with networkx, we need to merge the nodes back to\n# their positions in order to plot in networkx\npositions = dict(zip(delaunay_graph.nodes, coordinates))\n\n# Now, we can plot with a nice basemap.\nax = cells.plot(facecolor=\"lightblue\", alpha=0.50, edgecolor=\"cornsilk\", linewidth=2)\ntry: # Try-except for issues with timeout/parsing failures in CI\n add_basemap(ax)\nexcept:\n pass\n\nax.axis(\"off\")\nnx.draw(\n delaunay_graph,\n positions,\n ax=ax,\n node_size=2,\n node_color=\"k\",\n edge_color=\"k\",\n alpha=0.8,\n)\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.8"
}
},
"nbformat": 4,
"nbformat_minor": 0
}