# 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:

1. Open a drawing that contains points.

2. In the Transform pane, choose the drawing and the geometry field in that drawing.

3. Double-click the Voronoi template to launch it.

4. In the Voronoi template options, choose the Output type desired, either area, line, or point.

5. Choose the Margin size and the Unit for that margin size.

6. The Result is always a new drawing and table.   Specify the names desired.

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

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

Transform Pane

Transform Topics

Transform Reference

Transform - Geometry: Voronoi

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.