00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "qwt_clipper.h"
00011 #include "qwt_point_polar.h"
00012 #include <qrect.h>
00013 #include <string.h>
00014 #include <stdlib.h>
00015
00016 #if QT_VERSION < 0x040601
00017 #define qAtan(x) ::atan(x)
00018 #endif
00019
00020 namespace QwtClip
00021 {
00022
00023 template <class Point, typename T> class LeftEdge;
00024 template <class Point, typename T> class RightEdge;
00025 template <class Point, typename T> class TopEdge;
00026 template <class Point, typename T> class BottomEdge;
00027 }
00028
00029 template <class Point, typename Value>
00030 class QwtClip::LeftEdge
00031 {
00032 public:
00033 inline LeftEdge( Value x1, Value, Value, Value ):
00034 d_x1( x1 )
00035 {
00036 }
00037
00038 inline bool isInside( const Point &p ) const
00039 {
00040 return p.x() >= d_x1;
00041 }
00042
00043 inline Point intersection( const Point &p1, const Point &p2 ) const
00044 {
00045 double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
00046 return Point( d_x1, static_cast< Value >( p2.y() + ( d_x1 - p2.x() ) * dy ) );
00047 }
00048 private:
00049 const Value d_x1;
00050 };
00051
00052 template <class Point, typename Value>
00053 class QwtClip::RightEdge
00054 {
00055 public:
00056 inline RightEdge( Value, Value x2, Value, Value ):
00057 d_x2( x2 )
00058 {
00059 }
00060
00061 inline bool isInside( const Point &p ) const
00062 {
00063 return p.x() <= d_x2;
00064 }
00065
00066 inline Point intersection( const Point &p1, const Point &p2 ) const
00067 {
00068 double dy = ( p1.y() - p2.y() ) / double( p1.x() - p2.x() );
00069 return Point( d_x2, static_cast<Value>( p2.y() + ( d_x2 - p2.x() ) * dy ) );
00070 }
00071
00072 private:
00073 const Value d_x2;
00074 };
00075
00076 template <class Point, typename Value>
00077 class QwtClip::TopEdge
00078 {
00079 public:
00080 inline TopEdge( Value, Value, Value y1, Value ):
00081 d_y1( y1 )
00082 {
00083 }
00084
00085 inline bool isInside( const Point &p ) const
00086 {
00087 return p.y() >= d_y1;
00088 }
00089
00090 inline Point intersection( const Point &p1, const Point &p2 ) const
00091 {
00092 double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
00093 return Point( static_cast<Value>( p2.x() + ( d_y1 - p2.y() ) * dx ), d_y1 );
00094 }
00095
00096 private:
00097 const Value d_y1;
00098 };
00099
00100 template <class Point, typename Value>
00101 class QwtClip::BottomEdge
00102 {
00103 public:
00104 inline BottomEdge( Value, Value, Value, Value y2 ):
00105 d_y2( y2 )
00106 {
00107 }
00108
00109 inline bool isInside( const Point &p ) const
00110 {
00111 return p.y() <= d_y2;
00112 }
00113
00114 inline Point intersection( const Point &p1, const Point &p2 ) const
00115 {
00116 double dx = ( p1.x() - p2.x() ) / double( p1.y() - p2.y() );
00117 return Point( static_cast<Value>( p2.x() + ( d_y2 - p2.y() ) * dx ), d_y2 );
00118 }
00119
00120 private:
00121 const Value d_y2;
00122 };
00123
00124 using namespace QwtClip;
00125
00126 template <class Polygon, class Rect, typename T>
00127 class QwtPolygonClipper
00128 {
00129 typedef typename Polygon::value_type Point;
00130 public:
00131 explicit QwtPolygonClipper( const Rect &clipRect ):
00132 d_clipRect( clipRect )
00133 {
00134 }
00135
00136 void clipPolygon( Polygon &points1, bool closePolygon ) const
00137 {
00138 #if 0
00139 if ( d_clipRect.contains( points1.boundingRect() ) )
00140 return polygon;
00141 #endif
00142
00143 Polygon points2;
00144 points2.reserve( qMin( 256, points1.size() ) );
00145
00146 clipEdge< LeftEdge<Point, T> >( closePolygon, points1, points2 );
00147 clipEdge< RightEdge<Point, T> >( closePolygon, points2, points1 );
00148 clipEdge< TopEdge<Point, T> >( closePolygon, points1, points2 );
00149 clipEdge< BottomEdge<Point, T> >( closePolygon, points2, points1 );
00150 }
00151
00152 private:
00153 template <class Edge>
00154 inline void clipEdge( bool closePolygon,
00155 const Polygon &points, Polygon &clippedPoints ) const
00156 {
00157 clippedPoints.clear();
00158
00159 if ( points.size() < 2 )
00160 {
00161 if ( points.size() == 1 )
00162 clippedPoints += points[0];
00163
00164 return;
00165 }
00166
00167 const Edge edge( d_clipRect.x(), d_clipRect.x() + d_clipRect.width(),
00168 d_clipRect.y(), d_clipRect.y() + d_clipRect.height() );
00169
00170 if ( !closePolygon )
00171 {
00172 const Point &p1 = points.first();
00173
00174 if ( edge.isInside( p1 ) )
00175 clippedPoints += p1;
00176 }
00177 else
00178 {
00179 const Point &p1 = points.first();
00180 const Point &p2 = points.last();
00181
00182 if ( edge.isInside( p1 ) )
00183 {
00184 if ( !edge.isInside( p2 ) )
00185 clippedPoints += edge.intersection( p1, p2 );
00186
00187 clippedPoints += p1;
00188 }
00189 else if ( edge.isInside( p2 ) )
00190 {
00191 clippedPoints += edge.intersection( p1, p2 );
00192 }
00193 }
00194
00195 const uint nPoints = points.size();
00196 const Point* p = points.constData();
00197
00198 for ( uint i = 1; i < nPoints; i++ )
00199 {
00200 const Point &p1 = p[i];
00201 const Point &p2 = p[i - 1];
00202
00203 if ( edge.isInside( p1 ) )
00204 {
00205 if ( !edge.isInside( p2 ) )
00206 clippedPoints += edge.intersection( p1, p2 );
00207
00208 clippedPoints += p1;
00209 }
00210 else if ( edge.isInside( p2 ) )
00211 {
00212 clippedPoints += edge.intersection( p1, p2 );
00213 }
00214 }
00215 }
00216
00217 const Rect d_clipRect;
00218 };
00219
00220 class QwtCircleClipper
00221 {
00222 public:
00223 explicit QwtCircleClipper( const QRectF &r );
00224 QVector<QwtInterval> clipCircle( const QPointF &, double radius ) const;
00225
00226 private:
00227 enum Edge
00228 {
00229 Left,
00230 Top,
00231 Right,
00232 Bottom,
00233
00234 NEdges
00235 };
00236
00237 QVector<QPointF> cuttingPoints(
00238 Edge, const QPointF &pos, double radius ) const;
00239
00240 double toAngle( const QPointF &, const QPointF & ) const;
00241
00242 const QRectF d_rect;
00243 };
00244
00245
00246 QwtCircleClipper::QwtCircleClipper( const QRectF &r ):
00247 d_rect( r )
00248 {
00249 }
00250
00251 QVector<QwtInterval> QwtCircleClipper::clipCircle(
00252 const QPointF &pos, double radius ) const
00253 {
00254 QVector<QPointF> points;
00255 for ( int edge = 0; edge < NEdges; edge++ )
00256 points += cuttingPoints( static_cast<Edge>(edge), pos, radius );
00257
00258 QVector<QwtInterval> intv;
00259 if ( points.size() <= 0 )
00260 {
00261 QRectF cRect( 0, 0, 2 * radius, 2 * radius );
00262 cRect.moveCenter( pos );
00263 if ( d_rect.contains( cRect ) )
00264 intv += QwtInterval( 0.0, 2 * M_PI );
00265 }
00266 else
00267 {
00268 QList<double> angles;
00269 #if QT_VERSION >= 0x040700
00270 angles.reserve( points.size() );
00271 #endif
00272
00273 for ( int i = 0; i < points.size(); i++ )
00274 angles += toAngle( pos, points[i] );
00275
00276 qSort( angles );
00277
00278 const int in = d_rect.contains( qwtPolar2Pos( pos, radius,
00279 angles[0] + ( angles[1] - angles[0] ) / 2 ) );
00280
00281 intv.reserve( angles.size() / 2 );
00282 if ( in )
00283 {
00284 for ( int i = 0; i < angles.size() - 1; i += 2 )
00285 intv += QwtInterval( angles[i], angles[i+1] );
00286 }
00287 else
00288 {
00289 for ( int i = 1; i < angles.size() - 1; i += 2 )
00290 intv += QwtInterval( angles[i], angles[i+1] );
00291
00292 intv += QwtInterval( angles.last(), angles.first() );
00293 }
00294 }
00295
00296 return intv;
00297 }
00298
00299 double QwtCircleClipper::toAngle(
00300 const QPointF &from, const QPointF &to ) const
00301 {
00302 if ( from.x() == to.x() )
00303 return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;
00304
00305 const double m = qAbs( ( to.y() - from.y() ) / ( to.x() - from.x() ) );
00306
00307 double angle = qAtan( m );
00308 if ( to.x() > from.x() )
00309 {
00310 if ( to.y() > from.y() )
00311 angle = 2 * M_PI - angle;
00312 }
00313 else
00314 {
00315 if ( to.y() > from.y() )
00316 angle = M_PI + angle;
00317 else
00318 angle = M_PI - angle;
00319 }
00320
00321 return angle;
00322 }
00323
00324 QVector<QPointF> QwtCircleClipper::cuttingPoints(
00325 Edge edge, const QPointF &pos, double radius ) const
00326 {
00327 QVector<QPointF> points;
00328
00329 if ( edge == Left || edge == Right )
00330 {
00331 const double x = ( edge == Left ) ? d_rect.left() : d_rect.right();
00332 if ( qAbs( pos.x() - x ) < radius )
00333 {
00334 const double off = qSqrt( qwtSqr( radius ) - qwtSqr( pos.x() - x ) );
00335 const double m_y1 = pos.y() + off;
00336 if ( m_y1 >= d_rect.top() && m_y1 <= d_rect.bottom() )
00337 points += QPointF( x, m_y1 );
00338
00339 const double m_y2 = pos.y() - off;
00340 if ( m_y2 >= d_rect.top() && m_y2 <= d_rect.bottom() )
00341 points += QPointF( x, m_y2 );
00342 }
00343 }
00344 else
00345 {
00346 const double y = ( edge == Top ) ? d_rect.top() : d_rect.bottom();
00347 if ( qAbs( pos.y() - y ) < radius )
00348 {
00349 const double off = qSqrt( qwtSqr( radius ) - qwtSqr( pos.y() - y ) );
00350 const double x1 = pos.x() + off;
00351 if ( x1 >= d_rect.left() && x1 <= d_rect.right() )
00352 points += QPointF( x1, y );
00353
00354 const double m_x2 = pos.x() - off;
00355 if ( m_x2 >= d_rect.left() && m_x2 <= d_rect.right() )
00356 points += QPointF( m_x2, y );
00357 }
00358 }
00359 return points;
00360 }
00361
00369 void QwtClipper::clipPolygon(
00370 const QRectF &clipRect, QPolygon &polygon, bool closePolygon )
00371 {
00372 const int minX = qCeil( clipRect.left() );
00373 const int maxX = qFloor( clipRect.right() );
00374 const int minY = qCeil( clipRect.top() );
00375 const int maxY = qFloor( clipRect.bottom() );
00376
00377 const QRect r( minX, minY, maxX - minX, maxY - minY );
00378
00379 QwtPolygonClipper<QPolygon, QRect, int> clipper( r );
00380 clipper.clipPolygon( polygon, closePolygon );
00381 }
00382
00390 void QwtClipper::clipPolygon(
00391 const QRect &clipRect, QPolygon &polygon, bool closePolygon )
00392 {
00393 QwtPolygonClipper<QPolygon, QRect, int> clipper( clipRect );
00394 clipper.clipPolygon( polygon, closePolygon );
00395 }
00396
00404 void QwtClipper::clipPolygonF(
00405 const QRectF &clipRect, QPolygonF &polygon, bool closePolygon )
00406 {
00407 QwtPolygonClipper<QPolygonF, QRectF, double> clipper( clipRect );
00408 clipper.clipPolygon( polygon, closePolygon );
00409 }
00410
00420 QPolygon QwtClipper::clippedPolygon(
00421 const QRectF &clipRect, const QPolygon &polygon, bool closePolygon )
00422 {
00423 QPolygon points( polygon );
00424 clipPolygon( clipRect, points, closePolygon );
00425
00426 return points;
00427 }
00437 QPolygon QwtClipper::clippedPolygon(
00438 const QRect &clipRect, const QPolygon &polygon, bool closePolygon )
00439 {
00440 QPolygon points( polygon );
00441 clipPolygon( clipRect, points, closePolygon );
00442
00443 return points;
00444 }
00445
00455 QPolygonF QwtClipper::clippedPolygonF(
00456 const QRectF &clipRect, const QPolygonF &polygon, bool closePolygon )
00457 {
00458 QPolygonF points( polygon );
00459 clipPolygonF( clipRect, points, closePolygon );
00460
00461 return points;
00462 }
00463
00477 QVector<QwtInterval> QwtClipper::clipCircle( const QRectF &clipRect,
00478 const QPointF ¢er, double radius )
00479 {
00480 QwtCircleClipper clipper( clipRect );
00481 return clipper.clipCircle( center, radius );
00482 }