qwt_scale_engine.cpp

Go to the documentation of this file.

/* -*- mode: C++ ; c-file-style: "stroustrup" -*- *****************************
 * Qwt Widget Library
 * Copyright (C) 1997   Josef Wilgen
 * Copyright (C) 2002   Uwe Rathmann
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the Qwt License, Version 1.0
 *****************************************************************************/

#include "qwt_scale_engine.h"
#include "qwt_math.h"
#include "qwt_scale_map.h"
#include <qalgorithms.h>
#include <qmath.h>
#include <float.h>
#include <limits>

#if QT_VERSION < 0x040601
#define qFabs(x) ::fabs(x)
#define qExp(x) ::exp(x)
#endif

static inline double qwtLog( double base, double value )
{
    return log( value ) / log( base );
}

static inline QwtInterval qwtLogInterval( double base, const QwtInterval &interval )
{
    return QwtInterval( qwtLog( base, interval.minValue() ),
            qwtLog( base, interval.maxValue() ) );
}

static inline QwtInterval qwtPowInterval( double base, const QwtInterval &interval ) 
{
    return QwtInterval( qPow( base, interval.minValue() ),
            qPow( base, interval.maxValue() ) );
}


#if 1

// this version often doesn't find the best ticks: f.e for 15: 5, 10
static double qwtStepSize( double intervalSize, int maxSteps, uint base )
{
    const double minStep = 
        QwtScaleArithmetic::divideInterval( intervalSize, maxSteps, base );

    if ( minStep != 0.0 )
    {
        // # ticks per interval
        const int numTicks = qCeil( qAbs( intervalSize / minStep ) ) - 1;

        // Do the minor steps fit into the interval?
        if ( qwtFuzzyCompare( ( numTicks +  1 ) * qAbs( minStep ),
            qAbs( intervalSize ), intervalSize ) > 0 )
        {
            // The minor steps doesn't fit into the interval
            return 0.5 * intervalSize;
        }
    }

    return minStep;
}

#else

static double qwtStepSize( double intervalSize, int maxSteps, uint base )
{
    if ( maxSteps <= 0 )
        return 0.0;

    if ( maxSteps > 2 )
    {
        for ( int numSteps = maxSteps; numSteps > 1; numSteps-- )
        {
            const double stepSize = intervalSize / numSteps;

            const double p = ::floor( ::log( stepSize ) / ::log( base ) );
            const double fraction = qPow( base, p );

            for ( uint n = base; n > 1; n /= 2 )
            {
                if ( qFuzzyCompare( stepSize, n * fraction ) )
                    return stepSize;

                if ( n == 3 && ( base % 2 ) == 0 )
                {
                    if ( qFuzzyCompare( stepSize, 2 * fraction ) )
                        return stepSize;
                }
            }
        }
    }

    return intervalSize * 0.5;
}

#endif

static const double _eps = 1.0e-6;

double QwtScaleArithmetic::ceilEps( double value,
    double intervalSize )
{
    const double eps = _eps * intervalSize;

    value = ( value - eps ) / intervalSize;
    return ::ceil( value ) * intervalSize;
}

double QwtScaleArithmetic::floorEps( double value, double intervalSize )
{
    const double eps = _eps * intervalSize;

    value = ( value + eps ) / intervalSize;
    return ::floor( value ) * intervalSize;
}

double QwtScaleArithmetic::divideEps( double intervalSize, double numSteps )
{
    if ( numSteps == 0.0 || intervalSize == 0.0 )
        return 0.0;

    return ( intervalSize - ( _eps * intervalSize ) ) / numSteps;
}

double QwtScaleArithmetic::divideInterval( 
    double intervalSize, int numSteps, uint base ) 
{
    if ( numSteps <= 0 )
        return 0.0;

    const double v = QwtScaleArithmetic::divideEps( intervalSize, numSteps );
    if ( v == 0.0 )
        return 0.0;

    const double lx = qwtLog( base, qFabs( v ) );
    const double p = ::floor( lx );

    const double fraction = qPow( base, lx - p );

    uint n = base;
    while ( ( n > 1 ) && ( fraction <= n / 2 ) )
        n /= 2;

    double stepSize = n * qPow( base, p );
    if ( v < 0 )
        stepSize = -stepSize;

    return stepSize;
}

class QwtScaleEngine::PrivateData
{
public:
    PrivateData():
        attributes( QwtScaleEngine::NoAttribute ),
        lowerMargin( 0.0 ),
        upperMargin( 0.0 ),
        referenceValue( 0.0 ),
        base( 10 ),
        transform( NULL )
    {
    }

    ~PrivateData()
    {
        delete transform;
    }

    QwtScaleEngine::Attributes attributes;

    double lowerMargin;
    double upperMargin;

    double referenceValue;

    uint base;

    QwtTransform* transform;
};

QwtScaleEngine::QwtScaleEngine( uint base )
{
    d_data = new PrivateData;
    setBase( base );
}


QwtScaleEngine::~QwtScaleEngine ()
{
    delete d_data;
}

void QwtScaleEngine::setTransformation( QwtTransform *transform )
{
    if ( transform != d_data->transform )
    {
        delete d_data->transform;
        d_data->transform = transform;
    }
}

QwtTransform *QwtScaleEngine::transformation() const
{
    QwtTransform *transform = NULL;
    if ( d_data->transform )
        transform = d_data->transform->copy();

    return transform;
}

double QwtScaleEngine::lowerMargin() const
{
    return d_data->lowerMargin;
}

double QwtScaleEngine::upperMargin() const
{
    return d_data->upperMargin;
}

void QwtScaleEngine::setMargins( double lower, double upper )
{
    d_data->lowerMargin = qMax( lower, 0.0 );
    d_data->upperMargin = qMax( upper, 0.0 );
}

double QwtScaleEngine::divideInterval(
    double intervalSize, int numSteps ) const
{
    return QwtScaleArithmetic::divideInterval( 
        intervalSize, numSteps, d_data->base );
}

bool QwtScaleEngine::contains(
    const QwtInterval &interval, double value ) const
{
    if ( !interval.isValid() )
        return false;

    if ( qwtFuzzyCompare( value, interval.minValue(), interval.width() ) < 0 )
        return false;

    if ( qwtFuzzyCompare( value, interval.maxValue(), interval.width() ) > 0 )
        return false;

    return true;
}

QList<double> QwtScaleEngine::strip( const QList<double>& ticks,
    const QwtInterval &interval ) const
{
    if ( !interval.isValid() || ticks.count() == 0 )
        return QList<double>();

    if ( contains( interval, ticks.first() )
        && contains( interval, ticks.last() ) )
    {
        return ticks;
    }

    QList<double> strippedTicks;
    for ( int i = 0; i < ticks.count(); i++ )
    {
        if ( contains( interval, ticks[i] ) )
            strippedTicks += ticks[i];
    }
    return strippedTicks;
}

QwtInterval QwtScaleEngine::buildInterval( double value ) const
{
    const double delta = ( value == 0.0 ) ? 0.5 : qAbs( 0.5 * value );

    if ( DBL_MAX - delta < value )
        return QwtInterval( DBL_MAX - delta, DBL_MAX );

    if ( -DBL_MAX + delta > value )
        return QwtInterval( -DBL_MAX, -DBL_MAX + delta );

    return QwtInterval( value - delta, value + delta );
}

void QwtScaleEngine::setAttribute( Attribute attribute, bool on )
{
    if ( on )
        d_data->attributes |= attribute;
    else
        d_data->attributes &= ~attribute;
}

bool QwtScaleEngine::testAttribute( Attribute attribute ) const
{
    return ( d_data->attributes & attribute );
}

void QwtScaleEngine::setAttributes( Attributes attributes )
{
    d_data->attributes = attributes;
}

QwtScaleEngine::Attributes QwtScaleEngine::attributes() const
{
    return d_data->attributes;
}

void QwtScaleEngine::setReference( double r )
{
    d_data->referenceValue = r;
}

double QwtScaleEngine::reference() const
{
    return d_data->referenceValue;
}

void QwtScaleEngine::setBase( uint base )
{ 
    d_data->base = qMax( base, 2U );
}

uint QwtScaleEngine::base() const
{
    return d_data->base;
}

QwtLinearScaleEngine::QwtLinearScaleEngine( uint base ):
    QwtScaleEngine( base )
{
}

QwtLinearScaleEngine::~QwtLinearScaleEngine()
{
}

void QwtLinearScaleEngine::autoScale( int maxNumSteps,
    double &x1, double &x2, double &stepSize ) const
{
    QwtInterval interval( x1, x2 );
    interval = interval.normalized();

    interval.setMinValue( interval.minValue() - lowerMargin() );
    interval.setMaxValue( interval.maxValue() + upperMargin() );

    if ( testAttribute( QwtScaleEngine::Symmetric ) )
        interval = interval.symmetrize( reference() );

    if ( testAttribute( QwtScaleEngine::IncludeReference ) )
        interval = interval.extend( reference() );

    if ( interval.width() == 0.0 )
        interval = buildInterval( interval.minValue() );

    stepSize = QwtScaleArithmetic::divideInterval( 
        interval.width(), qMax( maxNumSteps, 1 ), base() );

    if ( !testAttribute( QwtScaleEngine::Floating ) )
        interval = align( interval, stepSize );

    x1 = interval.minValue();
    x2 = interval.maxValue();

    if ( testAttribute( QwtScaleEngine::Inverted ) )
    {
        qSwap( x1, x2 );
        stepSize = -stepSize;
    }
}

QwtScaleDiv QwtLinearScaleEngine::divideScale( double x1, double x2,
    int maxMajorSteps, int maxMinorSteps, double stepSize ) const
{
    QwtInterval interval = QwtInterval( x1, x2 ).normalized();

    if ( interval.widthL() > std::numeric_limits<double>::max() )
    {
        qWarning() << "QwtLinearScaleEngine::divideScale: overflow";
        return QwtScaleDiv();
    }

    if ( interval.width() <= 0 )
        return QwtScaleDiv();

    stepSize = qAbs( stepSize );
    if ( stepSize == 0.0 )
    {
        if ( maxMajorSteps < 1 )
            maxMajorSteps = 1;

        stepSize = QwtScaleArithmetic::divideInterval( 
            interval.width(), maxMajorSteps, base() );
    }

    QwtScaleDiv scaleDiv;

    if ( stepSize != 0.0 )
    {
        QList<double> ticks[QwtScaleDiv::NTickTypes];
        buildTicks( interval, stepSize, maxMinorSteps, ticks );

        scaleDiv = QwtScaleDiv( interval, ticks );
    }

    if ( x1 > x2 )
        scaleDiv.invert();

    return scaleDiv;
}

void QwtLinearScaleEngine::buildTicks(
    const QwtInterval& interval, double stepSize, int maxMinorSteps,
    QList<double> ticks[QwtScaleDiv::NTickTypes] ) const
{
    const QwtInterval boundingInterval = align( interval, stepSize );

    ticks[QwtScaleDiv::MajorTick] =
        buildMajorTicks( boundingInterval, stepSize );

    if ( maxMinorSteps > 0 )
    {
        buildMinorTicks( ticks[QwtScaleDiv::MajorTick], maxMinorSteps, stepSize,
            ticks[QwtScaleDiv::MinorTick], ticks[QwtScaleDiv::MediumTick] );
    }

    for ( int i = 0; i < QwtScaleDiv::NTickTypes; i++ )
    {
        ticks[i] = strip( ticks[i], interval );

        // ticks very close to 0.0 are
        // explicitely set to 0.0

        for ( int j = 0; j < ticks[i].count(); j++ )
        {
            if ( qwtFuzzyCompare( ticks[i][j], 0.0, stepSize ) == 0 )
                ticks[i][j] = 0.0;
        }
    }
}

QList<double> QwtLinearScaleEngine::buildMajorTicks(
    const QwtInterval &interval, double stepSize ) const
{
    int numTicks = qRound( interval.width() / stepSize ) + 1;
    if ( numTicks > 10000 )
        numTicks = 10000;

    QList<double> ticks;
#if QT_VERSION >= 0x040700
    ticks.reserve( numTicks );
#endif

    ticks += interval.minValue();
    for ( int i = 1; i < numTicks - 1; i++ )
        ticks += interval.minValue() + i * stepSize;
    ticks += interval.maxValue();

    return ticks;
}

void QwtLinearScaleEngine::buildMinorTicks(
    const QList<double>& majorTicks,
    int maxMinorSteps, double stepSize,
    QList<double> &minorTicks,
    QList<double> &mediumTicks ) const
{
    double minStep = qwtStepSize( stepSize, maxMinorSteps, base() );
    if ( minStep == 0.0 )
        return;

    // # ticks per interval
    const int numTicks = qCeil( qAbs( stepSize / minStep ) ) - 1;

    int medIndex = -1;
    if ( numTicks % 2 )
        medIndex = numTicks / 2;

    // calculate minor ticks

    for ( int i = 0; i < majorTicks.count(); i++ )
    {
        double val = majorTicks[i];
        for ( int k = 0; k < numTicks; k++ )
        {
            val += minStep;

            double alignedValue = val;
            if ( qwtFuzzyCompare( val, 0.0, stepSize ) == 0 )
                alignedValue = 0.0;

            if ( k == medIndex )
                mediumTicks += alignedValue;
            else
                minorTicks += alignedValue;
        }
    }
}

QwtInterval QwtLinearScaleEngine::align(
    const QwtInterval &interval, double stepSize ) const
{
    double x1 = interval.minValue();
    double x2 = interval.maxValue();

    // when there is no rounding beside some effect, when 
    // calculating with doubles, we keep the original value

    const double eps = 0.000000000001; // since Qt 4.8: qFuzzyIsNull
    if ( -DBL_MAX + stepSize <= x1 )
    {
        const double x = QwtScaleArithmetic::floorEps( x1, stepSize );
        if ( qAbs(x) <= eps || !qFuzzyCompare( x1, x ) )
            x1 = x;
    }

    if ( DBL_MAX - stepSize >= x2 )
    {
        const double x = QwtScaleArithmetic::ceilEps( x2, stepSize );
        if ( qAbs(x) <= eps || !qFuzzyCompare( x2, x ) )
            x2 = x;
    }

    return QwtInterval( x1, x2 );
}

QwtLogScaleEngine::QwtLogScaleEngine( uint base ):
    QwtScaleEngine( base )
{
    setTransformation( new QwtLogTransform() );
}

QwtLogScaleEngine::~QwtLogScaleEngine()
{
}

void QwtLogScaleEngine::autoScale( int maxNumSteps,
    double &x1, double &x2, double &stepSize ) const
{
    if ( x1 > x2 )
        qSwap( x1, x2 );

    const double logBase = base();

    QwtInterval interval( x1 / qPow( logBase, lowerMargin() ),
        x2 * qPow( logBase, upperMargin() ) );

    if ( interval.maxValue() / interval.minValue() < logBase )
    {
        // scale width is less than one step -> try to build a linear scale

        QwtLinearScaleEngine linearScaler;
        linearScaler.setAttributes( attributes() );
        linearScaler.setReference( reference() );
        linearScaler.setMargins( lowerMargin(), upperMargin() );

        linearScaler.autoScale( maxNumSteps, x1, x2, stepSize );

        QwtInterval linearInterval = QwtInterval( x1, x2 ).normalized();
        linearInterval = linearInterval.limited( LOG_MIN, LOG_MAX );

        if ( linearInterval.maxValue() / linearInterval.minValue() < logBase )
        {
            stepSize = 0.0;
            return;
        }
    }

    double logRef = 1.0;
    if ( reference() > LOG_MIN / 2 )
        logRef = qMin( reference(), LOG_MAX / 2 );

    if ( testAttribute( QwtScaleEngine::Symmetric ) )
    {
        const double delta = qMax( interval.maxValue() / logRef,
            logRef / interval.minValue() );
        interval.setInterval( logRef / delta, logRef * delta );
    }

    if ( testAttribute( QwtScaleEngine::IncludeReference ) )
        interval = interval.extend( logRef );

    interval = interval.limited( LOG_MIN, LOG_MAX );

    if ( interval.width() == 0.0 )
        interval = buildInterval( interval.minValue() );

    stepSize = divideInterval( qwtLogInterval( logBase, interval ).width(), 
        qMax( maxNumSteps, 1 ) );
    if ( stepSize < 1.0 )
        stepSize = 1.0;

    if ( !testAttribute( QwtScaleEngine::Floating ) )
        interval = align( interval, stepSize );

    x1 = interval.minValue();
    x2 = interval.maxValue();

    if ( testAttribute( QwtScaleEngine::Inverted ) )
    {
        qSwap( x1, x2 );
        stepSize = -stepSize;
    }
}

QwtScaleDiv QwtLogScaleEngine::divideScale( double x1, double x2,
    int maxMajorSteps, int maxMinorSteps, double stepSize ) const
{
    QwtInterval interval = QwtInterval( x1, x2 ).normalized();
    interval = interval.limited( LOG_MIN, LOG_MAX );

    if ( interval.width() <= 0 )
        return QwtScaleDiv();

    const double logBase = base();

    if ( interval.maxValue() / interval.minValue() < logBase )
    {
        // scale width is less than one decade -> build linear scale

        QwtLinearScaleEngine linearScaler;
        linearScaler.setAttributes( attributes() );
        linearScaler.setReference( reference() );
        linearScaler.setMargins( lowerMargin(), upperMargin() );

        return linearScaler.divideScale( x1, x2,
            maxMajorSteps, maxMinorSteps, 0.0 );
    }

    stepSize = qAbs( stepSize );
    if ( stepSize == 0.0 )
    {
        if ( maxMajorSteps < 1 )
            maxMajorSteps = 1;

        stepSize = divideInterval( 
            qwtLogInterval( logBase, interval ).width(), maxMajorSteps );
        if ( stepSize < 1.0 )
            stepSize = 1.0; // major step must be >= 1 decade
    }

    QwtScaleDiv scaleDiv;
    if ( stepSize != 0.0 )
    {
        QList<double> ticks[QwtScaleDiv::NTickTypes];
        buildTicks( interval, stepSize, maxMinorSteps, ticks );

        scaleDiv = QwtScaleDiv( interval, ticks );
    }

    if ( x1 > x2 )
        scaleDiv.invert();

    return scaleDiv;
}

void QwtLogScaleEngine::buildTicks(
    const QwtInterval& interval, double stepSize, int maxMinorSteps,
    QList<double> ticks[QwtScaleDiv::NTickTypes] ) const
{
    const QwtInterval boundingInterval = align( interval, stepSize );

    ticks[QwtScaleDiv::MajorTick] =
        buildMajorTicks( boundingInterval, stepSize );

    if ( maxMinorSteps > 0 )
    {
        buildMinorTicks( ticks[QwtScaleDiv::MajorTick], maxMinorSteps, stepSize,
            ticks[QwtScaleDiv::MinorTick], ticks[QwtScaleDiv::MediumTick] );
    }

    for ( int i = 0; i < QwtScaleDiv::NTickTypes; i++ )
        ticks[i] = strip( ticks[i], interval );
}

QList<double> QwtLogScaleEngine::buildMajorTicks(
    const QwtInterval &interval, double stepSize ) const
{
    double width = qwtLogInterval( base(), interval ).width();

    int numTicks = qRound( width / stepSize ) + 1;
    if ( numTicks > 10000 )
        numTicks = 10000;

    const double lxmin = ::log( interval.minValue() );
    const double lxmax = ::log( interval.maxValue() );
    const double lstep = ( lxmax - lxmin ) / double( numTicks - 1 );

    QList<double> ticks;
#if QT_VERSION >= 0x040700
    ticks.reserve( numTicks );
#endif

    ticks += interval.minValue();

    for ( int i = 1; i < numTicks - 1; i++ )
        ticks += qExp( lxmin + double( i ) * lstep );

    ticks += interval.maxValue();

    return ticks;
}

void QwtLogScaleEngine::buildMinorTicks(
    const QList<double> &majorTicks,
    int maxMinorSteps, double stepSize,
    QList<double> &minorTicks,
    QList<double> &mediumTicks ) const
{
    const double logBase = base();

    if ( stepSize < 1.1 )          // major step width is one base
    {
        double minStep = divideInterval( stepSize, maxMinorSteps + 1 );
        if ( minStep == 0.0 )
            return;
        
        const int numSteps = qRound( stepSize / minStep ); 

        int mediumTickIndex = -1;
        if ( ( numSteps > 2 ) && ( numSteps % 2 == 0 ) )
            mediumTickIndex = numSteps / 2;

        for ( int i = 0; i < majorTicks.count() - 1; i++ )
        {
            const double v = majorTicks[i];
            const double s = logBase / numSteps;

            if ( s >= 1.0 )
            {
                if ( !qFuzzyCompare( s, 1.0 ) )
                    minorTicks += v * s;

                for ( int j = 2; j < numSteps; j++ )
                {
                    minorTicks += v * j * s;
                }
            }
            else
            {
                for ( int j = 1; j < numSteps; j++ )
                {
                    const double tick = v + j * v * ( logBase - 1 ) / numSteps;
                    if ( j == mediumTickIndex )
                        mediumTicks += tick;
                    else
                        minorTicks += tick;
                }
            }
        }
    }
    else
    {
        double minStep = divideInterval( stepSize, maxMinorSteps );
        if ( minStep == 0.0 )
            return;

        if ( minStep < 1.0 )
            minStep = 1.0;

        // # subticks per interval
        int numTicks = qRound( stepSize / minStep ) - 1;

        // Do the minor steps fit into the interval?
        if ( qwtFuzzyCompare( ( numTicks +  1 ) * minStep,
            stepSize, stepSize ) > 0 )
        {
            numTicks = 0;
        }

        if ( numTicks < 1 )
            return; 

        int mediumTickIndex = -1;
        if ( ( numTicks > 2 ) && ( numTicks % 2 ) )
            mediumTickIndex = numTicks / 2;

        // substep factor = base^substeps
        const qreal minFactor = qMax( qPow( logBase, minStep ), qreal( logBase ) );

        for ( int i = 0; i < majorTicks.count(); i++ )
        {
            double tick = majorTicks[i];
            for ( int j = 0; j < numTicks; j++ )
            {
                tick *= minFactor;

                if ( j == mediumTickIndex )
                    mediumTicks += tick;
                else
                    minorTicks += tick;
            }
        }
    }
}

QwtInterval QwtLogScaleEngine::align(
    const QwtInterval &interval, double stepSize ) const
{
    const QwtInterval intv = qwtLogInterval( base(), interval );

    double x1 = QwtScaleArithmetic::floorEps( intv.minValue(), stepSize );
    if ( qwtFuzzyCompare( interval.minValue(), x1, stepSize ) == 0 )
        x1 = interval.minValue();

    double x2 = QwtScaleArithmetic::ceilEps( intv.maxValue(), stepSize );
    if ( qwtFuzzyCompare( interval.maxValue(), x2, stepSize ) == 0 )
        x2 = interval.maxValue();

    return qwtPowInterval( base(), QwtInterval( x1, x2 ) );
}