My word cloud algorithm

My word cloud algorithm works by successively placing words around previous, larger words.

I'm going to demonstrate it with diagrams.

Histogram (or weighted words)

Firstly, we are given a histogram of words:

Place the first word

You identify the most frequent word, or the “biggest” word, which is “bar”, and place it on the canvas. This can be placed in the centre, or in a random position. For this demonstration, it's in the centre.

The first word is special because it does not have a history of previously placed words (you will see what that means next), and we also don't care about that either.

The rest of the words

When placing the rest of the words, we do care about previously placed words, because that's how we decide where to put a word.

The next word in the histogram is “foo”, so we're going to try placing that.

When a word is placed, we are given the rectangular coordinates that the drawn text takes up. With this information we can know if two pieces of drawn text overlap. The rectangular area taken up by the drawn text is highlighted in green below.

Given this information, we can now try to place “foo” in some place around bar. We'll start at the top left, and go in an anti-clockwise direction around the word, pixel by pixel.

Above something bad has happened! An overlap. How exicting. “foo” here has left the canvas and so will not fit in that position. We're going to have to keep going down and around!

...And we have a place that fits. Let's not be picky; this will do. No need to continue.

Next on the list is “mu”, and, remember, we try the biggest word first, to fit around. We try to place “mu” around “mu” and it fits nicely at the top left:

You will notice that in my algorithm, words become smaller depending on their weight. This is a common characteristic of word clouds, and it looks pretty.

Next we encounter a word collision. Trying to place “zot” around “bar” at the first place (top left) has caused an overlap with “mu”:

So we have to move “zot” down a bit and it fits nicely:

And, likewise, we have a similar “shifting” motion for “foobar”:

That's the end of our histogram data, but next I will add a few more entries in order to show you the cool part of my algorithm.

Trying the next largest word

To make it interesting, let's add more histogram items -- song names from a band I like called Tool -- so that our histogram now looks like this:

Placing (in order) “parabola”, “schism”, “stinkfist”, and “aenema” looks like this:

Unsurprisingly, “stinkfist” was pushed up the top because it doesn't fit on the right of “bar”.

Placing the next word, “vicarious”, we notice that there is no space where it will fit, around the word “bar” (1). So what we have to do is choose the next largest word, that is, “foo”, and try to place it around that (2). And indeed we can:

The spiffiness of this algorithm is that if we couldn't place around “foo”, we'd try “mu”, and so forth -- this means that eventually, provided the canvas is large enough, a space around the edge of the cloud will be found where the word can be placed, because the smallest words are around the edge.

And for love; the finished, unannotated word cloud:

Doesn't look too bad at all!

Date Created: Fri 25 July 2008, contact chris done (chrisdone@gmail.com)