Voronoi Diagrams

The Voronoi template for geometry fields in the Transform pane and Voronoi functions in SQL create Voronoi diagrams for a set of points. See also the Transform - Geometry: Voronoi topic. To create a Voronoi diagram for polygonal areas, see the Example: Voronoi Diagram from Areas topic.

Suppose we have a drawing of points. A Voronoi diagram divides the drawing into regions around each point that are shaped so that the borders of the regions are equidistant from the two nearest points.

The illustration seen above shows the effect of the Voronoi : line operation.

By drawing lines to mark out Voronoi cells, or by creating areas in the shape of those cells, we divide up, that is tile or tessellate, the drawing into regions. Every location within a Voronoi cell is closer to the point about which that cell is drawn than it is to any other point. Voronoi diagrams are very important for dividing drawings into regions associated with points.

The Voronoi template provides three operations to create Voronoi diagrams:

area - Create area objects for each Voronoi cell.

line - Create line objects at the border of each Voronoi cell.

point - Create point objects at the intersections of the borders of the Voronoi cells. Rarely used.

The illustration seen above shows the effect of the Voronoi : line operation with the original points shown with reduced transparency.

Creating a new drawing with a Voronoi diagram:

Open a drawing that contains points.
In the Transform pane, choose the drawing and the geometry field in that drawing.
Double-click the Voronoi template to launch it.
In the Voronoi template options, choose the Output type desired, either area, line, or point.
Choose the Margin size and the Unit for that margin size.
The Result is always a new drawing and table. Specify the names desired.
Press Transform.

With the focus on the drawing window, in the Transform pane we choose the drawing with points, and we choose the Geom field. We double-click on the Voronoi template to launch it in the Transform pane.

In the Voronoi template, choose line as the Output type to generate a Voronoi diagram with border lines. Enter 50 for the Margin, or whatever other value is desired for the margin, using whatever Unit of measure is desired.

The Result is automatically set to New Table, the only allowed result choice. Specify memorable names for the New drawing and the New table.

Press Transform.

A new drawing with the specified name appears in the Project pane. We drag and drop the new drawing into the open window as a layer:

Controls

	Up one level. Return to the main template list to allow choosing the component or field. Use this button to choose a different template.
<component name>	Gives the name of the raster image layer in the map that the template is using as a source of terrain elevation data. If the map has other raster image layers, we can change to any other raster image layer in the same map.
Field	The name of the geometry field on which the template operates. If the drawing has other geometry fields providing points, we can choose any other such geometry field.
Output type	The type of Voronoi diagram to create. Choose from: area - Create area objects for each Voronoi cell. line - Create line objects at the border of each Voronoi cell. point - Create point objects at the intersections of the borders of the Voronoi cells. Rarely used.
Margin	Distance from the outermost points to clip the generated diagram. Using a Margin limits the diagram to a rectangular region with horizontal and vertical borders no further than the given distance from the outermost points. That prevents infinite areas from being generated for the outermost Voronoi cells.
Unit	Unit of measure to use for the Margin distance.
Result	The result for the Voronoi template is always New Table , creating a new drawing and a new table using the names specified in the New drawing and New table boxes.
Result type	The geometry type to use for the result drawing, Manifold's native geom type, geommfd type, or geomWKB type. Use the native geom type.
New drawing	The name to use for the new drawing the template will create.
New table	The name to use for the new drawing's table the template will create.
Resources	A choice of CPU and GPU parallelization resources the system is allowed to use: all CPU cores - Allow parallelization up to using all CPU cores (threads) with no use of parallel GPU allowed. all CPU cores, all GPU cores - Allow parallelization up to using all CPU cores (threads) and parallel use of all GPU cores. one CPU core - Allow use of only one CPU core (thread) with no use of parallel GPU allowed. one CPU core, all GPU cores - Allow use of only one CPU core (thread) and parallel use of all GPU cores. CPU "cores" are used in the Windows meaning of the word core, meaning hyperthread for CPUs that support hyperthreading when hyperthreading is turned on in the BIOS. Since most modern CPUs and systems support hyperthreading, when Windows reports the number of cores it is really reporting the number of threads. GPU cores are either used fully parallel for all cores or GPU is not used at all. The Resources setting puts limits on what the system is allowed to use. It does not force parallelization if that would result in slower operation.
Transform selection only	Use only selected points in the source drawing to create the Voronoi diagram, ignoring all points that are not selected.
Transform	Apply the transform template.
Preview	Show a preview of what the transform operation will do.
Edit Query	Launch a Command Window loaded with the SQL query that performs this transform with given settings.

Voronoi : area

Based on the drawing of points, create a drawing of areas that form a Voronoi diagram for those points.

The Voronoi : area operation preview, as seen above, creates area objects for the Voronoi diagram.

Voronoi : line

Based on the drawing of points, create a drawing of lines that form a Voronoi diagram for those points.

The Voronoi : line operation, as seen above, creates line objects for the Voronoi diagram.

Voronoi : point Operation

Based on the drawing of points, create a drawing of points at the intersection of borders of lines or areas that would form a Voronoi diagram for those points.

The Voronoi : point operation preview, as seen above, creates point objects for the Voronoi diagram. To see the relationship of the Voronoi points to the Voronoi regions, we can overlay with slight transparency a drawing of Voronoi lines, with the generated Voronoi points diagram shown in magenta.

Clipping of Infinite Regions

As a mathematical concept, the outermost Voronoi regions in a Voronoi diagram will extend out to infinity. The Margin parameter allows us to clip Voronoi diagrams to a rectangular region where the boundaries of the regions are the Margin distance from the outermost points used to create the diagram.

We can see what would happen without the Margin setting by creating a Voronoi diagram of lines using a very large Margin setting.

We specify 5000 meters as the Margin setting, and create a drawing called Big margin voronoi lines. We can compare the effect of a 5000 meter margin to that of a 50 meter margin:

The diagram created using a 50 meter Margin, seen at left above, limits the size of the Voronoi diagram to no greater than 50 meters in horizontal or vertical borders from the outermost points. The diagram created using a 5000 meter Margin, seen at right above, zoomed in enough so we can see the individual points, has very large Voronoi regions as the outer regions.

Using the Margin setting is a convenience, since Voronoi diagrams are almost always manually clipped to some reasonable area of interest when used in real life applications.

Example of Use

Suppose we have a few hundred environmental sampling stations scattered throughout a region. We also have a dozen data collection centers, numbered 1 through 12, within the region. Environmental sampling stations are connected to a data collection center using radio communications so we would like to assign each sampling station to the nearest data collection center.

To do this we first use a drawing of the data collection centers to create a Voronoi Area surrounding each center.

We can then use Join to transfer the identification number of each data collection center to the Voronoi cell that encloses it. Next, we can use Join once more to transfer the identification number from each Voronoi cell to all of the sampling station points within each cell.

The result is that each sampling site will have a field that contains the data collection center number that services it, and in all cases the data collection center will be the closest collection center to that sampling site.

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, first convert 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.

Descartes, Dirichlet, Voronoi, and Thiessen - Voronoi diagrams are also known in some cultures as Dirichlet or Thiessen tessellations. Although individual investigators have used this powerful concept informally at least as far back as Descartes in 1644 the key researchers formally developing this concept were Dirichlet and Voronoi.

J. P. G. Lejeune Dirichlet (1805 - 1859)

Dirichlet used a special form of the Voronoi tessellation in his study of positive quadratic forms. Dirichlet was born in a part of the French Empire long disputed back and forth between France and Germany, studied in Paris and settled down to an overworked and productive career in Germany. Voronoi later published a generalization of Dirichlet's concept that would apply to higher dimensions and so introduced the concept in its modern form.

Georgi. F. Voronoi (1868 - 1908)

Voronoi was born in Russia on 28 April 1868 and graduated from the University of St. Petersburg in 1889, winning the Bunyakovsky prize for his Master's thesis and again a second time for his Doctor's thesis. He was a lecturer at Warsaw University and contributed to the theory of algebraic numbers and the geometry of numbers.

At times Voronoi wrongly is claimed to be a German mathematician, an error repeated in some web sites. Even more inaccurately, some people refer to Voronoi's work by crediting the concept to Alfred Thiessen, an American meteorologist.

Thiessen used the idea of Voronoi diagrams much later than either Dirichlet or Voronoi, beginning only in 1911 to apply them to the study of meteorology. It is always possible Thiessen felt he had independently derived the concept (as have many workers in the years since Voronoi's publications). As a meteorologist Thiessen might not have known of the mathematical work of professional mathematicians such as Dirichlet or Voronoi.

Whatever the reason for the wrong attribution, in modern times if we are not to inadvertently repeat the error we should use the term "Voronoi" or "Dirichlet" tessellations for this concept. The term “Voronoi” is used by Manifold because it was Voronoi who presented the mathematics in the contemporary form used within Manifold. To honor Dirichlet It is tempting to suggest using “Voronoi-Dirichlet" diagrams. Has a nice ring to it.

Pronunciation

"Voronoi" is pronounced by English speakers as "Vo - ro - noi" with a short "o" sound, like the "o" in "or", for the first two syllables. The third syllable is pronounced like the "noi" in "noise". The stress is on the third syllable. Russian speakers will pronounce the name with such a short "o" in the first two syllables that it sounds like "uh" or even "ah".

"Dirichlet" is pronounced exactly as it is spelled, that is, if you are French: "Dee - reesh - lay" with the stress mostly on the first syllable. Although he lived and worked in Germany, Dirichlet retained the French pronunciation of his name.