qwt_clipper.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_clipper.h"
#include "qwt_point_polar.h"
#include "qwt_interval.h"
#include "qwt_math.h"

#include <qpolygon.h>
#include <qrect.h>

#include <algorithm>

namespace QwtClip
{
    // some templates used for inlining
    template <class Point, typename T> class LeftEdge;
    template <class Point, typename T> class RightEdge;
    template <class Point, typename T> class TopEdge;
    template <class Point, typename T> class BottomEdge;
}

template <class Point, typename Value>
class QwtClip::LeftEdge
{
public:
    inline LeftEdge( Value x1, Value, Value, Value ):
        d_x1( x1 )
    {
    }

    inline bool isInside( const Point &p  ) const
    {
        return p.x() >= d_x1;
    }

    inline Point intersection( const Point &p1, const Point &p2 ) const
    {
        double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
        return Point( d_x1, static_cast< Value >( p2.y() + ( d_x1 - p2.x() ) * dy ) );
    }
private:
    const Value d_x1;
};

template <class Point, typename Value>
class QwtClip::RightEdge
{
public:
    inline RightEdge( Value, Value x2, Value, Value ):
        d_x2( x2 )
    {
    }

    inline bool isInside( const Point &p  ) const
    {
        return p.x() <= d_x2;
    }

    inline Point intersection( const Point &p1, const Point &p2 ) const
    {
        double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
        return Point( d_x2, static_cast<Value>( p2.y() + ( d_x2 - p2.x() ) * dy ) );
    }

private:
    const Value d_x2;
};

template <class Point, typename Value>
class QwtClip::TopEdge
{
public:
    inline TopEdge( Value, Value, Value y1, Value ):
        d_y1( y1 )
    {
    }

    inline bool isInside( const Point &p  ) const
    {
        return p.y() >= d_y1;
    }

    inline Point intersection( const Point &p1, const Point &p2 ) const
    {
        double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
        return Point( static_cast<Value>( p2.x() + ( d_y1 - p2.y() ) * dx ), d_y1 );
    }

private:
    const Value d_y1;
};

template <class Point, typename Value>
class QwtClip::BottomEdge
{
public:
    inline BottomEdge( Value, Value, Value, Value y2 ):
        d_y2( y2 )
    {
    }

    inline bool isInside( const Point &p ) const
    {
        return p.y() <= d_y2;
    }

    inline Point intersection( const Point &p1, const Point &p2 ) const
    {
        double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
        return Point( static_cast<Value>( p2.x() + ( d_y2 - p2.y() ) * dx ), d_y2 );
    }

private:
    const Value d_y2;
};

using namespace QwtClip;

template <class Polygon, class Rect, typename T>
class QwtPolygonClipper
{
    typedef typename Polygon::value_type Point;
public:
    explicit QwtPolygonClipper( const Rect &clipRect ):
        d_clipRect( clipRect )
    {
    }

    void clipPolygon( Polygon &points1, bool closePolygon ) const
    {
#if 0
        if ( d_clipRect.contains( points1.boundingRect() ) )
            return polygon;
#endif

        Polygon points2;
        points2.reserve( qMin( 256, points1.size() ) );

        clipEdge< LeftEdge<Point, T> >( closePolygon, points1, points2 );
        clipEdge< RightEdge<Point, T> >( closePolygon, points2, points1 );
        clipEdge< TopEdge<Point, T> >( closePolygon, points1, points2 );
        clipEdge< BottomEdge<Point, T> >( closePolygon, points2, points1 );
    }

private:
    template <class Edge>
    inline void clipEdge( bool closePolygon,
        const Polygon &points, Polygon &clippedPoints ) const
    {
        clippedPoints.clear();

        if ( points.size() < 2 )
        {
            if ( points.size() == 1 )
                clippedPoints += points[0];

            return;
        }

        const Edge edge( d_clipRect.x(), d_clipRect.x() + d_clipRect.width(),
            d_clipRect.y(), d_clipRect.y() + d_clipRect.height() );

        if ( !closePolygon )
        {
            const Point &p1 = points.first();

            if ( edge.isInside( p1 ) )
                clippedPoints += p1;
        }
        else
        {
            const Point &p1 = points.first();
            const Point &p2 = points.last();

            if ( edge.isInside( p1 ) )
            {
                if ( !edge.isInside( p2 ) )
                    clippedPoints += edge.intersection( p1, p2 );

                clippedPoints += p1;
            }
            else if ( edge.isInside( p2 ) )
            {
                clippedPoints += edge.intersection( p1, p2 );
            }
        }

        const uint nPoints = points.size();
        const Point* p = points.constData();

        for ( uint i = 1; i < nPoints; i++ )
        {
            const Point &p1 = p[i];
            const Point &p2 = p[i - 1];

            if ( edge.isInside( p1 ) )
            {
                if ( !edge.isInside( p2 ) )
                    clippedPoints += edge.intersection( p1, p2 );

                clippedPoints += p1;
            }
            else if ( edge.isInside( p2 ) )
            {
                clippedPoints += edge.intersection( p1, p2 );
            }
        }
    }

    const Rect d_clipRect;
};

class QwtCircleClipper
{
public:
    explicit QwtCircleClipper( const QRectF &r );
    QVector<QwtInterval> clipCircle( const QPointF &, double radius ) const;

private:
    enum Edge
    {
        Left,
        Top,
        Right,
        Bottom,

        NEdges
    };

    QVector<QPointF> cuttingPoints(
        Edge, const QPointF &pos, double radius ) const;

    double toAngle( const QPointF &, const QPointF & ) const;

    const QRectF d_rect;
};


QwtCircleClipper::QwtCircleClipper( const QRectF &r ):
    d_rect( r )
{
}

QVector<QwtInterval> QwtCircleClipper::clipCircle(
    const QPointF &pos, double radius ) const
{
    // using QVarLengthArray TODO ...

    QVector<QPointF> points;
    for ( int edge = 0; edge < NEdges; edge++ )
        points += cuttingPoints( static_cast<Edge>(edge), pos, radius );

    QVector<QwtInterval> intv;
    if ( points.size() <= 0 )
    {
        QRectF cRect( 0, 0, 2 * radius, 2 * radius );
        cRect.moveCenter( pos );
        if ( d_rect.contains( cRect ) )
            intv += QwtInterval( 0.0, 2 * M_PI );
    }
    else
    {
        QVector<double> angles;
        angles.reserve( points.size() );

        for ( int i = 0; i < points.size(); i++ )
            angles += toAngle( pos, points[i] );

        std::sort( angles.begin(), angles.end() );

        const int in = d_rect.contains( qwtPolar2Pos( pos, radius,
            angles[0] + ( angles[1] - angles[0] ) / 2 ) );

        intv.reserve( angles.size() / 2 );
        if ( in )
        {
            for ( int i = 0; i < angles.size() - 1; i += 2 )
                intv += QwtInterval( angles[i], angles[i+1] );
        }
        else
        {
            for ( int i = 1; i < angles.size() - 1; i += 2 )
                intv += QwtInterval( angles[i], angles[i+1] );

            intv += QwtInterval( angles.last(), angles.first() );
        }
    }

    return intv;
}

double QwtCircleClipper::toAngle(
    const QPointF &from, const QPointF &to ) const
{
    if ( from.x() == to.x() )
        return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;

    const double m = qAbs( ( to.y() - from.y() ) / ( to.x() - from.x() ) );

    double angle = std::atan( m );
    if ( to.x() > from.x() )
    {
        if ( to.y() > from.y() )
            angle = 2 * M_PI - angle;
    }
    else
    {
        if ( to.y() > from.y() )
            angle = M_PI + angle;
        else
            angle = M_PI - angle;
    }

    return angle;
}

QVector<QPointF> QwtCircleClipper::cuttingPoints(
    Edge edge, const QPointF &pos, double radius ) const
{
    QVector<QPointF> points;

    if ( edge == Left || edge == Right )
    {
        const double x = ( edge == Left ) ? d_rect.left() : d_rect.right();
        if ( qAbs( pos.x() - x ) < radius )
        {
            const double off = std::sqrt( qwtSqr( radius ) - qwtSqr( pos.x() - x ) );
            const double m_y1 = pos.y() + off;
            if ( m_y1 >= d_rect.top() && m_y1 <= d_rect.bottom() )
                points += QPointF( x, m_y1 );

            const double m_y2 = pos.y() - off;
            if ( m_y2 >= d_rect.top() && m_y2 <= d_rect.bottom() )
                points += QPointF( x, m_y2 );
        }
    }
    else
    {
        const double y = ( edge == Top ) ? d_rect.top() : d_rect.bottom();
        if ( qAbs( pos.y() - y ) < radius )
        {
            const double off = std::sqrt( qwtSqr( radius ) - qwtSqr( pos.y() - y ) );
            const double x1 = pos.x() + off;
            if ( x1 >= d_rect.left() && x1 <= d_rect.right() )
                points += QPointF( x1, y );

            const double m_x2 = pos.x() - off;
            if ( m_x2 >= d_rect.left() && m_x2 <= d_rect.right() )
                points += QPointF( m_x2, y );
        }
    }
    return points;
}

void QwtClipper::clipPolygon(
    const QRectF &clipRect, QPolygon &polygon, bool closePolygon )
{
    const int minX = qCeil( clipRect.left() );
    const int maxX = qFloor( clipRect.right() );
    const int minY = qCeil( clipRect.top() );
    const int maxY = qFloor( clipRect.bottom() );

    const QRect r( minX, minY, maxX - minX, maxY - minY );

    QwtPolygonClipper<QPolygon, QRect, int> clipper( r );
    clipper.clipPolygon( polygon, closePolygon );
}

void QwtClipper::clipPolygon(
    const QRect &clipRect, QPolygon &polygon, bool closePolygon )
{
    QwtPolygonClipper<QPolygon, QRect, int> clipper( clipRect );
    clipper.clipPolygon( polygon, closePolygon );
}

void QwtClipper::clipPolygonF(
    const QRectF &clipRect, QPolygonF &polygon, bool closePolygon )
{
    QwtPolygonClipper<QPolygonF, QRectF, double> clipper( clipRect );
    clipper.clipPolygon( polygon, closePolygon );
}

QPolygon QwtClipper::clippedPolygon(
    const QRectF &clipRect, const QPolygon &polygon, bool closePolygon )
{
    QPolygon points( polygon );
    clipPolygon( clipRect, points, closePolygon );

    return points;
}
QPolygon QwtClipper::clippedPolygon(
    const QRect &clipRect, const QPolygon &polygon, bool closePolygon )
{
    QPolygon points( polygon );
    clipPolygon( clipRect, points, closePolygon );

    return points;
}

QPolygonF QwtClipper::clippedPolygonF(
    const QRectF &clipRect, const QPolygonF &polygon, bool closePolygon )
{
    QPolygonF points( polygon );
    clipPolygonF( clipRect, points, closePolygon );

    return points;
}

QVector<QwtInterval> QwtClipper::clipCircle( const QRectF &clipRect,
    const QPointF &center, double radius )
{
    QwtCircleClipper clipper( clipRect );
    return clipper.clipCircle( center, radius );
}