Draw n identical circles without overlap and centre gravity

Question

I was looking at a set of 100 PowerPoint slides which have same sized red circles with the first slide having 1 circle and the 100th slide having 100 circles. On each slide the circles don't overlap and while they are semi-randomly placed, they tend to gravitate towards the center and are not too close to each other (there are no extreme outliers that I can see). You can take a look at the slides yourself here).

These seem to have been created by hand (which must have taken a really long time!), and I got to thinking about what the best way would be to programmatically create something like this (interesting toy problem - automate the boring stuff)?

I have been thinking along the following lines.

For each slide up to n circles:

1. Generate coordinates for a circle at a random point on a canvas.
2. Calculate a larger diameter (for some value of larger) for this circle and all others already on the canvas and check the new circle doesn't overlap with any existing circles using the computed larger diameters (to stop the circles being too close together). Move on if ok, otherwise begin 2 again.
3. To stop outliers, do some sort of a check to ensure the newly generated circle is no further than x distance away from the centers of 3(?) existing circles?
4. If all checks out keep the new circle and start at 1 again until have enough circles.
5. Find some way to generate a png or something for each canvas.

Would also need to find a way for at least the first few circles to tend towards the center.

But while I like to think through problems my coding chops need work and there must be some sort of great algorithm or something to do this correctly?

Happy for any pointers or for anyone to have a crack at it - would especially love to read some python implementations to learn from.

[I know this may not exactly fit the StackOverflow style but not sure where else to go to get ideas on the problem].

Answer 1

Your requirements basically mean that you want to pick the centers of the circles using Poisson Disc sampling:

https://www.jasondavies.com/poisson-disc/

... so at least there's a lot of literature about it.

That gets you everything except the "center of gravity". There are a few different ways to do that, but the simplest way is to generate your circles in a smaller area, and then stretch the edges out.

For example, you could move each circle away from the center of the slide so that a circle at distance d moves to distance d^1.5 or so.

Answer 2

Iterative relaxation would be a common approach to something like this.

Basically, you start by randomly placing n circles. Then you do a number of iterations to try to move the circles into a more pleasing configuration.

For each circle C, you measure the distance to the other circles, and for each one, you calculate a force C which pushes C away from that other circle. The direction of the force will be opposite to the direction to the other circle, and the magnitude will generally be inversely proportional to the distance. (So the force would behave similar to gravity, but in the opposite direction.) You sum up all the forces on C, similarly sum up forces on all other circles, and then move each circle a little bit, based on the total force on it. (You'll also need a force keeping the circles away from the edges.) That's one iteration, and afterwards, the circles should be in a slightly better configuration than they were before.

Now, if you do this for a huge number of iterations, you'll likely end up with a regular hexagonal tiling, which won't look very interesting. So you might want to stop before then, or add another force keeping each circle from moving too far from its original position, or ignore any forces from other circles more than a given distance away, or not move a circle if its summed force is below a given magnitude.

Incidentally, a lot of what you'd be doing is pretty similar to smoothed-particle hydrodynamics, a fluid simulation method. Here's a video of, a Python-based simulation of, well, rather more than 100 spheres simulating a water splash, based almost entirely on individual spheres trying to stay the correct distance away from nearby ones.