How to Cluster Circles of Different Sizes While Preventing Overlap

2008 November 07

Launch the project >

That’s not the catchi­est head­line, but it’s what this post is about. I’ve finally solved the prob­lem I’ve been work­ing on since September: how to take a bunch of cir­cles of dif­fer­ent sizes and group them around a cen­tral point, while pre­vent­ing any over­lap. See this illustration:

This turned out to be much more com­pli­cated than I had expected. If all the cir­cles were of the same diam­e­ter, it would be easy to cal­cu­late reg­u­lar posi­tions and space them evenly. But I have a project with cir­cles of all dif­fer­ent sizes, and I needed them to be near each other, maybe even touch­ing, but not over­lap­ping. I knew it was pos­si­ble, because I’d seen it done before, such as in visu­al­iza­tions on Many Eyes.

I started by try­ing to solve the prob­lem using trigonom­e­try. Measuring radii, tan­gents, and such seemed to be the answer, but got very com­pli­cated very quickly. Then I turned to the Traer Physics library for Processing. My idea was to have a cen­tral point of “grav­ity” that would attract the cir­cle objects, but then make each cir­cle repel the oth­ers, so they would sort of come together and then space out. JohnG, on the Processing boards fig­ured out a way to do that, but his exam­ple used objects of uni­form size and mass. With a vari­ety of sizes, again, it got more com­pli­cated, and was using more com­pu­ta­tion power than I needed. After all, I didn’t need cool, fluid-like motion. I just needed to arrange things properly.

My answer came from Mike G. (thanks, Mike!), who sug­gested using a square-spiral approach, no trigonom­e­try involved. Take cir­cle A, placed at cen­ter. Then place cir­cle B at cen­ter as well, but move it to the right one pixel. Then check to see if it’s col­lid­ing (over­lap­ping) cir­cle A. If so, move it down one, then left one, two, then up one, two, then right one, two, three, and so on. Keep “spi­ralling” out­ward along a pro­gres­sively larger square path, and even­tu­ally you will find a point where the two cir­cles no longer overlap.

This was a major break­through, and I got pretty close to fig­ur­ing it out myself, but had to call in Mike for help. He sent me some code this morn­ing for spac­ing out three cir­cles. Things got more com­pli­cated the more cir­cles I added, but I man­aged to get it work­ing, finally, this after­noon. Give it a shot, and play around with adding/subtracting cir­cles and see­ing how the clus­ter is recal­cu­lated. As a bonus, I fac­tored in a spac­ing vari­able, so you can have the cir­cles sit far­ther apart or closer together. The next step is to inte­grate this into my iTunes visu­al­iza­tion.

Launch the project >

One comment. Posted in Thesis. Tagged with .

One comment. »

  1. Made a new ver­sion of your applet. Written in a hurry… Bit messy, but … Instead of using the square spi­ral it swings each sphere around the cir­cle at dif­fer­ent dis­tances. It seems to do a bet­ter job of avoid­ing putting a lot of spheres on the diag­o­nals. I also added a break in the col­li­sion count loop (which is applic­a­ble to your applet as well) because we don’t care to know how many col­li­sions we have. After the first we can break out.

    // // Circle clus­ter­ing // using a square spi­ral tech­nique // // by Scott Murray // 2008-11-06 //

    int numDiscs = 5; int spac­ing = 0; int min­Ra­dius = 10; int maxRa­dius = 50; Object[] objects = new Object[1]; //Initially just cre­ate one -- we’ll add more later, once data is loaded PFont font;

    void setup() { //size(screen.width, screen.height); size(500, 500); smooth(); ellipseMode(CENTER); noS­troke(); //font = loadFont(“AlteHaasGrotesk-20.vlw”);

    //Initialize the first object objects[0] = new Object(0);

    //Create all addi­tional objects and append them to the array for(int i = 1; i < numDiscs; i++) { Object objectIn­stance = new Object(i); objects = (Object[]) append(objects, objectInstance); } }

    void draw() { background(255); push­Ma­trix(); translate(width/2, height/2);

    //Draw each object for(int i = 0; i < objects.length; i++) { objects[i].display(); }

    pop­Ma­trix(); }

    class Object { int id; float x; float y; int radius; int diam­e­ter; float arm­Length = 0.0; int spi­ral­Phase = 1; //Which way we’re mov­ing around the spi­ral --- 1=right, 2=down, 3=left, 4=up float spi­ral­MaxDis­tance = 1; //The max x or y dis­tance from center

    //Constructor method Object(int _id) { id = _id; x = int(random(-width/2, width/2)); y = int(random(-height/2, height/2)); radius = int(random(minRadius, maxRa­dius)); diam­e­ter = radius * 2; }

    void dis­play() { push­Ma­trix(); translate(x, y); fill(150, 50); ellipse(0, 0, diam­e­ter, diam­e­ter); fill(0); // textFont(font, 20); text(id, -5, 7); popMatrix(); }

    void rese­tO­b­ject() { x = 0; y = 0; spi­ral­Phase = 1; spi­ral­MaxDis­tance = 1; arm­Length = 1; }

    void moveIn­Spi­ral() { float rota­tion = (6.18f / 360.0f); float oldx; float oldy;

    oldx = x;
oldy = y;
x = (oldx * cos(rotation) - oldy * sin(rotation));
y = (oldy * cos(rotation) + oldx * sin(rotation));

spiralPhase++;
if (spiralPhase > 360)
{
  armLength += 1.0;
  spiralPhase = 1;
  x = armLength;
  y = 0;
}

    }

    void newRan­dom­Po­si­tio­nAnd­Size() { x = int(random(-width/2, width/2)); y = int(random(-height/2, height/2)); radius = int(random(minRadius, maxRa­dius)); diam­e­ter = radius * 2; } }

    // // Checks for col­li­sions between any two (cir­cu­lar) objects // boolean isCollision(Object object1, Object object2) { float minDis­tance = object1.radius + object2.radius + spac­ing; float actualD­is­tance = dist(object1.x, object1.y, object2.x, object2.y); boolean isCol­li­sion; if (actualD­is­tance < minDis­tance) { isCol­li­sion = true; } else { isCol­li­sion = false; } return isCollision; }

    void clus­ter­Ob­jects() { //First reset all posi­tions to 0,0 for(int i = 0; i < objects.length; i++) { objects[i].resetObject(); } //Then resolve col­li­sions --- test cur­rent object (i) against all prior objects (j) //i starts at 1, though, in order to skip over the first object, which will just remain at 0,0 for(int i = 1; i < objects.length; i++) { boolean col­li­sionsOc­cur­ring = true; int col­li­sion­Tally = 0; while(collisionsOccurring) { for(int j = 0; j < i; j++) { //Test i vs. all prior j’s if(isCollision(objects[i], objects[j])) { col­li­sion­Tally++; //If there is a col­li­sion, then incre­ment the tally. break; } } if(collisionTally > 0) { //If any col­li­sions hap­pened, objects[i].moveInSpiral(); //then move object i to a new posi­tion col­li­sion­Tally = 0; //and start the loop over again. } else { //But if no coll­sions hap­pened, col­li­sionsOc­cur­ring = false; //then this loop is done, and we can move on to the next object i. } } } }

    void mouse­Pressed() { clusterObjects(); }

    void key­Pressed() { if (key == ‘r’) { //Randomize posi­tions and sizes for (int i = 0; i < objects.length; i++) { objects[i].newRandomPositionAndSize(); } } else if (key == ’]’) { //Increase spac­ing spac­ing++; clus­ter­Ob­jects(); } else if (key == ‘[‘) { //Decrease spac­ing spacing--; clus­ter­Ob­jects(); } else if (key == ‘+’ || key == ‘=’) { //Create a new object numDiscs++; Object objectIn­stance = new Object(objects.length); objects = (Object[]) append(objects, objectIn­stance); } else if (key == ‘-’ || key == ‘_’) { //Remove the newest object if(numDiscs > 0) { numDiscs--; objects = (Object[]) shorten(objects); } } }

    Comment by M — 2012 March 29 @ 6:05 pm

RSS feed for comments on this post.

Leave a comment

Site content and design © copyright 2006–2008 Scott Murray.