# The Circle Packing Algorithm

Implemented a mathematically beautiful generative pattern that looks deceivingly complex to the human.

###### Abdush Shakoor ● December 8th, 2019

Beautiful, isn't it? It might look complex but it's mathematically quite impressive. Making this pattern wasn't hard but it definitely took a lot of trial and error to get it right and honestly, I don't really know if it's this is the most efficient way to generate this pattern.

## How it works?

In order to achieve that "stacked" effect, there are two things to keep in mind:

1. Generate circles with a random radius
2. Look for collisions with other circles

The logic is quite similar to the Overlapping Rectangles problem except this is done with circles.

## Generate circles with dynamic radius

This method will help generate valid circles with a random radius. Circles that don't overlap or collide with other circles are considered to be valid.

    
// Generate a valid circle
const generateCircle = () => {
let newCircle;
let isValidCircle = false;

for(let i=0; i<attempts; i++) {
newCircle = {
x: Math.floor(Math.random() * width),
y: Math.floor(Math.random() * width),
};

if(checkForCollision(newCircle)) {
continue;
}
else {
isValidCircle = true;
break;
}
}

if(!isValidCircle) { return; }

if(checkForCollision(newCircle)) {
break;
}
}

circles.push(newCircle);
drawCircleOnCanvas(context, newCircle, colors[Math.floor(Math.random() * colors.length)]);
}



## Look for collision with other circles

Thanks to some online research, I was able implement the Euclidean Distance equation that helped with calculating the distances between each circle and detect for collisions. Along with that, I also found another article on Touching Circles that was quite useful.

These are the formulas used to detect the collision:

1. Find the distance between two centres $AB = \sqrt{ (x2 - x1)^2 - (y2 - y1)^2}$

2. Calculate the radii of both circles. $R = r1 + r2$

If the radii is greater than or equal to the euclidean distance of both circles, then it's a valid circle with no collisions.

    
// Check for collision in a canvas
const checkForCollision = (newCircle) => {

let x2 = newCircle.x;
let y2 = newCircle.y;

/*
Determine the euclidean distance between two circle
using Pythagorean Theorem.

Refer to:
https://en.wikipedia.org/wiki/Euclidean_distance
*/
for(let i=0; i= euclidDistance) {
return true;
}
}

// Check collision on top
if(x2 + r2 >= width ||
x2 - r2 <= 0) {
return true;
}

// Check collision on bottom
if(y2 + r2 >= width ||
y2 - r2 <= 0) {
return true;
}

//else return false
return false;
}



## Conclusion

I'm thinking of implementing more generative patterns like Triangular Mesh and Piet Mondrian's Red, Blue and Yellow composition.