Circle Packing Using Stochastic Search
All Processing code for this article, along with images and animated GIFs, can be found on Github
In this post I’m going to explain the idea behind stochastic search and a few examples of how it can be applied to circle packing.
What is Stochastic Search?
“Stochastic search” is just a fancy way of saying that we’re going to perform a random search until some condition is met. This is particularly useful for problems where a systematic approach is far too computationally expensive.
Now we’re interested in stochastic search within the context of generative art where the biggest application is in packing shapes. The basic algorithm for stochastic search looks like this:
Start with an initial state
while (some exit condition is not met) {
Generate a random candidate solution
if (It is a valid solution in the current state) {
Great! We now have a new state for the next iteration.
}
}
This might seem vague at this point, so let’s actually implement some examples in Processing so we can play around with it.
Circle Packing
We’re going to apply stochastic search to the problem of packing circles of different sizes into a specific area.
Let’s start with a simple Circle class. Each circle has an (x, y)
coordinate that specifies its center, and a radius r.
class Circle {
float x;
float y;
float r;
Circle(float x, float y, float r) {
this.x = x;
this.y = y;
this.r = r;
}
void draw() {
noStroke();
colorMode(HSB, 360, 100, 100);
fill(280 + random(-10, 10), 100, 100);
ellipse(x, y, 2*r, 2*r);
}
};
In the above code, we define two methods for our Circle class: a constructor
to initialize a new object and a draw() method that draws it onto the screen
using a random color.
We then define an ArrayList of Circle objects that we’re going to add to
every time we find a “valid” circle to place on the screen.
ArrayList<Circle> circles;
void setup() {
size(500, 500);
circles = new ArrayList<Circle>();
background(255);
}
Now we get to the draw() function which serves as one iteration of our
stochastic search loop. Recall that what we want to do is (i) generate a
random candidate solution, (ii) check if it’s valid, and (iii) trigger
some kind of exit condition so the sketch stops at some point.
Here is a simple version below:
int failed_tries = 0;
void draw() {
Circle nc = new Circle(random(width), random(height), 16);
if (isValidCircle(nc)) {
nc.draw();
circles.add(nc);
} else {
failed_tries++;
if (failed_tries > 16 * 1024) {
println("Done!");
noLoop();
}
}
}
In the above code, we first create a Circle object at a random location on
screen, with some fixed radius (16 pixels). We then check if this circle
satisfies certain conditions that we want using a yet-undefined
isValidCircle() function. If it turns out to satisfy all our conditions,
and isValidCircle() returns true, we draw this circle to the screen and
add it to the list of all valid circles (you’ll see in a bit why we need this
array in the first place).
If, on the other hand, some condition wasn’t met and isValidCircle() returned
false, we increment a counter (failed_tries, initially set to 0) specifying how many unsuccessful
tries we’ve had. If the number of failed tries exceeds some threshold (in the
above code, I arbitrarily picked 16 * 1024 tries), then we call the noLoop()
function which ends the sketch.
Now, we of course still need to define our isValidCircle() method! What should
go in this? Well, it depends on what you want! Let’s me give you some examples
to show you what I mean.
Tightly Packing Circles
Suppose we want to tightly pack circles, and when I say tightly packed, I just mean that we allow circles to be touching, placed right next to each other.
So what should our isValidCircle() function look like for this? Here it is:
class Circle {
...
boolean collides(Circle c) {
if (dist(x, y, c.x, c.y) < (r + c.r))
return true;
return false;
}
...
};
boolean isValidCircle(Circle new_circle) {
for (Circle c : circles)
if (new_circle.collides(c))
return false;
return true;
}
Let’s first look at the isValidCircle() function itself. Recall that the
parameter new_circle that is provied as a parameter is the randomly-create
circle in our draw() function. We iterate over every currently-valid circle
(see why we need the circles list now?) and if any of them collides with
our circle, we return false. Otherwise, if the loop completes without
any problems, which means no current circle collides with the newly-created one,
we return true.
Now let’s look at the collides() function we add to the Circle class. It
takes as a parameter a circle, and checks if this circle collides with it. How
do we check if two circles collide? It’s easy: if the distance between their
centers is less than the sum of their radii, then they collide! We use Processing’s
dist() function here.
And that’s it! Here’s how it looks, although it takes much longer to actually
generate because of the failed tries. On my machine it took around 15 minutes!
In general, the higher you set the threshold for failed_tries, the better
a packing you get, but the longer it takes.
Packing Circles with Margins
Suppose we want to add some margins to separate circles by a small distance.
We can simply modify our collides() function to account for this! All we
do is account for it in our distance calculation. We only consider a circle
to collide with another if the distance between their centers is greater than
the sum of their radii and a user-specified margin (in the MARGIN variable
below).
int MARGIN = 10;
class Circle {
...
boolean collides(Circle c) {
if (dist(x, y, c.x, c.y) < (r + c.r + MARGIN))
return true;
return false;
}
...
};
And here is the result. Note how the circles are no longer touching and are separated by a margin of at least 10 pixels!
Packing Circles of Different Size
We can also modify our loop to pack circles of different sizes!
We do this by reducing the radius of the randomly-created circle when the number of failed tries at a given radius exceeds some threshold. Here is an example loop I wrote for doing this.
float RADIUS_MAX = 16;
float RADIUS_MIN = 2;
float current_radius;
int failed_tries = 0;
void setup() {
...
current_radius = RADIUS_MAX;
...
}
void draw() {
Circle nc = new Circle(random(width), random(height), current_radius);
if (isValidCircle(nc)) {
...
} else {
failed_tries++;
if (failed_tries > 32 * 1024 / current_radius) {
current_radius /= 2;
failed_tries = 0;
if (current_radius < RADIUS_MIN) {
println("Done!");
noLoop();
}
}
}
}
In the above loop, the first change we make is that we create circles based on
a radius stored in a current_radius variable (which is initialized to RADIUS_MAX in setup()).
Second we modify the exit condition of our loop. Recall that earlier we called
noLoop() when the number of failed tried exceeded a threshold. Instead, now
when we exceed a threshold, we reduce current_radius by half and reset
failed_tries to zero.
Next, we change our threshold for failed_tries to be dependent on the
current radius. Why? The reason is that we want more tries when the radius is
smaller since the screen will already be packed with bigger circles, making it
harder to find a valid circle.
Finally, we still need to finish the sketch at some point. In this case, we end the sketch if we hit our threshold of failed tries and the new, halved radius is less than a specified minimum radius (RADIUS_MIN).
And that’s it! We now have a circle packing algorithm that looks like this:
Packing Inside a Shape
The approach is also very flexible in that isValidCircle() can be modified
to account for other conditions, such as whether it is inside a custom shape.
Here’s a simple version of isValidCircle() that additionally checks if it
inside a radius of 200 pixels from the center of the screen (see the first two
lines).
boolean isValidCircle(Circle nc) {
if (dist(nc.x, nc.y, width/2, height/2) > 200)
return false;
for (Circle c : circles)
if (nc.collides(c))
return false;
return true;
}
Of course, in order to improve this, we can also be a little smarter about how we generate our random circles, but I leave that to you as an exercise (read: I’m lazy!).
And here is the result:
Really, this can be extended to account for any condition you want. For example,
you can check if the circle is inside a polygon (see here for Tyler Hobbs’
polygonContainsPoint() function)
Allowing Overlapping Circles
Here is another example showing the flexibility of this simple algorithm. We set the margin between circles to a negative number, therefore allowing the overlapping of circles.
int MARGIN = -5;
And here is the result!
I also did one with a much longer run to get the following image.
You can even try to modify the exit condition so that it stops the sketch when no more white pixels remain on the screen, although it would take significantly longer.
Next Steps
You can try implementing similar stuff for rectangles or arbitrary polygons. In a future post, we’ll also look at how we can speed this up significantly using spacial search with a QuadTree. Stay tuned!
In the meantime, you can subscribe to my list to stay informed on new posts! No spam, guaranteed.
