community
cancel
Showing results for 
Search instead for 
Did you mean: 

Data Science Blog

Machine learning & data science for beginners and experts alike.
Sr. Data Science Content Engineer
Sr. Data Science Content Engineer

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.

 

Voronoi_diagram.png

 

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.

 

John_Snow.png

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.png

 

Delaunay triangulation allows for the creation of a Triangulated Irregular Network (TIN) surface, which can be used for digital elevation models. 

 

Triangulated_irregular_network.png

 

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:

 

  1. 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
  2. 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!

 

Voronoi_workflow.png

 

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:

 

Summarize_tool_config.png

 

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.

 

Trade_Area_tool_config.png

 

Next, we append our two newly made spatial object fields together

 

Append_Fields_tool_config.png

 

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!

 

Voronoi_Alteryx_output.png

 

Aren't they beautiful?

Sydney Firmin

A geographer by training and a data geek at heart, Sydney joined the Alteryx team as a Customer Support Engineer in 2017. She strongly believes that data and knowledge are most valuable when they can be clearly communicated and understood. In her current role as a Sr. Data Science Content Engineer, she gets to spend her days doing what she loves best; transforming technical knowledge and research into engaging, creative, and fun content for the Alteryx Community.

A geographer by training and a data geek at heart, Sydney joined the Alteryx team as a Customer Support Engineer in 2017. She strongly believes that data and knowledge are most valuable when they can be clearly communicated and understood. In her current role as a Sr. Data Science Content Engineer, she gets to spend her days doing what she loves best; transforming technical knowledge and research into engaging, creative, and fun content for the Alteryx Community.

Comments
Atom

Hi Sydney,

I used this some time ago and found it a useful macro.  Thanks.  Unfortunately it no longer works as R is bombing:  Error in binsrtR(x,y,rw).  I tried to fix it a couple of times but could never get it to work.  Any ideas?

Dan

Sr. Data Science Content Engineer
Sr. Data Science Content Engineer

Hi @serr8ted,

 

I am so glad to hear you have enjoyed using the tool! I think I have a pretty good idea of what you are encountering and would be happy to help you troubleshoot. Another user reported the same error with the tool in this thread

 

Are you currently using a version of Alteryx Designer  2018.2, having originally installed the deldir tool on an older version of Designer? If so, what you are likely encountering is an issue with the underlying R package (deldirregistering Fortran routines. 

 

As of R version 3.4.0, CRAN has started enforcing a new way for declaring foreign code routines. In Designer 2018.2, the underlying R version was upgraded from 3.3.2 to 3.4.4. The error message you are getting indicates an issue with the function binsrt(), which calls Fortran. 

 

When I reproduced the error in my own environment, I was able to resolve the error by updating the deldir package installed on my machine.  To do this, you can either use the Install R Packages Analytic App, and specify deldir as the package to install, or you can add an R tool to a blank workflow, paste the following code into the tool, and run the workflow.

 

install.packages("deldir", repos = "http://cran.us.r-project.org")

Please let me know if upgrading your deldir package resolves the issue for you or not! I would be happy to continue to help you with troubleshooting if this error or a different error persists. 

Atom

Thanks @SydneyF .  Indeed deldir was not even installed.  I finally was able to get it installed but still getting the error with the macro. Perhaps there is a pointer or ini file that needs to be changed?

D.

Sr. Data Science Content Engineer
Sr. Data Science Content Engineer

Hi @serr8ted,

 

Alteryx references multiple R libraries in different locations on a machine, so what I am thinking may have happened is the updated version of the deldir package was installed in a different location from the original installation, and the tool is still referencing the first installation location of the package.

 

To try troubleshooting this, can you please try navigating to the following locations (some of them may not exist on your machine, and delete any folders you find called deldir?

 

%AppData%\Roaming\Alteryx\R-library

%AppData%\Local\Alteryx\R-3.4.4\library

%AppData%\Local\Alteryx\R-3.3.2\library

%ProgramData%\Alteryx\R-library

%Program Files%\Alteryx\R-3.4.4\library

%Program Files%\Alteryx\R-3.3.2\library

 

Once you've checked these locations for the deldir package, can you please try opening Alteryx as an administrator (Right-Click > Run as Administrator) and running a workflow that includes the deldir tool? There is a function in the tool that conditionally installs the package if it is unable to find it in the available libraries, and this function should be triggered after deleting all occurrences of the package.