A Randomized Approach to Circle Packing
A few months ago, I got really into circle packing. The goal of circle packing is basically to cram a bunch of circles into a space as tightly as possible. This is actually a well-explored area of mathematics (just check out the Wikipedia article), but I wanted something simple that's easy to implement and has a nice aesthetic effect. I opted for a brute-force approach that tries to place a circle in thousands of random locations until a fit is found. I'll describe the details of that and some of the artwork that I've created with this approach.
The Basic Algorithm
To begin, I pick the size of the circles I want to insert, and roughly how many circles of each size to use. For example, I may ask for 10 circles with radius 50 and 300 circles with radius 10. The count is "rough" because it's just an upper bound -- the algorithm may give up before hitting that number.
The algorithm begins with the largest circles and ends with the smallest circles. For each circle size, it attempts to insert new circles until it hits the requested count or there are 2000 failed attempts in a row. Once the count or failure limit is hit, it moves on to the next smaller size. I picked 2000 failures to provide a balance between performance and the final density. A lower number can be used to give up more quickly, or a higher number can be used to pack the circles with higher density.
To see if a randomly chosen location is a good fit for a new circle, we need to check for collisions with any other circles. Fortunately, it's very efficient to check for a collision of two circles: you just need to see if the distance between their center points is larger than the sum of their radii. Another improvement to efficiency comes from checking against the largest circles first. A large circle covers more area, making it more likely to be responsible for a collision.
Combined with some colors, this procedure is really all it took to produce Take Me to the Desert:
Take me to the Desert, 2016
Filling an Arbitrary Polygon
Filling any arbitrary polygon with circles is a little trickier, because we not only need to check for collisions with other circles, but also with the border of the polygon. Checking if a circle is inside of a polygon is more complex and more expensive to compute. Fortunately, there's a pretty well known solution. Here's my version in Java:
public static boolean polygonContainsPoint(int[] polygonXPoints, int[] polygonYPoints, int testX, int testY) {
int numVerts = polygonXPoints.length;
boolean c = false;
int j = numVerts - 1;
for (int i = 0; i < numVerts; i++) {
double deltaX = polygonXPoints[j] - polygonXPoints[i];
double ySpread = testY - polygonYPoints[i];
double deltaY = polygonYPoints[j] - polygonYPoints[i];
if (((polygonYPoints[i] > testY) != (polygonYPoints[j] > testY)) &&
(testX < (((deltaX * ySpread) / deltaY) + polygonXPoints[i]))) {
c = !c;
}
j = i;
}
return c;
}You just pass in a list of x and y vertices that make up the polygon along with a point to test, and you get back a boolean to let you know if the point is inside the polygon.
To know if a circle is fully inside a polygon, you technically need to check every point in the circle. However, for our purposes, just checking some of the points around the circle is good enough. I opted to test a decihexagon (16 points) with the same centerpoint and radius as the circle:
for (int k = 0; k < 16; k++) {
double theta = Math.PI * (k / 8.0);
int pointX = x + (int) (radius * Math.cos(theta));
int pointY = y + (int) (radius * Math.sin(theta));
if (!polygonContainsPoint(xPolygon, yPolygon, pointX, pointY)) {
// move on to the next location
}
}With the ability to fill arbitrary polygons, we can now do cool stuff like Meet Me Inside, which fills many (potentially overlapping) polygons:
Meet Me Inside, 2016
Furthermore
A nice thing about this approach is that it's applicable to other shapes besides circles. For example, I've used the same technique for a series of works packing triangles:
Up There, 2016
I hope this inspires you to play around with circle packing and create new artwork!
–
From time to time, I write about my thoughts and artistic process. If you'd like to be notified the next time I publish an essay, sign up for my newsletter in the menu.