[kde-edu]: KDE/kdeedu/libkdeedu/kdeeduplot

[Jason Harris]

SVN commit 599914 by harris:

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.

CCMAIL: kde-edu at kde.org



 M  +33 -27    kplotobject.cpp  
 M  +154 -5    kplotwidget.cpp  
 M  +64 -0     kplotwidget.h  
 M  +8 -12     tests/testplot_widget.cpp