source: ntrip/trunk/BNC/qwt/qwt_clipper.cpp @ 4271

Last change on this file since 4271 was 4271, checked in by mervart, 7 years ago
File size: 11.7 KB
Line 
1/* -*- mode: C++ ; c-file-style: "stroustrup" -*- *****************************
2 * Qwt Widget Library
3 * Copyright (C) 1997   Josef Wilgen
4 * Copyright (C) 2002   Uwe Rathmann
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the Qwt License, Version 1.0
8 *****************************************************************************/
9
10#include "qwt_clipper.h"
11#include "qwt_point_polar.h"
12#include <qrect.h>
13
14#if QT_VERSION < 0x040601
15#define qAtan(x) ::atan(x)
16#endif
17
18namespace QwtClip
19{
20    // some templates used for inlining
21    template <class Point, typename T> class LeftEdge;
22    template <class Point, typename T> class RightEdge;
23    template <class Point, typename T> class TopEdge;
24    template <class Point, typename T> class BottomEdge;
25
26    template <class Point> class PointBuffer;
27}
28
29template <class Point, typename Value>
30class QwtClip::LeftEdge
31{
32public:
33    inline LeftEdge( Value x1, Value, Value, Value ):
34        d_x1( x1 )
35    {
36    }
37
38    inline bool isInside( const Point &) const
39    {
40        return p.x() >= d_x1;
41    }
42
43    inline Point intersection( const Point &p1, const Point &p2 ) const
44    {
45        double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
46        return Point( d_x1, ( Value ) ( p2.y() + ( d_x1 - p2.x() ) * dy ) );
47    }
48private:
49    const Value d_x1;
50};
51
52template <class Point, typename Value>
53class QwtClip::RightEdge
54{
55public:
56    inline RightEdge( Value, Value x2, Value, Value ):
57        d_x2( x2 )
58    {
59    }
60
61    inline bool isInside( const Point &) const
62    {
63        return p.x() <= d_x2;
64    }
65
66    inline Point intersection( const Point &p1, const Point &p2 ) const
67    {
68        double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
69        return Point( d_x2, ( Value ) ( p2.y() + ( d_x2 - p2.x() ) * dy ) );
70    }
71
72private:
73    const Value d_x2;
74};
75
76template <class Point, typename Value>
77class QwtClip::TopEdge
78{
79public:
80    inline TopEdge( Value, Value, Value y1, Value ):
81        d_y1( y1 )
82    {
83    }
84
85    inline bool isInside( const Point &) const
86    {
87        return p.y() >= d_y1;
88    }
89
90    inline Point intersection( const Point &p1, const Point &p2 ) const
91    {
92        double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
93        return Point( ( Value )( p2.x() + ( d_y1 - p2.y() ) * dx ), d_y1 );
94    }
95
96private:
97    const Value d_y1;
98};
99
100template <class Point, typename Value>
101class QwtClip::BottomEdge
102{
103public:
104    inline BottomEdge( Value, Value, Value, Value y2 ):
105        d_y2( y2 )
106    {
107    }
108
109    inline bool isInside( const Point &p ) const
110    {
111        return p.y() <= d_y2;
112    }
113
114    inline Point intersection( const Point &p1, const Point &p2 ) const
115    {
116        double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
117        return Point( ( Value )( p2.x() + ( d_y2 - p2.y() ) * dx ), d_y2 );
118    }
119
120private:
121    const Value d_y2;
122};
123
124template<class Point>
125class QwtClip::PointBuffer
126{
127public:
128    PointBuffer( int capacity = 0 ):
129        m_capacity( 0 ),
130        m_size( 0 ),
131        m_buffer( NULL )
132    {
133        if ( capacity > 0 )
134            reserve( capacity );
135    }
136
137    ~PointBuffer()
138    {
139        if ( m_buffer )
140            qFree( m_buffer );
141    }
142
143    inline void setPoints( int numPoints, const Point *points )
144    {
145        reserve( numPoints );
146
147        m_size = numPoints;
148        qMemCopy( m_buffer, points, m_size * sizeof( Point ) );
149    }
150
151    inline void reset() 
152    { 
153        m_size = 0; 
154    }
155
156    inline int size() const 
157    { 
158        return m_size; 
159    }
160
161    inline Point *data() const 
162    { 
163        return m_buffer; 
164    }
165
166    inline Point &operator[]( int i ) 
167    { 
168        return m_buffer[i]; 
169    }
170
171    inline const Point &operator[]( int i ) const 
172    { 
173        return m_buffer[i]; 
174    }
175
176    inline void add( const Point &point )
177    {
178        if ( m_capacity <= m_size )
179            reserve( m_size + 1 );
180
181        m_buffer[m_size++] = point;
182    }
183
184private:
185    inline void reserve( int size )
186    {
187        if ( m_capacity == 0 )
188            m_capacity = 1;
189
190        while ( m_capacity < size )
191            m_capacity *= 2;
192
193        m_buffer = ( Point * ) qRealloc( 
194            m_buffer, m_capacity * sizeof( Point ) );
195    }
196
197    int m_capacity;
198    int m_size;
199    Point *m_buffer;
200};
201
202using namespace QwtClip;
203
204template <class Polygon, class Rect, class Point, typename T>
205class QwtPolygonClipper
206{
207public:
208    QwtPolygonClipper( const Rect &clipRect ):
209        d_clipRect( clipRect )
210    {
211    }
212
213    Polygon clipPolygon( const Polygon &polygon, bool closePolygon ) const
214    {
215#if 0
216        if ( d_clipRect.contains( polygon.boundingRect() ) )
217            return polygon;
218#endif
219
220        PointBuffer<Point> points1;
221        PointBuffer<Point> points2( qMin( 256, polygon.size() ) );
222
223        points1.setPoints( polygon.size(), polygon.data() );
224
225        clipEdge< LeftEdge<Point, T> >( closePolygon, points1, points2 );
226        clipEdge< RightEdge<Point, T> >( closePolygon, points2, points1 );
227        clipEdge< TopEdge<Point, T> >( closePolygon, points1, points2 );
228        clipEdge< BottomEdge<Point, T> >( closePolygon, points2, points1 );
229
230        Polygon p;
231        p.resize( points1.size() );
232        qMemCopy( p.data(), points1.data(), points1.size() * sizeof( Point ) );
233
234        return p;
235    }
236
237private:
238    template <class Edge>
239    inline void clipEdge( bool closePolygon,
240        PointBuffer<Point> &points, PointBuffer<Point> &clippedPoints ) const
241    {
242        clippedPoints.reset();
243
244        if ( points.size() < 2 )
245        {
246            if ( points.size() == 1 )
247                clippedPoints.add( points[0] );
248            return;
249        }
250
251        const Edge edge( d_clipRect.x(), d_clipRect.x() + d_clipRect.width(),
252            d_clipRect.y(), d_clipRect.y() + d_clipRect.height() );
253
254        int lastPos, start;
255        if ( closePolygon )
256        {
257            start = 0;
258            lastPos = points.size() - 1;
259        }
260        else
261        {
262            start = 1;
263            lastPos = 0;
264
265            if ( edge.isInside( points[0] ) )
266                clippedPoints.add( points[0] );
267        }
268
269        const uint nPoints = points.size();
270        for ( uint i = start; i < nPoints; i++ )
271        {
272            const Point &p1 = points[i];
273            const Point &p2 = points[lastPos];
274
275            if ( edge.isInside( p1 ) )
276            {
277                if ( edge.isInside( p2 ) )
278                {
279                    clippedPoints.add( p1 );
280                }
281                else
282                {
283                    clippedPoints.add( edge.intersection( p1, p2 ) );
284                    clippedPoints.add( p1 );
285                }
286            }
287            else
288            {
289                if ( edge.isInside( p2 ) )
290                {
291                    clippedPoints.add( edge.intersection( p1, p2 ) );
292                }
293            }
294            lastPos = i;
295        }
296    }
297
298    const Rect d_clipRect;
299};
300
301class QwtCircleClipper
302{
303public:
304    QwtCircleClipper( const QRectF &r );
305    QVector<QwtInterval> clipCircle( const QPointF &, double radius ) const;
306
307private:
308    enum Edge
309    {
310        Left,
311        Top,
312        Right,
313        Bottom,
314
315        NEdges
316    };
317
318    QList<QPointF> cuttingPoints(
319        Edge, const QPointF &pos, double radius ) const;
320
321    double toAngle( const QPointF &, const QPointF & ) const;
322
323    const QRectF d_rect;
324};
325
326
327QwtCircleClipper::QwtCircleClipper( const QRectF &r ):
328    d_rect( r )
329{
330}
331
332QVector<QwtInterval> QwtCircleClipper::clipCircle(
333    const QPointF &pos, double radius ) const
334{
335    QList<QPointF> points;
336    for ( int edge = 0; edge < NEdges; edge++ )
337        points += cuttingPoints( ( Edge )edge, pos, radius );
338
339    QVector<QwtInterval> intv;
340    if ( points.size() <= 0 )
341    {
342        QRectF cRect( 0, 0, 2 * radius, 2 * radius );
343        cRect.moveCenter( pos );
344        if ( d_rect.contains( cRect ) )
345            intv += QwtInterval( 0.0, 2 * M_PI );
346    }
347    else
348    {
349        QList<double> angles;
350        for ( int i = 0; i < points.size(); i++ )
351            angles += toAngle( pos, points[i] );
352        qSort( angles );
353
354        const int in = d_rect.contains( qwtPolar2Pos( pos, radius,
355            angles[0] + ( angles[1] - angles[0] ) / 2 ) );
356
357        if ( in )
358        {
359            for ( int i = 0; i < angles.size() - 1; i += 2 )
360                intv += QwtInterval( angles[i], angles[i+1] );
361        }
362        else
363        {
364            for ( int i = 1; i < angles.size() - 1; i += 2 )
365                intv += QwtInterval( angles[i], angles[i+1] );
366            intv += QwtInterval( angles.last(), angles.first() );
367        }
368    }
369
370    return intv;
371}
372
373double QwtCircleClipper::toAngle(
374    const QPointF &from, const QPointF &to ) const
375{
376    if ( from.x() == to.x() )
377        return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;
378
379    const double m = qAbs( ( to.y() - from.y() ) / ( to.x() - from.x() ) );
380
381    double angle = qAtan( m );
382    if ( to.x() > from.x() )
383    {
384        if ( to.y() > from.y() )
385            angle = 2 * M_PI - angle;
386    }
387    else
388    {
389        if ( to.y() > from.y() )
390            angle = M_PI + angle;
391        else
392            angle = M_PI - angle;
393    }
394
395    return angle;
396}
397
398QList<QPointF> QwtCircleClipper::cuttingPoints(
399    Edge edge, const QPointF &pos, double radius ) const
400{
401    QList<QPointF> points;
402
403    if ( edge == Left || edge == Right )
404    {
405        const double x = ( edge == Left ) ? d_rect.left() : d_rect.right();
406        if ( qAbs( pos.x() - x ) < radius )
407        {
408            const double off = qSqrt( qwtSqr( radius ) - qwtSqr( pos.x() - x ) );
409            const double m_y1 = pos.y() + off;
410            if ( m_y1 >= d_rect.top() && m_y1 <= d_rect.bottom() )
411                points += QPointF( x, m_y1 );
412
413            const double m_y2 = pos.y() - off;
414            if ( m_y2 >= d_rect.top() && m_y2 <= d_rect.bottom() )
415                points += QPointF( x, m_y2 );
416        }
417    }
418    else
419    {
420        const double y = ( edge == Top ) ? d_rect.top() : d_rect.bottom();
421        if ( qAbs( pos.y() - y ) < radius )
422        {
423            const double off = qSqrt( qwtSqr( radius ) - qwtSqr( pos.y() - y ) );
424            const double x1 = pos.x() + off;
425            if ( x1 >= d_rect.left() && x1 <= d_rect.right() )
426                points += QPointF( x1, y );
427
428            const double m_x2 = pos.x() - off;
429            if ( m_x2 >= d_rect.left() && m_x2 <= d_rect.right() )
430                points += QPointF( m_x2, y );
431        }
432    }
433    return points;
434}
435
436/*!
437   Sutherland-Hodgman polygon clipping
438
439   \param clipRect Clip rectangle
440   \param polygon Polygon
441   \param closePolygon True, when the polygon is closed
442
443   \return Clipped polygon
444*/
445QPolygon QwtClipper::clipPolygon(
446    const QRect &clipRect, const QPolygon &polygon, bool closePolygon )
447{
448    QwtPolygonClipper<QPolygon, QRect, QPoint, int> clipper( clipRect );
449    return clipper.clipPolygon( polygon, closePolygon );
450}
451
452/*!
453   Sutherland-Hodgman polygon clipping
454
455   \param clipRect Clip rectangle
456   \param polygon Polygon
457   \param closePolygon True, when the polygon is closed
458
459   \return Clipped polygon
460*/
461QPolygonF QwtClipper::clipPolygonF(
462    const QRectF &clipRect, const QPolygonF &polygon, bool closePolygon )
463{
464    QwtPolygonClipper<QPolygonF, QRectF, QPointF, double> clipper( clipRect );
465    return clipper.clipPolygon( polygon, closePolygon );
466}
467
468/*!
469   Circle clipping
470
471   clipCircle() devides a circle into intervals of angles representing arcs
472   of the circle. When the circle is completely inside the clip rectangle
473   an interval [0.0, 2 * M_PI] is returned.
474
475   \param clipRect Clip rectangle
476   \param center Center of the circle
477   \param radius Radius of the circle
478
479   \return Arcs of the circle
480*/
481QVector<QwtInterval> QwtClipper::clipCircle( const QRectF &clipRect,
482    const QPointF &center, double radius )
483{
484    QwtCircleClipper clipper( clipRect );
485    return clipper.clipCircle( center, radius );
486}
Note: See TracBrowser for help on using the repository browser.