# The stuff I do

## Circle packing algorithm (with kittens 🐱)

- 758 words -

← Posts

Inspired by a video by Daniel Shiffman on YouTube I decided to create a short little project involving circle packing and kittens.

Before reading my rambling go and watch the kitties in the demo.

Note that for a reason that I don't understand for now, the demo seems to be working only with chromium/chrome... Maybe I'll investigate that later on

And if that was cute enough to make you want to see the code, here you are.

### What does it mean? 🔗

To quote wiki

In geometry, circle packing is the study of the arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap.

And to quote the same source

A kitten is a juvenile cat. After being born, kittens display primary altriciality and are totally dependent on their mother for survival.

So for this project I wanted to use some really cute pictures and duplicate them with a bunch of non overlapping circles.

Before packing circles on these cuties we first need to load the images in our p5.js sketch. To do so I created a `reset()` function which will be used each time I need a new image. It's goal is to get the color of each pixels on the image so that we can use the color later on:

``````const IMAGES = [
'data/kitten1.png',
'data/kitten2.jpg',
'data/kitten3.jpg'
];

function reset() {
// Stop calling draw() while we load the picture otherwise we break everything
noLoop();

// iterate through my image list
imgIndex++;
if (imgIndex >= IMAGES.length) {
imgIndex = 0;
}
const path = IMAGES[imgIndex];

// load the image and get the color for each of its pixels
img = loadImage(path, (img) => {
pixelDensity(1);
circles = [];
imgColors = [];

let d = img.pixels.length;
for (let i = 0; i < d; i+=4) {
r = img.pixels[i];
g = img.pixels[i+1];
b = img.pixels[i+2];
a = img.pixels[i+3];

imgColors.push(color(r, g, b, a))
}

// Start the packing again!
loop();
});
}``````

Because p5.js is constantly calling the `draw()` function I need to use a little trick calling `noLoop()` to avoid calling `draw()` while there is no data, otherwise things will not work.

The interesting part of this function is how p5 gives access to the pixels of an image: After calling `img.loadPixels()`, the `img` object will have a `pixels` property containing a list of integers. For each pixels in the image, four integers are added to `pixels` one for each of the RGB values of the pixel and a last one for its alpha value.

Once we looped through all these values we have an array `imgColors` containing for `P5.Color` object 🎉

### Generating circles 🔗

Before we pack the image with circles we need to generate one of them. Here our goal is the following: Return a new circle which does not overlap the others or return nothing (we will handle the failed generations later). So far the algorithm is not very complex: We have a list of existing circles `circles` (Empty at the beginning), we generate a random position `(x, y)` and a radius `r`, we then iterate on the list of existing circles and test if its distance to the newly generated one is larger than the sum of their radius (i.e. they don't overlap).

``````function newCircle() {
let x = random(img.width);
let y = random(img.height);
let r = random(MAX_INITIAL_SIZE);

const intersection = circles.findIndex(other => {
if (dist(x, y, other.x, other.y) < other.r + r) {
return true;
}
return false;
});

if (intersection !== -1) {
return;
}

let color = imgColors[int(x) + int(y) * img.width];
return new Circle(x, y, r, color);
}``````

Now that we can generate one circle let's make a function which tries to generate a given amount of circles so that one iteration will see several ones created:

``````function newCircles() {
let totalNewCircles = NEW_CIRCLES_BY_ITERATION;
let remainingAttemps = NEW_CIRCLES_ATTEMPTS;
let countNewCircles = 0;

while (countNewCircles < totalNewCircles && remainingAttemps > 0) {
remainingAttemps--;

const newC = newCircle();
if (newC !== undefined) {
circles.push(newC);
countNewCircles++;
}
}
}``````

Of course the more circles we generate the harder it become to find the right spot for a new one, that why we need to use a maximum number of attempts to avoid blocking the main loop.

### And making them grow 🔗

Now that we can generate a bunch of new circle on each iteration, let's make them grow too and that's how we pack circles on kittens 💪

← Posts

### Related posts

Posts in the same category: [p5]