Scatter Rectangles From the Center - No Overlap

Hi, I have seen codes that scatter circles all over the canvas without overlaps (https://www.youtube.com/watch?v=XATr_jdh-44&feature=youtu.be), but if the total number of circles is low, then there’s a chance that the cluster will be very far apart from each other. Is there a way to scatter similarly (but not same) sized rectangles that remains a minimum distance from each other but is never too far away?

Hi,

Welcome to the forum! :slight_smile:

Actually your question was a nice exercise! I came with my own idea :

  • Start with a circle of radius 0 then add a cube at the origin of the coordinate system (0, 0).

  • Increase the size of the circle by a certain amount and then sample points on this circle.

  • At each point create a randomly sized square and check if it intersects with other rectangles already on the screen. If you can put it somewhere, do it.

  • Increase the radius of the circle at each frame so the squares will grow from the center

So this is the result :

Note that this is not the optimal solution and depends on the number of samples that you pick each frame. Also the code only works for squares that are not rotated (because the code is more complicated ahah :wink: )

Feel free to play with the parameters :

// The list of rectangles
ArrayList<Rectangle> rectangles;

// The search radius grows at every frame
float searchRadius = 0;

// The increment of the search radius
float radiusIncr = 1;

// The number of trials per increment
float tryPerIncr = 500;

int minRectSize = 10;
int maxRectSize = 100;

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

  rectangles = new ArrayList<Rectangle>();
}

void draw() {
  background(255);
  
  // Display text
  fill(0);
  text("Search radius : " + searchRadius + "\nPlaced rectangles : " + rectangles.size(), 50, 50);

  // Each frame, try to place a random square 
  for (int i = 0; i < tryPerIncr; i++) {
    float rAngle = random(TWO_PI);
    float rSize = random(minRectSize, maxRectSize);
    
    // Create the random rectangle
    Rectangle r = new Rectangle(cos(rAngle) * searchRadius, sin(rAngle) * searchRadius, rSize);
  
    // Check if it intersects with the others
    boolean placeable = true;
    for (Rectangle other : rectangles) {
      if (r.intersect(other)) {
        placeable = false;
        break;
      }
    }
    
    // Add it if not
    if (placeable) rectangles.add(r);
  }
  
  // Display the rectangles
  translate(width / 2, height / 2);
  for (Rectangle r : rectangles) {
    r.display();
  }
  
  // Display the search area
  stroke(255, 0, 0);
  noFill();
  circle(0, 0, searchRadius * 2);
  
  // Increment the search radius
  searchRadius += radiusIncr;
  
  // Stop when reaching the limits of the screen
  if (searchRadius >= width / 2) noLoop();
}

// The Rectangle class holding coordinates
class Rectangle {
  float x, y, size;

  Rectangle(float x, float y, float size) {
    this.x = x;
    this.y = y;
    this.size = size;
  }

  void display() {
    rectMode(CENTER);
    stroke(0);
    noFill();
    rect(x, y, size, size);
  }

  // Returns true if the current square intersect with another one
  // Only valid for non rotated rectangles
  boolean intersect(Rectangle other) {
    return (other.x - other.size / 2 < x + size / 2) &&
      (other.x + other.size / 2 > x - size / 2) &&
      (other.y - other.size / 2 < y + size / 2) &&
      (other.y + other.size / 2 > y - size / 2);
  }
}

1 Like

Hey Joseph, thank you so much for your response! You put a lot of efforts into this and I appreciate it so much. I was just thinking about a solution like this when I went to bed last night but I was only considering an expanding rectangular area and couldn’t get it to work. Your solution is elegant and I will look over it in a bit. Thanks again!

1 Like