Circle/ Square Packing Tips

Processing Coding Questions
1

Hello I am new here so I hope I follow the rules and am able to get some help :stuck_out_tongue:
I have this code from my Prof that was originally for circle packing and i just slightly adjusted it to be square packing and added some offset between the squares so there is little to no overlap.
I have two problems with this code though that I am looking for help with.

A. the code itself is meant for ellipse: the portion of code that is checking for overlap before placing the next shape is still checking for overlapping ellipse and this is why I have to multiply my rectangle width and height by 0.8 (step 5 in the script) to avoid them overlapping. How can I instead check for overlapping rectangles and not ellipse?
Note: visually i do avoid overlap but it would be nice to get it so I could pack the squares extremely tight which can only be done by checking for the overlap of squares and not ellipse.

B. the section of script “4a. check to see if inside the big circle” is another thing I would like to change to a rectangle. As of now, it is measuring a distance from a point and and placing all the rectangles within that distance. How can I have them all placed within a square instead?

Thanks in advance for tips and advice.

import processing.pdf.*;

// circle packing

int bigDia = 500;
int minDia = 20;
int maxDia = 150;
int OS = 10;
boolean record = false;
int colAmt = 30;
int bigX, bigY;
int numLoops = 10000;

float[] dia = new float[0];
int[] xVal = new int[0];
int[] yVal = new int[0];
int count = 0;
boolean overlap = false;

void setup() {
  // 1. define space
  size(800, 800);
  background(255);
  // no loop for draw
  noLoop();
  // big cirlce
  bigX = width/2;
  bigY = height/2;
  // pdf export
  if (record) beginRecord(PDF, "myPlan01.pdf");
}
void draw() {
  // loop here
  for (int j = 0; j <numLoops; j ++) {
    fill(240, 200);
    stroke(25);
    // 2. random position - new circle
    int x = round(random(0, width));
    int y = round(random(0, height));
    // 3. random radium
    float myDia = random(minDia, maxDia);
    // 4. check for overlaps
    // 4a. check to see if inside the big circle
    float myDist = dist(x, y, bigX, bigY) + (myDia/2);
    if (myDist < (bigDia/2)) {
      // 4b. check to see if another circle is already there
      if (count == 0){
      overlap = false;
    } else {
      for (int i = 0; i < count; i ++){
        myDist = dist(x, y, xVal[i], yVal[i]) - ((myDia + dia[i])/2 + OS);
        if (myDist > 0){
          overlap = false;
        } else {
          overlap = true;
          break;
        }
      }
    }
    // 5. if no overlap then place circle
    if (overlap == false) {
      rectMode(CENTER);
      stroke (0);
      strokeWeight(3);
      rect (x, y, myDia*.8, myDia*.8);
      xVal = append(xVal, x);
      yVal = append(yVal, y);
      dia = append(dia, myDia);
      count ++;
        if (myDia < colAmt) {
          //place column
          rect (x, y, 5, 5);
        }
      }
    }
    // 6. otherwise go back to 2
  }
  // export pdf
  if (record) endRecord();
}
1 Like
2

i tried that here
possibly helps.

1 Like
4

My advice around checking if the squares are overlapping is to check to see if the any of the corners from one of the rectangles is in another one. Could would look something like:

// changed myDia to mySize because it makes more sense
float[][] myRectCorners = {
  {x - mySize / 2, y - mySize / 2}, // top left
  {x + mySize / 2, y - mySize / 2}, // top right
  {x - mySize / 2, y + mySize / 2}, // bottom left
  {x + mySize / 2, y + mySize / 2} // bottom right
};
// do the same for the rectangle you are checking against.
float[][] otherRectCorners = {{...}};

// checking all of myRectCorner to see if any are inside of otherRect
for (int i = 0; i < myRectCorners.length; i++) {
  // 0 is xs and 1 is ys
  if (myRectCorners[i][0] >= otherRectCorners[i][0] &&
      myRectCorners[i][0] <= otherRectCorners[][0] &&
      myRectCorners[i][1] >= otherRectCorners[i][1] &&
      myRectCorners[i][1] <= otherRectCorners[i][1])
  {
    overlap = true;
  }
}

// do the same but with loop as above with myRectCorners and otherRectCorners reversed as this will check if any of my otherRectCorners are in myRect.

This becomes more complex if you are rotating the squares and I would search for articles on collision detection if that’s something you want to do. Also calculated corners based on using rectMode(CENTER) so if you switch to rectMode(CORNER) that would have to be updated. Might not be the best solution but will hopefully get the job done.

Also used a 2d array. Check out this article on 2d arrays for an explanation if you need one.

The same principle could be applied to containing them in a rectangle. By checking each corner of both rectangles.

Hope that gives you some idea of what to do and wasn’t confusing. Feel free to ask follow up questions if it didn’t make sense.

3 Likes
5

Hey the link works now thanks. It will definitely take me some time to unpack that script but this is very close to what I am trying to achieve.

1 Like
6

No rotation thankfully and I’ll stick to rectMode(CENTER). Checking for overlapping corners makes sense I’ll try this today thanks.

7

The website cited in your code was super helpful!
Rectangle/Rectangle
I was able to make parameters to test for overlap.
And instead of checking to see if the rectangles are located in a larger square I just limited the placement of the initial random rectangles inside of a border before testing them for overlap.
:grin:

1 Like