Sorting circles by radius and avoiding overlap between random circles?

Processing Beginners
1

I have code that generates a certain number of circles of random radii that don’t overlap. I want to be able to order them from smallest to largest in terms of radius so that circle[0] is the smallest. I want them sorted by “circle.r” property. The sort() function doesn’t seem to work for my needs. Or am I wrong?

Here is my code. I have an object of a circle:

class Circle {
  float x, y, r;

  Circle( float x_, float y_, float r_ ) {
    x = x_;  y = y_;  r = r_;
  }

And then I have this code that somehow I figured out at some point which generates an array of non-overlapping circles of random radii:

Circle[] circles = new Circle[6];

int circleCount = 0;
int protection = 0;

 while (circleCount < 6) {
    Circle circle = new Circle(random(bound),random(bound),random(3,80));
  
  boolean overlapping = false;
  
   for (int j = 0; j < circleCount; j ++ ) {
     Circle other = circles[j];
     float d = dist(circle.x, circle.y, other.x, other.y);
     //check for overlap and also to make sure they are on the canvas
     if (d < circle.r+other.r || 0 < (circle.x-circle.r)/-1 || 0 < (circle.y-circle.r)/-1 || circle.x+circle.r > bound || circle.y+circle.r > bound){
       overlapping = true;
     }
   }
   if (!overlapping) {
     circles[circleCount]=circle;
     circleCount++;
  }
  protection++;
    if (protection > 10000) {
      break;
    }
2
3

Using the links provided we can create a simple example for sorting an array of circles based on their radii

import java.util.Arrays;
Circle[] circles = new Circle[6];

void setup() {
  size(640, 400);
  for (int i = 0; i < circles.length; i++)
    circles[i] = new Circle(random(width), random(height), random(3, 80));
  listCircleRadii(circles);
  Arrays.sort(circles);
  listCircleRadii(circles);
}

void listCircleRadii(Circle[] a) {
  println("Circle radii");
  for (int i = 0; i < circles.length; i++)
    print("  " + circles[i].r);
  println();
}

class Circle implements Comparable<Circle> {
  float x, y, r;

  Circle( float x_, float y_, float r_ ) {
    x = x_;
    y = y_;
    r = r_;
  }

  public int compareTo(Circle c) {
    return (int)Math.signum(r - c.r);
  }
}

I suggest that you read the links provided by @GoToLoop to find more on the compareTo method. Also look at the Arrays.sort method.

If you want to order them in descending order change the comparison statement to
return (int)Math.signum(c.r - r);

And then I have this code that somehow I figured out at some point which generates an array of non-overlapping circles of random radii:

Unfortunately you might create up to 10000 circle objects and perform millions of circle-circle comparisons and still not get the 6 non-intersecting circles you want. You need to find a better algorithm - one that guarantees success with reasonable efficiency.

1 Like
4

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

You appear to have two constraints

  1. the circles must not overlap
  2. 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();
  }
}