Circle packing with adaptive radius

Filling surfaces with a given number of equal sized disks without overlaps is a topic that has come up quite often here, and I’ve posted numerous examples and variations of how to do this with collisions.

However, one thing I’ve always wanted to improve upon is automatically finding the correct radius. It is possible to do this by manually adjusting with a slider until they fill the shape without overlapping, but I thought it would be nice if this radius could also be found by the solver.

So here’s a recent experiment with a new goal for this.


Adaptive_Circle_Filler.gh (57.5 KB)

This is still a bit experimental and fairly untested, and there’s probably improvement possible in the convergence for finding the radius, but I thought I’d share in its current state for anyone who’s interested. When opening the file you’ll need to set the assembly reference location, which is usually C:\Program Files\Rhino 7\Plug-ins\Grasshopper\Components

Related to this…
There is quite a lot of mathematical work published on the topic of optimal packings of N disks in a square (i.e. what arrangement allows the largest radius without overlaps), and it is a surprisingly tricky thing to solve. The solutions are often more chaotic looking than you might expect. Even for low N many of the results have only been found relatively recently, and of the solutions known there are only proofs of optimality up to 30, while above that the results are just the best found so far and could possibly be improved upon.

Circles_in_a_square.gh (37.2 KB)

Here’s another definition in which you can try your hand at finding the optimal arrangements. The solver adjusts the radius and finds the packing, but you can drag the points around to switch between the many possible local energy minima to try and find the global one as a sort of puzzle. It turns green when solved, and there are buttons to advance N. If you get really stuck there is a catalogue of the solutions at http://www.packomania.com/ (where there are also links to many other packing topics and references)

The difficulty of finding the solutions doesn’t increase linearly - 10 and 13 in particular are quite subtle, and harder to solve than many higher numbers.

16 Likes