Transform - Voronoi Operators

These operators create a Voronoi diagram for the points in the active drawing.

 

images\sc_voronoi_points.gif

 

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.

 

images\sc_voronoi_lines.gif

 

By drawing lines to mark out Voronoi cells (or drawing areas in the shape of those cells), we divide up (or 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.

 

Voronoi Diagram

Create area, line and point objects for each Voronoi cell.

Voronoi Areas

Create area objects for each Voronoi cell.

Voronoi Lines

Create line objects at the border of each Voronoi cell.

Voronoi Points

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

 

images\sc_voronoi_diagram.gif

 

The Voronoi Diagram operator, as seen above, creates area, line and point objects for the Voronoi diagram. Note that points appear at the intersection of the borders of the Voronoi cells. These points are created by the Voronoi Points operator.

 

The areas, lines or points created by this operator will be selected after they are created. It's a good idea to move them to a new drawing to keep the map well organized. Move them by using Edit - Cut and then Edit - Paste into a new drawing or Edit - Paste As a new drawing in the project pane.

 

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.

 

images\sc_voronoi_overlay_eg01.gif

 

We would like to assign each sampling station to the nearest collection center. To do this we first use a drawing of the data collection centers to create a Voronoi Area surrounding each center.

 

images\sc_voronoi_overlay_eg02.gif

 

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

 

Transfer Rules

 

All of the Voronoi operators except Voronoi Lines will transfer column data from source to target (created) objects using whatever transfer rules are in force for the data attribute columns.

 

Historical Note:

 

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.

 

images\ill_dirichlet.gif

 

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.

 

images\ill_voronoi.gif

 

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 Thiessen, a German meteorologist. Both errors appear to arise from the dominance during the inter-war years of German researchers in crystallography and other subjects in which Voronoi diagrams are used.

 

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. Thiessen quite likely felt he had independently derived the concept (as have many workers in the years since Voronoi's publications).

 

As a meteorologist Thiessen probably would not have had full awareness of all that was done in mathematics by professional mathematicians such as Dirichlet or Voronoi. But is unfortunate that some writers who certainly knew of Voronoi's work would deny either Voronoi or Dirichlet credit while advancing Thiessen as the inventor of a concept that Voronoi developed both more fully and at an earlier date, not to mention Dirichlet's earlier work as well.

 

Whatever the reason for the original misattribution, 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 of this notion in the contemporary form used within Manifold.

 

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