Qwt User's Guide 6.2.0

qwt_spline_local.cpp
1 /******************************************************************************
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_spline_local.h"
11 #include "qwt_spline_parametrization.h"
12 #include "qwt_spline_polynomial.h"
13
14 #include <qpainterpath.h>
15
16 static inline bool qwtIsStrictlyMonotonic( double dy1, double dy2 )
17 {
18 if ( dy1 == 0.0 || dy2 == 0.0 )
19 return false;
20
21 return ( dy1 > 0.0 ) == ( dy2 > 0.0 );
22 }
23
24 static inline double qwtSlopeLine( const QPointF& p1, const QPointF& p2 )
25 {
26 // ???
27 const double dx = p2.x() - p1.x();
28 return dx ? ( p2.y() - p1.y() ) / dx : 0.0;
29 }
30
31 static inline double qwtSlopeCardinal(
32 double dx1, double dy1, double s1, double dx2, double dy2, double s2 )
33 {
34 Q_UNUSED(s1)
35 Q_UNUSED(s2)
36
37 return ( dy1 + dy2 ) / ( dx1 + dx2 );
38 }
39
40 static inline double qwtSlopeParabolicBlending(
41 double dx1, double dy1, double s1, double dx2, double dy2, double s2 )
42 {
43 Q_UNUSED( dy1 )
44 Q_UNUSED( dy2 )
45
46 return ( dx2 * s1 + dx1 * s2 ) / ( dx1 + dx2 );
47 }
48
49 static inline double qwtSlopePChip(
50 double dx1, double dy1, double s1, double dx2, double dy2, double s2 )
51 {
52 if ( qwtIsStrictlyMonotonic( dy1, dy2 ) )
53 {
54 #if 0
55 // weighting the slopes by the dx1/dx2
56 const double w1 = ( 3 * dx1 + 3 * dx2 ) / ( 2 * dx1 + 4 * dx2 );
57 const double w2 = ( 3 * dx1 + 3 * dx2 ) / ( 4 * dx1 + 2 * dx2 );
58
59 s1 *= w1;
60 s2 *= w2;
61
62 // harmonic mean ( see https://en.wikipedia.org/wiki/Pythagorean_means )
63 return 2.0 / ( 1.0 / s1 + 1.0 / s2 );
64 #endif
65 // the same as above - but faster
66
67 const double s12 = ( dy1 + dy2 ) / ( dx1 + dx2 );
68 return 3.0 * ( s1 * s2 ) / ( s1 + s2 + s12 );
69 }
70
71 return 0.0;
72 }
73
74 namespace QwtSplineLocalP
75 {
76 class PathStore
77 {
78 public:
79 inline void init( const QVector< QPointF >& )
80 {
81 }
82
83 inline void start( const QPointF& p0, double )
84 {
85 path.moveTo( p0 );
86 }
87
88 inline void addCubic( const QPointF& p1, double m1,
89 const QPointF& p2, double m2 )
90 {
91 const double dx3 = ( p2.x() - p1.x() ) / 3.0;
92
93 path.cubicTo( p1.x() + dx3, p1.y() + m1 * dx3,
94 p2.x() - dx3, p2.y() - m2 * dx3,
95 p2.x(), p2.y() );
96 }
97
98 QPainterPath path;
99 };
100
101 class ControlPointsStore
102 {
103 public:
104 inline void init( const QVector< QPointF >& points )
105 {
106 if ( points.size() > 0 )
107 controlPoints.resize( points.size() - 1 );
108 m_cp = controlPoints.data();
109 }
110
111 inline void start( const QPointF&, double )
112 {
113 }
114
115 inline void addCubic( const QPointF& p1, double m1,
116 const QPointF& p2, double m2 )
117 {
118 const double dx3 = ( p2.x() - p1.x() ) / 3.0;
119
120 QLineF& l = *m_cp++;
121 l.setLine( p1.x() + dx3, p1.y() + m1 * dx3,
122 p2.x() - dx3, p2.y() - m2 * dx3 );
123 }
124
125 QVector< QLineF > controlPoints;
126
127 private:
128 QLineF* m_cp;
129 };
130
131 class SlopeStore
132 {
133 public:
134 void init( const QVector< QPointF >& points )
135 {
136 slopes.resize( points.size() );
137 m_m = slopes.data();
138 }
139
140 inline void start( const QPointF&, double m0 )
141 {
142 *m_m++ = m0;
143 }
144
145 inline void addCubic( const QPointF&, double,
146 const QPointF&, double m2 )
147 {
148 *m_m++ = m2;
149 }
150
151 QVector< double > slopes;
152
153 private:
154 double* m_m;
155 };
156
157 struct slopeCardinal
158 {
159 static inline double value( double dx1, double dy1, double s1,
160 double dx2, double dy2, double s2 )
161 {
162 return qwtSlopeCardinal( dx1, dy1, s1, dx2, dy2, s2 );
163 }
164 };
165
166 struct slopeParabolicBlending
167 {
168 static inline double value( double dx1, double dy1, double s1,
169 double dx2, double dy2, double s2 )
170 {
171 return qwtSlopeParabolicBlending( dx1, dy1, s1, dx2, dy2, s2 );
172 }
173 };
174
175 struct slopePChip
176 {
177 static inline double value( double dx1, double dy1, double s1,
178 double dx2, double dy2, double s2 )
179 {
180 return qwtSlopePChip( dx1, dy1, s1, dx2, dy2, s2 );
181 }
182 };
183 }
184
185 template< class Slope >
186 static inline double qwtSlopeP3(
187 const QPointF& p1, const QPointF& p2, const QPointF& p3 )
188 {
189 const double dx1 = p2.x() - p1.x();
190 const double dy1 = p2.y() - p1.y();
191 const double dx2 = p3.x() - p2.x();
192 const double dy2 = p3.y() - p2.y();
193
194 return Slope::value( dx1, dy1, dy1 / dx1, dx2, dy2, dy2 / dx2 );
195 }
196
197 static inline double qwtSlopeAkima( double s1, double s2, double s3, double s4 )
198 {
199 if ( ( s1 == s2 ) && ( s3 == s4 ) )
200 {
201 return 0.5 * ( s2 + s3 );
202 }
203
204 const double ds12 = qAbs( s2 - s1 );
205 const double ds34 = qAbs( s4 - s3 );
206
207 return ( s2 * ds34 + s3 * ds12 ) / ( ds12 + ds34 );
208 }
209
210 static inline double qwtSlopeAkima( const QPointF& p1, const QPointF& p2,
211 const QPointF& p3, const QPointF& p4, const QPointF& p5 )
212 {
213 const double s1 = qwtSlopeLine( p1, p2 );
214 const double s2 = qwtSlopeLine( p2, p3 );
215 const double s3 = qwtSlopeLine( p3, p4 );
216 const double s4 = qwtSlopeLine( p4, p5 );
217
218 return qwtSlopeAkima( s1, s2, s3, s4 );
219 }
220
221 template< class Slope >
222 static void qwtSplineBoundariesL1(
223 const QwtSplineLocal* spline, const QVector< QPointF >& points,
224 double& slopeBegin, double& slopeEnd )
225 {
226 const int n = points.size();
227 const QPointF* p = points.constData();
228
229 if ( ( spline->boundaryType() == QwtSpline::PeriodicPolygon )
230 || ( spline->boundaryType() == QwtSpline::ClosedPolygon ) )
231 {
232 const QPointF pn = p[0] - ( p[n - 1] - p[n - 2] );
233 slopeBegin = slopeEnd = qwtSlopeP3< Slope >( pn, p[0], p[1] );
234 }
235 else
236 {
237 const double m2 = qwtSlopeP3< Slope >( p[0], p[1], p[2] );
238 slopeBegin = spline->slopeAtBeginning( points, m2 );
239
240 const double mn2 = qwtSlopeP3< Slope >( p[n - 3], p[n - 2], p[n - 1] );
241 slopeEnd = spline->slopeAtEnd( points, mn2 );
242 }
243 }
244
245 template< class SplineStore, class Slope >
246 static inline SplineStore qwtSplineL1(
247 const QwtSplineLocal* spline, const QVector< QPointF >& points )
248 {
249 const int size = points.size();
250 const QPointF* p = points.constData();
251
252 double slopeBegin, slopeEnd;
253 qwtSplineBoundariesL1< Slope >( spline, points, slopeBegin, slopeEnd );
254
255 double m1 = slopeBegin;
256
257 SplineStore store;
258 store.init( points );
259 store.start( p[0], m1 );
260
261 double dx1 = p[1].x() - p[0].x();
262 double dy1 = p[1].y() - p[0].y();
263 double s1 = dy1 / dx1;
264
265 for ( int i = 1; i < size - 1; i++ )
266 {
267 const double dx2 = p[i + 1].x() - p[i].x();
268 const double dy2 = p[i + 1].y() - p[i].y();
269
270 // cardinal spline doesn't need the line slopes, but
271 // the compiler will eliminate pointless calculations
272 const double s2 = dy2 / dx2;
273
274 const double m2 = Slope::value( dx1, dy1, s1, dx2, dy2, s2 );
275
276 store.addCubic( p[i - 1], m1, p[i], m2 );
277
278 dx1 = dx2;
279 dy1 = dy2;
280 s1 = s2;
281 m1 = m2;
282 }
283
284 store.addCubic( p[size - 2], m1, p[size - 1], slopeEnd );
285
286 return store;
287 }
288
289 static inline void qwtSplineAkimaBoundaries(
290 const QwtSplineLocal* spline, const QVector< QPointF >& points,
291 double& slopeBegin, double& slopeEnd )
292 {
293 const int n = points.size();
294 const QPointF* p = points.constData();
295
296 if ( ( spline->boundaryType() == QwtSpline::PeriodicPolygon )
297 || ( spline->boundaryType() == QwtSpline::ClosedPolygon ) )
298 {
299 const QPointF p2 = p[0] - ( p[n - 1] - p[n - 2] );
300 const QPointF p1 = p2 - ( p[n - 2] - p[n - 3] );
301
302 slopeBegin = slopeEnd = qwtSlopeAkima( p1, p2, p[0], p[1], p[2] );
303
304 return;
305 }
306
307 if ( spline->boundaryCondition( QwtSpline::AtBeginning ) == QwtSpline::Clamped1
308 && spline->boundaryCondition( QwtSpline::AtEnd ) == QwtSpline::Clamped1 )
309 {
310 slopeBegin = spline->boundaryValue( QwtSpline::AtBeginning);
311 slopeEnd = spline->boundaryValue( QwtSpline::AtEnd );
312
313 return;
314 }
315
316 if ( n == 3 )
317 {
318 const double s1 = qwtSlopeLine( p[0], p[1] );
319 const double s2 = qwtSlopeLine( p[1], p[2] );
320 const double m = qwtSlopeAkima( 0.5 * s1, s1, s2, 0.5 * s2 );
321
322 slopeBegin = spline->slopeAtBeginning( points, m );
323 slopeEnd = spline->slopeAtEnd( points, m );
324 }
325 else
326 {
327 double s[3];
328
329 s[0] = qwtSlopeLine( p[0], p[1] );
330 s[1] = qwtSlopeLine( p[1], p[2] );
331 s[2] = qwtSlopeLine( p[2], p[3] );
332
333 const double m2 = qwtSlopeAkima( 0.5 * s[0], s[0], s[1], s[2] );
334
335 slopeBegin = spline->slopeAtBeginning( points, m2 );
336
337 s[0] = qwtSlopeLine( p[n - 4], p[n - 3] );
338 s[1] = qwtSlopeLine( p[n - 3], p[n - 2] );
339 s[2] = qwtSlopeLine( p[n - 2], p[n - 1] );
340
341 const double mn2 = qwtSlopeAkima( s[0], s[1], s[2], 0.5 * s[2] );
342
343 slopeEnd = spline->slopeAtEnd( points, mn2 );
344 }
345 }
346
347 template< class SplineStore >
348 static inline SplineStore qwtSplineAkima(
349 const QwtSplineLocal* spline, const QVector< QPointF >& points )
350 {
351 const int size = points.size();
352 const QPointF* p = points.constData();
353
354 double slopeBegin, slopeEnd;
355 qwtSplineAkimaBoundaries( spline, points, slopeBegin, slopeEnd );
356
357 double m1 = slopeBegin;
358
359 SplineStore store;
360 store.init( points );
361 store.start( p[0], m1 );
362
363 double s2 = qwtSlopeLine( p[0], p[1] );
364 double s3 = qwtSlopeLine( p[1], p[2] );
365 double s1 = 0.5 * s2;
366
367 for ( int i = 0; i < size - 3; i++ )
368 {
369 const double s4 = qwtSlopeLine( p[i + 2], p[i + 3] );
370
371 const double m2 = qwtSlopeAkima( s1, s2, s3, s4 );
372 store.addCubic( p[i], m1, p[i + 1], m2 );
373
374 s1 = s2;
375 s2 = s3;
376 s3 = s4;
377
378 m1 = m2;
379 }
380
381 const double m2 = qwtSlopeAkima( s1, s2, s3, 0.5 * s3 );
382
383 store.addCubic( p[size - 3], m1, p[size - 2], m2 );
384 store.addCubic( p[size - 2], m2, p[size - 1], slopeEnd );
385
386 return store;
387 }
388
389 template< class SplineStore >
390 static inline SplineStore qwtSplineLocal(
391 const QwtSplineLocal* spline, const QVector< QPointF >& points )
392 {
393 SplineStore store;
394
395 const int size = points.size();
396 if ( size <= 1 )
397 return store;
398
399 if ( size == 2 )
400 {
401 const double s0 = qwtSlopeLine( points[0], points[1] );
402 const double m1 = spline->slopeAtBeginning( points, s0 );
403 const double m2 = spline->slopeAtEnd( points, s0 );
404
405 store.init( points );
406 store.start( points[0], m1 );
407 store.addCubic( points[0], m1, points[1], m2 );
408
409 return store;
410 }
411
412 switch( spline->type() )
413 {
414 case QwtSplineLocal::Cardinal:
415 {
416 using namespace QwtSplineLocalP;
417 store = qwtSplineL1< SplineStore, slopeCardinal >( spline, points );
418 break;
419 }
420 case QwtSplineLocal::ParabolicBlending:
421 {
422 using namespace QwtSplineLocalP;
423 store = qwtSplineL1< SplineStore, slopeParabolicBlending >( spline, points );
424 break;
425 }
426 case QwtSplineLocal::PChip:
427 {
428 using namespace QwtSplineLocalP;
429 store = qwtSplineL1< SplineStore, slopePChip >( spline, points );
430 break;
431 }
432 case QwtSplineLocal::Akima:
433 {
434 store = qwtSplineAkima< SplineStore >( spline, points );
435 break;
436 }
437 default:
438 break;
439 }
440
441 return store;
442 }
443
450 QwtSplineLocal::QwtSplineLocal( Type type )
451 : m_type( type )
452 {
453 setBoundaryCondition( QwtSpline::AtBeginning, QwtSpline::LinearRunout );
454 setBoundaryValue( QwtSpline::AtBeginning, 0.0 );
455
456 setBoundaryCondition( QwtSpline::AtEnd, QwtSpline::LinearRunout );
457 setBoundaryValue( QwtSpline::AtEnd, 0.0 );
458 }
459
461 QwtSplineLocal::~QwtSplineLocal()
462 {
463 }
464
468 QwtSplineLocal::Type QwtSplineLocal::type() const
469 {
470 return m_type;
471 }
472
482 QPainterPath QwtSplineLocal::painterPath( const QPolygonF& points ) const
483 {
484 if ( parametrization()->type() == QwtSplineParametrization::ParameterX )
485 {
486 using namespace QwtSplineLocalP;
487 return qwtSplineLocal< PathStore >( this, points).path;
488 }
489
490 return QwtSplineC1::painterPath( points );
491 }
492
502 QVector< QLineF > QwtSplineLocal::bezierControlLines( const QPolygonF& points ) const
503 {
504 if ( parametrization()->type() == QwtSplineParametrization::ParameterX )
505 {
506 using namespace QwtSplineLocalP;
507 return qwtSplineLocal< ControlPointsStore >( this, points ).controlPoints;
508 }
509
510 return QwtSplineC1::bezierControlLines( points );
511 }
512
521 QVector< double > QwtSplineLocal::slopes( const QPolygonF& points ) const
522 {
523 using namespace QwtSplineLocalP;
524 return qwtSplineLocal< SlopeStore >( this, points ).slopes;
525 }
526
537 QVector< QwtSplinePolynomial > QwtSplineLocal::polynomials( const QPolygonF& points ) const
538 {
539 // Polynomial store -> TODO
540 return QwtSplineC1::polynomials( points );
541 }
542
552 uint QwtSplineLocal::locality() const
553 {
554 switch ( m_type )
555 {
556 case Akima:
557 {
558 // polynomials: 2 left, 2 right
559 return 2;
560 }
561 case Cardinal:
562 case ParabolicBlending:
563 case PChip:
564 {
565 // polynomials: 1 left, 1 right
566 return 1;
567 }
568 }
569
570 return QwtSplineC1::locality();
571 }
QVector
Definition: qwt_clipper.h:23
QwtSplineC1::slopeAtBeginning
virtual double slopeAtBeginning(const QPolygonF &, double slopeNext) const
Definition: qwt_spline.cpp:979
QwtSplineC1::painterPath
virtual QPainterPath painterPath(const QPolygonF &) const override
Calculate an interpolated painter path.
Definition: qwt_spline.cpp:1043
QwtSplineC1::bezierControlLines
virtual QVector< QLineF > bezierControlLines(const QPolygonF &) const override
Interpolate a curve with Bezier curves.
Definition: qwt_spline.cpp:1101
QwtSplineC1::slopeAtEnd
virtual double slopeAtEnd(const QPolygonF &, double slopeBefore) const
Definition: qwt_spline.cpp:997
QwtSplineC1::polynomials
virtual QVector< QwtSplinePolynomial > polynomials(const QPolygonF &) const
Calculate the interpolating polynomials for a non parametric spline.
Definition: qwt_spline.cpp:1201
QwtSpline::AtBeginning
@ AtBeginning
the condition is at the beginning of the polynomial
Definition: qwt_spline.h:102
QwtSpline::AtEnd
@ AtEnd
the condition is at the end of the polynomial
Definition: qwt_spline.h:105
QwtSpline::boundaryValue
double boundaryValue(BoundaryPosition) const
Definition: qwt_spline.cpp:682
QwtSpline::setBoundaryCondition
void setBoundaryCondition(BoundaryPosition, int condition)
Define the condition for an endpoint of the spline.
Definition: qwt_spline.cpp:639
QwtSpline::parametrization
const QwtSplineParametrization * parametrization() const
Definition: qwt_spline.cpp:605
QwtSpline::boundaryCondition
int boundaryCondition(BoundaryPosition) const
Definition: qwt_spline.cpp:651
QwtSpline::boundaryType
BoundaryType boundaryType() const
Definition: qwt_spline.cpp:626
QwtSpline::locality
virtual uint locality() const
Definition: qwt_spline.cpp:564
QwtSpline::setBoundaryValue
void setBoundaryValue(BoundaryPosition, double value)
Define the boundary value.
Definition: qwt_spline.cpp:670
QwtSpline::ClosedPolygon
@ ClosedPolygon
Definition: qwt_spline.h:92
QwtSpline::PeriodicPolygon
@ PeriodicPolygon
Definition: qwt_spline.h:79
QwtSpline::LinearRunout
@ LinearRunout
Definition: qwt_spline.h:153
QwtSpline::Clamped1
@ Clamped1
Definition: qwt_spline.h:125
QwtSplineLocal
A spline with C1 continuity.
Definition: qwt_spline_local.h:25
QwtSplineLocal::Type
Type
Spline interpolation type.
Definition: qwt_spline_local.h:35
QwtSplineLocal::Akima
@ Akima
Definition: qwt_spline_local.h:53
QwtSplineLocal::PChip
@ PChip
Definition: qwt_spline_local.h:62
QwtSplineLocal::ParabolicBlending
@ ParabolicBlending
Definition: qwt_spline_local.h:48
QwtSplineLocal::Cardinal
@ Cardinal
Definition: qwt_spline_local.h:42
QwtSplineLocal::~QwtSplineLocal
virtual ~QwtSplineLocal()
Destructor.
Definition: qwt_spline_local.cpp:461
QwtSplineLocal::type
Type type() const
Definition: qwt_spline_local.cpp:468
QwtSplineLocal::locality
virtual uint locality() const override
Definition: qwt_spline_local.cpp:552
QwtSplineLocal::painterPath
virtual QPainterPath painterPath(const QPolygonF &) const override
Interpolate a curve with Bezier curves.
Definition: qwt_spline_local.cpp:482
QwtSplineLocal::QwtSplineLocal
QwtSplineLocal(Type type)
Constructor.
Definition: qwt_spline_local.cpp:450
QwtSplineLocal::bezierControlLines
virtual QVector< QLineF > bezierControlLines(const QPolygonF &) const override
Interpolate a curve with Bezier curves.
Definition: qwt_spline_local.cpp:502
QwtSplineLocal::slopes
virtual QVector< double > slopes(const QPolygonF &) const override
Find the first derivative at the control points.
Definition: qwt_spline_local.cpp:521
QwtSplineLocal::polynomials
virtual QVector< QwtSplinePolynomial > polynomials(const QPolygonF &) const override
Calculate the interpolating polynomials for a non parametric spline.
Definition: qwt_spline_local.cpp:537
QwtSplineParametrization::ParameterX
@ ParameterX
Definition: qwt_spline_parametrization.h:54