Implementing non-colliding text labels in kdeeduplot, based on kmplot code.

It works, but it could probably be faster. You don't need to know anything about it to use the feature, it all happens behind the scenes. Just add some items with labels and enjoy the magic.

However, in the interest of inspiring optimization, here's a brief description of how it works.

KPlotWidget now has a private array of floats: PlotMask[100][100]. This is a rough division of the content of the plot into a 100x100 grid. Where the plot is empty, the array is zero, where it has content, it is >0. When items are added to the plot (points, lines, bars, or labels), the corresponding positions in PlotMask are incremented by an amount that can vary for different kinds of items (for example, right now Bars don't increment as much as points or lines).

The function KPlotWidget::placeLabel() is responsible for positioning item labels. It attempts to place the label close to the point to which it belongs, while minimizing the label's overlap with masked regions of the plot. Ideally, it won't overlap with masked regions at all. This is done in a rather brute-force way: it tests label positions in a 40x40 grid around the position of the point, and determines the "cost" for placing the label at each position. Higher cost is incurred for (a) overlapping with a masked region, (b) being further from the point position, and (c) extending beyond the bounds of the plot. The position that has the lowest "cost" is then adopted, and the label is drawn at that position.

You can get an idea of the CPU impact of this cost-analysis using the test suite I added to kdeeduplot. Display the "Points, lines and bars" plot, and then resize the window. Note the smoothness of the redraws. Now display "Points, lines and bars with labels" and resize the window. The redraws take much longer in this case.