Skip to content

Instantly share code, notes, and snippets.

@volfegan
Last active April 10, 2021 00:17
Show Gist options
  • Save volfegan/c65eac48249990dd87da86371eee98d1 to your computer and use it in GitHub Desktop.
Save volfegan/c65eac48249990dd87da86371eee98d1 to your computer and use it in GitHub Desktop.
Non overlapping circle packing
// author Volfegan [Daniel L Lacerda]
import java.lang.Math;
public class Circle {
public float x, y, r;
public Circle(float x, float y, float r) {
this.x = x;
this.y = y;
this.r = Math.abs(r); //radius of the circle
}
//check if this circle intersects another circle object
public boolean intersects(Circle other_circle) {
float xDist = Math.abs(other_circle.x - this.x);
float yDist = Math.abs(other_circle.y - this.y);
float rDist = this.r + other_circle.r;
//intersection happens when the distance from the circles centres is less than the sum of their radius
return rDist >= Math.sqrt(xDist*xDist + yDist*yDist);
}
public boolean equals(Circle other_circle) {
return this.x == other_circle.x && this.y == other_circle.y && this.r == other_circle.r;
}
}
//reference https://generativeartistry.com/tutorials/circle-packing/
//more info to improve efficiency
//http://paulbourke.net/fractals/randomtile/
//http://john-art.com/stat_geom_described_v5.pdf
//http://john-art.com/
ArrayList<Circle> circles = new ArrayList<Circle>();
float minRadius = 3;
float maxRadius = 100;
float totalCircles = 4000;
float createAttempts = 500;
void setup() {
size(1280, 720);
colorMode(HSB);
noFill();
clear();
for (int i=0; i < totalCircles; i++) {
float x, y;
if (random(1)<.7) {
//random position across the screen
x = random(width);
y = random(height);
} else {
//random position near the centre
x = (width/4) + randomGaussian(width /4, width / 8);
y = (height/4) + randomGaussian(height / 4, height / 8);
}
createCircle(x, y);
}
println(circles.size());
//save("circle_packing.png");
}
public float randomGaussian(float min, float max) {
return min + randomGaussian() * (max - min);
}
void createCircle(float x, float y) {
boolean safePosition = false;
float r = minRadius;
Circle circle = new Circle(x, y, r);
for (int i=0; i < createAttempts; i++) {
//check if circle collides with another and random walk it to a new postion if true
if (detectCollision(circle)) {
x+= random(-1,1);
y+= random(-1,1);
circle = new Circle(x, y, r);
continue;
} else {
safePosition = true;
break;
}
}
if (!safePosition) {
return;
}
//Grow radius of circle until a collision;
float inc = .1;
for (float radius = minRadius; radius < maxRadius; radius += inc) {
circle.r = radius;
if (detectCollision(circle)) {
circle.r -= inc;
break;
}
}
circles.add(circle);
stroke(random(255),255,255);
circle(circle.x, circle.y, circle.r*2);//Processing uses diameter
}
// Check if the circle collides with the others.
boolean detectCollision(Circle circle) {
for (Circle c : circles) {
if (circle.intersects(c) && circle.equals(c)==false) {
return true;
}
}
//check collision against screen size
if (circle.x+circle.r > width || circle.x-circle.r <= 0 ||
circle.y+circle.r >= height || circle.y-circle.r <= 0) {
return true;
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment