« Back to Processing

Tutorial #9: Filling Space

| No Comments | Published on June 26, 2008
The content that follows was originally published on the Don Havey website at http://donhavey.com/blog/tutorials/tutorial-9-filling-space/

Space-filling previewI had a crotchety old man as a 2nd-year studio instructor. He was very adamant about the usage of the word space. He tried to tell us that space cannot be created (sometimes architects say that they “create spaces”), but all I learned was that it was very difficult to learn anything from crotchety old men.

It’s a matter of semantics, if you ask me. Creating space, defining space… whatever. Today, I am concentrating on fillling space. There should be no controversy there. Even while he was yelling about space, my professor was certainly occupying some.

I’ve been thinking of trying a space-filling algorithm for some time now. They’re quite simple, and quite useful. Jared Tarbell made a nice one a few years ago: Emotion Fractal. In the world of data analysis, they are commonly referred to as Treemaps.

Here’s what it will look like: The final result (click to activate, then press the spacebar to add boxes)

And here’s the source code: Space-filling classes

Let’s get started…

By the way, I didn’t look at any precedent code for this applet… maybe I should have. You be the judge.

The process

We want to be able to take a rectangle of a given size and cram it full of as many other rectangles as possible. Of course, the rectangles don’t have to be just rectangles… they can represent the bounding boxes of any irregular shape as well.

Our script should take a given rectangle (a width and height) and place it, without overlaps, inside our applet’s boundaries. If a given rectangle can’t be placed without overlapping another, we’ll send back an arbitrary pair of error “coordinates” (I use {-9999,-9999}) to let us know that we’ll have to make some adjustments.

The process will go like this:

  1. Test a given rectangle against a random “region” of the applet.
  2. If it fits, place it either randomly or methodically (e.g. centered, left-top-corner, etc.) within that region.
  3. Subdivide the region that we have just placed our rectangle in. See the diagram below. We’ll split it into three rows, the center of which will consist of three columns.
  4. The subdivisions, excluding the rectangle which we’ve just placed, become a part of our set of regions to test on. Repeat.

Subregion divisionsTo the left is an illustration of exactly how an area is subdivided in our algorithm. Of course, other variations exist, but this was one of the simplest. It favors creating rows over columns. If the rectangle being inserted into a given region abuts the side of the region, we don’t want a cell there… so this algorithm may divide a region into as few as one (when the inserted rectangle occupies the entire area), to as many as 5 subregions.

The Region class

Our only new class is the Region class, which I’ve been alluding to. It will define a unique rectangle in our applet and include a method for dividing itself into smaller Regions. Here’s some code:

//this function returns true when a region has been split up
//useful because we don't want to modify or render regions that have been divided
boolean is_divided(){
  if(nsubregions==0){ return false; }
  return true;
}
//divide the region according to the inserted rectangle's size
float[] divide(float $w,float $h){
  //the size difference between the rectangle to insert and this region's bounds
  float xspace = w-$w;
  float yspace = h-$h;
  //choose an arbitrary offset from the top left corner of this region
  float ox = random(xspace);
  float oy = random(yspace);
  //divide it up into subregions
  //first row
  if(oy>distance_tolerance){
    subregions[nsubregions++] = new Region(x,y,w,oy,false);
  }
  //second row
  //first column
  if(ox>distance_tolerance){
    subregions[nsubregions++] = new Region(x,y+oy,ox,$h,false);
  }
  //second column
  //this is the inserted rectangle! note the "true" value, which means it's full
  //and therefore shouldn't be considered for future subdividing
  subregions[nsubregions++] = new Region(x+ox,y+oy,$w,$h,true);
  //third column
  if(xspace-ox>distance_tolerance){
    subregions[nsubregions++] = new Region(x+ox+$w,y+oy,xspace-ox,$h,false);
  }
  //third row
  if(yspace-oy>distance_tolerance){
    subregions[nsubregions++] = new Region(x,y+oy+$h,w,yspace-oy,false);
  }
  float[] coordinates = {x+ox,y+oy};
  return coordinates;
}

I didn’t include the constructor function in the code above because it’s pretty self-explanatory. The only thing to note is that we’re relying on the existing Polygon class as our renderable object.

Calling the divide() method

Our spacefilling.pde file contains all of the rest of the code for this applet. I’ve set it up to generate a random set of 1000 rectangles, sort them into an array, and then attempt to iteratively fill the screen with them. Of course, many will need to be skipped. Here’s the insert_region() method that is called per key press:

float[] insert_region(float $w,float $h){
  int n = 0;
  int i = 0;
  //test no more than 100 regions for a match that will hold this rectangle
  //if you're looking for an efficient method, this is not it
  //instead, you would sort the array of regions according to size
  //and then try only the first region, resulting in optimal packing efficiency
  //so long as the array of rectangles to be inserted is sorted as well
  while(i<100&&(regions[n]==null||regions[n].is_divided()||
        regions[n].full||regions[n].w<$w||regions[n].h<$h)){
    n = floor(random(nregions-.00001));
    i++;
  }
  if(i!=100){
    return regions[n].divide($w,$h);
  }else{
    //if a region could not be found to hold this rectangle, return an error "coordinate"
    //this is done to avoid return type conflicts
    float[] error = {-9999,-9999};
    return error;
  }
}

Efficiency

I’ve already noted some ways to make the code more efficient. I was going for a random-distribution aesthetic when I wrote this, similar to Jared Tarbell’s piece, but if you really want a diagram that, for example, tells you how to pack the trunk of your car most effectively, you’d need to tweak the applet.

Efficient space-fillingFirst you should go ahead and implement the Region-sorting described above, and then, more importantly, you can change the ox and oy values in the Region divide() method to zero, meaning that each inserted rectangle will be placed in the top left corner of the region, dividing it up into a maximum of three (much larger) subregions.

You’ll get something like this image on the left. It reduces the gaps caused by our randomness, and therefore allows for larger rectangles. Some of them will still be skipped (you’ll have to leave that fourth suitcase at home), but at least this method favors larger pieces.

All that said, this script still isn’t a great approach to space-filling. Dividing into regions is fast and easy, but it greatly limits the size of the inserts, because adjacent empty regions are not merged into one. Instead, you could try a more tedious proximity-testing approach… or better yet, figure out how to use something like a Voronoi diagram to determine where to place the boxes.

All done

Not much else to say here. Enjoy!

Here’s the demo again: The final result (click to activate, then press the spacebar to add boxes)

And here’s the source code: Space-filling classes

Categories: Processing / Tutorials

Tags: / / / /

Leave a Response

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>