Qwt User's Guide 6.2.0

qwt_clipper.cpp
1 /******************************************************************************
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 "qwt_interval.h"
13 #include "qwt_math.h"
14
15 #include <qpolygon.h>
16 #include <qrect.h>
17
18 #include <algorithm>
19
20 namespace 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
29 template< class Point, typename Value >
30 class QwtClip::LeftEdge
31 {
32 public:
33 inline LeftEdge( Value x1, Value, Value, Value ):
34 m_x1( x1 )
35 {
36 }
37
38 inline bool isInside( const Point& p ) const
39 {
40 return p.x() >= m_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( m_x1, static_cast< Value >( p2.y() + ( m_x1 - p2.x() ) * dy ) );
47 }
48 private:
49 const Value m_x1;
50 };
51
52 template< class Point, typename Value >
53 class QwtClip::RightEdge
54 {
55 public:
56 inline RightEdge( Value, Value x2, Value, Value ):
57 m_x2( x2 )
58 {
59 }
60
61 inline bool isInside( const Point& p ) const
62 {
63 return p.x() <= m_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( m_x2, static_cast< Value >( p2.y() + ( m_x2 - p2.x() ) * dy ) );
70 }
71
72 private:
73 const Value m_x2;
74 };
75
76 template< class Point, typename Value >
77 class QwtClip::TopEdge
78 {
79 public:
80 inline TopEdge( Value, Value, Value y1, Value ):
81 m_y1( y1 )
82 {
83 }
84
85 inline bool isInside( const Point& p ) const
86 {
87 return p.y() >= m_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( static_cast< Value >( p2.x() + ( m_y1 - p2.y() ) * dx ), m_y1 );
94 }
95
96 private:
97 const Value m_y1;
98 };
99
100 template< class Point, typename Value >
101 class QwtClip::BottomEdge
102 {
103 public:
104 inline BottomEdge( Value, Value, Value, Value y2 ):
105 m_y2( y2 )
106 {
107 }
108
109 inline bool isInside( const Point& p ) const
110 {
111 return p.y() <= m_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( static_cast< Value >( p2.x() + ( m_y2 - p2.y() ) * dx ), m_y2 );
118 }
119
120 private:
121 const Value m_y2;
122 };
123
124 using namespace QwtClip;
125
126 template< class Polygon, class Rect, typename T >
127 class QwtPolygonClipper
128 {
129 typedef typename Polygon::value_type Point;
130 public:
131 explicit QwtPolygonClipper( const Rect& clipRect ):
132 m_clipRect( clipRect )
133 {
134 }
135
136 void clipPolygon( Polygon& points1, bool closePolygon ) const
137 {
138 #if 0
139 if ( m_clipRect.contains( points1.boundingRect() ) )
140 return polygon;
141 #endif
142
143 Polygon points2;
144 points2.reserve( qMin( 256, points1.size() ) );
145
146 clipEdge< LeftEdge< Point, T > >( closePolygon, points1, points2 );
147 clipEdge< RightEdge< Point, T > >( closePolygon, points2, points1 );
148 clipEdge< TopEdge< Point, T > >( closePolygon, points1, points2 );
149 clipEdge< BottomEdge< Point, T > >( closePolygon, points2, points1 );
150 }
151
152 private:
153 template< class Edge >
154 inline void clipEdge( bool closePolygon,
155 const Polygon& points, Polygon& clippedPoints ) const
156 {
157 clippedPoints.clear();
158
159 if ( points.size() < 2 )
160 {
161 if ( points.size() == 1 )
162 clippedPoints += points[0];
163
164 return;
165 }
166
167 const Edge edge( m_clipRect.x(), m_clipRect.x() + m_clipRect.width(),
168 m_clipRect.y(), m_clipRect.y() + m_clipRect.height() );
169
170 if ( !closePolygon )
171 {
172 const Point& p1 = points.first();
173
174 if ( edge.isInside( p1 ) )
175 clippedPoints += p1;
176 }
177 else
178 {
179 const Point& p1 = points.first();
180 const Point& p2 = points.last();
181
182 if ( edge.isInside( p1 ) )
183 {
184 if ( !edge.isInside( p2 ) )
185 clippedPoints += edge.intersection( p1, p2 );
186
187 clippedPoints += p1;
188 }
189 else if ( edge.isInside( p2 ) )
190 {
191 clippedPoints += edge.intersection( p1, p2 );
192 }
193 }
194
195 const uint nPoints = points.size();
196 const Point* p = points.constData();
197
198 for ( uint i = 1; i < nPoints; i++ )
199 {
200 const Point& p1 = p[i];
201 const Point& p2 = p[i - 1];
202
203 if ( edge.isInside( p1 ) )
204 {
205 if ( !edge.isInside( p2 ) )
206 clippedPoints += edge.intersection( p1, p2 );
207
208 clippedPoints += p1;
209 }
210 else if ( edge.isInside( p2 ) )
211 {
212 clippedPoints += edge.intersection( p1, p2 );
213 }
214 }
215 }
216
217 const Rect m_clipRect;
218 };
219
220 class QwtCircleClipper
221 {
222 public:
223 explicit QwtCircleClipper( const QRectF& r );
224 QVector< QwtInterval > clipCircle( const QPointF&, double radius ) const;
225
226 private:
227 enum Edge
228 {
229 Left,
230 Top,
231 Right,
232 Bottom,
233
234 NEdges
235 };
236
237 QVector< QPointF > cuttingPoints(
238 Edge, const QPointF& pos, double radius ) const;
239
240 double toAngle( const QPointF&, const QPointF& ) const;
241
242 const QRectF m_rect;
243 };
244
245
246 QwtCircleClipper::QwtCircleClipper( const QRectF& r )
247 : m_rect( r )
248 {
249 }
250
251 QVector< QwtInterval > QwtCircleClipper::clipCircle(
252 const QPointF& pos, double radius ) const
253 {
254 // using QVarLengthArray TODO ...
255
256 QVector< QPointF > points;
257 for ( int edge = 0; edge < NEdges; edge++ )
258 points += cuttingPoints( static_cast< Edge >( edge ), pos, radius );
259
260 QVector< QwtInterval > intv;
261 if ( points.size() <= 0 )
262 {
263 QRectF cRect( 0, 0, 2 * radius, 2 * radius );
264 cRect.moveCenter( pos );
265 if ( m_rect.contains( cRect ) )
266 intv += QwtInterval( 0.0, 2 * M_PI );
267 }
268 else
269 {
270 QVector< double > angles;
271 angles.reserve( points.size() );
272
273 for ( int i = 0; i < points.size(); i++ )
274 angles += toAngle( pos, points[i] );
275
276 std::sort( angles.begin(), angles.end() );
277
278 const int in = m_rect.contains( qwtPolar2Pos( pos, radius,
279 angles[0] + ( angles[1] - angles[0] ) / 2 ) );
280
281 intv.reserve( angles.size() / 2 );
282 if ( in )
283 {
284 for ( int i = 0; i < angles.size() - 1; i += 2 )
285 intv += QwtInterval( angles[i], angles[i + 1] );
286 }
287 else
288 {
289 for ( int i = 1; i < angles.size() - 1; i += 2 )
290 intv += QwtInterval( angles[i], angles[i + 1] );
291
292 intv += QwtInterval( angles.last(), angles.first() );
293 }
294 }
295
296 return intv;
297 }
298
299 double QwtCircleClipper::toAngle(
300 const QPointF& from, const QPointF& to ) const
301 {
302 if ( from.x() == to.x() )
303 return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;
304
305 const double m = qAbs( ( to.y() - from.y() ) / ( to.x() - from.x() ) );
306
307 double angle = std::atan( m );
308 if ( to.x() > from.x() )
309 {
310 if ( to.y() > from.y() )
311 angle = 2 * M_PI - angle;
312 }
313 else
314 {
315 if ( to.y() > from.y() )
316 angle = M_PI + angle;
317 else
318 angle = M_PI - angle;
319 }
320
321 return angle;
322 }
323
324 QVector< QPointF > QwtCircleClipper::cuttingPoints(
325 Edge edge, const QPointF& pos, double radius ) const
326 {
327 QVector< QPointF > points;
328
329 if ( edge == Left || edge == Right )
330 {
331 const double x = ( edge == Left ) ? m_rect.left() : m_rect.right();
332 if ( qAbs( pos.x() - x ) < radius )
333 {
334 const double off = std::sqrt( qwtSqr( radius ) - qwtSqr( pos.x() - x ) );
335 const double m_y1 = pos.y() + off;
336 if ( m_y1 >= m_rect.top() && m_y1 <= m_rect.bottom() )
337 points += QPointF( x, m_y1 );
338
339 const double m_y2 = pos.y() - off;
340 if ( m_y2 >= m_rect.top() && m_y2 <= m_rect.bottom() )
341 points += QPointF( x, m_y2 );
342 }
343 }
344 else
345 {
346 const double y = ( edge == Top ) ? m_rect.top() : m_rect.bottom();
347 if ( qAbs( pos.y() - y ) < radius )
348 {
349 const double off = std::sqrt( qwtSqr( radius ) - qwtSqr( pos.y() - y ) );
350 const double x1 = pos.x() + off;
351 if ( x1 >= m_rect.left() && x1 <= m_rect.right() )
352 points += QPointF( x1, y );
353
354 const double m_x2 = pos.x() - off;
355 if ( m_x2 >= m_rect.left() && m_x2 <= m_rect.right() )
356 points += QPointF( m_x2, y );
357 }
358 }
359 return points;
360 }
361
369 void QwtClipper::clipPolygon(
370 const QRectF& clipRect, QPolygon& polygon, bool closePolygon )
371 {
372 const int minX = qCeil( clipRect.left() );
373 const int maxX = qFloor( clipRect.right() );
374 const int minY = qCeil( clipRect.top() );
375 const int maxY = qFloor( clipRect.bottom() );
376
377 const QRect r( minX, minY, maxX - minX, maxY - minY );
378
379 QwtPolygonClipper< QPolygon, QRect, int > clipper( r );
380 clipper.clipPolygon( polygon, closePolygon );
381 }
382
390 void QwtClipper::clipPolygon(
391 const QRect& clipRect, QPolygon& polygon, bool closePolygon )
392 {
393 QwtPolygonClipper< QPolygon, QRect, int > clipper( clipRect );
394 clipper.clipPolygon( polygon, closePolygon );
395 }
396
404 void QwtClipper::clipPolygonF(
405 const QRectF& clipRect, QPolygonF& polygon, bool closePolygon )
406 {
407 QwtPolygonClipper< QPolygonF, QRectF, double > clipper( clipRect );
408 clipper.clipPolygon( polygon, closePolygon );
409 }
410
420 QPolygon QwtClipper::clippedPolygon(
421 const QRectF& clipRect, const QPolygon& polygon, bool closePolygon )
422 {
423 QPolygon points( polygon );
424 clipPolygon( clipRect, points, closePolygon );
425
426 return points;
427 }
437 QPolygon QwtClipper::clippedPolygon(
438 const QRect& clipRect, const QPolygon& polygon, bool closePolygon )
439 {
440 QPolygon points( polygon );
441 clipPolygon( clipRect, points, closePolygon );
442
443 return points;
444 }
445
455 QPolygonF QwtClipper::clippedPolygonF(
456 const QRectF& clipRect, const QPolygonF& polygon, bool closePolygon )
457 {
458 QPolygonF points( polygon );
459 clipPolygonF( clipRect, points, closePolygon );
460
461 return points;
462 }
463
477 QVector< QwtInterval > QwtClipper::clipCircle( const QRectF& clipRect,
478 const QPointF& center, double radius )
479 {
480 QwtCircleClipper clipper( clipRect );
481 return clipper.clipCircle( center, radius );
482 }
QVector
Definition: qwt_clipper.h:23
QwtInterval
A class representing an interval.
Definition: qwt_interval.h:23
QwtClipper::clipPolygon
QWT_EXPORT void clipPolygon(const QRect &, QPolygon &, bool closePolygon=false)
Definition: qwt_clipper.cpp:390
QwtClipper::clippedPolygonF
QWT_EXPORT QPolygonF clippedPolygonF(const QRectF &, const QPolygonF &, bool closePolygon=false)
Definition: qwt_clipper.cpp:455
QwtClipper::clipPolygonF
QWT_EXPORT void clipPolygonF(const QRectF &, QPolygonF &, bool closePolygon=false)
Definition: qwt_clipper.cpp:404
QwtClipper::clipCircle
QWT_EXPORT QVector< QwtInterval > clipCircle(const QRectF &, const QPointF &, double radius)
Definition: qwt_clipper.cpp:477
QwtClipper::clippedPolygon
QWT_EXPORT QPolygon clippedPolygon(const QRect &, const QPolygon &, bool closePolygon=false)
Definition: qwt_clipper.cpp:437