:MeetPi

Over the past few days I’ve been busy packing rectangles into squares.  The packing problem is a well known one, and is an active area of research in computer science.  There’s this project, for example, that’s seeking to document and implement all known packing algorithms.

Packing is an area of interest and active research in computer science not only because it’s a challenging problem, but also because it has a range of practical applications – for working out how arrangements of molecules to actually packing objects in boxes in the most efficient way possible.

My own foray into box packing algorithms comes from a different angle: I want to pack text.  I’ve been working on building a tool for visualising Moodle log data.  A tag cloud is a perfect way to see which students have been accessing the Moodle site the most.  My default tag cloud was the standard one – each tag in the cloud is presented in a sentence of words of various sizes, eg:

This is pretty much the default tag cloud format, and you see it everywhere.  But then there’s more exciting and aesthetically pleasing examples of tag clouds – none better than Wordle. Wordle’s impressive graphics are even more impressive because they are generative – that is, they are created by an algorithm rather than by manual placement by a human.  The thing is, the Wordle algorithm is not publicly available and there’s no API.  A quick search turned up lots of papers on packing algorithms and a few relating directly to using packing methods to create tag clouds, but all at a fairly abstract level, and few with any example code.

To be honest, I smelled a fun challenge and didn’t want to dig too deep because I wanted to solve the problem myself – even if it was a case of reinventing the wheel.  The problem: given a bunch of 500 rectangles, all of random sizes, how can they be drawn on the screen in such a way to a) use the available screen space effectively, and b) look interesting to the human viewer?

I played with a few ideas before I came to a space partitioning approach.  Essentially, what I decided to do was think of the screen as a rectangular ‘region’ that could contain a number of rectangular child regions.  When a rectangle gets added to the region, two other rectangles are formed like this:

The top left (light grey) rectangle contains the object we want to place – text, in my case.  The other two rectangles are empty, and can themselves have an object added to them and then be further subdivided.  The idea is that we start off with an initial empty region and add a rectangle, which leaves us with two free regions.  Then when we add another rectangle, we put it one of these two regions, which creates another two free regions, and so on, until the regions get too small to fit any more objects.

Doing this with 500 randomly shaped rectangles creates the image above.  The red rectangles were placed first, the yellow ones in the middle of the process, and the green ones were placed last.

I also experimented with different placements, which required up to five child rectangles.  The first, pictured left in the above image sequence shows a centre pack, where rectangles are placed in the centre of the subdivided region.  The middle one shows a bottom right packing sequence, and the last one shows a random packing sequence, which is a mix of all three methods (top-left, centre, bottom-right).

Out of all of them, the top left method produced the best results (although there I’m still experimenting with other methods).  I’ve also added some extra code to account for rotation, and even auto-rotation to help fitting text (which is buggy at the moment).  When turned into a tag cloud, the results aren’t Wordle, but they’re better than the basic tag cloud:

And this is how Wordle rendered the same text:

Not quite Wordle, but then again, I’m not quite Jonathan Feinberg, either.  I’m posting the processing applet here, too, so if anybody out there wants to give me any feedback or suggestions, please let me know.  The class that does most of the work is CRegion.

1 Comment