technology from back to front

Archive for January, 2007

The right placement

I wrote a short script to display the results of the 2004 US presidential elections as a bar chart, shown below (click for full-size image, which will make more sense):

The width of each state indicates the number of electoral college votes it has; the height the extent to which votes for one party exceeded votes for the other. The script is in Python and uses Cairo for drawing. The most challenging part of writing the script was…

…placing the labels that indicate the states.

You can’t just place the labels above/below the states, because some of the states are too narrow; the labels would overlap each other. So some labels need to be moved a little to one side or the other for them all to fit. It took me a little while to find a neat, satisfying algorithm for solving the problem. I’m sure it’s well known – it’s too simple not to be, and I’m sure I’m not the first with this problem – but it was fun to find.

Formally, we have some minimum distance between labels d, as well as smallest and largest positions they can be in (xmin and xmax). Each label wants to be in a position ai, so we want to choose each xi such that xi+1xi + d, but |aixi| is small. The first requirement is strict and formally defined; the second is a fuzzier goodness factor.

My solution looks something like this:

offsets = [s.desired_x - i * d for i, s in enumerate(states)]
max_offset = x_max – d * (len(states) -1)
for i, s in enumerate(states):
new_offset = (max(offsets[:i+1]) + min(offsets[i:])) / 2.0
s.label_x = i * d + max(x_min, min(max_offset, new_offset))

How does it work?

Define ai = aiid, and similarly xi = xiid. Note that xi+1xi + d if and only if xi+1xi, in other words, xi has to be a monotonically nondecreasing sequence. Note also that |aixi| = |aixi|. So we’ve reduced the problem to finding a nondecreasing sequence that’s “close” in some sense to an arbitrary sequence. We make two non-decreasing sequences – “smallest point ahead of me” and “largest point behind me” – and average the two, which is guaranteed to yield another non-decreasing sequence. We then clamp this sequence between suitable min/max bounds, which again is guaranteed to yield a non-decreasing sequence. So it’s not hard to prove that labels never overlap.

How does it do on the goodness factor? As can be seen from the example, not too badly. Where there is plenty of room, the ai sequence is monotonically increasing, and so the other sequences we average cling to it; the result is that ai = xi. Where they are bunched together, the labels are spread out above, centered on the center of the labels, except at the ends where they fan out into the space available.

It’s not perfect; look in particular at New Jersey, which is making more room for its neighbours than it needs to. I may yet be able to improve on this. But it’s pleasing when you replace a nastily hacked-up thirty-line succesive approximation solution with a five-line solution that runs faster and produces more aesthetically pleasing results.

Paul Crowley



You are currently browsing the LShift Ltd. blog archives for January, 2007.



2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us