source: ntrip/branches/BNC_2.11.0/qwt/qwt_clipper.cpp@ 6381

Last change on this file since 6381 was 4271, checked in by mervart, 12 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 &p ) 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 &p ) 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 &p ) 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.