Voronoi Tessellation

Introduction

A simple Voronoi diagram can be described as: Given a finite set of points, called seeds, sites or generators, in a 2D plane. Each point lies in a corresponding region or cell. A seed's corresponding Voronoi cell consists of every point in the plane whose distance to this seed is less than or equal to its distance to any other seed in the plane. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest seeds. The Voronoi vertices (aka nodes) are the points equidistant to three or more seeds.

Voronoi diagrams are used to model phenomena and processes involving growth or spatial division, such as cell architecture in biological tissue, microstructure of polycrystalline metal, nearest neighbor searches, mesh generation, etc, etc.

More about the seeds

In figure 2 the seeds are points, randomly positioned in the plane. We can also position the seeds in a certain pattern. In addition, seeds do not have to be points; in a plane a seed can be any line, circle, curve, etc.

Voronoi parabola

In figure 3 a number of seeds are positioned on a straight horizontal line and one seed is positioned above or below that line. In this JavaScript application you can change the number of seeds on the horizontal line and change the distance to the point below or above that line and see what effect this has on the shape of the cell.

The more the number of points on the horizontal line approaches infinity, the more the edge of the cell belonging to the one point above the horizontal line looks like a parabolic curve. And indeed, a geometrical description of a parabola involves a point, the focus, and a line, the directrix: a parabola, being the locus of points equidistant from both the directrix and the focus. An infinite number of points on a straight line is actually a straight line, and hence a parabola can be viewed as a Voronoi diagram of two seeds: a point and a straight line.

Seeds of all sorts

So, seeds of a Voronoi diagram are not limited to points. In a plane a seed can be any plane figure e.g. a line, a circle, a curve, a polygon. Figure 4 shows some examples.

Symmetric patterns

Every symmetry of a set of seeds is also a symmetry of the corresponding Voronoi diagram. So, using a symmetric arrangement of points in a plane, or any set of seeds with some set of symmetries, results in a symmetric tiling of the plane. Figure 5 shows two examples of symmetrical arrangements of point seeds.

Figure 6 shows symmetric Voronoi tilings based on the seed arrangements of figure 5.

Disc phyllotaxis

In 1979 the German physicist Helmut Vogel proposed a model for a close packing pattern of florets (disc flowers) in the flower head (pseudanthium) of asteraceae flowering plants, like sunflowers, daisies or asters. The florets eventually mature into seeds and are arranged spirally. His model is a Fermat's spiral, expressed in polar coordinates by r = c√n and θ = nϕ where r is the radius from the center, θ is the angle, n is an index number of a floret, c is a constant scaling factor and ϕ is the golden angle ( ϕ = π(3 − √5) ≈ 2.399963 [rad] ).

The polar coordinates are describing geometrical points, but the florets, the flower seeds, can be modeled as them emerging from these points by radial growth, described by a Voronoi diagram (see figure 7).

Just for fun

Just a final animation for fun. The constant scale factor c in Vogel's model is being animated using Perlin noise, making the Voronoi diagram appear to be the surface of a living creature.

Much more about Voronoi diagrams

This was just a brief and shallow view upon some aspects of Voronoi diagrams from a certain perspective. Many further extensions to this basic scheme are possible, such as weighted seeds (multiply all distances in a cell by some factor), other distance functions (metrics) or diagrams in more than two dimensions.