Example: Voronoi Diagram from Areas

Voronoi diagrams are normally created from points.  This example shows how to create a Voronoi diagram for polygonal areas, so that every location in a given cell in the Voronoi diagram shows which area is the closest to that location.

 

In three easy steps we will create a Voronoi diagram for polygonal areas that represent parks.   The resulting diagram for any location in the map will show the closest park to that location.

 

 

We begin with a map that has one layer, a Parks drawing that contains five polygonal areas.

 

 

Opening the drawing's table, we see that each object has a Name text field.   For the sake of this example, the names are simple, just a single letter from a to e.   The polygonal areas have been thematically formatted in the drawing using a different pastel color for each unique value of the Name field.    The background color for the map is a light green.

Step 1: Convert Areas to Points

Since the Voronoi transform template works on points, our first step is to convert the polygonal areas to points.   

 

With the focus on the Map window, in the Transform pane we choose the Parks drawing, and then we choose the Geom field.    We double-click the Convert entry in the list of available templates to launch the Convert template:

 

 

In the Convert to option we choose point.  For the Result, we choose New Table and then we enter Points as the name for the new drawing and an analogous name for the new drawing's table.   

 

Press Transform.

 

A new Points drawing appears in the Project pane, along with the drawing's table.   We drag and drop the new Points drawing into the Map window:

 

 

The Convert: points template created points at the locations of each of the vertices that define an area object in the Parks layer.  The point objects inherit the field values for the area from which they were created, so that the points created from the area object that has a Name of a also have a in their Name field.  

 

In the illustration above we have Styled the points using the same thematic format, with pastel colors for each unique value in the Name field, as used for areas in the Parks layer.

 

A nuance:  the Convert: points template creates multipoints at the locations of vertices that define areas.   For example, what appear to be four separate points at the vertices of the blue rectangle in the middle of the above illustration are in fact a single point object, with four branches.   That is convenient for maintaining a one to one association between a source area's Geom and the resulting Geom that represents that area as points, but it might be confusing (as the use of multipoints often can be) if we expect to see a single area object, one row in the Parks Table, with four point objects, four rows in the Points Table.  

 

If we like, we can convert the multipoints into separate point objects using the Split template with the coordinates choice for Split into.   That is not necessary for use with the Voronoi template, which automatically will decompose multipoints into separate point coordinates for the purpose of creating a Voronoi diagram.

Step 2: Create Voronoi Areas

Now that we have points, we can use the Voronoi transform template to create Voronoi areas from those points.    With the focus on the Map window, in the Transform pane choose the Points drawing and the Geom field in that drawing.   In the list of available templates, double-click the Voronoi entry to launch the Voronoi template.

 

 

In the Voronoi template we choose area as the Output type.   For Margin, we choose 100 meters.   To decide on a sensible margin we have taken a moment to use the Path tool to measure distances in the map, and then decided that using a Margin of 100 meters would be about right.

 

For the Result we choose New Table, and for the name of the new drawing we choose Voronoi Areas, with an analogous name for the new drawing's table.

 

Press Transform.

 

A new Voronoi Areas drawing appears in the Project pane.   We drag and drop that into the map, and then move the tab for the new layer below the Parks layer.

 

 

The Voronoi template created Voronoi cells for each point in the Points layer.  If we merged the Voronoi cells for the points that were created from each Parks area, we would have a Voronoi cell for that area.

Step 3:  Join

If the Voronoi cells for each point inherited the Name field for each point, we could simply use the Merge Transform template with the dissolve option using the Name field.   However, the Manifold Voronoi template does not transfer into created Voronoi cells the field values for points that were used as seeds for the Voronoi cells.    Those are easy to assign with a quick use of the Join dialog.

 

With the focus on the Voronoi Areas layer in the Map window, choose Edit - Join to launch the Join dialog.

 

 

Since the focus was on the Voronoi Areas layer, that will be the destination layer in the upper left corner of the dialog.   We choose Points as the source layer for the join in the upper right corner.   For the join method we choose touches.  (We do not use contains as the join method because the points we created in the first step are multipoints, and do not all fall within a single cell.)

 

 Press the Add button and add the Name field, creating a new row shown in provisional blue color as seen above.  

 

Press Join.

 

 

If we pop open the Voronoi Areas Table, we see that each of the Voronoi areas now has a Name field with the name (a letter from a to e) of the seed point that was used to create that area.

 

 

We can Style the Voronoi Areas layer using the same thematic format as used for the Parks layer areas and the Points layer points.   That shows how the Join has correctly assigned the right names to each of the Voronoi areas.

 

At this point in our example we have basically accomplished the task we set out to do.   We have created a Voronoi diagram where the various Voronoi areas indicate which of the Parks areas is closest to any location in the diagram.   From here on what we do is a matter of taste as to how we want our results to be structured.

 

Many people will prefer to add two additional quick steps:  a Merge: area (dissolve) to combine Voronoi regions for the same park, followed by a quick use of Clip to knock out park regions from the Voronoi regions.

Step 4:  Merge Voronoi Areas by Name

In many applications it will be more convenient to have a single Voronoi region associated with a park, instead of, for example, four Voronoi regions seen for the blue park in the center of the illustration above.  We can achieve that with a quick use of the Merge: area (dissolve) transform template.

 

With the focus on the Map window, in the Transform pane choose the Voronoi Areas drawing and the Geom field.    In the list of templates, double-click the Merge template to launch it.

 

 

In the Merge template, choose area (dissolve) as the Merge into option.   For the Group option choose the Name field.   For the Result, choose New Table, and specify the name Dissolved Voronoi for the new drawing, with an analogous name for the new drawing's table.  

 

Press Transform.

 

A new drawing called Dissolved Voronoi appears in the Project pane, along with the new drawing's table.   Drag and drop the Dissolved Voronoi drawing into the Map window.

 

 

 

Styling the Dissolved Voronoi layer the same as the Voronoi Areas layer, we can see how all Voronoi areas with the same name have been dissolved into a single Voronoi area for that name.

 

 

In the illustration above we have turned off the Parks layer, to show how the dissolved Voronoi areas, which were created from Voronoi areas created from the points, extend throughout the entire region of the dissolved Voronoi area, overlapping the Parks area.    

Step 5:  Clip Park Areas from Voronoi Areas

If we do not want any overlap with Parks areas, we can take a moment to Clip those areas out of the dissolved Voronoi areas.  

 

With the focus on the Map window, in the Transform pane we choose the Dissolved Voronoi layer and the Geom field.   In the list of templates we double-click the Clip template to launch it.

 

 

In the Clip template we choose Parks as the Clip with layer.

 

 We uncheck the Keep inner part option.  We want to keep those parts of the Dissolved Voronoi areas that are outside of the Parks areas.  

 

For the Result destination we choose New Table.  We enter a name of Clipped Voronoi for the new drawing and an analogous name for the new drawing's table.

 

Press Transform.

 

A new drawing called Clipped Voronoi and its table appear in the Project pane.   We drag and drop the Clipped Voronoi drawing into the Map.

 

 

 

Styling the Clipped Voronoi layer using the same thematic format as the other layers, we can see how each Voronoi region in that layer continues to have the Name of the Park area that it surrounds.   Each area in the Clipped Voronoi layer has had the Park area from which it derives clipped out, so there is no overlap between the originating park area and the Voronoi area with the same name.

 

For any location in the map, we can see from the color of the Voronoi area for that point what is the closest park to that point.   By closest we mean any part of the park: the geometry of how Voronoi diagrams are computed on points means that all of the various Euclidean distances to the borders of park areas are automatically and correctly computed.

 

Notes

Curvilinear segments - As a practical matter, most people doing GIS will use straight line segments for lines and areas.   Few GIS systems do a good job of supporting curved segments, so there is much less data published using curved segments.   Manifold's ability to work with curved segments allows us to use that data within Manifold in a limited way, at least for display and interactive editing.  

 

However, most processing tools in Manifold, such as Transform templates and various Geom SQL functions, do their work by first converting a curvilinear segment into a straight line segment between the same two start and finish coordinates.  That will often lead to weird or otherwise unexpected results.  To avoid such problems, if any of the Park areas are drawn using curvilinear segments, first convert those curvilinear segments into equivalent constellations of straight line segments at whatever resolution is desired, using the Clean transform template with the convert curves to lines operation option and the number of linear segments desired to approximate the curve in the Curve limit parameter.   See the Curved Segments discussion in the Drawings topic.

 

Voronoi - See the Voronoi Diagrams topic for historic notes on Descartes, Dirichlet, Voronoi, and Thiessen.

 

Inheriting fields -  The Manifold Voronoi template does not automatically transfer field values from seed points into resultant Voronoi polygonal areas.  That is a difference from how the Thiessen Polygons geoprocessing tool works in Esri's ArcGIS Pro, where there is an option to inherit field values from seed points into Voronoi polygons (Esri calls Voronoi polygons Thiessen polygons - see the Notes in the Voronoi Diagrams  topic for the history on names).    Manifold does not automatically transfer attributes from seed points into Voronoi regions, since the Manifold Voronoi template offers a choice of creating Voronoi diagrams as areas, as lines, or as points.  With areas, there can be a one to one association between seed points and surrounding polygons, but in the case of line boundaries or inflection points between cells, the lines or points are in common between more than one seed point.

 

See Also

Transform Pane

 

Transform Reference

 

Transform - Geometry

 

Transform - Geometry: Triangulate

 

Voronoi Diagrams

 

Example: Voronoi Diagram from Areas - Voronoi diagrams are normally created from points.  This example shows how to create a Voronoi diagram for polygonal areas, so that every location in a given cell in the Voronoi diagram shows which area is the closest to that location.