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

Last change on this file since 8127 was 8127, checked in by stoecker, 23 months ago

update qwt and qwtpolar, many QT5 fixes (unfinished)

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