Given a set of points in the plane, there exists an associated set of regions surrounding these points, such that all locations within any given region are closer to one of the points than to any other point. These regions may be regarded as the dual of the point set, and are known as proximity polygons, Voronoi polygons or Thiessen regions. These various terms are equivalent, as is the term Dirichlet cell, all being derived from the names of their proponents: Dirichlet (in 1850); Voronoi (in 1909); and Thiessen (in 1912).

Figure 4‑32A shows an example of Voronoi region creation, in this case using ArcGIS. The point set from which the map was generated is also shown and as can be seen, points are frequently close to polygon edges. Indeed, in some applications it may be desirable to exclude points that are closer together than some predefined tolerance level. Note that in this example Voronoi regions at the edges of the sample extend to infinity, and are shown as bounded (e.g. by the MBR of the point set plus 10%).

Figure 4‑32B shows the same point set plus the associated Delaunay triangulation once more, created within the MATLab mathematical modelling package. This enables us to see exactly how Voronoi regions are created. There are two steps: the first is the triangulation process, connecting the point set as described in subsection 4.2.14.1; and the second is bisection of the triangulation lines of adjacent points to define Voronoi polygon boundaries.

Figure 4‑32 Voronoi regions generated in ArcGIS and MATLab

There are many reasons an analyst may wish to generate Voronoi polygons from a point set, but a common requirement is to assign values to regions or cells based on the attributes of the point set. The most common assignment is that of the individual point, or nearest-neighbour model. Other options are offered by some GIS packages in much the same way as is applied to grid and image files (in which each cell is surrounded by 4 or 8 immediate neighbours, depending on the model used). Note that the MATLab implementation does not extend to the MBR or other bounding region (e.g. rectangle) defined by the user. A selection of (a) MATLab and (b) GRASS functions that support operations discussed in this section is shown in Table 4‑7.

Table 4‑7 Selected MATLab/GRASS planar geometric analysis functions

Assignment facilities provided within ArcGIS include: local mean value — the cell is assigned the average value of the cell and its direct neighbours; and local modal value — determined by computing the frequency distribution of all adjacent cells in 5 classes and then assigning the cell the class value from this set that is the most common amongst the cell and its immediate neighbours. These assignments represent local smoothing procedures. Local variation rather than values may also be computed. For example:

·         local entropy value (equivalent to Shannon’s Landscape Diversity Index, SHDI — see Section 5.3.4) — in this model the adjacent cells are again grouped into 5 sets (smart quantiles or natural breaks classes) and the number in each class is represented as a proportion of the total, p_i, i=1‑5, from which Shannon’s entropy statistic is computed (Table 1‑4) and this value is assigned to the cell — values will range from 0 to log₂(5); and

·         local standard deviation and local inter-quartile range — these statistics are computed for the cell and its immediate neighbours and the value assigned to the selected cell

Voronoi polygons may also be generated in grid or raster datasets (perhaps better described as Voronoi patches). Since the definition of a Voronoi polygon in the plane is that it consists of all locations closer to selected points than to any other points, such regions can be generated by a form of spreading algorithm. In this case we start with a number of points (the source points, sometimes called the target points) and spread outwards in all directions at a constant rate, like ripples spreading across the surface of a pond when a stone has been thrown into the middle. The process stops when the ripple (spreading) from another point is encountered. The rectangular grid structure and the number of search directions (typically 8) affect the form of the resulting cells (Figure 4‑33). With the raster representation Voronoi patch shape and boundary definition are not as clear cut as in vector operations.

Figure 4‑33 Voronoi cells for a homogeneous grid

Within GIS packages processing activities of this type are usually carried out using techniques described as cost distance, or accumulated cost distance tools (e.g. in ArcGIS Spatial Analyst). Other packages have specific functions to generate regions of this kind (e.g. the Fence function in MFWorks).

In image processing the procedures adopt a somewhat different set of algorithms, based on scanning rather than spreading, which are known as distance transforms. The latter may be exact (in Euclidean distance terms) or approximate (see further, Section 4.4.2). Furthermore, with both approaches the space across which the scan or spread procedure is conducted may be homogenous (i.e. treated as uniform in all directions and at all points) or non-homogenous, containing areas of varying difficulty to traverse, varying cost, and/or including obstacles.

The most comprehensive book on this field is by Okabe, Boots and Sugihara (1992), a monumental work entitled “Spatial tessellations: Concepts and applications of Voronoi diagrams”. For details on the huge range of applications and methods relating to Voronoi diagrams readers are recommended to dip into Okabe et al.’s work. Our discussion at various points in this Guide will be restricted to a small subset of these applications. Okabe and colleagues have also developed a software package, SANET, which can be installed as an ArcGIS add-in for “Spatial Analysis on a Network”. The SANET software includes a network-based Voronoi tool, very similar to some of the network analysis tools provided in ArcGIS itself and in network-oriented packages such as TransCAD. An illustration of its facilities is shown in Figure 4‑34. In this example the point set (off-network sites which are Bank premises) have been linked to the nearest network edge, and then network Voronoi regions generated from these locations (new network nodes) using shortest path distances.