We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Index › Programming Questions & Help › Programs › overlap prevention for randomly placed circles
‹ Previous Topic | Next Topic ›
Page Index Toggle Pages: 1
overlap prevention for randomly placed circles? (Read 626 times)
skr
overlap prevention for randomly placed circles?
Feb 4th, 2009, 8:40pm  
Note: I'm a beginner

I just started thinking about this problem, and I thought I would check to see if anyone had any resources to which they could direct me.

I want to randomly place a given number of circles of fixed size on a field without overlap.  

I have looked at the packing thread, but I don't want the growth, so that is throwing me off a little bit.  I have used the sqrt method for collision detection, and was able to detect collision and overlap, but I had other code errors.  I don't have the code with me right now, so I will post it later.  Until then, if anyone has any suggestions, I would greatly appreciate it.
Back to top
 
 
skr
Re: overlap prevention for randomly placed circles
Reply #1 - Feb 5th, 2009, 12:25am  
Ok, here is what I have so far.
Code:
int numBalls = 8;
boolean overlap;
Ball[] balls = new Ball[numBalls];

void setup(){
  size(100,100);
  noStroke();
  smooth();
  for (int i = 0; i < numBalls; i++){
    balls[i] = new Ball(random(width), random(height), i, balls);
  }
}

void draw(){
  background(0);
  for (int i = 0; i < numBalls; i++){
    balls[i].collide();
    balls[i].display();
    print(overlap); //checking if collision detection is working
    print(",");
  }
}

class Ball{
  float x, y;
  float diameter;
  int id;
  Ball[] others;
  
  Ball(float xin, float yin, int idin, Ball[] oin){
    x = xin;
    y = yin;
    diameter = 20;
    id = idin;
    others = oin;
  }
  
  void collide(){
    overlap = false;
    for (int i = id + 1; i < numBalls; i++){
      float dx = others[i].x - x;
      float dy = others[i].y - y;
      float distance = sqrt(dx*dx + dy*dy);
      float minDist = others[i].diameter/2 + diameter/2;
      if (distance < minDist){
        overlap = true;
      }
    }
  }
  
  void display(){
    fill(255,200);
    ellipse(x, y, diameter, diameter);
  }
}


I tried checking overlap in draw() and only running display() if false, but even though I was showing false in the print, no balls would display.

Also, can anyone tell me why the print command for overlap keeps running constantly?

Any ideas where I should go from here?
Back to top
 
 
PhiLho 
Re: overlap prevention for randomly placed circles
Reply #2 - Feb 5th, 2009, 1:01pm  
Quote:
can anyone tell me why the print command for overlap keeps running constantly?

Because it is in draw() which is called n times per second...

If the drawing is static, you should put the collision detection in setup(), when you construct the ball array.

Instead of not displaying colliding balls, you might make the ball check collision at creation time, and re-compute a new random position if there is a collision. If, after a few attempts, it keeps colliding (too tight or no luck -- in the first case, must avoid infinite loop), set a flag in the Ball object to tell it not to display: it is the task of the object to manage its state/appearance.
Back to top
 
WWW  
skr
Re: overlap prevention for randomly placed circles
Reply #3 - Feb 7th, 2009, 2:07am  
Thank you for all your help so far, I really appreciate it.

Since I am just making a static image, I moved collision detection to setup(). I tried changing the for loop in setup() to this:
Code:

for (int i = 0; i < numBalls; i++){
   balls[i] = new Ball(random(width), random(height), i, balls, true);
   balls[i].collide();
   if (overlap == true){
      ball[i].dsply = false;
   }
  }


I also changed the Ball class to include a boolean field called dsply so the object can control its appearance state.  That led me to change display() as follows (which I hope will work):
Code:

void display(){
   fill(255.200);
   if(ball[i].dsply == true){
      ellipse(x,y,diameter,diameter);
   }
  }


The problem I encountered is that since the array isn't filled, the collide() call in setup() is returning null values giving me a null Exception error that I don't know how to eliminate.  I tried catching the null with an if statement and returning out of collide, thinking that if it is null there is no reason to check. That just short-circuited the collide function and would always return overlap = false.

Thanks again.
Back to top
« Last Edit: Feb 7th, 2009, 3:15am by skr »  
 
PhiLho 
Re: overlap prevention for randomly placed circles
Reply #4 - Feb 7th, 2009, 11:54am  
If I follow your logic, you should first generate the balls, then check for collision.
Example:
Code:
int numBalls = 8;
boolean overlap;
Ball[] balls = new Ball[numBalls];
 
void setup(){
  size(100,100);
  noStroke();
  smooth();
  for (int i = 0; i < numBalls; i++){
    balls[i] = new Ball(random(width), random(height), i, balls);
  }
  for (int i = 0; i < numBalls; i++){
    balls[i].collide();
  }
  for (int i = 0; i < numBalls; i++){
    balls[i].display();
  }
}
 
class Ball{
  float x, y;
  float diameter;
  int id;
  Ball[] others;
  boolean display = true;
  
  Ball(float xin, float yin, int idin, Ball[] oin){
    x = xin;
    y = yin;
    diameter = 20;
    id = idin;
    others = oin;
  }
  
  void collide(){
    for (int i = id + 1; i < numBalls; i++){
	float distance = dist(x, y, others[i].x, others[i].y);
	float minDist = others[i].diameter/2 + diameter/2;
	if (distance < minDist){
	  display = false;
	  break;
	}
    }
  }
  
  void display(){
    if (!display) return;
    fill(255,200);
    ellipse(x, y, diameter, diameter);
  }
}

Or, check against the previously generated balls, not the next:
Code:
[...]
void setup(){
  size(100,100);
  noStroke();
  smooth();
  for (int i = 0; i < numBalls; i++){
    balls[i] = new Ball(random(width), random(height), i, balls);
    balls[i].collide();
  }
  for (int i = 0; i < numBalls; i++){
    balls[i].display();
  }
}
[...]
  void collide(){
    for (int i = 0; i < id - 1; i++){
	float distance = dist(x, y, others[i].x, others[i].y);
	float minDist = others[i].diameter/2 + diameter/2;
	if (distance < minDist){
	  display = false;
	  break;
	}
    }
  }
Back to top
 
WWW  
skr
Re: overlap prevention for randomly placed circles
Reply #5 - Feb 9th, 2009, 7:20pm  
Yea, thanks.

Sometimes you just need to see the code for it all to click into place.  Also thanks for the revision on the collision function.  I had just copied that and didn't really understand what it was doing until you changed it and then I was able to understand both.

Thanks again
Back to top
 
 
Page Index Toggle Pages: 1
‹ Previous Topic | Next Topic ›