1
/* -*- mode: C++ ; c-file-style: "stroustrup" -*- *****************************
3
* Copyright (C) 1997 Josef Wilgen
4
* Copyright (C) 2002 Uwe Rathmann
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
*****************************************************************************/
12
#include "qwt_clipper.h"
14
static inline QwtDoubleRect boundingRect(const QwtPolygonF &polygon)
16
#if QT_VERSION < 0x040000
17
if (polygon.isEmpty())
18
return QwtDoubleRect(0, 0, 0, 0);
20
register const QwtDoublePoint *pd = polygon.data();
22
double minx, maxx, miny, maxy;
23
minx = maxx = pd->x();
24
miny = maxy = pd->y();
27
for (uint i = 1; i < polygon.size(); i++, pd++)
31
else if (pd->x() > maxx)
35
else if (pd->y() > maxy)
38
return QwtDoubleRect(minx, miny, maxx - minx, maxy - miny);
40
return polygon.boundingRect();
53
class QwtPolygonClipper: public QRect
56
QwtPolygonClipper(const QRect &r);
58
QwtPolygon clipPolygon(const QwtPolygon &) const;
61
void clipEdge(Edge, const QwtPolygon &, QwtPolygon &) const;
62
bool insideEdge(const QPoint &, Edge edge) const;
63
QPoint intersectEdge(const QPoint &p1,
64
const QPoint &p2, Edge edge) const;
66
void addPoint(QwtPolygon &, uint pos, const QPoint &point) const;
69
class QwtPolygonClipperF: public QwtDoubleRect
72
QwtPolygonClipperF(const QwtDoubleRect &r);
73
QwtPolygonF clipPolygon(const QwtPolygonF &) const;
76
void clipEdge(Edge, const QwtPolygonF &, QwtPolygonF &) const;
77
bool insideEdge(const QwtDoublePoint &, Edge edge) const;
78
QwtDoublePoint intersectEdge(const QwtDoublePoint &p1,
79
const QwtDoublePoint &p2, Edge edge) const;
81
void addPoint(QwtPolygonF &, uint pos, const QwtDoublePoint &point) const;
84
#if QT_VERSION >= 0x040000
85
class QwtCircleClipper: public QwtDoubleRect
88
QwtCircleClipper(const QwtDoubleRect &r);
89
QwtArray<QwtDoubleInterval> clipCircle(
90
const QwtDoublePoint &, double radius) const;
93
QList<QwtDoublePoint> cuttingPoints(
94
Edge, const QwtDoublePoint &pos, double radius) const;
95
double toAngle(const QwtDoublePoint &, const QwtDoublePoint &) const;
99
QwtPolygonClipper::QwtPolygonClipper(const QRect &r):
104
inline void QwtPolygonClipper::addPoint(
105
QwtPolygon &pa, uint pos, const QPoint &point) const
107
if ( uint(pa.size()) <= pos )
110
pa.setPoint(pos, point);
113
//! Sutherland-Hodgman polygon clipping
114
QwtPolygon QwtPolygonClipper::clipPolygon(const QwtPolygon &pa) const
116
if ( contains( pa.boundingRect() ) )
119
QwtPolygon cpa(pa.size());
121
clipEdge((Edge)0, pa, cpa);
123
for ( uint edge = 1; edge < NEdges; edge++ )
125
const QwtPolygon rpa = cpa;
126
#if QT_VERSION < 0x040000
129
clipEdge((Edge)edge, rpa, cpa);
135
bool QwtPolygonClipper::insideEdge(const QPoint &p, Edge edge) const
140
return p.x() > left();
142
return p.y() > top();
144
return p.x() < right();
146
return p.y() < bottom();
154
QPoint QwtPolygonClipper::intersectEdge(const QPoint &p1,
155
const QPoint &p2, Edge edge ) const
160
const double dy = p2.y() - p1.y();
161
const double dx = p2.x() - p1.x();
167
m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
168
y = p1.y() + int(dy * m);
172
m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
173
x = p1.x() + int(dx * m);
177
m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
178
y = p1.y() + int(dy * m);
182
m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
183
x = p1.x() + int(dx * m);
192
void QwtPolygonClipper::clipEdge(Edge edge,
193
const QwtPolygon &pa, QwtPolygon &cpa) const
195
if ( pa.count() == 0 )
201
unsigned int count = 0;
203
QPoint p1 = pa.point(0);
204
if ( insideEdge(p1, edge) )
205
addPoint(cpa, count++, p1);
207
const uint nPoints = pa.size();
208
for ( uint i = 1; i < nPoints; i++ )
210
const QPoint p2 = pa.point(i);
211
if ( insideEdge(p2, edge) )
213
if ( insideEdge(p1, edge) )
214
addPoint(cpa, count++, p2);
217
addPoint(cpa, count++, intersectEdge(p1, p2, edge));
218
addPoint(cpa, count++, p2);
223
if ( insideEdge(p1, edge) )
224
addPoint(cpa, count++, intersectEdge(p1, p2, edge));
231
QwtPolygonClipperF::QwtPolygonClipperF(const QwtDoubleRect &r):
236
inline void QwtPolygonClipperF::addPoint(QwtPolygonF &pa, uint pos, const QwtDoublePoint &point) const
238
if ( uint(pa.size()) <= pos )
241
pa[(int)pos] = point;
244
//! Sutherland-Hodgman polygon clipping
245
QwtPolygonF QwtPolygonClipperF::clipPolygon(const QwtPolygonF &pa) const
247
if ( contains( ::boundingRect(pa) ) )
250
QwtPolygonF cpa(pa.size());
252
clipEdge((Edge)0, pa, cpa);
254
for ( uint edge = 1; edge < NEdges; edge++ )
256
const QwtPolygonF rpa = cpa;
257
#if QT_VERSION < 0x040000
260
clipEdge((Edge)edge, rpa, cpa);
266
bool QwtPolygonClipperF::insideEdge(const QwtDoublePoint &p, Edge edge) const
271
return p.x() > left();
273
return p.y() > top();
275
return p.x() < right();
277
return p.y() < bottom();
285
QwtDoublePoint QwtPolygonClipperF::intersectEdge(const QwtDoublePoint &p1,
286
const QwtDoublePoint &p2, Edge edge ) const
291
const double dy = p2.y() - p1.y();
292
const double dx = p2.x() - p1.x();
298
m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
299
y = p1.y() + int(dy * m);
303
m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
304
x = p1.x() + int(dx * m);
308
m = double(qwtAbs(p1.x() - x)) / qwtAbs(dx);
309
y = p1.y() + int(dy * m);
313
m = double(qwtAbs(p1.y() - y)) / qwtAbs(dy);
314
x = p1.x() + int(dx * m);
320
return QwtDoublePoint(x,y);
323
void QwtPolygonClipperF::clipEdge(Edge edge,
324
const QwtPolygonF &pa, QwtPolygonF &cpa) const
326
if ( pa.count() == 0 )
332
unsigned int count = 0;
334
QwtDoublePoint p1 = pa[0];
335
if ( insideEdge(p1, edge) )
336
addPoint(cpa, count++, p1);
338
const uint nPoints = pa.size();
339
for ( uint i = 1; i < nPoints; i++ )
341
const QwtDoublePoint p2 = pa[(int)i];
342
if ( insideEdge(p2, edge) )
344
if ( insideEdge(p1, edge) )
345
addPoint(cpa, count++, p2);
348
addPoint(cpa, count++, intersectEdge(p1, p2, edge));
349
addPoint(cpa, count++, p2);
354
if ( insideEdge(p1, edge) )
355
addPoint(cpa, count++, intersectEdge(p1, p2, edge));
362
#if QT_VERSION >= 0x040000
364
QwtCircleClipper::QwtCircleClipper(const QwtDoubleRect &r):
369
QwtArray<QwtDoubleInterval> QwtCircleClipper::clipCircle(
370
const QwtDoublePoint &pos, double radius) const
372
QList<QwtDoublePoint> points;
373
for ( int edge = 0; edge < NEdges; edge++ )
374
points += cuttingPoints((Edge)edge, pos, radius);
376
QwtArray<QwtDoubleInterval> intv;
377
if ( points.size() <= 0 )
379
QwtDoubleRect cRect(0, 0, 2 * radius, 2* radius);
380
cRect.moveCenter(pos);
381
if ( contains(cRect) )
382
intv += QwtDoubleInterval(0.0, 2 * M_PI);
386
QList<double> angles;
387
for ( int i = 0; i < points.size(); i++ )
388
angles += toAngle(pos, points[i]);
391
const int in = contains(qwtPolar2Pos(pos, radius,
392
angles[0] + (angles[1] - angles[0]) / 2));
395
for ( int i = 0; i < angles.size() - 1; i += 2)
396
intv += QwtDoubleInterval(angles[i], angles[i+1]);
400
for ( int i = 1; i < angles.size() - 1; i += 2)
401
intv += QwtDoubleInterval(angles[i], angles[i+1]);
402
intv += QwtDoubleInterval(angles.last(), angles.first());
409
double QwtCircleClipper::toAngle(
410
const QwtDoublePoint &from, const QwtDoublePoint &to) const
412
if ( from.x() == to.x() )
413
return from.y() <= to.y() ? M_PI / 2.0 : 3 * M_PI / 2.0;
415
const double m = qwtAbs((to.y() - from.y()) / (to.x() - from.x()) );
417
double angle = ::atan(m);
418
if ( to.x() > from.x() )
420
if ( to.y() > from.y() )
421
angle = 2 * M_PI - angle;
425
if ( to.y() > from.y() )
426
angle = M_PI + angle;
428
angle = M_PI - angle;
434
QList<QwtDoublePoint> QwtCircleClipper::cuttingPoints(
435
Edge edge, const QwtDoublePoint &pos, double radius) const
437
QList<QwtDoublePoint> points;
439
if ( edge == Left || edge == Right )
441
const double x = (edge == Left) ? left() : right();
442
if ( qwtAbs(pos.x() - x) < radius )
444
const double off = ::sqrt(qwtSqr(radius) - qwtSqr(pos.x() - x));
445
const double y1 = pos.y() + off;
446
if ( y1 >= top() && y1 <= bottom() )
447
points += QwtDoublePoint(x, y1);
448
const double y2 = pos.y() - off;
449
if ( y2 >= top() && y2 <= bottom() )
450
points += QwtDoublePoint(x, y2);
455
const double y = (edge == Top) ? top() : bottom();
456
if ( qwtAbs(pos.y() - y) < radius )
458
const double off = ::sqrt(qwtSqr(radius) - qwtSqr(pos.y() - y));
459
const double x1 = pos.x() + off;
460
if ( x1 >= left() && x1 <= right() )
461
points += QwtDoublePoint(x1, y);
462
const double x2 = pos.x() - off;
463
if ( x2 >= left() && x2 <= right() )
464
points += QwtDoublePoint(x2, y);
471
QwtPolygon QwtClipper::clipPolygon(
472
const QRect &clipRect, const QwtPolygon &polygon)
474
QwtPolygonClipper clipper(clipRect);
475
return clipper.clipPolygon(polygon);
478
QwtPolygonF QwtClipper::clipPolygonF(
479
const QwtDoubleRect &clipRect, const QwtPolygonF &polygon)
481
QwtPolygonClipperF clipper(clipRect);
482
return clipper.clipPolygon(polygon);
485
#if QT_VERSION >= 0x040000
486
QwtArray<QwtDoubleInterval> QwtClipper::clipCircle(
487
const QwtDoubleRect &clipRect,
488
const QwtDoublePoint ¢er, double radius)
490
QwtCircleClipper clipper(clipRect);
491
return clipper.clipCircle(center, radius);