I was looking through some of Tyler Hobbs’s work recently, and I came upon this blog post about how he produced generative art by packing circles into polygons. Like Tyler, I used a brute force approach to fit my circles into polygons, which you can see here: Circle Packing in Polygons / Harry Stevens / Observable.
It’d be fun to try to improve this algorithm. Anyone know how?
I guess trying to fit a big circle when you are struggling to place even small circles is a waste of iterations.
So there must be some nice cooling function that changes the shape sampling function as time goes on.
An infinitesimally small shape p of being placed is % of shape occupied. It monotonically is harder to place as the shape increases in size. It is impossible to place a shape whose size is bigger than the arena.
I expect there is a nice analytical approximation to this curve
prediction: I think if you adjust the shape sampler to use a fixed size circle (based on current arena occupancy), you can end up with a similar distribution but with an order of magnitude fewer samples to achieve a given density.
EDIT: now I look at it I see you don’t have any very large circles because your shape size sampler is truncated at a certain size
Is the goal to fit a fixed set of circles into the shape, or to fill the shape with as many circles as possible (down to a lower radius bound)?
I’m thinking that triangulation might be an option:
There’s some handwaving with regard to the handling of nodes on the edge (not fully surrounded by triangles), but applying a variety of rules to the splitting should allow for a broad range of possible outcomes.
Right now the code tries to pack N circles, but the actual goal is just to make it look pretty, so the second approach you suggested might be better.
Here’s my first, failed attempt at an optimization. The area of a new circle cannot be greater than the remaining area inside the polygon. I thought I could use that fact to avoid testing circles whose areas were greater than the area of the remaining space in the polygon.
I started by measuring how much space was left over inside of the polygon after the packing completed. Unfortunately, I found that, even after packing 2,000 circles, the area of the polygon minus the sum of the area of the circles was still greater than the area of the largest circle I tried packing at the very beginning.
Take, for example, this hexagon:
Its area is 256,000 pixels. Even after packing all 2,000 circles, the sum of their areas is 151,731 pixels. That leaves an area of 104,269 pixels. If we were to somehow recombine that leftover area into a circle, that circle would have a radius of 182 pixels, which is more than the 64-pixel radius of the largest possible circle. As Toph Tucker might say, there’s plenty of room in the corners.
I still like the idea of testing progressively smaller circles, but they need to get smaller some other way.
Some more links:
Both suggest using an advancing wavefront.
Another approach to try, maybe, would be to select a center at random, continue if it’s already inside a circle or outside the polygon; measure the maximum radius r that it can have, and set its radius to r * Math.random().
For the record, I no longer think that my triangulation idea is viable. Without some very ingenious (read: complicated) bisection rules the circles would either end up at similar sizes or would produce a lot of empty areas.
I notice you don’t have any fancy collision data structure and compare each circle to every other. In the 2D plane you can
maintain all circles ordered by x (xsort)
if you try to insert a circle a xz, yz with radius rz, you can range query xsort for xz - xr < X < xz + xr and then do the intersection tests on the results.
