Shape packing with P5.js
In my last post I mentioned that I was working on daily art for #genuary2022. I've been learning a lot of new techniques, like flow fields, dithering, and shape packing. In this post, I'm going to talk about the shape packing algorithm that I used to create the above image.
I start off with some boilerplate P5 code, to create an image and add a background.
let c,
bg;
function setup() {
createCanvas(1280, 1280);
c = "#f3e5dc";
bg = color("#142b42");
background(bg);
}
function draw() {
}Now, what I want to do is start adding circles (or whatever shape), and grow each one until it touches another circle, or the edge of the image. So for each circle, we need to do a check of whether or not the length of the radius of one circle and the length of the radius of any other circle is greater than or equal to the distance between them, and also check to see if the distance between the center of the circle and the edge of the image is less than or equal to the radius of the circle.
In pseudocode:
foreach circle in circle_array {
if (distance between current_circle.center + circle.center < current_circle.radius + circle.radius) {
current_circle.stop_growing();
} else {
current_circle.grow();
}
if (distance between current_circle.center.x and image.left or image.right < current_circle.radius
OR distance between current_circle.center.y and image.top or image.bottom < current_circle.radius) {
current_circle.stop_growing();
} else {
current_circle.grow();
}Before I get to that logic, though, I want to create a class for my shape. This way, the shape info, like the radius and coordinates, are self-contained. Each of these shapes will be added to an array instantiated at the top of the file.
let c,
bg,
shape_array = [];
function setup() {
...
}
class Shape {
constructor(x, y, radius) {
this.x = x;
this.y = y;
this.r = radius;
}
draw() {
stroke(c);
strokeWeight(1);
noFill();
circle(this.x, this.y, this.r * 2);
}
grow() {
this.r++;
this.draw();
}
}
function draw() {
background(bg); // Clear the background on every iteration!
let shape = new Shape(random(0, width), random(0, height), 1);
shape_array.push(shape);
for (let s of shape_array) {
s.grow();
}
if (frameCount > 100) {
noLoop();
}
}You see that I've added a simple Shape class that creates a circle at a random coordinate with two methods, draw() and grow(). We'll use grow when we want the shape to expand, and draw when it needs to remain a static size. For now, I'm creating new shapes on each frame, pushing them to an array, iterating over that array, and drawing a circle that grows by two pixels in diameter each frame. The result looks like this:
Now, we'll add a function to detect if a circle has hit the edge of the image, and stop just that circle if it has.
function detectEdgeCollision(shape) {
if (
dist(shape.x, shape.y, 0, shape.y) <= shape.r ||
dist(shape.x, shape.y, width, shape.y) <= shape.r ||
dist(shape.x, shape.y, shape.x, 0) <= shape.r ||
dist(shape.x, shape.y, shape.x, height) <= shape.r
) {
return true;
}
return false;
}
function draw() {
background(bg); // Clear the background on every iteration!
let shape = new Shape(random(0, width), random(0, height), 1);
shape_array.push(shape);
for (let s of shape_array) {
if (detectEdgeCollision(s)) {
s.draw();
} else {
s.grow();
}
}
if (frameCount > 100) {
noLoop();
}
}The circles stop as they the edge of the image now. Instead of growing the shape, it just draws the shape at the same radius.
Next, there needs to be another, similar, function to detect if two circles are going to collide.
function detectShapeCollision(shape, array) {
for (let i = 0; i < array.length; i++) {
let shape2 = array[i];
let distance = dist(shape.x, shape.y, shape2.x, shape2.y);
if (distance !== 0 && distance <= shape.r + shape2.r) {
return true;
}
}
return false;
}
function draw() {
background(bg); // Clear the background on every iteration!
let shape = new Shape(random(0, width), random(0, height), 1);
shape_array.push(shape);
for (let s of shape_array) {
if (detectEdgeCollision(s)) {
s.draw();
} else if (detectShapeCollision(s, shape_array)) {
s.draw();
} else {
s.grow();
}
}
if (frameCount > 100) {
noLoop();
}
}
The shapes stop growing as they touch each other, but it doesn't keep new shapes from propagating inside of old shapes. If we were using shapes with a fill this wouldn't matter, but since these shapes are outlined only, we need to filter out any shapes that trigger shape collision and have a radius of 1, which indicates a brand-new shape.
function detectShapeCollision(shape, array) {
for (let i = 0; i < array.length; i++) {
let shape2 = array[i];
let distance = dist(shape.x, shape.y, shape2.x, shape2.y);
if (distance !== 0 && distance <= shape.r + shape2.r) {
if (shape.r === 1) {
array.pop();
}
return true;
}
}
return false;
}In my Genuary piece I filter out stars that are larger than the default radius, which requires removing them from the array by index, but since we're just looking for newly-created shapes with this filter, we can just pop them off the end of the array.
This is starting to look good! Finally, I want to try to get as many circles in as I can, instead of just stopping at the 100th frame. So, I'm going to create a global variable to count how many circles I've "killed" (by popping them off of the array), and once that hits a certain number I can assume that my image is sufficiently full, since new shapes are populating inside of old shapes.
I've also added a radius > 1 check to only draw the circle if it's passed the initial check to make sure it's not inside of another circle. This eliminates the small flashing shapes that are being deleted.
Here's the final code!
let c,
bg,
shape_array = [],
kills = 0;
function setup() {
createCanvas(1280, 1280);
c = "#f3e5dc";
bg = color("#142b42");
background(bg);
}
class Shape {
constructor(x, y, radius) {
this.x = x;
this.y = y;
this.r = radius;
}
draw() {
stroke(c);
strokeWeight(1);
noFill();
circle(this.x, this.y, this.r * 2);
}
grow() {
this.r++;
this.draw();
}
}
function detectEdgeCollision(shape) {
if (
dist(shape.x, shape.y, 0, shape.y) <= shape.r ||
dist(shape.x, shape.y, width, shape.y) <= shape.r ||
dist(shape.x, shape.y, shape.x, 0) <= shape.r ||
dist(shape.x, shape.y, shape.x, height) <= shape.r
) {
return true;
}
return false;
}
function detectShapeCollision(shape, array) {
for (let i = 0; i < array.length; i++) {
let shape2 = array[i];
let distance = dist(shape.x, shape.y, shape2.x, shape2.y);
if (distance !== 0 && distance <= shape.r + shape2.r) {
if (shape.r === 1) {
array.pop();
kills++;
}
return true;
}
}
return false;
}
function draw() {
background(bg); // Clear the background on every iteration!
let shape = new Shape(random(0, width), random(0, height), 1);
shape_array.push(shape);
for (let s of shape_array) {
if (detectEdgeCollision(s)) {
s.draw();
} else if (detectShapeCollision(s, shape_array)) {
if (s.r > 1) {
s.draw();
}
} else {
s.grow();
}
}
if (kills > 10000) {
console.log("stopped");
noLoop();
}
}And the final image, with 10k "kills". There are plenty of refinements that can be made, but for basic shape packing this isn't too bad!
If you want to look at something a bit more complicated, you can find the code for my Genuary star design at GitHub.