Circle packing problem

Lilarie

Hi! So here's the code to Daniel Shiffman's circle packing problem. I want to make some modifications.

1. Make the program put the circles beside each other which means dist = 0
2. Make it stop generating circles only when the canvass don’t have space anymore. (Also, only whole circles. I noticed there were partial circles on the edges of the tutorial. I think this means we do not randomize x and y)
3. Make the program choose from three sizes of radii instead of random sizes. For example, I want it to only generate circles of radii 20 (r1), 40(r2) and 60(r3). No other size of circles. Specifically 3 sizes of circle.

4. Also, I want the r1 circles to be of specific distance from each other. Like all r1 sized circles should be 120 pixels apart from each other.

   var circles = [];
   
   function setup() { 
     createCanvas(600, 600);
   
     var protection = 0;
   
     while(circles.length<300) {
       var circle = {
         x:random(width),
         y:random(height),
         r:random(10, 30)
       }
       var overlapping = false;
   
       for(var j = 0; j<circles.length; j++){
         var other = circles[j];
         var d = dist(circle.x, circle.y, other.x, other.y);
         if(d<circle.r + other.r){
           overlapping = true;
   }
       }
        if (!overlapping) {
         circles.push(circle);
       }
   
        protection++;
       if (protection > 10000) {
           break;
       }
     }
         for (var i = 0; i < circles.length; i++) {
       fill(255, 0, 175, 100);
       noStroke();
       ellipse(circles[i].x, circles[i].y, circles[i].r * 2, circles[i].r * 2);
     }
   
   }
   

kfrajer

I want to make it that the circles are drawn beside each other instead of random

Do you mean right beside each other or to be placed on the surface while none of them overlap with each other?

Kf

Lilarie

For them to be right beside each other, @kfrajer

TfGuy44

https://forum.processing.org/two/discussion/15473/readme-how-to-format-code-and-text#latest

Get this right. It's basically a prereq for people here to help you.

Lilarie

@TfGuy44 There it is. I'm sorry and thank you!

Chrisir

When you know the left edge of the box you can calculate the position of first circle by saying boxX + radius1

The second circle is this value plus radius2

You can use dist() to find out the distance

Maybe you read about (recursive) backtracking algorithm which would be one way of attacking this

Or you think like you have an imaginary list of 300 circles (different sizes) then you do all permutations and check each of them how many fit in the box (all circles would never fit but the order would be different every time.). An additional Variation is the placement when you're planning to place the boxes on x and y coordinates (when the box is higher than your circles diameter)

Chrisir

TfGuy44

Okay. Now that I can actually read the code you have posted without my eyes bleeding, I can see that it is generating a random candidate circle, checking it against all already placed circles, and then only placing the candidate circle if it doesn't create any overlaps.

Since it's the easiest thing to change, we might as well do it first: You only want three sizes of circles. So let's see what happens to this sketch if we only have three sizes of circles:

var circles = [];
var valid_sizes = [];
var valid_colors = []; 

function setup() { 
  createCanvas(600, 600);

  var protection = 0;

  valid_sizes = [ 20, 40, 60 ];
  valid_colors = [ color(255,0,0),color(0,255,0),color(0,0,255) ];

  while (circles.length<300) {
    var circle = { x: random(width), y: random(height), r: int(random(3)) };
    var overlapping = false;

    for (var j = 0; j<circles.length; j++) {
      var other = circles[j];
      var d = dist(circle.x, circle.y, other.x, other.y);
      if (2*d<valid_sizes[circle.r] + valid_sizes[other.r]) {
        overlapping = true;
      }
    }
    if (!overlapping) {
      circles.push(circle);
    }

    protection++;
    if (protection > 10000) {
      break;
    }
  }
  for (var i = 0; i < circles.length; i++) {
    fill(valid_colors[circles[i].r]);
    noStroke();
    ellipse(circles[i].x, circles[i].y, valid_sizes[circles[i].r], valid_sizes[circles[i].r]);
  }
}

Notice the changes here. The r property of a circle now ranges from 0 to 2. 0 means a small circle. 1 is a medium circle. 2 is a large circle. the valid_sizes[] array stores the sizes, and the circle's r property is used as an index into that array in all places where a radius was expected before (including in the code that checks for overlaps and drawing the circle!). A valid_colors[] array has also been added to draw each size in a different color. As before, r is the index into that array.

Lilarie

@Tfguy44 , this is amazing! Thank you! Is it also possible to put the circles right beside each other such that no space is wasted? My research is about space optimization.

Chrisir

Show your attempt please - did you read my post and the Wikipedia article? Tfguy can't do your work for you, that would be cheating, right?

Lilarie

Here it is, @Chrisir . I just think my codes aren't any good.

 "// noprotect"
var circles = [];

function setup() { 

    var canvasheight = 600;
    var canvaswidth = 600;
    var newradii=0;
    var newr3distance=60;
    var newr1=20;
    var newr2=40;
    var newr3=60;
  createCanvas(canvaswidth, canvasheight);

  var protection = 0;

   while(circles.length<canvaswidth+canvasheight)
     {
            var rsize=Math.round(Math.random()*3) + 1;
            if(rsize==1)
                newradii=newr1;
            else if(rsize==2)
                newradii=newr2;
            else if(rsize==3)
                newradii=newr3;

            var xaxis = Math.random() * ((canvaswidth-newradii) - newradii) + newradii;
            var yaxis = Math.random() * ((canvasheight-newradii) - newradii) + newradii;

            var circle = {
                x:xaxis,
                y:yaxis,
                r:(newradii, newradii)
            }
            var overlapping = false;

            for(var j = 0; j<circles.length; j++){
                var other = circles[j];
                var d = dist(circle.x, circle.y, other.x, other.y);
                if(circle.r==newr3&&other.r==newr3&&d<newr3distance+circle.r+other.r)
                        overlapping=true;
                else if(d<circle.r + other.r){
                    overlapping = true;
                }
            }
             if (!overlapping) {
                circles.push(circle);
            }

             protection++;
            if (protection > (canvaswidth+canvasheight)*800) {
                break;
            }
     }

      for (var i = 0; i < circles.length; i++) {
                fill(255, 0, 175, 100);
    noStroke();
    ellipse(circles[i].x, circles[i].y, circles[i].r * 2, circles[i].r * 2);
            }
}

Chrisir

In which way aren't they good? What do you dislike? What needs change, what did you try?

Lilarie

@Chrisir

Hmm. Well, I couldn't get to combine two algorithms. I can make it that the circles are right beside each other BUT only with 1 size of circle, I need 3 sizes. I can make it generate 3 sizes of circles BUT the circles won't be beside each other. I can't seem to figure out a way to combine those two. And my code is structured as that it will not stop until the loop is finished instead of stopping when there's no space to put another circle in. Well, to summarize it all, what I need is for it to generate 3 sizes of circles (c1, c2 and c3) such that c1 types of circles are a certain distance apart from each other but all circles are right beside each other without overlap. From my attempts, they can be done separately, but I just can't put them all together.

Chrisir

Well you need a counter how much space you used already with the circles up to now.

For a new circle, add its diameter to the counter.

How would you do this?

Lilarie

@Chrisir , that is for the part where my c1 circles are a certain distance from each other, right? I think I already got that part in my code there with the variable newr3 distance . The part I cannot get here is how to put them right beside each other.

Chrisir

You mean how to put them graphically?

Just reduce x-value until dist(.....) <= sum of radius of both circles (or see my post above)

Lilarie

Here's the latest update. Got it to count the circles and actually put a certain distance to the one of the 3 types of circles which I thought I already did earlier, my bad. Thank you @Chrisir and @TfGuy44 for guiding me here! Just one more modification is missing, the part where dist = 0 among all the circles. I am still trying to understand what Chrisir is saying.

"// noprotect"
var circles = [];

function setup() { 

    var canvasheight = 600;
    var canvaswidth = 800;
    var newradii=0;
    var newr3distance=60;
    var newr1=20;
    var newr2=40;
    var newr3=60;
  createCanvas(canvaswidth, canvasheight);

  var protection = 0;

    var firstcircle = {};
    for(var r3circlesx = 0; r3circlesx<Math.floor(canvaswidth/((newr3*2)+newr3distance)); r3circlesx++)
    {
        for(var r3circlesy = 0; r3circlesy<Math.floor(canvasheight/((newr3*2)+newr3distance)); r3circlesy++)
        {
                firstcircle = {
                    x:(((newr3*2)+newr3distance)*(r3circlesx))+newr3,
                    y:(((newr3*2)+newr3distance)*(r3circlesy))+newr3,
                    r:(newr3, newr3)
                }
                circles.push(firstcircle);
        }
    }

   while(circles.length<canvaswidth+canvasheight)
     {
            rsize=Math.round(Math.random()*3) + 1;
            if(rsize==1)
                newradii=newr1;
            else if(rsize==2)
                newradii=newr2;
            else if(rsize==3)
                newradii=newr3;
            xaxis = Math.random() * ((canvaswidth-newradii) - newradii) + newradii;
            yaxis = Math.random() * ((canvasheight-newradii) - newradii) + newradii;

            circle = {
                x:xaxis,
                y:yaxis,
                r:(newradii, newradii)
            }
            overlapping = false;

            for(var js = 0; js<circles.length; js++){
                var others = circles[js];
                var ds = dist(circle.x, circle.y, others.x, others.y);
                if(circle.r==newr3&&others.r==newr3&&ds<newr3distance+circle.r+others.r)
                        overlapping=true;
                else if(ds<circle.r + others.r){
                    overlapping = true;
                }
            }
             if (!overlapping) {
                circles.push(circle);
            }

             protection++;
            if (protection > (canvaswidth+canvasheight)*800) {
                break;
            }
     }

      for (var i = 0; i < circles.length; i++) {
                fill(255, 0, 175, 100);
    noStroke();
    ellipse(circles[i].x, circles[i].y, circles[i].r * 2, circles[i].r * 2);
        text(i+1,circles[i].x-5,circles[i].y);

            }
            text(circles.length,canvaswidth-20,canvasheight-10);
}_

Chrisir

You really have to dig into it to solve this. Read it carefully tell yourself what's happening in every line and understand the code

Then you'll be able to solve it.

It's an art.

TfGuy44

Right now you are placing your largest circles in a grid, and then trying to place smaller circles at random (by making sure there are no overlaps).

If you want there to no space between randomly placed circles - that is, the candidate circle is touching an existing circle, you'll need to do some stricter checking. Not only will it have to be placed in a spot that it doesn't overlap any other circle, but it will also have to be placed in a spot so that the distance between it and some other circle is just enough for them to look like they are touching.

You can add this check, but then you have a different problem: How likely is it that your candidate circle is randomly put in such a "good" position? Not very!

Lilarie

@TfGuy44 oh, yeah. Wow. :/ So the only solution here might be to make the code check every point in the canvass, right? Or is it not even possible that way?

TfGuy44

It's possible, but it is a lot of wasted effort. As has been said many times already, circle packing is not an easy problem!

If you really want my advice, here it is: Forget this approach. Instead, get a physics engine. Heck, Box2D's CollisionListening example has everything you'd need.

Lilarie

@TfGuy44 just when i'm really getting into it. Well, guess I don't have a choice. I'm no expert in this. Haha. Thanks for the help and advice!

Chrisir

I guess it's a task from university / school.

It's an optimization problem.

A physics engine is probably not allowed then.

Read the articles on wikipedia for packing problems, backtracking, optimization etc.

My ideas with the permutation is also not too bad I guess

but there must be a formula you can find on google

TfGuy44

Tinkering with it and I got this:

// The Nature of Code
// <http://www.shiffman.net/teaching/nature>;
// Spring 2011
// Box2DProcessing example

// Basic example of controlling an object with our own motion (by attaching a MouseJoint)
// Also demonstrates how to know which object was hit

import shiffman.box2d.*;
import org.jbox2d.common.*;
import org.jbox2d.dynamics.joints.*;
import org.jbox2d.collision.shapes.*;
import org.jbox2d.collision.shapes.Shape;
import org.jbox2d.common.*;
import org.jbox2d.dynamics.*;
import org.jbox2d.dynamics.contacts.*;

// A reference to our box2d world
Box2DProcessing box2d;

// An ArrayList of particles that will fall on the surface
ArrayList<Particle> particles;

boolean toggle = true;

Boundary wall;
Boundary wall1;
Boundary wall2;

void setup() {
  size(800, 600);
  smooth();

  // Initialize box2d physics and create the world
  box2d = new Box2DProcessing(this);
  box2d.createWorld();

  // Turn on collision listening!
  box2d.listenForCollisions();

  // Create the empty list
  particles = new ArrayList<Particle>();

  wall = new Boundary(width/2, height, width, 10);
  wall1 = new Boundary(width, height/2, 10, height);
  wall2 = new Boundary(0, height/2, 10, height);


}

void draw() {
  background(255);

  if (random(1) < 0.1 && toggle) {
    particles.add(new Particle(random(width), -60 ));
  }


  // We must always step through time!
  box2d.step();

  // Look at all particles
  for (int i = particles.size()-1; i >= 0; i--) {
    Particle p = particles.get(i);
    p.display();
    // Particles that leave the screen, we delete them
    // (note they have to be deleted from both the box2d world and our list
    if (p.done()) {
      particles.remove(i);
    }
  }

  //wall.display();
}


// Collision event functions!
void beginContact(Contact cp) {
  // Get both fixtures
  Fixture f1 = cp.getFixtureA();
  Fixture f2 = cp.getFixtureB();
  // Get both bodies
  Body b1 = f1.getBody();
  Body b2 = f2.getBody();

  // Get our objects that reference these bodies
  Object o1 = b1.getUserData();
  Object o2 = b2.getUserData();

  if (o1.getClass() == Particle.class && o2.getClass() == Particle.class) {
    Particle p1 = (Particle) o1;
    p1.change();
    Particle p2 = (Particle) o2;
    p2.change();
  }

}

// Objects stop touching each other
void endContact(Contact cp) {
}

void mousePressed(){
  toggle = !toggle;
}

// The Nature of Code
// <http://www.shiffman.net/teaching/nature>;
// Spring 2012
// Box2DProcessing example

// A fixed boundary class

class Boundary {

  // A boundary is a simple rectangle with x,y,width,and height
  float x;
  float y;
  float w;
  float h;

  // But we also have to make a body for box2d to know about it
  Body b;

  Boundary(float x_,float y_, float w_, float h_) {
    x = x_;
    y = y_;
    w = w_;
    h = h_;

    // Define the polygon
    PolygonShape sd = new PolygonShape();
    // Figure out the box2d coordinates
    float box2dW = box2d.scalarPixelsToWorld(w/2);
    float box2dH = box2d.scalarPixelsToWorld(h/2);
    // We're just a box
    sd.setAsBox(box2dW, box2dH);


    // Create the body
    BodyDef bd = new BodyDef();
    bd.type = BodyType.STATIC;
    bd.position.set(box2d.coordPixelsToWorld(x,y));
    b = box2d.createBody(bd);

    // Attached the shape to the body using a Fixture
    b.createFixture(sd,1);

    b.setUserData(this);
  }

  // Draw the boundary, if it were at an angle we'd have to do something fancier
  void display() {
    fill(0);
    stroke(0);
    rectMode(CENTER);
    rect(x,y,w,h);
  }

}

// The Nature of Code
// <http://www.shiffman.net/teaching/nature>;
// Spring 2010
// Box2DProcessing example

// A circular particle

color[] particle_colors = { color(255,0,0), color(0,255,0), color(0,0,255) };

class Particle {

  // We need to keep track of a Body and a radius
  Body body;
  float r;
  int type = 0;
  color col;


  Particle(float x, float y) {
    type = int(random(3));
    r = 20 + 20 * type;
    // This function puts the particle in the Box2d world
    makeBody(x, y, r);
    body.setUserData(this);
    col = color(175);
  }

  // This function removes the particle from the box2d world
  void killBody() {
    box2d.destroyBody(body);
  }

  // Change color when hit
  void change() {
    col = color(255, 0, 0);
  }

  // Is the particle ready for deletion?
  boolean done() {
    // Let's find the screen position of the particle
    Vec2 pos = box2d.getBodyPixelCoord(body);
    // Is it off the bottom of the screen?
    if (pos.y > height+r*2) {
      killBody();
      return true;
    }
    return false;
  }


  // 
  void display() {
    // We look at each body and get its screen position
    Vec2 pos = box2d.getBodyPixelCoord(body);
    if( pos.y < r ) return; // Do not show cutoffs at top!
    // Get its angle of rotation
    float a = body.getAngle();
    pushMatrix();
    translate(pos.x, pos.y);
    rotate(a);
    fill(particle_colors[type]);
    stroke(0);
    strokeWeight(1);
    ellipse(0, 0, r*2, r*2);
    // Let's add a line so we can see the rotation
    //line(0, 0, r, 0);
    popMatrix();
  }

  // Here's our function that adds the particle to the Box2D world
  void makeBody(float x, float y, float r) {
    // Define a body
    BodyDef bd = new BodyDef();
    // Set its position
    bd.position = box2d.coordPixelsToWorld(x, y);
    bd.type = BodyType.DYNAMIC;
    body = box2d.createBody(bd);

    // Make the body's shape a circle
    CircleShape cs = new CircleShape();
    cs.m_radius = box2d.scalarPixelsToWorld(r);

    FixtureDef fd = new FixtureDef();
    fd.shape = cs;
    // Parameters that affect physics
    fd.density = 1;
    fd.friction = 0.01;
    fd.restitution = 0.3;

    // Attach fixture to body
    body.createFixture(fd);

    body.setAngularVelocity(random(-10, 10));
  }
}

Do with this as you like - I'm unwilling to help beyond this point.

Lilarie

Will do, @Chrisir! Thanks! :)

And i'll try that out when I figure out how this box2d thing works, @TfGuy44 . Thanks! :)

TfGuy44

Sketch > Import Library... > Add Library... > Add "Box2D for Processing"