Now you know how to sort the circles I would like to consider the problem of overlapping

You appear to have two constraints

- the circles must not overlap
- the circles should fully appear on the canvas

The only problem here is that if you require lots of circles and/or circles of large radius then it might be impossible to satisfy condition (2) so this must be considered when designing the algorithms.

We start the sketch by creating an array of randomly sized and positioned circles that fit inside a rectangular area ignoring any overlap between them. This is easily done it we calculate the radius *first* and then get a random position [x, y] such that the circle fully fits inside the rectangle. The method

`createCircles(int n, float lowX, float lowY, float highX, float highY)`

does that for you and in setup we have

`createCircles(numCircles, 0, 0, width, height);`

which keeps the circles inside the canvas.

To remove overlaps we compare every pair of circles in turn and if they overlap then move them apart along the vector that links their centers. In this operation both circles are moved so it might cause additional overlaps with other circles so we repeat this operation until there are no overlaps.

It might also cause the circle to move so it no longer fully appears in the rectangle so before checking for overlaps we need to move these circles back inside the rectangle but as I said before it might be impossible to satisfy constraint (2) and avoid overlap.

In this case we need a way of avoiding an infinite loop and crashing the program. In the sketch below I have created a limit based on the number of circles. If the number of iterations exceeds the limit constraint (2) is abandoned meaning the circles do not overlap but do not fits inside the desired rectangle.

When you run the sketch you will see a 10 random circles, click the mouse and the circles will be moved to avoid overlap.

If you continue clicking then you will repeat this process increasing the number of circles by 10 each time.

This algorithm guarantees to avoid overlap between circles even if it can’t fit them inside the display.

```
Circle[] circles;
int numCircles = 10;
int midX, midY;
int state = 1;
void setup() {
size(640, 640);
midX = width/2;
midY = height/2;
createCircles(numCircles, 0, 0, width, height);
}
void createCircles(int n, float lowX, float lowY, float highX, float highY) {
circles = new Circle[numCircles];
for (int i = 0; i < n; i++) {
float r = random(3, 80);
float x = random(lowX+r, highX-r);
float y = random(lowY+r, highY-r);
circles[i] = new Circle(x, y, r);
}
}
void draw() {
background(255, 255, 200);
for (Circle c : circles)
c.render();
}
boolean moveApart(Circle c0, Circle c1) {
// Need to move circles that are centered on the same coordinates
if (c0.x == c1.x && c0.y == c1.y) {
c0.x += random(-0.5f, 0.5f);
c0.y += random(-0.5f, 0.5f);
c1.x += random(-0.5f, 0.5f);
c1.y += random(-0.5f, 0.5f);
}
PVector line = new PVector(c1.x - c0.x, c1.y - c0.y);
float c2c = (c1.r + c0.r);
float overlap = c2c - line.mag();
if (overlap > 0.1) {
float t0 = - overlap * c1.r / c2c;
float t1 = overlap * c0.r / c2c;
line.normalize();
c0.x += t0 * line.x;
c0.y += t0 * line.y;
c1.x += t1 * line.x;
c1.y += t1 * line.y;
return true;
}
return false;
}
void separateCircles(Circle[] array) {
int time = millis();
boolean circlesMoved = false;
int iters = 0, limit = 3 * array.length;
do {
// Keep circles in display area
if (iters < limit)
for (int c = 0; c < array.length; c++)
array[c].constrainToArea(0, 0, width, height);
// Separate
circlesMoved = false;
for (int i = 0; i < array.length - 1; i++) {
Circle ci = array[i];
for (int j = i + 1; j < array.length; j++) {
Circle cj = array[j];
circlesMoved |= moveApart(ci, cj);
}
}
iters ++;
} while (circlesMoved);
time = millis() - time;
println(numCircles + " circles separated in "+ time + " ms");
println(" required "+ iters + " iterations");
if (iters >= limit)
println(" circles do not fits canvas!");
println("--------------------------------------------------------");
}
void mouseClicked() {
if (state == 1)
separateCircles(circles);
else {
numCircles += 10;
createCircles(numCircles, 0, 0, width, height);
}
state = 3 - state; // flip state
}
class Circle {
float x, y, r;
Circle( float x_, float y_, float r_ ) {
x = x_;
y = y_;
r = r_;
}
boolean intersects(Circle c) {
float dx = c.x - x, dy = c.y - y, rr = c.r + r;
return dx*dx + dy*dy < rr*rr;
}
void constrainToArea(float lowX, float lowY, float highX, float highY) {
if (x < lowX + r)
x = lowX + r;
else if (x > highX - r)
x = highX - r;
if (y < lowY + r)
y = lowY + r;
else if (y > highY - r)
y = highY - r;
}
void render() {
push();
translate(x, y);
noStroke();
fill(0, 20);
ellipse(0, 0, 2*r, 2*r);
pop();
}
}
```