Apart from the adjustment of a given distribution to a density function while maintaining its random characteristic, it is also possible to change the statistical attributes directly. An important example in connection with plants is the transformation of a Poisson distribution or otherwise given random distribution into a Poisson disk distribution.
For this process the problem is more generally approached and converted into an optimization task: A quantity of points pl, ..,pn is to be distributed over a region, so that the region is divided into subregions, as equally sized as possible. To achieve this, a cost function is introduced, which is to be minimized by optimization:
Here, ф(р) is a weighting function that indicates the local weight of a region and, thus, its desired point density. The term f (||p – p^||) describes a simple cost function on the basis of the Euclidean distance. The global nonlinear optimization of a larger number of point objects based on such a cost function is very expensive. Fortunately, Eqn. (8.1) can be solved by local optimization on the basis of Voronoi regions (see [20]).
Each point pi in the point set is assigned its respective Voronoi region. This is an area surrounding pi that contains all points of the plane that are closer to pi than to every other point of the given point set. For the Euclidean distance function the Voronoi regions are bounded by convex polygons; altogether all Voronoi regions of the point set form a complete partitioning of the plane.
The local optimization uses an iterative method, in which each point is successively moved into the centroid of its Voronoi region. This is called the generalized Lloyd’s method. It ensures that after each iteration the optimization goal is reached for the point’s local region. Open regions, which develop at the border of the point set, must be closed before, for example by intersection with the boundaries of a given definition area. This process is iterated until convergence is reached, i. e., the points form the desired distribution.
If the process is continued for a huge number of iterations, a pattern would develop, in which all Voronoi regions are equally large: a hexagonal grid. Although this seems to always be the result in practical attempts, a convergence
of the procedure to this kind of global minimum for the general case is analytically not yet proven [49].
ч *>
* » c 4
V. /4 „
(b)
In Fig. 8.2 the algorithm is applied to a small point set. At the beginning of the iteration, the Voronoi regions have a very irregular form. Toward the end we find almost equal pentagons and hexagons. In Fig. 8.4c the procedure is applied to the positioning of grass tufts obtained from an image drawn by the user that was discretized.
The procedure can be extended to general objects. The Voronoi regions can be computed similarly; instead to a specific point now the distance to a whole object is defined. However, the areas are now not necessarily convex any longer, and in some cases the optimization also no longer converges in an even manner. Additionally to the displacements, with expanded objects also a rotation can be implemented, in order to further optimize the distribution.
In particular, the procedure can also be applied hierarchically. Thus, for example, in the first step large objects of a population can be distributed; these remain stationary, while smaller objects are iteratively distributed around them.
Figure 8.3
Hierarchical distribution of objects: the points with a circular marking are generated first. The other points are inserted later and the set is then relaxed while the first points are held in a fixed position. (Image courtesy of Stefan Hiller)
This extension of the above methodology is being examined by Hiller et al. in [87]. In Fig. 8.3, the procedure is demonstrated by a synthetically generated distribution of larger and smaller objects, both arranged in Poisson disk distributions, but with differing disk sizes.
