Introduction: The "Brute Force" Trap
I’ll be honest: I thought this would be easy. My goal was simple: fit as many non-overlapping circles as possible into a 100x100 pixel grid.
My first instinct was to use a standard Brute Force approach. I wrote a script to randomly guess x, y coordinates and radii. I let it run for hours. The result? A mess. The circles either overlapped constantly or left huge, inefficient gaps. The problem wasn't the geometry; it was the grid.
Unlike pure math, where a circle can be at position 10.5553, my system was constrained to an Integer Grid (pixels). This seemingly small constraint broke standard geometric formulas. The "perfect" mathematical position was often "illegal" in my pixel grid.
I realized I didn't need a calculator; I needed an evolution. I needed an algorithm that could "learn" the landscape of the grid. That’s why I turned to Differential Evolution.
The Logic (Defining the Chaos)
In a perfect world, I could use Descartes' Circle Theorem to calculate exactly where every circle should go. That gives you those beautiful, symmetric patterns (often called Apollonian Gaskets).
But my problem wasn't theoretical. It was practical.
I didn't want a pretty shape; I wanted density. I wanted to know: "If I throw 10 circles into this box, what is the absolute best way to arrange them so they don't overlap, but also waste zero space?"
This is where standard formulas fail. Formulas break when you force them onto an Integer Grid (pixels). A formula might say the circle belongs at x=50.4, but my pixel grid only allows x=50 or x=51. That rounding error causes overlaps.
So, I had to treat this as an Optimization Problem, not a Geometry problem.
The "Chromosome" Strategy
I set up the problem for the Differential Evolution algorithm by defining a "Chromosome", a single list of numbers that represents the entire solution.
Instead of solving for one circle at a time, I told the solver:
"Here is a list of 30 numbers representing 10 circles (x, y, radius for each). Shuffle these numbers until you minimize the 'Pain'."
The "Pain" (Objective) Function
This is the secret sauce. The algorithm needs to know when it's doing a bad job. I defined "Pain" (Cost) using two simple rules:
The Overlap Penalty: If the distance between two circles is less than the sum of their radii, that's a collision. I added a massive penalty (10,000 points) for every pixel of overlap.
The Wall Penalty: If a circle crosses the grid boundary (x < 0 or x > 100), that's illegal. Another massive penalty.
The Reward: If the circles are safe, I subtracted the Total Radius from the score. This forces the algorithm to "inflate" the circles as much as possible to fill the empty voids.
The Implementation: From Theory to Python
Here is the exact script I used. I utilized scipy.optimize.differential_evolution because it handles the "stochastic" (random) nature of this problem much better than standard gradient descent.
Notice the objective function. This is where the magic happens. It’s not just math; it’s a set of strict rules telling the algorithm exactly what "failure" looks like.
import numpy as np from scipy.optimize import differential_evolution import matplotlib.pyplot as plt import matplotlib.patches as patches # 1. CONFIGURATION # We define the constraints of our "Integer Grid" GRID_SIZE = 100 N_CIRCLES = 10 def objective(x): """ The Cost Function. The goal is to MINIMIZE this score. High Score = Bad (Overlaps). Low Score = Good (Packed). """ # Reshape the flat list back into (x, y, r) for each circle circles = x.reshape((N_CIRCLES, 3)) penalty = 0 for i in range(N_CIRCLES): xi, yi, ri = circles[i] # Rule 1: Don't leave the grid! # If a circle crosses the 0 or 100 line, punish it heavily. if xi - ri < 0 or xi + ri > GRID_SIZE: penalty += 1000 if yi - ri < 0 or yi + ri > GRID_SIZE: penalty += 1000 # Rule 2: Don't touch your neighbors! for j in range(i + 1, N_CIRCLES): xj, yj, rj = circles[j] # Calculate distance between centers dist = np.sqrt((xi - xj)**2 + (yi - yj)**2) # If distance < sum of radii, they are overlapping if dist < (ri + rj): # The penalty scales with how bad the overlap is penalty += 10000 * (ri + rj - dist) # Rule 3: Be Big! # We subtract the total radius because 'differential_evolution' # tries to minimize the number. Subtracting makes it want larger circles. total_radius = np.sum(circles[:, 2]) return penalty - total_radius # 2. THE EVOLUTION # We set bounds for x (0-100), y (0-100), and radius (1-25) bounds = [(0, GRID_SIZE), (0, GRID_SIZE), (1, GRID_SIZE/4)] * N_CIRCLES # This line runs the genetic algorithm. It breeds generation after generation. result = differential_evolution(objective, bounds, maxiter=100, workers=-1) # 3. VISUALIZATION # Plot the winner to see if it actually worked fig, ax = plt.subplots(figsize=(6, 6)) best_circles = result.x.reshape((N_CIRCLES, 3)) for c in best_circles: circle = patches.Circle((c[0], c[1]), c[2], edgecolor='blue', facecolor='cyan', alpha=0.5) ax.add_patch(circle) ax.set_xlim(0, GRID_SIZE) ax.set_ylim(0, GRID_SIZE) ax.set_aspect('equal') plt.title(f"Optimized Packing on {GRID_SIZE}x{GRID_SIZE} Grid") plt.show()
The Result
After running the evolution for just a few seconds (approx 100 generations), the algorithm converged.
Unlike Brute Force, which blindly guesses, you can watch Differential Evolution "learn." In the first generation, circles are overlapping everywhere. By generation 50, they have learned to separate. By generation 100, they expand to fill the available voids.
Conclusion: Chaos is Efficient
When I started this experiment, I wanted a perfect, symmetric packing. I failed. But in failing, I found something more useful.
By treating the "Circle Packing Problem" as an evolutionary optimization task rather than a geometry task, I was able to solve it on a constrained Integer Grid, something standard formulas struggle with.
The final result isn't a perfect fractal. It’s chaotic. It’s messy. But it is dense. The algorithm found a way to utilize 78% of the available grid space in under 30 seconds of compute time.
For developers working on sprite sheets, texture atlases, or even physical storage systems, this is the lesson: Sometimes, you don't need the perfect formula. You just need a good definition of "Pain," and enough generations to evolve a solution that works.
Top comments (0)