Transform: Voronoi Diagrams

 

Transform: Voronoi Diagrams

Voronoi templates in the Transform panel and Voronoi functions in SQL create Voronoi diagrams for a set of points.

 

il_trans_drawing_voronoi_start.png

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.

 

il_trans_drawing_voronoi_lines_compare_pre.png

The illustration seen above shows the effect of the Voronoi Diagram, Lines template with the original points shown with reduced transparency.

 

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 Transform panel provides three templates for drawings to create Voronoi diagrams:

 

 

 

 

The illustration seen above shows the effect of the Voronoi Diagram, Lines template with the original points shown with reduced transparency.

Controls

Geom

The geom field which contains points to use as the basis of the Voronoi diagram.

Inflate X, Y

Factors by which to increase the bounding box used for clipping infinite regions.   See discussion below.

Tolerance

Value within which objects are judged adjacent, for computations required to draw borders between Voronoi regions.  Use 0 for automatic tolerance, the default and highly recommended.   

Options

See the Transform Options topic.

 

Voronoi Diagram Template

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

 

il_trans_drawing_voronoi_start.png il_trans_drawing_voronoi_diagram.png

The Voronoi Diagram template preview, as seen above, creates area objects for the Voronoi diagram.

 

Voronoi Diagram, Lines Template

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

 

il_trans_drawing_voronoi_start.png il_trans_drawing_voronoi_lines.png

The Voronoi Diagram template preview, as seen above, creates line objects for the Voronoi diagram.    The relationship of the lines to the original can be seen by adding the original points to the illustration below:

 

il_trans_drawing_voronoi_lines_compare_pre.png

Voronoi Diagram, Points Template

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.

 

il_trans_drawing_voronoi_start.png il_trans_drawing_voronoi_points.png

The Voronoi Diagram template preview, as seen above, creates line 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:

 

il_trans_drawing_voronoi_points_compare.png

 

Clipping of Infinite Regions

Manifold will automatically clip regions that grow to infinite extent in a Voronoi diagram.   The horizontal boundaries at the top of Voronoi diagrams in illustrations above show clipping where the upper regions would diverge and thus grow to infinite extent.  

il_voronoi_clipping.png

Zooming out in the Voronoi Diagram, Lines template preview we can see how a clipping box is constructed using locations where the borders of regions converge.    Such clipping is a convenience as Voronoi diagrams are almost always manually clipped to some reasonable area of interest when used in real life applications.

 

Important: Clipping as shown in previews is approximate.  Zooming in or out will change the apparent extents of the clipping

Example

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.

 

eg_voronoi_overlay01_01.png

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

 

eg_voronoi_overlay01_02.png

We can then use an Overlay template to transfer the identification number of each data collection center to the Voronoi cell that encloses it. Next, we can use an Overlay 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

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.

 

img_dirichlet.png

 

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.

 

img_voronoi.png

 

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.

 

See Also

Contents Pane

 

Transform

 

Contents - Transform

 

Transform Templates

 

Transform Templates - Drawings

 

Transform Templates - Geom

 

Transform: Overlay