Ideas for an algorithm for random distribution of circles in a square

Question

I am searching for a concept to distribute circles in a square randomly, so that they dont overlap. All circles are of the same size. The area covered by the circles can be high, up to the theoretical maximum of ca. 90 % of the square (in which they are completely ordered). About 200 circles should be placed and I want to specify the number of circles exactly. (The distribution is needed as input for a model generation of a FE-analysis, btw)

With a straight-forward algorithm that places circles sequentially on a free spot, it is not possible to cover more than about 54%, which is not a surprise, as at some point there is just no space left. Therefore previous SO-threads do not really cover my issue (getting close: Placing random circles without overlap (and without using brute force)?)

With a simple random displacement of the circles of an ordered set of circles, the distribution seems to be "not random enough".

All concepts, I came up with so far, feel either to complicated or to brute-force-style. The approach I like most is to determine all possible positions on which the next circle can be placed, so that the left-over space is big enough to place the remaining circles. Then pick one of these positions randomly and so on. But: To determine the "capacity" of the left-over space is not easy and numerically very complex. I dont really know how to do it, and whether it can be done with reasonable numerical effort.

Second idea is a billard simulation: Place all circles in a whatever pattern and simulate a big pool billard. Pretty brute force and numerically very costly as well. I am a bit afraid of descretization issues as well.

Number 3 is more mathematical and is based on defining a potential field for every circle with a random "strength", so that there is some kind of gravitation between the circles and calculate the equilibrium state. The development of a mathematical model for this is not trivial and would be quite a mission...

So - finally - the question: What are your suggestions to solve the problem as leightweight as possible? Do you know algorithms I should look at to solve this? What are your remarks to my ideas?

Thank you all a lot in advance! I am excited to read your answers.

Answer 1

Start by using the basic algorithm to draw as many as possible circles that don't collide. When it finishes (and it can't reach 200 circles), start pushing in circles. I mean physically push them in with a physics engine: http://www.sgtconker.com/2010/09/article-xna-farseer-platform-physics-tutorial/ (without using gravity).

Answer 2

2 ideas:

Instead of thinking of the square as a closed box, take the top away and allow the circles to fall under the effects of gravity into the open box. By altering the position of the circles before they fall you create randomness. This might be the same or similar to your billards example.

or

Use Quadtrees to divide up the space in the box and place randomly checking for overlap using collision detection, which in this case might only need to be the center of the circle to another center is greater than double the radius and the walls of the box are greater than a radius away. By using quadtrees this will make the algorithm more efficient.