Adaptive Production

Apart from the adjustment of a given distribution to a density function while maintaining its random characteristic, it is also possible to change the statisti­cal 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.

Подпись: optimizationFor 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 possi­ble. To achieve this, a cost function is introduced, which is to be minimized by optimization:

Adaptive Production

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 op­timization 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]).

Подпись: Voronoi regionEach 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.

Подпись: Lloyd’s methodThe local optimization uses an iterative method, in which each point is succes­sively moved into the centroid of its Voronoi region. This is called the general­ized 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. Al­though 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 analy­tically not yet proven [49].

Подпись: 1Подпись:Подпись:Подпись: (c)Подпись:Adaptive ProductionПодпись: t ! 4“ » t ,» Adaptive ProductionПодпись: (a)ч *>

* » c 4

V. /4 „


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 ob­ject 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 man­ner. 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 exam­ple, in the first step large objects of a population can be distributed; these re­main stationary, while smaller objects are iteratively distributed around them.

Adaptive ProductionFigure 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 gener­ated distribution of larger and smaller objects, both arranged in Poisson disk distributions, but with differing disk sizes.