[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-core-devel
Subject: [PATCH] Improved text label placement in KPlotWidget
From: "Jason Harris" <kstars () 30doradus ! org>
Date: 2008-08-18 0:23:24
Message-ID: 401f1570808171723n490ac153h2a1aaf035af46ebf () mail ! gmail ! com
[Download RAW message or body]
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
["kplotwidget_cpp.diff" (text/x-patch)]
Index: kplotwidget.cpp
===================================================================
--- kplotwidget.cpp (revision 848394)
+++ kplotwidget.cpp (working copy)
@@ -97,9 +97,8 @@
QRectF dataRect, secondDataRect;
// Limits of the plot area in pixel units
QRect pixRect;
- // Grid of bools to mask "used" regions of the plot
- float plotMask[100][100];
- double px[100], py[100];
+ //Array holding the mask of "used" regions of the plot
+ QImage plotMask;
};
KPlotWidget::KPlotWidget( QWidget * parent )
@@ -248,9 +247,10 @@
}
void KPlotWidget::resetPlotMask() {
- for (int ix=0; ix<100; ++ix )
- for ( int iy=0; iy<100; ++iy )
- d->plotMask[ix][iy] = 0.0;
+ d->plotMask = QImage( pixRect().size(), QImage::Format_ARGB32 );
+ QColor fillColor = Qt::black;
+ fillColor.setAlpha( 128 );
+ d->plotMask.fill( fillColor.rgb() );
}
void KPlotWidget::resetPlot() {
@@ -377,7 +377,7 @@
if ( d->showObjectToolTip )
{
QHelpEvent *he = static_cast<QHelpEvent*>( e );
- const QList<KPlotPoint*> pts = pointsUnderPoint( he->pos() - QPoint( \
leftPadding(), topPadding() ) - contentsRect().topLeft() ); + \
QList<KPlotPoint*> pts = pointsUnderPoint( he->pos() - QPoint( leftPadding(), \
topPadding() ) - contentsRect().topLeft() ); if ( pts.count() > 0 ) {
QToolTip::showText( he->globalPos(), pts.front()->label(), this );
}
@@ -391,6 +391,8 @@
void KPlotWidget::resizeEvent( QResizeEvent* e ) {
QFrame::resizeEvent( e );
+ setPixRect();
+ resetPlotMask();
}
void KPlotWidget::setPixRect() {
@@ -398,10 +400,6 @@
int newHeight = contentsRect().height() - topPadding() - bottomPadding();
// PixRect starts at (0,0) because we will translate by leftPadding(), \
topPadding() d->pixRect = QRect( 0, 0, newWidth, newHeight );
- for ( int i=0; i<100; ++i ) {
- d->px[i] = double(i*d->pixRect.width())/100.0 + double(d->pixRect.x());
- d->py[i] = double(i*d->pixRect.height())/100.0 + double(d->pixRect.y());
- }
}
QPointF KPlotWidget::mapToWidget( const QPointF& p ) const
@@ -411,133 +409,179 @@
return QPointF( px, py );
}
-void KPlotWidget::maskRect( const QRectF& r, float value ) {
- //Loop over Mask grid points that are near the target rectangle.
- int ix1 = int( 100.0*(r.x() - d->pixRect.x())/d->pixRect.width() );
- int iy1 = int( 100.0*(r.y() - d->pixRect.y())/d->pixRect.height() );
- if ( ix1 < 0 ) ix1 = 0;
- if ( iy1 < 0 ) iy1 = 0;
- int ix2 = int( 100.0*(r.right() - d->pixRect.x())/d->pixRect.width() ) + 2;
- int iy2 = int( 100.0*(r.bottom() - d->pixRect.y())/d->pixRect.height() ) + 2;
- if ( ix1 > 99 ) ix1 = 99;
- if ( iy1 > 99 ) iy1 = 99;
+void KPlotWidget::maskRect( const QRectF& rf, float fvalue ) {
+ QRect r = rf.toRect().intersected( d->pixRect );
+ int value = int( fvalue );
+ QColor newColor;
+ for ( int ix=r.left(); ix<r.right(); ++ix ) {
+ for ( int iy=r.top(); iy<r.bottom(); ++iy ) {
+ newColor = QColor( d->plotMask.pixel(ix,iy) );
+ newColor.setAlpha( 200 );
+ newColor.setRed( qMin( newColor.red() + value, 255 ) );
+ d->plotMask.setPixel( ix, iy, newColor.rgba() );
+ }
+ }
- for ( int ix=ix1; ix<ix2; ++ix )
- for ( int iy=iy1; iy<iy2; ++iy )
- d->plotMask[ix][iy] += value;
}
-void KPlotWidget::maskAlongLine( const QPointF &p1, const QPointF &p2, float value ) \
{ +void KPlotWidget::maskAlongLine( const QPointF &p1, const QPointF &p2, float \
fvalue ) { + if ( ! d->pixRect.contains( p1.toPoint() ) && ! d->pixRect.contains( \
p2.toPoint() ) ) { + return;
+ }
+
+ int value = int( fvalue );
+
//Determine slope and zeropoint of line
double m = (p2.y() - p1.y())/(p2.x() - p1.x());
double y0 = p1.y() - m*p1.x();
-
- //Make steps along line from p1 to p2, computing the nearest
- //gridpoint position at each point.
- double x1 = p1.x();
- double x2 = p2.x();
- if ( x1 > x2 ) {
- x1 = p2.x();
- x2 = p1.x();
- }
- for ( double x=x1; x<x2; x+=0.01*(x2-x1) ) {
- double y = y0 + m*x;
- int ix = int( 100.0*( x - d->pixRect.x() )/d->pixRect.width() );
- int iy = int( 100.0*( y - d->pixRect.y() )/d->pixRect.height() );
+ QColor newColor;
- if ( ix >= 0 && ix < 100 && iy >= 0 && iy < 100 )
- d->plotMask[ix][iy] += value;
+ //Mask each pixel along the line joining p1 and p2
+ if ( m > 1.0 || m < -1.0 ) { //step in y-direction
+ int y1 = int( p1.y() );
+ int y2 = int( p2.y() );
+ if ( y1 > y2 ) {
+ y1 = int( p2.y() );
+ y2 = int( p1.y() );
+ }
+ for ( int y=y1; y<=y2; ++y ) {
+ int x = int( (y - y0)/m );
+ if ( d->pixRect.contains( x, y ) ) {
+ newColor = QColor( d->plotMask.pixel(x,y) );
+ newColor.setAlpha( 100 );
+ newColor.setRed( qMin( newColor.red() + value, 255 ) );
+ d->plotMask.setPixel( x, y, newColor.rgba() );
+ }
+ }
+
+ } else { //step in x-direction
+ int x1 = int( p1.x() );
+ int x2 = int( p2.x() );
+ if ( x1 > x2 ) {
+ x1 = int( p2.x() );
+ x2 = int( p1.x() );
+ }
+
+ for ( int x=x1; x<=x2; ++x ) {
+ int y = int( y0 + m*x );
+ if ( d->pixRect.contains( x, y ) ) {
+ newColor = QColor( d->plotMask.pixel(x,y) );
+ newColor.setAlpha( 100 );
+ newColor.setRed( qMin( newColor.red() + value, 255 ) );
+ d->plotMask.setPixel( x, y, newColor.rgba() );
+ }
+ }
}
}
void KPlotWidget::placeLabel( QPainter *painter, KPlotPoint *pp ) {
int textFlags = Qt::TextSingleLine | Qt::AlignCenter;
- float rbest = 100;
- float bestCost = 1.0e7;
QPointF pos = mapToWidget( pp->position() );
- QRectF bestRect;
- int ix0 = int( 100.0*( pos.x() - d->pixRect.x() )/d->pixRect.width() );
- int iy0 = int( 100.0*( pos.y() - d->pixRect.y() )/d->pixRect.height() );
+ if ( ! d->pixRect.contains( pos.toPoint() ) ) return;
QFontMetricsF fm( painter->font(), painter->device() );
- int xmin = qMax( ix0 - 20, 0 );
- int xmax = qMin( ix0 + 20, 100 );
- int ymin = qMax( iy0 - 20, 0 );
- int ymax = qMin( iy0 + 20, 100 );
- for ( int ix = xmin; ix < xmax; ++ix )
- {
- for ( int iy = ymin; iy < ymax; ++iy )
- {
- QRectF labelRect = fm.boundingRect( QRectF( d->px[ix], d->py[iy], 1, 1 \
), textFlags, pp->label() );
- //Add some padding to labelRect
- labelRect.adjust( -2, -2, 2, 2 );
+ QRectF bestRect = fm.boundingRect( QRectF( pos.x(), pos.y(), 1, 1 ), textFlags, \
pp->label() ); + float xStep = 0.5*bestRect.width();
+ float yStep = 0.5*bestRect.height();
+ float maxCost = 0.05 * bestRect.width() * bestRect.height();
+ float bestCost = d->rectCost( bestRect );
+ float lastCost = bestCost;
- float r = sqrt( (float)(ix-ix0)*(ix-ix0) + (iy-iy0)*(iy-iy0) );
- float cost = d->rectCost( labelRect ) + 0.1*r;
+ while ( bestCost > maxCost ) {
+ //Displace the label up and down, to compute vertical cost gradient
+ QRectF upRect = bestRect;
+ upRect.moveTop( upRect.top() + yStep );
+ float upCost = d->rectCost( upRect );
+ QRectF downRect = bestRect;
+ downRect.moveTop( downRect.top() - yStep );
+ float downCost = d->rectCost( downRect );
- if ( cost < bestCost ) {
- bestRect = labelRect;
- bestCost = cost;
- rbest = r;
- }
+ //Displace the label left and right, to compute horizontal cost gradient
+ QRectF rightRect = bestRect;
+ rightRect.moveLeft( rightRect.left() + xStep );
+ float rightCost = d->rectCost( rightRect );
+ QRectF leftRect = bestRect;
+ leftRect.moveLeft( leftRect.left() - xStep );
+ float leftCost = d->rectCost( leftRect );
+
+ //If any of the displacements improves the cost, adopt the new position
+ if ( upCost <= downCost && upCost < bestCost ) {
+ bestRect.moveTop( upRect.top() );
+ bestCost = upCost;
+ } else if ( downCost < upCost && downCost < bestCost ) {
+ bestRect.moveTop( downRect.top() );
+ bestCost = downCost;
}
+ if ( rightCost <= leftCost && rightCost < bestCost ) {
+ bestRect.moveLeft( rightRect.left() );
+ bestCost = rightCost;
+ } else if ( leftCost < rightCost && leftCost < bestCost ) {
+ bestRect.moveLeft( leftRect.left() );
+ bestCost = leftCost;
+ }
+
+ //If no improvement was found, adopt bestRect as the minimum cost
+ //(even if it exceeds maxCost)
+ if ( bestCost == lastCost ) {
+ break;
+ }
+
+ lastCost = bestCost;
}
- if ( ! bestRect.isNull() ) {
- painter->drawText( bestRect, textFlags, pp->label() );
+ painter->drawText( bestRect, textFlags, pp->label() );
- //Is a line needed to connect the label to the point?
- if ( rbest > 2.0 ) {
- //Draw a rectangle around the label
- painter->setBrush( QBrush() );
- //QPen pen = painter->pen();
- //pen.setStyle( Qt::DotLine );
- //painter->setPen( pen );
- painter->drawRoundRect( bestRect );
-
- //Now connect the label to the point with a line.
- //The line is drawn from the center of the near edge of the rectangle
- float xline = bestRect.center().x();
- if ( bestRect.left() > pos.x() )
- xline = bestRect.left();
- if ( bestRect.right() < pos.x() )
- xline = bestRect.right();
-
- float yline = bestRect.center().y();
- if ( bestRect.top() > pos.y() )
- yline = bestRect.top();
- if ( bestRect.bottom() < pos.y() )
- yline = bestRect.bottom();
-
- painter->drawLine( QPointF( xline, yline ), pos );
- }
-
- //Mask the label's rectangle so other labels won't overlap it.
- maskRect( bestRect );
+ //Is a line needed to connect the label to the point?
+ float deltax = pos.x() - bestRect.center().x();
+ float deltay = pos.y() - bestRect.center().y();
+ float rbest = sqrt( deltax*deltax + deltay*deltay );
+ if ( rbest > 20.0 ) {
+ //Draw a rectangle around the label
+ painter->setBrush( QBrush() );
+ //QPen pen = painter->pen();
+ //pen.setStyle( Qt::DotLine );
+ //painter->setPen( pen );
+ painter->drawRoundRect( bestRect );
+
+ //Now connect the label to the point with a line.
+ //The line is drawn from the center of the near edge of the rectangle
+ float xline = bestRect.center().x();
+ if ( bestRect.left() > pos.x() )
+ xline = bestRect.left();
+ if ( bestRect.right() < pos.x() )
+ xline = bestRect.right();
+
+ float yline = bestRect.center().y();
+ if ( bestRect.top() > pos.y() )
+ yline = bestRect.top();
+ if ( bestRect.bottom() < pos.y() )
+ yline = bestRect.bottom();
+
+ painter->drawLine( QPointF( xline, yline ), pos );
}
+
+ //Mask the label's rectangle so other labels won't overlap it.
+ maskRect( bestRect );
}
float KPlotWidget::Private::rectCost( const QRectF &r ) const
{
- int ix1 = int( 100.0 * ( r.x() - pixRect.x() ) / pixRect.width() );
- int ix2 = int( 100.0 * ( r.right() - pixRect.x() ) / pixRect.width() );
- int iy1 = int( 100.0 * ( r.y() - pixRect.y() ) / pixRect.height() );
- int iy2 = int( 100.0 * ( r.bottom() - pixRect.y() ) / pixRect.height() );
- float cost = 0.0;
-
- for ( int ix=ix1; ix<ix2; ++ix ) {
- for ( int iy=iy1; iy<iy2; ++iy ) {
- if ( ix >= 0 && ix < 100 && iy >= 0 && iy < 100 ) {
- cost += plotMask[ix][iy];
- } else {
- cost += 100.;
- }
+ if ( ! plotMask.rect().contains( r.toRect() ) ) {
+ return 10000.;
+ }
+
+ //Compute sum of mask values in the rect r
+ QImage subMask = plotMask.copy( r.toRect() );
+ int cost = 0;
+ for ( int ix=0; ix<subMask.width(); ++ix ) {
+ for ( int iy=0; iy<subMask.height(); ++iy ) {
+ cost += QColor( subMask.pixel( ix, iy ) ).red();
}
}
-
- return cost;
+
+ return float(cost);
}
void KPlotWidget::paintEvent( QPaintEvent *e ) {
@@ -559,22 +603,9 @@
foreach( KPlotObject *po, d->objectList )
po->draw( &p, this );
- //DEBUG_MASK
- /*
- p.setPen( Qt::magenta );
- p.setBrush( Qt::magenta );
- for ( int ix=0; ix<100; ++ix ) {
- for ( int iy=0; iy<100; ++iy ) {
- if ( PlotMask[ix][iy] > 0.0 ) {
- double x = d->pixRect.x() + double(ix*d->pixRect.width())/100.;
- double y = d->pixRect.y() + double(iy*d->pixRect.height())/100.;
+//DEBUG: Draw the plot mask
+// p.drawImage( 0, 0, d->plotMask );
- p.drawRect( QRectF(x-1, y-1, 2, 2 ) );
- }
- }
- }
- */
-
p.setClipping( false );
drawAxes( &p );
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic