Non-overlapping markup label tags using matplotlib

Question

I have a scatter plot with several points. Each point has a line associated with it (varying in length), which I would like to label, but I cannot fit all of them. Therefore, I would like to iterate over my data points from the most to the least important and in each case apply a label only if it does not overlap as an existing label. Lines vary in length. One commentator mentions a solution to a backpack problem in order to find the best solution. In my case, a greedy algorithm (always denoting the most important remaining point that can be marked without overlapping) will be a good start and may be sufficient.

Here is an example of a toy. Can I make Python stick only as many points as possible without overlapping?

import matplotlib.pylab as plt, numpy as np npoints = 100 xs = np.random.rand(npoints) ys = np.random.rand(npoints) plt.scatter(xs, ys) labels = iter(dir(np)) for x, y, in zip(xs, ys): # Ideally I'd condition the next line on whether or not the new label would overlap with an existing one plt.annotate(labels.next(), xy = (x, y)) plt.show() 

Answer 1

First you can select all annotations, and then use a mask to check for overlap and hide set_visible() . Here is an example:

 import numpy as np import pylab as pl import random import string import math random.seed(0) np.random.seed(0) n = 100 labels = ["".join(random.sample(string.ascii_letters, random.randint(4, 10))) for _ in range(n)] x, y = np.random.randn(2, n) fig, ax = pl.subplots() ax.scatter(x, y) ann = [] for i in range(n): ann.append(ax.annotate(labels[i], xy = (x[i], y[i]))) mask = np.zeros(fig.canvas.get_width_height(), bool) fig.canvas.draw() for a in ann: bbox = a.get_window_extent() x0 = int(bbox.x0) x1 = int(math.ceil(bbox.x1)) y0 = int(bbox.y0) y1 = int(math.ceil(bbox.y1)) s = np.s_[x0:x1+1, y0:y1+1] if np.any(mask[s]): a.set_visible(False) else: mask[s] = True 

conclusion:

Answer 2

Just as an additional note: for my code to work, I had to add an additional parameter renderer=fig.canvas.get_renderer() to the get_window_extent() method. I think the need for this line of code depends on the operating system.