Testing for overlap of circles

Programming Questions

bigbugbuzz

Testing for overlap of circles

in Programming Questions • 2 years ago

Hi Everyone,

Suppose I have the code shown at the bottom, which draws many circles at random on the screen (thank you drum whore for you effort in getting me that far). My question is:

How do I ensure that the image actually displayed does not have overlapping circles? (I am thinking, a trial and error process, but still, that needs to control for the position of each circle, right?)

PrintWriter positions;
int cycles = 100; //number of circles

void setup() {
size(600, 600);
smooth();
background(0);
noStroke();
fill(226);

positions = createWriter("positions.txt");
noLoop();
}

void draw() {
for (int i = 0; i < cycles; i++) {
    int xLength = int(random(25,25));
    int yHeight = int(random(25,25));
    int xPos = int(random(0 + xLength, width - xLength));
    int yPos = int(random(0 + yHeight, width - yHeight));
    ellipse(xPos, yPos, xLength, yHeight);
    positions.println(xLength + " " + yHeight + " " + xPos + " " + yPos);
}
positions.flush();
positions.close();
}

Replies(9)

PhiLho

Re: Testing for overlap of circles

2 years ago

Why are your storing the positions of the circles in a text file?

Anyway, you have to store the circles' data in an array and for each new circle, check if there is no overlap with the previous ones, or something like that.

bigbugbuzz

Re: Re: Testing for overlap of circles

2 years ago

I am a beginner at Processing - you are right, I should look into arrays.

But regarding your solution, comparing merely two consecutive circles won't do, because there is no guarantee that the third won't overlap with the first, and so on...

So, I am thinking, is it possible to loop through an array of positions, for each new circle, adding the newest circle to the end IF it passes a non-overlap criteria, and starting the whole process again if an overlap occurs?

I found this function, which might do the trick, but I am unsure how to loop through an array:

circleCircleIntersect(circleX1, circleY1, circleRadius1, circleX2, circleY2, circleRadius2)

boolean circleCircleIntersect(float cx1, float cy1, float cr1, float cx2, float cy2, float cr2) {
if (dist(cx1, cy1, cx2, cy2) < cr1 + cr2) {
return true;
} else {
return false;
}
}

drumwhore

Re: Testing for overlap of circles

2 years ago

I think it would be easier to work with an ArrayList of circle objects: each time a new circle is created, it checks through the ArrayList if it doesn't overlap an existing one. If not, create it (and add it to the ArrayList). Else check for a new location and try again. Hope this helps ;)

Edit: I just noticed that's pretty much what phi.lho said ;)

bigbugbuzz

Re: Testing for overlap of circles

2 years ago

I wonder if anyone is willing to implement drumwhore's solution in the code below. Only difference to drumwhore's suggestion is that instead of "Else check for a new location and try again" should instead be "Else start from scratch again (that is, from empty array)". The reason for this latter difference is that I want to count how many attempts it takes to create n circles without experiencing overlap.

the overlap testing function is circleCircleIntersect shown above.

CODE FOLLOWS:

// DECLARE
ArrayList ballCollection;

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

// INITIALIZE
ballCollection = new ArrayList();

for(int i = 0; i < 100; i ++){
Ball myBall = new Ball(random(0,width),random(0,height));
ballCollection.add(myBall);

}
}

void draw() {
background(0);

// CALL FUNCTIONALITY

for(int i = 0; i < ballCollection.size(); i ++){
Ball mb = (Ball) ballCollection.get(i);
mb.run();
}
}

// CLASS

class Ball{
// GLOBAL VARIABLES (Main variables of class, eg. location, speed)
float x = 0;
float y = 0;
float speedX = 0;
float speedY = 0;

// CONSTRUCTIOR (Place where variables are initialized)
Ball(float _x, float _y){

    x = _x;
    y = _y;

}

// FUNCTION
void run() {
    display();
    move();
    bounce();
    gravity();
}

void gravity() {
    speedY += 0;
}

void bounce() {
    if(x > width) {
     speedX = speedX * -1;
    }
    if(x < 0) {
     speedX = speedX * -1;
    }
    if(y > height) {
     speedY = speedY * -1;
    }
    if(y < 0) {
     speedY = speedY * -1;
    }
}

void move() {
    y += speedY; // += takes y, adds something to y, to get new y
    x += speedX;
}

void display(){
    ellipse(x, y, 20, 20);
}

}

PhiLho

Re: Testing for overlap of circles

2 years ago

You missed the plural in "previous ones"...
And I don't see what the bounce code does there.

An alternative, instead of trying a random different position if there is collision, might be to move a bit the new circle until it has no overlap.

bigbugbuzz

Re: Testing for overlap of circles

2 years ago

I know, the move, bounce and gravity are not important. I should have removed these.

But I would like to implement the solution I proposed. But I am stuck. How do I access the position of a ball in the ArrayList?

Would appreciate some hints :)

PhiLho

Re: Testing for overlap of circles

2 years ago

When you have a variable ball of type Ball, you can use ball.x and ball.y.

expdas

Re: Testing for overlap of circles

2 years ago

Have a look at this code, it is a bit rough around the edges but maybe it gives you an idea for your challenge?

int [] [] myArray;
int circleRadius;
int xPos;
int yPos;
int cycles =100;
int j, k;

void setup() {
size(600, 600);
smooth();
background(0);
noStroke();
myArray = new int[100][3];
noLoop();
}

void draw() {
// create array with circles
for (int i=0;i<cycles;i++)
{
    computePositions(i);
}
// check every circle in array for collision
for (int j = 1; j < cycles; j++) {
    innerLoop(j);
}
// draw all circles
for (int i=0;i<cycles;i++)
{
    fill(218);
    ellipse(myArray[i][0], myArray[i][1], myArray[i][2], myArray[i][2]);
}
}

void circleCircleIntersect(int j, int k, int cx1, int cy1, int cr1, int cx2, int cy2, int cr2) {
if (dist(cx1, cy1, cx2, cy2) <= (cr1 + cr2)/2) {
    computePositions(j);
    innerLoop(j); // after you create a new circle you want to check all other entries
}
}

void computePositions (int position) {
int circleRadius = int(random(25, 25));
int xPos = int(random(0 + circleRadius, width - circleRadius)); // circleRadius is not the radius, it is the Radius
int yPos = int(random(0 + circleRadius, height - circleRadius)); // variable yPos is depending on variable height not width
myArray[position][0]= xPos;
myArray[position][1]= yPos;
myArray[position][2]= circleRadius;
}

void innerLoop(int j) {
for (int k = 0; k <j; k++) {
    circleCircleIntersect(j, k, myArray[j][0], myArray[j][1], myArray[j][2], myArray[k][0], myArray[k][1], myArray[k][2]);
}
}

bigbugbuzz

Re: Re: Testing for overlap of circles

2 years ago

Hi Expdas (or anyone else),

I have a couple of questions regarding your code.

1) Does the code

      a) check if the latest ball intersects with any other ball, and if it does, then it tries a new position for this latest ball OR
      b) check if the latest ball intersects with any other ball, and if it does, then ALL balls are deleted, and the process starts anew?

2) I have implemented a little change in the code, by confining the area where balls may be drawn. Obviously, when that area is small, and for a given ball size, adding too many balls creates problems (stack overflow). However, is that because 1a is implemented, where, because of the configuration of the previous balls, there simply is no room for the last ball, and the algorithm keeps checking endlessly? Here 1b might work, because there might actually be room for all balls, and this solution would be found, admittedly after many attempts.

I would ideally like 1b to be implemented, because I wish to keep track of how many attempts the algorithm makes at finding non-overlap configurations given the confinement, and number of balls.

The change in code is shown below:

int [] [] myArray;
int circleRadius;
int xPos;
int yPos;
int cycles =30;
int j, k;
int confinementWidth = 150;
int confinementHeight = 150;

void setup() {
size(600, 600);
smooth();
background(0);
noStroke();
myArray = new int[100][3];
noLoop();
}

void draw() {
// create array with circles
for (int i=0;i<cycles;i++)
{
    computePositions(i);
}
// check every circle in array for collision
for (int j = 1; j < cycles; j++) {
    innerLoop(j);
}
// draw all circles
for (int i=0;i<cycles;i++)
{
    fill(218);
    ellipse(myArray[i][0], myArray[i][1], myArray[i][2], myArray[i][2]);
}
}

void circleCircleIntersect(int j, int k, int cx1, int cy1, int cr1, int cx2, int cy2, int cr2) {
if (dist(cx1, cy1, cx2, cy2) <= (cr1 + cr2)/2) {
    computePositions(j);
    innerLoop(j); // after you create a new circle you want to check all other entries
}
}

void computePositions (int position) {
int circleRadius = int(random(25, 25));
int xPos = int(random(width/2 - confinementWidth/2, width/2 + confinementWidth/2));
int yPos = int(random(height/2 - confinementHeight/2, height/2 + confinementHeight/2));
myArray[position][0]= xPos;
myArray[position][1]= yPos;
myArray[position][2]= circleRadius;
}

void innerLoop(int j) {
for (int k = 0; k <j; k++) {
    circleCircleIntersect(j, k, myArray[j][0], myArray[j][1], myArray[j][2], myArray[k][0], myArray[k][1], myArray[k][2]);
}
}

Top Reply