qwt_clipper.cpp
Go to the documentation of this file.
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 00479 QwtPolygon QwtClipper::clipPolygon( 00480 const QRect &clipRect, const QwtPolygon &polygon) 00481 { 00482 QwtPolygonClipper clipper(clipRect); 00483 return clipper.clipPolygon(polygon); 00484 } 00485 00494 QwtPolygonF QwtClipper::clipPolygonF( 00495 const QwtDoubleRect &clipRect, const QwtPolygonF &polygon) 00496 { 00497 QwtPolygonClipperF clipper(clipRect); 00498 return clipper.clipPolygon(polygon); 00499 } 00500 00501 #if QT_VERSION >= 0x040000 00502 00515 QwtArray<QwtDoubleInterval> QwtClipper::clipCircle( 00516 const QwtDoubleRect &clipRect, 00517 const QwtDoublePoint ¢er, double radius) 00518 { 00519 QwtCircleClipper clipper(clipRect); 00520 return clipper.clipCircle(center, radius); 00521 } 00522 #endif
