I tried an experiment with one channel run through the QwtWeedingCurveFitter and the other through the min/max weeding routine I have. With 1,000,000 samples the QwtWeedingCurveFitter with a tolerance of 50 (not sure if that's large or small) took about 20+ seconds to weed the 1,000,000 points to about 1557.
Could you please upload the data set somewhere - I would be interested in checking the DP implementation and playing with alternative algorithms ?
But in the end its obvious that you can implement a faster algorithm easily, when you know that a polygon has increasing x values ( maybe even equidistant ) only !
In general it might be a good idea to introduce an API where the user can pass the information, that the samples are ordered in one direction. At the moment there is only qwtUpperSampleIndex that could use this information, but several other operations could benefit from this information:
- clipping algorithm ( your ROI code would be obsolete )
- bounding rectangle calculation
- closest point lookups
- ...
If you are overloading the drawSeries() could you also restrict the to/from at this level also to solve the ROI data point reduction
Sure.
Maybe its worth to disable polygon clipping for situations, when the curve is vertically also inside of the visible area. But be careful with it as Qt renders before it clips what leads to a horrible performance when the points are far outside the visible area.
What is the magic code line for this ...
As said before: this is more interesting for oscilloscope alike plots that need high refresh rates. With having levels of detail the performance will be by far good enough.
But anyway here is the line:
plot->setCanvas( new QwtPlotGLCanvas() );
plot->setCanvas( new QwtPlotGLCanvas() );
To copy to clipboard, switch view to plain text mode
Uwe
I tried an experiment with one channel run through the QwtWeedingCurveFitter and the other through the min/max weeding routine I have. With 1,000,000 samples the QwtWeedingCurveFitter with a tolerance of 50 (not sure if that's large or small) took about 20+ seconds to weed the 1,000,000 points to about 1557.
Could you please upload the data set somewhere - I would be interested in checking the DP implementation and playing with alternative algorithms ?
But in the end its obvious that you can implement a faster algorithm easily, when you know that a polygon has increasing x values ( maybe even equidistant ) only !
In general it might be a good idea to introduce an API where the user can pass the information, that the samples are ordered in one direction. At the moment there is only qwtUpperSampleIndex that could use this information, but several other operations could benefit from this information:
- clipping algorithm ( your ROI code would be obsolete )
- bounding rectangle calculation
- closest point lookups
- ...
If you are overloading the drawSeries() could you also restrict the to/from at this level also to solve the ROI data point reduction
Sure.
Maybe its worth to disable polygon clipping for situations, when the curve is vertically also inside of the visible area. But be careful with it as Qt renders before it clips what leads to a horrible performance when the points are far outside the visible area.
What is the magic code line for this ...
As said before: this is more interesting for oscilloscope alike plots that need high refresh rates. With having levels of detail the performance will be by far good enough.
But anyway here is the line:
plot->setCanvas( new QwtPlotGLCanvas() );
plot->setCanvas( new QwtPlotGLCanvas() );
To copy to clipboard, switch view to plain text mode
Uwe
Added after 4 minutes:
Before it is forgotten: the performance of the Douglas-Peucker algorithm is not linear with increasing n ( worst case : O( n * n ) ).
So it should be possible to improve the performance heavily by splitting up your series in smaller chunks applying the algorithm for each of them. The price for this would be that you lose a possible optimization at the borders of the chunks - what leads to a result with a couple of points more ( depending on the number of chunks ).
Could you please compare your tests with the following code:
QPolygonF fitPolygon
( const QPolygonF
& points uint chunkSize,
double tolerance
) {
QwtWeedingCurveFitter fitter( tolerance );
for ( int i = 0; i < points.size(); i += chunkSize )
fittedPoints += fitter.fitCurve( points.mid( i, qMin( i + chunkSize, points.size() - 1 ) );
return fittedPoints;
}
QPolygonF fitPolygon( const QPolygonF& points uint chunkSize, double tolerance )
{
QwtWeedingCurveFitter fitter( tolerance );
QPolygonF fittedPoints;
for ( int i = 0; i < points.size(); i += chunkSize )
fittedPoints += fitter.fitCurve( points.mid( i, qMin( i + chunkSize, points.size() - 1 ) );
return fittedPoints;
}
To copy to clipboard, switch view to plain text mode
Uwe
Added after 6 minutes:
And finally it is possible to speed up the current implementation easily by eliminating the calls of qSqrt by comparing the squares instead.
Uwe
Bookmarks