Filling domains with disks: an advancing front approach

An advancing front-based algorithm is proposed to constructively generate a random initial packing for disks with different radii within a 2D domain, which is often required in discrete element methods (DEM). Depending on whether the domain boundary is included in the initial front and how the front is formed, two different versions of the algorithm, termed the closed and open form, respectively, are presented. The open form version has an inherent linear complexity. The closed form can achieve the same complexity under a relatively weak condition. The generated packing is not a globally optimal arrangement but achieves a locally highest density from the algorithmic point of view. The performance of the algorithm is illustrated in several examples. The major benefit of this development is the significant reduction of CPU time required for the preparation of an initial discrete object configuration in DEM simulations. It is demonstrated that it takes only 3.77 s for the proposed algorithm to generate one million disks on a PC with a one 1 GHz processor. Copyright (C) 2002 John Wiley Sons, Ltd.