help random distribution of non-overlapping circles

Programming Questions

zombience

help random distribution of non-overlapping circles

in Programming Questions • 1 year ago

I've been trying to sort this out for hours ,since yesterday. I'm afraid I just don't know programming technique well enough to think my way around this one.

How can I randomly distribute circles without them overlapping? I've been banging my head against the wall!

I took info from these two sources:

http://paulbourke.net/texture_colour/randomtile/

and

http://alignedleft.com/blog/2008/11/how-to-cluster-circles-of-different-sizes-while-preventing-overlap/

I was trying to create my own from scratch while taking inspiration from these two sources. I feel like I'm close, but keep getting caught in infinite loop or null pointer exceptions (values don't get assigned).

Um, I'm probably over thinking this. Here's what I got so far.

int circleCount = 10;
float maxRadii = 200;
float minRadii = 20;
PVector circleArray[] = new PVector[circleCount];
float radArray[] = new float[circleCount];
PVector loc;
float radii;
void setup(){
size(800, 600);
background(0);
initCircles();
}
void draw(){
fill(150);
noStroke();
drawCircles();
}
void initCircles(){
boolean overlap;
boolean finalJ;
for (int i = 0; i < circleCount; i ++){
if (i < 2){ //added this because I kept getting caught in problems with i = 1 and j = 0, cancelling loop
loc = new PVector(width/2 + (i * maxRadii), height/2 + (i * maxRadii));
radii = ((minRadii + maxRadii - 2) /2);
circleArray[i] = loc;
radArray[i] = radii;
println("inside initial i<2 loop, " + circleArray[i] + " circleArray[i] " + radArray[i] + " rads");
overlap = false;
}//end if i < 2
else
{
overlap = true;
for (int j = 0; j <= i; j ++){
finalJ = false;
if (j >= i - 1){
finalJ = true;
}//end else of if i < 2
println("start j at " + j);
println("comparing " + i + "i to " + j + "j " );
while (overlap){
println("start overlap");
loc = new PVector(random(maxRadii, width - maxRadii), random(maxRadii, height - maxRadii));
radii = random(minRadii, maxRadii);
float rads = radii + radArray[j];
float distance = loc.dist(circleArray[j]);
println("comparing " + distance + " distance to " + radii + " radii");
if (distance > rads && finalJ == false){
println("no Overlap, more j to compare");
break;
}// end if distance > rads
if (distance < rads)
{
println("overlap found to be true, back to overlap loop");
overlap = true;
}//end of if distance > rads
while(finalJ){
if(distance > rads){
circleArray[i] = loc;
radArray[i] = radii;
overlap = false;
finalJ = false;
println("overlap found to be false at " + j + " j of " + i + ", assigning " + loc + " to circleArray " + i);
}//end if distance > rads
else//else of if under finalJ
{
overlap = true;
}//end else
}//end while(finalJ)
} //end while (overlap)
println("out of while overlap loop, iterating j");
}//end for j
println(" j compared to all existing i, incrementing i");
}//end for i
}//end else (of i)
}//end initCircles
void drawCircles(){
for (int i = 0; i < circleCount; i ++){
ellipse(circleArray[i].x, circleArray[i].y, radArray[i], radArray[i]);
}
}

/*
Please forgive my ignorance. I only know what I've already learned, and this world is a lot bigger than that.
*/

Replies(11)

amnon.owed

Re: help random distribution of non-overlapping circles

1 year ago

I've always liked the look of circle packing, so decided to give it a shot as a result of your question. Your code didn't work for me, it just gave me a bunch of lines of text in the console... So I started from scratch as well. The applet from the blog post you linked to seemed to be inaccurate. The Paul Bourke link was very good, although I only glanced through it. Which means I may or may not have subconciously stolen his idea.

I posted a picture of the end-result of my attempt on my Tumblr. Note I've built in a way to manually remove circles as well by pressing or dragging the mouse, which can give a nice visual effect.

Code Example

ArrayList <PVector> circles = new ArrayList <PVector> ();
float diameter = 100;
void setup() {
size(1280, 720);
colorMode(HSB, 360, 100, 100);
noStroke();
smooth();
}
void draw() {
background(0);
addCircle();
for (int i=0; i<circles.size(); i++) {
PVector p = circles.get(i);
fill(i % 360, 100, 100);
ellipse(p.x, p.y, p.z, p.z);
}
if (diameter < 0.1) {
println("Done!");
noLoop();
}
}
void mousePressed() {
removeCircle();
}
void mouseDragged() {
removeCircle();
}
void addCircle() {
PVector c = randomVector();
int tries = 10000;
while (overlap(c) && tries > 0) {
c = randomVector();
tries--;
}
if (!overlap(c)) {
circles.add(c);
} else {
diameter *= 0.9;
addCircle();
}
}
void removeCircle() {
for (int i=circles.size()-1; i>=0; i--) {
PVector p = circles.get(i);
if (dist(mouseX, mouseY, p.x, p.y) < p.z*0.5) {
circles.remove(i);
}
}
}
PVector randomVector() {
return new PVector(random(width), random(height), diameter);
}
boolean overlap(PVector c) {
for (PVector p : circles) {
if (dist(c.x, c.y, p.x, p.y) < (c.z + p.z)*0.5) {
return true;
}
}
return false;
}

zombience

Re: help random distribution of non-overlapping circles

1 year ago

Thanks!

It'll take me a bit to pick this apart so that I can use it for the sketch I'm creating (I really just needed a way to create n circles, randomly spaced, without overlapping. you've gone the whole way and made it fill up the whole screen!).

I've come across your site before, I think I found it through the forums from a post on how to put sketches on tumblr.

Again, I appreciate the help, although I'm afraid your solution is beyond my understanding, so I'll have to pick it apart a little at a time.

/*
Please forgive my ignorance. I only know what I've already learned, and this world is a lot bigger than that.
*/

amnon.owed

Re: help random distribution of non-overlapping circles

1 year ago

All right, let me know if you need some clarification.

Basically I use (an ArrayList of) PVector(s) to store the x,y position and the diameter (in the z). When adding a circle I try up to 10.000 random positions (usually less) until a non-overlapping position is found. If it isn't found even after 10.000 tries, the diameter is decreased. This process is repeated on each draw() loop.

I'm pretty sure there are more efficient methods to do this, but... whatever works.

hellochar

Re: help random distribution of non-overlapping circles

1 year ago

Another method is to pick a point and then reduce the diameter until your sure it won't overlap. If you have the list of all circle positions and diameters you can just loop through them all, find the one that is closest to you and how close that is, and then make your circle that size (or smaller).

Jo Wood

Re: help random distribution of non-overlapping circles

1 year ago

Amnon - that's really nice. I've taken the liberty of modifying your example slightly to give more muted colours and to render the circles in a sketchy style. I quite like the effect:

zombience

Re: help random distribution of non-overlapping circles

1 year ago

Jo Wood, that's a nice looking patch.

Thanks all for the help on this

/*
Please forgive my ignorance. I only know what I've already learned, and this world is a lot bigger than that.
*/

v.k.

Re: help random distribution of non-overlapping circles

11 months ago

Nice one! Thanks for sharing amnon.

I tried adding:

PVector randomVector() {
float diameter = random(0.1, 200);
return new PVector(random(width), random(height), diameter);
}

To get a less regular distribution, it is cool but never ends... And get very inefficient when there are only little spaces available.

Jo Wood , loved the look! How did you go for this irregular shapes? Would you mind sharing? Love the colors also.

here the never ending/less regular version, as you can see still a lot of black areas:

and amn

on's original to compare:

Jo Wood

Re: help random distribution of non-overlapping circles

11 months ago

The irregular circles were produced using my 'Handy' Processing library for creating hand-drawn, sketchy looking shapes:

See gicentre.org/handy for the library and for those interested in some of the technical/scientific ideas associated with the work, see also Sketchy Rendering for Information Visualization presented at this year's VisWeek conference.

zombience

Re: help random distribution of non-overlapping circles

11 months ago

Thanks for the links Jo! I'd forgotten all about this, and I'd love to pick up some new drawing tricks.

/*
thinking about learning how to think in order to more effectively learn
*/

v.k.

Re: help random distribution of non-overlapping circles

11 months ago

Thanks Jo Wood, i'll have a look.

nootropic..

Re: help random distribution of non-overlapping circles

10 months ago

See gicentre.org/handy for the library and for those interested in some of the technical/scientific ideas associated with the work, see also Sketchy Rendering for Information Visualization presented at this year's VisWeek conference .

very nice!

Top Reply