qwt_clipper.cpp

00001 /* -*- mode: C++ ; c-file-style: "stroustrup" -*- *****************************
00002  * Qwt Widget Library
00003  * Copyright (C) 1997   Josef Wilgen
00004  * Copyright (C) 2002   Uwe Rathmann
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the Qwt License, Version 1.0
00008  *****************************************************************************/
00009 
00010 #include <qrect.h>
00011 #include "qwt_math.h"
00012 #include "qwt_clipper.h"
00013 
00014 static inline QwtDoubleRect boundingRect(const QwtPolygonF &polygon)
00015 {
00016 #if QT_VERSION < 0x040000
00017     if (polygon.isEmpty())
00018         return QwtDoubleRect(0, 0, 0, 0);
00019 
00020     register const QwtDoublePoint *pd = polygon.data();
00021 
00022     double minx, maxx, miny, maxy;
00023     minx = maxx = pd->x();
00024     miny = maxy = pd->y();
00025     pd++;
00026 
00027     for (uint i = 1; i < polygon.size(); i++, pd++) 
00028     {
00029         if (pd->x() < minx)
00030             minx = pd->x();
00031         else if (pd->x() > maxx)
00032             maxx = pd->x();
00033         if (pd->y() < miny)
00034             miny = pd->y();
00035         else if (pd->y() > maxy)
00036             maxy = pd->y();
00037     }
00038     return QwtDoubleRect(minx, miny, maxx - minx, maxy - miny);
00039 #else
00040     return polygon.boundingRect();
00041 #endif
00042 }
00043 
00044 enum Edge 
00045 { 
00046     Left, 
00047     Top, 
00048     Right, 
00049     Bottom, 
00050     NEdges 
00051 };
00052 
00053 class QwtPolygonClipper: public QRect
00054 {
00055 public:
00056     QwtPolygonClipper(const QRect &r);
00057 
00058     QwtPolygon clipPolygon(const QwtPolygon &) const;
00059 
00060 private:
00061     void clipEdge(Edge, const QwtPolygon &, QwtPolygon &) const;
00062     bool insideEdge(const QPoint &, Edge edge) const;
00063     QPoint intersectEdge(const QPoint &p1,
00064         const QPoint &p2, Edge edge) const;
00065 
00066     void addPoint(QwtPolygon &, uint pos, const QPoint &point) const;
00067 };
00068 
00069 class QwtPolygonClipperF: public QwtDoubleRect
00070 {
00071 public:
00072     QwtPolygonClipperF(const QwtDoubleRect &r);
00073     QwtPolygonF clipPolygon(const QwtPolygonF &) const;
00074 
00075 private:
00076     void clipEdge(Edge, const QwtPolygonF &, QwtPolygonF &) const;
00077     bool insideEdge(const QwtDoublePoint &, Edge edge) const;
00078     QwtDoublePoint intersectEdge(const QwtDoublePoint &p1,
00079         const QwtDoublePoint &p2, Edge edge) const;
00080 
00081     void addPoint(QwtPolygonF &, uint pos, const QwtDoublePoint &point) const;
00082 };
00083 
00084 #if QT_VERSION >= 0x040000
00085 class QwtCircleClipper: public QwtDoubleRect
00086 {
00087 public:
00088     QwtCircleClipper(const QwtDoubleRect &r);
00089     QwtArray<QwtDoubleInterval> clipCircle(
00090         const QwtDoublePoint &, double radius) const;
00091 
00092 private:
00093     QList<QwtDoublePoint> cuttingPoints(
00094         Edge, const QwtDoublePoint &pos, double radius) const;
00095     double toAngle(const QwtDoublePoint &, const QwtDoublePoint &) const;
00096 };
00097 #endif
00098 
00099 QwtPolygonClipper::QwtPolygonClipper(const QRect &r): 
00100     QRect(r) 
00101 {
00102 }
00103 
00104 inline void QwtPolygonClipper::addPoint(
00105     QwtPolygon &pa, uint pos, const QPoint &point) const
00106 {
00107     if ( uint(pa.size()) <= pos ) 
00108         pa.resize(pos + 5);
00109 
00110     pa.setPoint(pos, point);
00111 }
00112 
00114 QwtPolygon QwtPolygonClipper::clipPolygon(const QwtPolygon &pa) const
00115 {
00116     if ( contains( pa.boundingRect() ) )
00117         return pa;
00118 
00119     QwtPolygon cpa(pa.size());
00120 
00121     clipEdge((Edge)0, pa, cpa);
00122 
00123     for ( uint edge = 1; edge < NEdges; edge++ ) 
00124     {
00125         const QwtPolygon rpa = cpa;
00126 #if QT_VERSION < 0x040000
00127         cpa.detach();
00128 #endif
00129         clipEdge((Edge)edge, rpa, cpa);
00130     }
00131 
00132     return cpa;
00133 }
00134 
00135 bool QwtPolygonClipper::insideEdge(const QPoint &p, Edge edge) const
00136 {
00137     switch(edge) 
00138     {
00139         case Left:
00140             return p.x() > left();
00141         case Top:
00142             return p.y() > top();
00143         case Right:
00144             return p.x() < right();
00145         case Bottom:
00146             return p.y() < bottom();
00147         default:
00148             break;
00149     }
00150 
00151     return false;
00152 }
00153 
00154 QPoint QwtPolygonClipper::intersectEdge(const QPoint &p1, 
00155     const QPoint &p2, Edge edge ) const
00156 {
00157     int x=0, y=0;
00158     double m = 0;
00159 
00160     const double dy = p2.y() - p1.y();
00161     const double dx = p2.x() - p1.x();
00162 
00163     switch ( edge ) 
00164     {
00165         case Left:
00166             x = left();
00167             m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
00168             y = p1.y() + int(dy * m);
00169             break;
00170         case Top:
00171             y = top();
00172             m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
00173             x = p1.x() + int(dx * m);
00174             break;
00175         case Right:
00176             x = right();
00177             m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
00178             y = p1.y() + int(dy * m);
00179             break;
00180         case Bottom:
00181             y = bottom();
00182             m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
00183             x = p1.x() + int(dx * m);
00184             break;
00185         default:
00186             break;
00187     }
00188 
00189     return QPoint(x,y);
00190 }
00191 
00192 void QwtPolygonClipper::clipEdge(Edge edge, 
00193     const QwtPolygon &pa, QwtPolygon &cpa) const
00194 {
00195     if ( pa.count() == 0 )
00196     {
00197         cpa.resize(0);
00198         return;
00199     }
00200 
00201     unsigned int count = 0;
00202 
00203     QPoint p1 = pa.point(0);
00204     if ( insideEdge(p1, edge) )
00205         addPoint(cpa, count++, p1);
00206 
00207     const uint nPoints = pa.size();
00208     for ( uint i = 1; i < nPoints; i++ )
00209     {
00210         const QPoint p2 = pa.point(i);
00211         if ( insideEdge(p2, edge) )
00212         {
00213             if ( insideEdge(p1, edge) )
00214                 addPoint(cpa, count++, p2);
00215             else
00216             {
00217                 addPoint(cpa, count++, intersectEdge(p1, p2, edge));
00218                 addPoint(cpa, count++, p2);
00219             }
00220         }
00221         else
00222         {
00223             if ( insideEdge(p1, edge) )
00224                 addPoint(cpa, count++, intersectEdge(p1, p2, edge));
00225         }
00226         p1 = p2;
00227     }
00228     cpa.resize(count);
00229 }
00230 
00231 QwtPolygonClipperF::QwtPolygonClipperF(const QwtDoubleRect &r): 
00232     QwtDoubleRect(r) 
00233 {
00234 }
00235 
00236 inline void QwtPolygonClipperF::addPoint(QwtPolygonF &pa, uint pos, const QwtDoublePoint &point) const
00237 {
00238     if ( uint(pa.size()) <= pos ) 
00239         pa.resize(pos + 5);
00240 
00241     pa[(int)pos] = point;
00242 }
00243 
00245 QwtPolygonF QwtPolygonClipperF::clipPolygon(const QwtPolygonF &pa) const
00246 {
00247     if ( contains( ::boundingRect(pa) ) )
00248         return pa;
00249 
00250     QwtPolygonF cpa(pa.size());
00251 
00252     clipEdge((Edge)0, pa, cpa);
00253 
00254     for ( uint edge = 1; edge < NEdges; edge++ ) 
00255     {
00256         const QwtPolygonF rpa = cpa;
00257 #if QT_VERSION < 0x040000
00258         cpa.detach();
00259 #endif
00260         clipEdge((Edge)edge, rpa, cpa);
00261     }
00262 
00263     return cpa;
00264 }
00265 
00266 bool QwtPolygonClipperF::insideEdge(const QwtDoublePoint &p, Edge edge) const
00267 {
00268     switch(edge) 
00269     {
00270         case Left:
00271             return p.x() > left();
00272         case Top:
00273             return p.y() > top();
00274         case Right:
00275             return p.x() < right();
00276         case Bottom:
00277             return p.y() < bottom();
00278         default:
00279             break;
00280     }
00281 
00282     return false;
00283 }
00284 
00285 QwtDoublePoint QwtPolygonClipperF::intersectEdge(const QwtDoublePoint &p1, 
00286     const QwtDoublePoint &p2, Edge edge ) const
00287 {
00288     double x=0.0, y=0.0;
00289     double m = 0;
00290 
00291     const double dy = p2.y() - p1.y();
00292     const double dx = p2.x() - p1.x();
00293 
00294     switch ( edge ) 
00295     {
00296         case Left:
00297             x = left();
00298             m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
00299             y = p1.y() + int(dy * m);
00300             break;
00301         case Top:
00302             y = top();
00303             m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
00304             x = p1.x() + int(dx * m);
00305             break;
00306         case Right:
00307             x = right();
00308             m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
00309             y = p1.y() + int(dy * m);
00310             break;
00311         case Bottom:
00312             y = bottom();
00313             m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
00314             x = p1.x() + int(dx * m);
00315             break;
00316         default:
00317             break;
00318     }
00319 
00320     return QwtDoublePoint(x,y);
00321 }
00322 
00323 void QwtPolygonClipperF::clipEdge(Edge edge, 
00324     const QwtPolygonF &pa, QwtPolygonF &cpa) const
00325 {
00326     if ( pa.count() == 0 )
00327     {
00328         cpa.resize(0);
00329         return;
00330     }
00331 
00332     unsigned int count = 0;
00333 
00334     QwtDoublePoint p1 = pa[0];
00335     if ( insideEdge(p1, edge) )
00336         addPoint(cpa, count++, p1);
00337 
00338     const uint nPoints = pa.size();
00339     for ( uint i = 1; i < nPoints; i++ )
00340     {
00341         const QwtDoublePoint p2 = pa[(int)i];
00342         if ( insideEdge(p2, edge) )
00343         {
00344             if ( insideEdge(p1, edge) )
00345                 addPoint(cpa, count++, p2);
00346             else
00347             {
00348                 addPoint(cpa, count++, intersectEdge(p1, p2, edge));
00349                 addPoint(cpa, count++, p2);
00350             }
00351         }
00352         else
00353         {
00354             if ( insideEdge(p1, edge) )
00355                 addPoint(cpa, count++, intersectEdge(p1, p2, edge));
00356         }
00357         p1 = p2;
00358     }
00359     cpa.resize(count);
00360 }
00361 
00362 #if QT_VERSION >= 0x040000
00363 
00364 QwtCircleClipper::QwtCircleClipper(const QwtDoubleRect &r):
00365     QwtDoubleRect(r)
00366 {
00367 }
00368 
00369 QwtArray<QwtDoubleInterval> QwtCircleClipper::clipCircle(
00370     const QwtDoublePoint &pos, double radius) const
00371 {
00372     QList<QwtDoublePoint> points;
00373     for ( int edge = 0; edge < NEdges; edge++ )
00374         points += cuttingPoints((Edge)edge, pos, radius);
00375 
00376     QwtArray<QwtDoubleInterval> intv;
00377     if ( points.size() <= 0 )
00378     {
00379         QwtDoubleRect cRect(0, 0, 2 * radius, 2* radius);
00380         cRect.moveCenter(pos);
00381         if ( contains(cRect) )
00382             intv += QwtDoubleInterval(0.0, 2 * M_PI);
00383     }
00384     else
00385     {
00386         QList<double> angles;
00387         for ( int i = 0; i < points.size(); i++ )
00388             angles += toAngle(pos, points[i]);
00389         qSort(angles);
00390 
00391         const int in = contains(qwtPolar2Pos(pos, radius, 
00392             angles[0] + (angles[1] - angles[0]) / 2));
00393         if ( in )
00394         {
00395             for ( int i = 0; i < angles.size() - 1; i += 2)
00396                 intv += QwtDoubleInterval(angles[i], angles[i+1]);
00397         }
00398         else
00399         {
00400             for ( int i = 1; i < angles.size() - 1; i += 2)
00401                 intv += QwtDoubleInterval(angles[i], angles[i+1]);
00402             intv += QwtDoubleInterval(angles.last(), angles.first());
00403         }
00404     }
00405 
00406     return intv;
00407 }
00408 
00409 double QwtCircleClipper::toAngle(
00410     const QwtDoublePoint &from, const QwtDoublePoint &to) const
00411 {
00412     if ( from.x() == to.x() )
00413         return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;
00414 
00415     const double m = qwtAbs((to.y() - from.y()) / (to.x() - from.x()) );
00416 
00417     double angle = ::atan(m);
00418     if ( to.x() > from.x() )
00419     {   
00420         if ( to.y() > from.y() )
00421             angle = 2 * M_PI - angle;
00422     }
00423     else
00424     {
00425         if ( to.y() > from.y() )
00426             angle = M_PI + angle;
00427         else
00428             angle = M_PI - angle;
00429     }
00430 
00431     return angle;
00432 }
00433 
00434 QList<QwtDoublePoint> QwtCircleClipper::cuttingPoints(
00435     Edge edge, const QwtDoublePoint &pos, double radius) const
00436 {
00437     QList<QwtDoublePoint> points;
00438 
00439     if ( edge == Left || edge == Right )
00440     {
00441         const double x = (edge == Left) ? left() : right();
00442         if ( qwtAbs(pos.x() - x) < radius )
00443         {
00444             const double off = ::sqrt(qwtSqr(radius) - qwtSqr(pos.x() - x));
00445             const double y1 = pos.y() + off;
00446             if ( y1 >= top() && y1 <= bottom() )
00447                 points += QwtDoublePoint(x, y1);
00448             const double y2 = pos.y() - off;
00449             if ( y2 >= top() && y2 <= bottom() )
00450                 points += QwtDoublePoint(x, y2);
00451         }
00452     }
00453     else
00454     {
00455         const double y = (edge == Top) ? top() : bottom();
00456         if ( qwtAbs(pos.y() - y) < radius )
00457         {
00458             const double off = ::sqrt(qwtSqr(radius) - qwtSqr(pos.y() - y));
00459             const double x1 = pos.x() + off;
00460             if ( x1 >= left() && x1 <= right() )
00461                 points += QwtDoublePoint(x1, y);
00462             const double x2 = pos.x() - off;
00463             if ( x2 >= left() && x2 <= right() )
00464                 points += QwtDoublePoint(x2, y);
00465         }
00466     }
00467     return points;
00468 }
00469 #endif
00470     
00471 QwtPolygon QwtClipper::clipPolygon(
00472     const QRect &clipRect, const QwtPolygon &polygon)
00473 {
00474     QwtPolygonClipper clipper(clipRect);
00475     return clipper.clipPolygon(polygon);
00476 }
00477 
00478 QwtPolygonF QwtClipper::clipPolygonF(
00479     const QwtDoubleRect &clipRect, const QwtPolygonF &polygon)
00480 {
00481     QwtPolygonClipperF clipper(clipRect);
00482     return clipper.clipPolygon(polygon);
00483 }
00484 
00485 #if QT_VERSION >= 0x040000
00486 QwtArray<QwtDoubleInterval> QwtClipper::clipCircle(
00487     const QwtDoubleRect &clipRect, 
00488     const QwtDoublePoint &center, double radius)
00489 {
00490     QwtCircleClipper clipper(clipRect);
00491     return clipper.clipCircle(center, radius);
00492 }
00493 #endif

Generated on Sat May 24 18:47:39 2008 for Qwt User's Guide by  doxygen 1.5.0