1  /* * mode: C++ ; cfilestyle: "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 


18  namespace 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 


29  template <class Point, typename Value>


30  class QwtClip::LeftEdge


31  {


32  public:


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  }


48  private:


49  const Value d_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  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 


72  private:


73  const Value d_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  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 


96  private:


97  const Value d_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  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 


120  private:


121  const Value d_y2;


122  };


123 


124  template<class Point>


125  class QwtClip::PointBuffer


126  {


127  public:


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 


184  private:


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 


202  using namespace QwtClip;


203 


204  template <class Polygon, class Rect, class Point, typename T>


205  class QwtPolygonClipper


206  {


207  public:


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 


237  private:


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 


301  class QwtCircleClipper


302  {


303  public:


304  QwtCircleClipper( const QRectF &r );


305  QVector<QwtInterval> clipCircle( const QPointF &, double radius ) const;


306 


307  private:


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 


327  QwtCircleClipper::QwtCircleClipper( const QRectF &r ):


328  d_rect( r )


329  {


330  }


331 


332  QVector<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 


373  double 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 


398  QList<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  SutherlandHodgman 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  */


445  QPolygon 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  SutherlandHodgman 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  */


461  QPolygonF 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  */


481  QVector<QwtInterval> QwtClipper::clipCircle( const QRectF &clipRect,


482  const QPointF ¢er, double radius )


483  {


484  QwtCircleClipper clipper( clipRect );


485  return clipper.clipCircle( center, radius );


486  }

