Space Filling using Genetic Algorithm

General Discussion Other

sriiyer89

Space Filling using Genetic Algorithm

in General Discussion • Other • 5 months ago

Hi,

I am working on a research project, and being an infant in the world of processing usage, I have some starting trouble.

For my project, I need to fill a rectangular space with a cluster of standard sized geometric shapes, be it another rectangle, a square, trapezium or any other polygon. I understand that there are many ways of accomplishing this, but I want to do this using Genetic Algorithm. I have understood the concept of GA, but I am unable to relate it to this particular problem.

Could someone please guide me with how I should start going about this code?

Replies(3)

tfguy44

Re: Space Filling using Genetic Algorithm

5 months ago

Here is a start. This provides you with an ever-changing collection of randomly generated shapes. Now all you need to do is find a way to score a collection, have multiple collections, and have the next generation of collections depend on the best of the previous generation (possibly with some mutation for good measure).

As a good scoring metric, I would suggest ( (Area (measured in pixels) of the target rectangle covered) - (Area of overlapping shapes) - (Area of shapes outside the rectange) ) * (Number of shapes).

Determining these various areas can be done with some fancy image mapping, possibly to offscreen-buffers.

static int max_shape_width = 40;
static int max_shape_height = 40;
ArrayList things;
int time;
void setup(){
size(600,400);
things = new ArrayList();
time = 0;
}
void draw(){
background(196);
// Let's define a rectangular space to try to cover!
stroke(0);
fill(255);
translate(50,50);
rect(0,0,width-100,height-100);
// Is it time to make new shapes?
if( time < millis() ){
makeNewThings();
time = millis() + 5000;
}
// Let's draw the shapes!
for( int i = 0; i < 20 ; i++ ){
((Thing) things.get(i)).draw();
}
}
void makeNewThings(){
// For the time being...
// Remove all the things.
for( int i = things.size()-1; i >= 0 ; i -- ){
things.remove(i);
}
// And add some new ones.
for( int i = 0; i < 20 ; i++ ){
things.add( new Thing() );
}
// You'll need to do better than this, of course.
}
class Thing {
// Everything a thing needs to know to be a shape.
float x, y; // position
float w, h; // size
float r; // orientation
int t; // type
color c; // color
// Maybe a list of vertecies if you want to get fancy.
PVector[] vs; // Not used yet.
// Just for now, make a random thing.
Thing(){
c = color( random(255), random(255), random(255) );
x = random(width);
y = random(height);
w = random(max_shape_width);
h = random(max_shape_height);
r = random(TWO_PI);
t = int( random(2) );
}
// A way to draw the shape.
void draw(){
pushStyle();
pushMatrix();
translate(x,y);
fill(c, 128);
stroke(0);
ellipseMode(CENTER);
rectMode(CENTER);
rotate( r );
if( t == 0 ){
ellipse(0,0,w,h);
}
if( t == 1 ){
rect(0,0,w,h);
}
popMatrix();
popStyle();
}
}

If you need additional help, I have a sick cat that needs money for cancer treatments.

Shoot me an email: TfGuy44 at gmail dot com.

amnon.owed

Re: Space Filling using Genetic Algorithm

5 months ago

For the fitness of each generation you could use the pixel array, as in empty/filled/overlapping space.

amnon.owed

Re: Space Filling using Genetic Algorithm

5 months ago

Inspirational if not helpful: http://vimeo.com/63755542

Perhaps this paper is also of interest:

Generating Sequential Space-Filling Designs Using Genetic Algorithms and Monte Carlo Methods
by Karel Crombecq and Tom Dhaene

It concludes that Monte Carlo Methods are more optimal for space filling than GA.

Top Reply