3
\$\begingroup\$

I just need a general idea for how to do this.

I have a list of Circle objects.

Circle {

private int yCoord;
private int xCoord;


Circle(int a, int b) {

xCoord = a;

yCoord = b;

}
}

I randomly spawn circles on a screen:

private void spawnCircles() {


   //Spawns new circle in a rectangular region that starts at top corner
   //of screen and has 100 pixels length and width.
   Circles.add(new Circle(rand.next(100),rand.next(100));
}

The radius of the circles is 20 pixels.

How can I spawn these circles randomly so they don't overlap?

All I need is pseudo code or a rough outline.

\$\endgroup\$
2
  • \$\begingroup\$ Two questions: 1) how many circles are we talking about? 2) do they have to stay fully inside the screen or can parts of the circles lay outside the screen? \$\endgroup\$
    – MAnd
    Jan 27, 2016 at 3:27
  • 3
    \$\begingroup\$ I was looking this up recently for another answer - are you familiar with Poisson disc sampling? This lets you fill a space with points, respecting a minimum distance between any pair (here, that distance would be twice your circles' radius). Check out the animated demonstrations here \$\endgroup\$
    – DMGregory
    Jan 27, 2016 at 6:59

2 Answers 2

3
\$\begingroup\$

You did not specify whether you will have many circles or just a few. However, by the measures you mentioned I assumed it's just a few (by the way, if the measures you are thinking of are correct, only 4 circles will fit perfectly into the rectangle...).

So, if you have just a few circles, you can opt for a very naive solution: save each new valid circle in a list and check if the next to be generated overlaps any of those already in the list. In a bit more detail, you would run a "while" type of loop, doing the following at each iteration:

1) generate the center point (X,Y) of a new circle with your random generator code;

2) check whether that circle is overlapping any of the other circles already present in the list of circles. Although it's iterative since you will have to check each pair of circles each time, that is a very cheap test in terms of computation.

To test whether two circles overlap you just have to check whether the distance between their center is smaller than the sum of their radii: if such distance is:

  1. is smaller, then they overlap;
  2. identical, then they just touch each other at one single point;
  3. greater, than they don't neither touch nor overlap each other;

3.1) if the new circle does not overlap any of the other circles in the list, that is fine and you can include add it to the list and move back to step one.

3.2) if the new circle does overlap any of the other circles, you can don't include the new circle in the list and go back to step one.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you, this provides a easy method to determine if a circle is intersecting another circle. However, lets say there were more than just 4 circles in my box, more like 20, would you change the spawning method? \$\endgroup\$
    – Foobar
    Jan 28, 2016 at 12:24
  • \$\begingroup\$ @user3847117 Not at all. That would probably work well and fast even for hundreds of circles. It can even work if the circles are not of the same size - although, of course, if their sizes differ too much, the code could take longer to find a free spot for each circle. \$\endgroup\$
    – MAnd
    Jan 28, 2016 at 19:35
  • 1
    \$\begingroup\$ Be careful in your implementation of this algorithm. If implemented poorly, it won't scale well (I learned the hard way!). Also be especially careful about that last step. You'll need to add a condition under which it gives up trying to spawn a new entity. You don't want to this cycle going on forever because there are no good places to spawn! :) \$\endgroup\$
    – Cypher
    Jan 28, 2016 at 23:01
  • 1
    \$\begingroup\$ @Cypher Sure thing! That's why the first thing I've asked the OP was if he/she had many circles, because this does not scale well. However, since the OP's first example talked about only 4 circles in practice, fancier implementations would be overkilling. Now the OP asked if that would still work fine for 20 circles. Well, it will even for hundreds. The worst problem arises when one wants that the circles stay very closely fitted against each other: in that case, fancier solutions will also be needed for sure! \$\endgroup\$
    – MAnd
    Jan 28, 2016 at 23:42
  • 1
    \$\begingroup\$ @MAnd Agreed on all points. I've used this method to spawn entities at a pretty high scale, and it works well if care is taken. :) \$\endgroup\$
    – Cypher
    Jan 29, 2016 at 22:35
2
\$\begingroup\$

If you're not in need of a very fancy way to deal with this problem you could just brute-force it by doing these steps:

  1. Randomize the circle coordinates.
  2. Check if the distance vs all other circles that you have drawn. If it is greater than the sum of the radius of the two circles (40, in your case) you can go ahead and draw the circle.
  3. If it is equal to or less than the sum of the radius of both circles, re-randomize the coordinates and perform these steps again until a preferred amount of circles has been drawn.

Distance method:

public float checkDistance(float x1, float y1, float x2, float y2) {
    // If you use this, make sure the x and y values are the center of the circles.
    float distanceX = x1 - x2;
    float distanceY = y1 - y2;
    float distance = distanceX*distanceX + distanceY*distanceY;
    return distance;
}

Or preferable might be to add this method inside your Circle class:

public float checkDistanceTo(Circle circle) {

    float distanceX = this.xCoord+radius - circle.getXcoord()+radius;
    float distanceY = this.yCoord+radius - circle.getYcoord()+radius;
    // In your case, radius would be 20.
    float distance = distanceX*distanceX + distanceY*distanceY;
    return distance;
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Your answer is pretty much the same that I have said in mine, with the difference that you seem to be suggesting the OP to check the distance between the circumferences, instead of the distance between their center points. Is that it? In any case, your answer has a mistake. If you are talking about minimum distance between circumferences, such distance doesn't have to be >20, but just >0. If you are talking about distance between the centers, then as I've said in my answer, it actually has to be "smaller than the sum of the radii". \$\endgroup\$
    – MAnd
    Jan 29, 2016 at 0:00
  • \$\begingroup\$ You are correct, thanks for pointing this out. I've changed my answer and added some comments to point out that he also has to check the distance between the center of the circles. \$\endgroup\$
    – Charanor
    Jan 29, 2016 at 22:22
  • \$\begingroup\$ How can one know that the algorithm will not loop forever? \$\endgroup\$ Jan 30, 2016 at 14:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .