Voronoi Tesselation and Delaunay Trianglulation both perform spatial calculations on a set of irregular points, and both have a variety of really cool spatial applications.
A Voronoi diagram is the partitioning of an area into regions based on distance from points. The individual components of a Voronoi diagram are Voronoi polygons. In spatial analysis, Voronoi Polygons are often also referred to as Thiessen Polygons.
Using Voronoi polygons for spatial analysis dates as far back as geography legend John Snow, who used a Voronoi diagram in 1854 to illustrate how most people dying from the Broad Street Cholera outbreak lived closer to the Broad Street water pump than any other water source.
Voronoi polygons are still used in a wide range of spatial research applications. They have been used in ecology research to model tree canopy growth and forest fires, as well as in transportation research to determine walksheds around stores or bus stops. Voronoi polygons are also the basis for the nearest neighbor and natural neighbor spatial interpolation methods.
Delaunay triangulation is when a set of irregular points are divided into triangles so that no point in the set is inside the circumcircle of any triangle created from the points. This process minimizes narrow triangles. Delaunay triangulation corresponds to the dual graph of a Voronoi tessellation of the same set of points.
Delaunay triangulation allows for the creation of a Triangulated Irregular Network (TIN) surface, which can be used for digital elevation models.
Delaunay triangulations can also be used to assess point density by Delaunay Tessellation field estimator.
I have recently published a tool on Alteryx Gallery that creates both Voronoi Polygons and Delaunay Triangles around a set of input points (either x,y coordinates or a point spatial object) using the deldir package in R and allows you select a projection you’d like your Voronoi polygons to be calculated in. It is called the DTVT Tool, and can be downloaded from the Alteryx Gallery here.
In case you don’t feel like downloading the tool I’ve created (and I’m only a little hurt 😊), did you know you can also use the Trade Area Tool in Alteryx to create Voronoi polygons?!
There are two key tricks to this:
- Setting your buffer zones to be large enough in the trade area to that there are no gaps between the objects when you set it to
- Creating a convex hull around your points so that the polygons are clipped to a reasonable area.
The workflow to do this is relatively simple!
The Voronoi tessellation will only work on points in Alteryx, so the first step if you don’t already have point objects is to make them.
Then, you can create a convex hull around your points using the summarize tool:
And create a small buffer around your convex hull so that when you clip your tessellation to the area the points are in, the outer points don’t end up on an edge. The distance you set this buffer tool to will depend on how spread out your data is.
Meanwhile, set up the trade area tool to create buffers large enough that there won’t be any gaps between each of your buffers (this value will again depend on how spread out your points are), and so that the Eliminate Overlap option is selected.
Next, we append our two newly made spatial object fields together
If you are dealing with more than 16 spatial objects, you may need to change the Warn/Error on Too Many Records Being Generated Option from Error to Warn to allow the workflow to run.
Then, you perform an intersection between your buffered Convex Hull object and your trade area polygons using the Spatial Process Tool.
Run the workflow, and Ta-da! Behold, Voronoi Polygons via an Alteryx Workflow!
Aren't they beautiful?