# Thread: Center-weighted bin packing algorithm?

1. ## Center-weighted bin packing algorithm?

Hello, good people!

I cannot for the life of me Figure out what type of rectangle packing algorithm is used for generating such word frequency clouds as this one:

http://cfftjresources.wikispaces.com...ord-cloud1.jpg

Does anyone have a clue? Any hints are much appreciated!

2. You will want to read this:
Fast optimizing rectangle packing algorithm for building CSS sprites - CodeProject

Basically all words start by becoming individual rectangles of varying sizes, according to your word cloud algorithm.
You then pack them following some appropriate method like the one described by Richard E. Korf. (here, pdf link)

As far as generating the images, you can use a library like imagick for the web, or whatever is more appropriate for your programming language.

EDIT: Hey, and welcome back.

3. Thank you! Glad to be back! It's been literally ages since my last post. I do have to admit to being more than slightly embarassed of my nick, avatar and sig...

I will most probably use libcairo for my graphical needs. If pressed I could write to a PostScript file. I will be using C++ or Java for this btw.

I am far more interested in the algorithmical basis of this. I have taken a look at both of your links - thanks! However, as far as I can see most of the word clouds I find have the largest rectangles gravitating towards the middle, while the smaller ones are more or less evenly distributed towards the edges. Is this how the algorithm works intrinsically? Or do I have to use some kind of tweaks?

What if I want to shape my cloud as a drop or a circle or whatever? Any advice?

4. Yup. Your post title makes it clear, but I didn't notice.

The method described gives you a nice seemingly random distribution resembling the image you posted. The trick, if I'm not mistaken, is to look at the outer rectangle as extending the general properties of the smaller rectangles you want to pack. Being that these are images containing a word, you will want to make a slight modification to the steps on that Code Project article and sort your rectangles by width instead of height -- and starting with an outer rectangle that is as wide as the widest rectangle (because all your images to be packed will tend to be wider than they are taller).

Now -- and this is speculation at this point and hopefully someone will correct me if I'm wrong -- but I believe you could, during the process described for packing the rectangles, alternatively add more space first to the left then to the right (and to the top and then to the bottom) moving the already parked rectangles up and down, left and right, in the opposite direction according to the algorithm rules. This would result in a final image that would tend (but not always) to pack the largest rectangles at the center, since they are sorted by size as you insert them, giving you your desired look.

As for packing inside a circle or oval shape, the principle is exactly the same I believe. But with a tweak. You consider your outer rectangle, the rectangle that encloses your circle or oval. But when packing you take into account the 4 no-go zones that are the areas between the oval and the enclosing rectangle. In the end you will always be packing inside a rectangle, but -- provinding you have enough shapes to pack -- you'll come up with a circle or oval shaped cloud.

5. Thank you for your explanation - I will try out your suggestions as soon as I get the chance!