Point-feature labeling in matplotlib

[dhn]

I am trying to automate the generation of scatterplots in matplotlib.
The problem of where to put the labels is known as 'point-feature
labeling' (a main application is in cartography, where cities and such
are known as 'point features'). In general the problem is not easy.
Some references:

http://www.merl.com/reports/docs/TR96-04.pdf
http://www.eecs.harvard.edu/shieber/Biblio/Papers/tog-final.pdf

If anyone knows of any canned python algorithms to do this, please
direct me to them. If not, I will need to implement one.

My problem is not that hard, as I will not have more than 20 labels to
place. As I see it, the steps that need to be taken are:

1. locate the points
2. compute the size of the text boxes for the labels
3. minimize a loss function reflecting one of the algorithms discussed
in the papers cited to determine the optimal placement of the labels

At the moment I was wondering if any matplotlib experts (I am a bit of
a novice) could suggest a good way to accomplish 2. I have tried to do
something like

In [1]: from pylab import *
In [2]: plot([0.5],[0.5],'bo')
In [3]: axis([0,1,0,1])
In [4]: t = text(0.50,0.51,'Test')
In [5]: t._get_layout(t._renderer)[1][0][1]
Out[5]: (20.0, 6.0)

Then I have tried to use t._transform to convert these dimensions back
into axis coordinates. Unfortunately this method seems to require that
the plot be rendered to be able to get the dimensions, which is not too
efficient. I'm sure there is a better way to do this; does anyone have
any ideas?