[PATCH] Improved text label placement in KPlotWidget

Jason Harris kstars at 30doradus.org
Mon Aug 18 01:23:24 BST 2008


Hello,

Sorry this is long...

In KPlotWidget, when a plot point is given a name, a text label is
added to the plot near the point.  The function
KPlotWidget::placeLabel() is in charge of selecting an optimal
position for the label, such that it doesn't overlap with other plot
elements.  This is achieved by attaching a "cost" to overlapping
regions, and finding the label position that minimizes the cost.

The current version of placeLabel() is kind of embarrassingly dumb (I
can say so because I wrote it :).  When elements are added to the
plot, the locations are marked using a 100x100 array of floats that
serves as a low-resolution "mask" of the plot contents.  When placing
a label, it does a brute-force search of a 20x20 subsection of this
mask, centered on the point to be labeled.  This is not only slow, but
the label positions are very quantized...both of these problems are
obvious when you actually use the label feature.

For example, in the KStars "Solar System viewer" tool, each of the
planets is labeled, and the plot takes 250-300 ms to draw.  If I
remove the labels, that falls to 75-85 ms.

The attached patch uses a much better implementation of placeLabel().
Here I am using an actual QImage for the plot-contents mask, which is
always the same size as the plot area in pixels.  The mask values are
arbitrarily stored in the red channel of the image's pixel values.
(You may be wondering why I need a range of values for the mask rather
than a bitmask.  If more than one plot element occupies a pixel, I
want it to be cumulative.  Also, I want different kinds of plot
elements to have different imprints on the mask.  For example, points
have a bigger impact than lines.)

Anyway, in addition to using a QImage for the mask, I now also use
something like a "downhill simplex" to find the optimum label
position.  Starting at the position of the labeled point, I take a
small step in each direction (up down left right) to determine the
local cost gradient, and then I take a downhill step. This iterates
until the cost falls below a preset threshold.

With the new system, adding labels to the Solar System viewer tool
makes the draw cycle take only 80-90 msec, or only 5 msec more than
with no labels!  Also, the label positions are no longer so obviously
quantized.

Issues:
+ The setAlpha() calls are there as part of my debugging.  If you
uncomment the line after "DEBUG: Draw the plot mask", then the mask
QImage will be drawn on top of the plot; the transparency allows the
underlying plot to show through.

+ The positions are not as optimal as they might be.  While searching
for a low-cost position, it will give up if the current position is a
cost minimum.  Occasionally, this is a local minimum, and a different
path choice at the beginning would have led to a better solution.  I
will try to fix this soon.

+ Thinking specifically of the Solar System tool, which includes the
ability to zoom in/out.  When you change the zoom, it recomputes the
label positions from scratch, which tends to make them jump around a
lot.  It might make sense to start from the last optimal position,
rather than the position of the labeled point, when recomputing the
positions.

Ok to commit?  Er, actually, I don't think I have privileges to commit
to kdeui, so I'll have to ask someone to do it for me...

thanks,
Jason
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kplotwidget_cpp.diff
Type: text/x-patch
Size: 13655 bytes
Desc: not available
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080817/fcf7980c/attachment.bin>


More information about the kde-core-devel mailing list