From 03589b92ae05f59acd60f43414858a6fe586be0b Mon Sep 17 00:00:00 2001 From: Jason Harris Date: Sun, 29 Oct 2006 03:25:34 +0000 Subject: [PATCH] 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@kde.org svn path=/trunk/KDE/kdeedu/libkdeedu/; revision=599914 --- kdeeduplot/kplotobject.cpp | 60 +++++----- kdeeduplot/kplotwidget.cpp | 159 ++++++++++++++++++++++++++- kdeeduplot/kplotwidget.h | 64 +++++++++++ kdeeduplot/tests/testplot_widget.cpp | 20 ++-- 4 files changed, 259 insertions(+), 44 deletions(-) diff --git a/kdeeduplot/kplotobject.cpp b/kdeeduplot/kplotobject.cpp index c9d1b97..418fc61 100644 --- a/kdeeduplot/kplotobject.cpp +++ b/kdeeduplot/kplotobject.cpp @@ -23,10 +23,9 @@ #include "kplotobject.h" #include "kplotwidget.h" -KPlotPoint::KPlotPoint() { - X = 0.0; - Y = 0.0; - Label = QString(); +KPlotPoint::KPlotPoint() + : X(0), Y(0), Label(QString()), BarWidth(0.0) +{ } KPlotPoint::KPlotPoint( double x, double y, const QString &label, double barWidth ) @@ -106,7 +105,9 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { QPointF sp1 = pw->toScreen( p1 ); QPointF sp2 = pw->toScreen( p2 ); - painter->drawRect( QRectF( sp1.x(), sp1.y(), sp2.x()-sp1.x(), sp2.y()-sp1.y() ) ); + QRectF barRect = QRectF( sp1.x(), sp1.y(), sp2.x()-sp1.x(), sp2.y()-sp1.y() ).normalized(); + painter->drawRect( barRect ); + pw->maskRect( barRect, 0.25 ); } } @@ -122,6 +123,7 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { if ( ! Previous.isNull() ) { painter->drawLine( Previous, q ); + pw->maskAlongLine( Previous, q ); } Previous = q; @@ -134,10 +136,13 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { foreach( KPlotPoint *pp, pList ) { //q is the position of the point in screen pixel coordinates QPointF q = pw->toScreen( pp->position() ); - double x1 = q.x() - 0.5*size(); - double y1 = q.y() - 0.5*size(); - QRectF qr = QRectF( x1, y1, size(), size() ); - + double x1 = q.x() - size(); + double y1 = q.y() - size(); + QRectF qr = QRectF( x1, y1, 2*size(), 2*size() ); + + //Mask out this rect in the plot for label avoidance + pw->maskRect( qr, 2.0 ); + painter->setPen( pen() ); painter->setBrush( brush() ); @@ -153,7 +158,9 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { case TRIANGLE: { QPolygonF tri; - tri << QPointF( x1, y1 ) << QPointF( q.x(), y1-size() ) << QPointF( x1+size(), y1 ); + tri << QPointF( q.x() - size(), q.y() + size() ) + << QPointF( q.x(), q.y() - size() ) + << QPointF( q.x() + size(), q.y() + size() ); painter->drawPolygon( tri ); break; } @@ -165,11 +172,11 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { case PENTAGON: { QPolygonF pent; - pent << QPointF( q.x(), q.y() + size() ) - << QPointF( q.x() + size(), q.y() + 0.309*size() ) - << QPointF( q.x() + 0.588*size(), q.y() - size() ) - << QPointF( q.x() - 0.588*size(), q.y() - size() ) - << QPointF( q.x() - size(), q.y() + 0.309*size() ); + pent << QPointF( q.x(), q.y() - size() ) + << QPointF( q.x() + size(), q.y() - 0.309*size() ) + << QPointF( q.x() + 0.588*size(), q.y() + size() ) + << QPointF( q.x() - 0.588*size(), q.y() + size() ) + << QPointF( q.x() - size(), q.y() - 0.309*size() ); painter->drawPolygon( pent ); break; } @@ -199,16 +206,16 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { case STAR: { QPolygonF star; - star << QPointF( q.x(), q.y() + size() ) - << QPointF( q.x() + 0.2245*size(), q.y() + 0.309*size() ) - << QPointF( q.x() + size(), q.y() + 0.309*size() ) - << QPointF( q.x() + 0.363*size(), q.y() - 0.118*size() ) - << QPointF( q.x() + 0.588*size(), q.y() - size() ) - << QPointF( q.x(), q.y() - 0.382*size() ) - << QPointF( q.x() - 0.588*size(), q.y() - size() ) - << QPointF( q.x() - 0.363*size(), q.y() - 0.118*size() ) - << QPointF( q.x() - size(), q.y() + 0.309*size() ) - << QPointF( q.x() - 0.2245*size(), q.y() + 0.309*size() ); + star << QPointF( q.x(), q.y() - size() ) + << QPointF( q.x() + 0.2245*size(), q.y() - 0.309*size() ) + << QPointF( q.x() + size(), q.y() - 0.309*size() ) + << QPointF( q.x() + 0.363*size(), q.y() + 0.118*size() ) + << QPointF( q.x() + 0.588*size(), q.y() + size() ) + << QPointF( q.x(), q.y() + 0.382*size() ) + << QPointF( q.x() - 0.588*size(), q.y() + size() ) + << QPointF( q.x() - 0.363*size(), q.y() + 0.118*size() ) + << QPointF( q.x() - size(), q.y() - 0.309*size() ) + << QPointF( q.x() - 0.2245*size(), q.y() - 0.309*size() ); painter->drawPolygon( star ); break; } @@ -220,12 +227,11 @@ void KPlotObject::draw( QPainter *painter, KPlotWidget *pw ) { } //Draw labels - //FIXME: implement non-collision labels painter->setPen( labelPen() ); foreach ( KPlotPoint *pp, pList ) { if ( ! pp->label().isEmpty() ) { - painter->drawText( pw->toScreen( pp->position() ), pp->label() ); + pw->placeLabel( painter, pp ); } } diff --git a/kdeeduplot/kplotwidget.cpp b/kdeeduplot/kplotwidget.cpp index 2a54e50..62ab5af 100644 --- a/kdeeduplot/kplotwidget.cpp +++ b/kdeeduplot/kplotwidget.cpp @@ -15,6 +15,7 @@ * * ***************************************************************************/ +#include #include #include @@ -160,6 +161,25 @@ void KPlotWidget::clearObjectList() { update(); } +void KPlotWidget::resetPlotMask() { + for (int ix=0; ix<100; ++ix ) + for ( int iy=0; iy<100; ++iy ) + PlotMask[ix][iy] = 0.0; +} + +void KPlotWidget::resetPlot() { + clearObjectList(); + clearSecondaryLimits(); + setLimits(0.0, 1.0, 0.0, 1.0); + axis(KPlotWidget::RightAxis)->setShowTickLabels( false ); + axis(KPlotWidget::TopAxis)->setShowTickLabels( false ); + axis(KPlotWidget::LeftAxis)->setLabel( QString() ); + axis(KPlotWidget::BottomAxis)->setLabel( QString() ); + axis(KPlotWidget::RightAxis)->setLabel( QString() ); + axis(KPlotWidget::TopAxis)->setLabel( QString() ); + resetPlotMask(); +} + void KPlotWidget::replaceObject( int i, KPlotObject *o ) { // skip null pointers if ( !o ) return; @@ -234,6 +254,10 @@ void KPlotWidget::setPixRect() { int newHeight = contentsRect().height() - topPadding() - bottomPadding(); // PixRect starts at (0,0) because we will translate by leftPadding(), topPadding() PixRect = QRect( 0, 0, newWidth, newHeight ); + for ( int i=0; i<100; ++i ) { + px[i] = double(i*PixRect.width())/100.0 + double(PixRect.x()); + py[i] = double(i*PixRect.height())/100.0 + double(PixRect.y()); + } } QPointF KPlotWidget::toScreen( const QPointF& p ) const { @@ -242,6 +266,101 @@ QPointF KPlotWidget::toScreen( const QPointF& p ) const { 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() - PixRect.x())/PixRect.width() ); + int iy1 = int( 100.0*(r.y() - PixRect.y())/PixRect.height() ); + if ( ix1 < 0 ) ix1 = 0; + if ( iy1 < 0 ) iy1 = 0; + int ix2 = int( 100.0*(r.right() - PixRect.x())/PixRect.width() ) + 2; + int iy2 = int( 100.0*(r.bottom() - PixRect.y())/PixRect.height() ) + 2; + if ( ix1 > 99 ) ix1 = 99; + if ( iy1 > 99 ) iy1 = 99; + + for ( int ix=ix1; ix x2 ) { + x1 = p2.x(); + x2 = p1.x(); + } + for ( double x=x1; x= 0 && ix < 100 && iy >= 0 && iy < 100 ) + PlotMask[ix][iy] += value; + + } +} + +void KPlotWidget::placeLabel( QPainter *painter, KPlotPoint *pp ) { + int textFlags = Qt::TextSingleLine | Qt::AlignLeft | Qt::AlignTop; + + float bestCost = 1.0e7; + QPointF pos = toScreen( pp->position() ); + QRectF bestRect; + int ix0 = int( 100.0*( pos.x() - PixRect.x() )/PixRect.width() ); + int iy0 = int( 100.0*( pos.y() - PixRect.y() )/PixRect.height() ); + + for ( int ix=ix0-20; ix= 0 && ix < 100 ) && ( iy >= 0 && iy < 100 ) ) { + QRectF labelRect = painter->boundingRect( QRectF( px[ix], py[iy], 1, 1 ), textFlags, pp->label() ); + + float r = sqrt( (ix-ix0)*(ix-ix0) + (iy-iy0)*(iy-iy0) ); + float cost = rectCost( labelRect ) + 0.1*r; + + if ( cost < bestCost ) { + bestRect = labelRect; + bestCost = cost; + } + } + } + } + + painter->drawText( bestRect, textFlags, pp->label() ); + + //DEBUG_LABEL_RECT + //painter->setBrush( QBrush() ); + //painter->drawRect( bestRect ); + + //Mask the label's rectangle so other labels won't overlap it. + maskRect( bestRect ); +} + +float KPlotWidget::rectCost ( const QRectF &r ) { + 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= 0 && ix < 100 && iy >= 0 && iy < 100 ) { + cost += PlotMask[ix][iy]; + } else { + cost += 100.; + } + } + } + + return cost; +} + void KPlotWidget::paintEvent( QPaintEvent *e ) { // let QFrame draw its default stuff (like the frame) QFrame::paintEvent( e ); @@ -256,9 +375,27 @@ void KPlotWidget::paintEvent( QPaintEvent *e ) { p.setClipRect( PixRect ); p.setClipping( true ); + resetPlotMask(); + foreach( KPlotObject *po, 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 = PixRect.x() + double(ix*PixRect.width())/100.; + double y = PixRect.y() + double(iy*PixRect.height())/100.; + + p.drawRect( QRectF(x-1, y-1, 2, 2 ) ); + } + } + } + */ + p.setClipping( false ); drawAxes( &p ); @@ -372,6 +509,18 @@ void KPlotWidget::drawAxes( QPainter *p ) { } } //End of LeftAxis + //Prepare for top and right axes; we may need the secondary data rect + double x0 = x(); + double y0 = y(); + double dw = dataWidth(); + double dh = dataHeight(); + if ( secondaryDataRect().isValid() ) { + x0 = secondaryDataRect().x(); + y0 = secondaryDataRect().y(); + dw = secondaryDataRect().width(); + dh = secondaryDataRect().height(); + } + /*** TopAxis ***/ a = axis(TopAxis); if (a->isVisible()) { @@ -380,13 +529,13 @@ void KPlotWidget::drawAxes( QPainter *p ) { // Draw major tickmarks foreach( double xx, a->majorTickMarks() ) { - double px = PixRect.width() * (xx - x()) / dataWidth(); + double px = PixRect.width() * (xx - x0) / dw; if ( px > 0 && px < PixRect.width() ) { p->drawLine( QPointF( px, TICKOFFSET ), QPointF( px, double(BIGTICKSIZE + TICKOFFSET)) ); //Draw ticklabel if ( a->showTickLabels() ) { - QRect r( int(px) - BIGTICKSIZE, -1*BIGTICKSIZE, 2*BIGTICKSIZE, BIGTICKSIZE ); + QRect r( int(px) - BIGTICKSIZE, -1.5*BIGTICKSIZE, 2*BIGTICKSIZE, BIGTICKSIZE ); p->drawText( r, Qt::AlignCenter | Qt::TextDontClip, a->tickLabel( xx ) ); } } @@ -394,7 +543,7 @@ void KPlotWidget::drawAxes( QPainter *p ) { // Draw minor tickmarks foreach ( double xx, a->minorTickMarks() ) { - double px = PixRect.width() * (xx - x()) / dataWidth(); + double px = PixRect.width() * (xx - x0) / dw; if ( px > 0 && px < PixRect.width() ) { p->drawLine( QPointF( px, TICKOFFSET ), QPointF( px, double(SMALLTICKSIZE + TICKOFFSET)) ); } @@ -415,7 +564,7 @@ void KPlotWidget::drawAxes( QPainter *p ) { // Draw major tickmarks foreach( double yy, a->majorTickMarks() ) { - double py = PixRect.height() * ( 1.0 - (yy - y()) / dataHeight() ); + double py = PixRect.height() * ( 1.0 - (yy - y0) / dh ); if ( py > 0 && py < PixRect.height() ) { p->drawLine( QPointF( double(PixRect.width() - TICKOFFSET), py ), QPointF( double(PixRect.width() - TICKOFFSET - BIGTICKSIZE), py ) ); @@ -430,7 +579,7 @@ void KPlotWidget::drawAxes( QPainter *p ) { // Draw minor tickmarks foreach ( double yy, a->minorTickMarks() ) { - double py = PixRect.height() * ( 1.0 - (yy - y()) / dataHeight() ); + double py = PixRect.height() * ( 1.0 - (yy - y0) / dh ); if ( py > 0 && py < PixRect.height() ) { p->drawLine( QPointF( double(PixRect.width() - 0.0), py ), QPointF( double(PixRect.width() - 0.0 - SMALLTICKSIZE), py ) ); diff --git a/kdeeduplot/kplotwidget.h b/kdeeduplot/kplotwidget.h index acda935..45a2035 100644 --- a/kdeeduplot/kplotwidget.h +++ b/kdeeduplot/kplotwidget.h @@ -181,6 +181,16 @@ public: */ void clearObjectList(); + /** + * Reset the PlotMask so that all regions are empty + */ + void resetPlotMask(); + + /** + * Clear the object list, reset the data limits, and remove axis labels + */ + void resetPlot(); + /** * Replace an item in the KPlotObject list. * @param i the index of th item to be replaced @@ -303,6 +313,46 @@ public: */ QPointF toScreen( const QPointF& p ) const; + /** + * Indicate that object labels should not occupy the given + * rectangle in the plot. The rectangle is in pixel coordinates. + * + * @note You should not normally call this function directly. + * It is called by KPlotObject when points, bars and labels are drawn. + * @param r the rectangle defining the region in the plot that + * text labels should avoid (in pixel coordinates) + * @param value Allows you to determine how strongly the rectangle + * should be avoided. Larger values are avoided more strongly. + */ + void maskRect( const QRectF &r, float value=1.0 ); + + /** + * Indicate that object labels should not be placed over the line + * joining the two given points (in pixel coordinates). + * + * @note You should not normally call this function directly. + * It is called by KPlotObject when lines are drawn in the plot. + * @param p1 the starting point for the line + * @param p2 the ending point for the line + * @param value Allows you to determine how strongly the line + * should be avoided. Larger values are avoided more strongly. + */ + void maskAlongLine( const QPointF &p1, const QPointF &p2, float value=1.0 ); + + /** + * Place an object label optimally in the plot. This function will + * attempt to place the label as close as it can to the point to which + * the label belongs, while avoiding overlap with regions of the plot + * that have been masked. + * + * @note You should not normally call this function directly. + * It is called internally in KPlotObject::draw(). + * + * @param painter Pointer to the painter on which to draw the label + * @param pp pointer to the KPlotPoint whose label is to be drawn. + */ + void placeLabel( QPainter *painter, KPlotPoint *pp ); + /** * Retrieve the pointer to the axis of type @p a. * @sa Axis @@ -360,6 +410,16 @@ protected: */ QList pointsUnderPoint( const QPoint& p ) const; + /** + * @return a value indicating how well the given rectangle is + * avoiding masked regions in the plot. A higher returned value + * indicates that the rectangle is intersecting a larger portion + * of the masked region, or a portion of the masked region which + * is weighted higher. + * @param r The rectangle to be tested + */ + float rectCost( const QRectF &r ); + /** * Limits of the plot area in pixel units */ @@ -384,6 +444,10 @@ protected: bool ShowGrid, ShowObjectToolTips, UseAntialias; //padding int LeftPadding, RightPadding, TopPadding, BottomPadding; + + //Grid of bools to mask "used" regions of the plot + float PlotMask[100][100]; + double px[100], py[100]; }; #endif diff --git a/kdeeduplot/tests/testplot_widget.cpp b/kdeeduplot/tests/testplot_widget.cpp index de98a53..7de958e 100644 --- a/kdeeduplot/tests/testplot_widget.cpp +++ b/kdeeduplot/tests/testplot_widget.cpp @@ -23,6 +23,7 @@ #include "../kplotwidget.h" #include "../kplotobject.h" +#include "../kplotaxis.h" #include "testplot_widget.h" TestPlot::TestPlot( QWidget *p ) : KMainWindow( p ), po1(0), po2(0) { @@ -39,6 +40,7 @@ TestPlot::TestPlot( QWidget *p ) : KMainWindow( p ), po1(0), po2(0) { plot = new KPlotWidget( w ); plot->setMinimumSize( 400,400 ); + plot->setAntialias( true ); vlay->addWidget( PlotSelector ); vlay->addWidget( plot ); @@ -49,12 +51,12 @@ TestPlot::TestPlot( QWidget *p ) : KMainWindow( p ), po1(0), po2(0) { } void TestPlot::slotSelectPlot( int n ) { + plot->resetPlot(); + switch ( n ) { case 0: //Points plot { plot->setLimits( -6.0, 11.0, -10.0, 110.0 ); - plot->clearSecondaryLimits(); - plot->clearObjectList(); po1 = new KPlotObject( Qt::white, KPlotObject::POINTS, 4, KPlotObject::ASTERISK ); po2 = new KPlotObject( Qt::green, KPlotObject::POINTS, 4, KPlotObject::TRIANGLE ); @@ -75,8 +77,10 @@ void TestPlot::slotSelectPlot( int n ) { { plot->setLimits( -0.1, 6.38, -1.1, 1.1 ); plot->setSecondaryLimits( -5.73, 365.55, -1.1, 1.1 ); - plot->clearObjectList(); - + plot->axis(KPlotWidget::TopAxis)->setShowTickLabels( true ); + plot->axis(KPlotWidget::BottomAxis)->setLabel(i18n("Angle [radians]")); + plot->axis(KPlotWidget::TopAxis)->setLabel(i18n("Angle [degrees]")); + po1 = new KPlotObject( Qt::red, KPlotObject::LINES, 2 ); po2 = new KPlotObject( Qt::cyan, KPlotObject::LINES, 2 ); @@ -95,8 +99,6 @@ void TestPlot::slotSelectPlot( int n ) { case 2: //Bars plot { plot->setLimits( -7.0, 7.0, -5.0, 105.0 ); - plot->clearSecondaryLimits(); - plot->clearObjectList(); po1 = new KPlotObject( Qt::white, KPlotObject::BARS, 2 ); po1->setBarBrush( QBrush(Qt::green, Qt::Dense4Pattern) ); @@ -114,8 +116,6 @@ void TestPlot::slotSelectPlot( int n ) { case 3: //Points plot with labels { plot->setLimits( -1.1, 1.1, -1.1, 1.1 ); - plot->clearSecondaryLimits(); - plot->clearObjectList(); po1 = new KPlotObject( Qt::yellow, KPlotObject::POINTS, 10, KPlotObject::STAR ); po1->setLabelPen( QPen(Qt::green) ); @@ -138,8 +138,6 @@ void TestPlot::slotSelectPlot( int n ) { case 4: //Points, Lines and Bars plot { plot->setLimits( -2.1, 2.1, -0.1, 4.1 ); - plot->clearSecondaryLimits(); - plot->clearObjectList(); po1 = new KPlotObject( Qt::white, KPlotObject::POINTS, 10, KPlotObject::PENTAGON ); @@ -167,8 +165,6 @@ void TestPlot::slotSelectPlot( int n ) { case 5: //Points, Lines and Bars plot with labels { plot->setLimits( -2.1, 2.1, -0.1, 4.1 ); - plot->clearSecondaryLimits(); - plot->clearObjectList(); po1 = new KPlotObject( Qt::white, KPlotObject::POINTS, 10, KPlotObject::PENTAGON ); -- 2.47.3