Premium
Filling domains with disks: an advancing front approach
Author(s) -
Feng Y. T.,
Han K.,
Owen D. R. J.
Publication year - 2002
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.583
Subject(s) - front (military) , domain (mathematical analysis) , algorithm , boundary (topology) , reduction (mathematics) , computer science , point (geometry) , packing problems , discrete element method , computational complexity theory , object (grammar) , element (criminal law) , mathematics , computational science , geometry , mathematical analysis , engineering , mechanical engineering , artificial intelligence , physics , mechanics , law , political science
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 © 2002 John Wiley & Sons, Ltd.