Fastline series with simplification

[hedgehog]

Hi!
Once upon a time, for one of my projects, I made a Fastline series for TAChart.
I recently added a polyline simplification feature.
Hope this will be useful for someone.
Criticism and suggestions are welcome.

I added a test project

[wp]

Although I did not fully understand your algorithm (what are this CalculateAngles and the Epsilon good for?) I guess that you try to reduce the number of datapoints. Could you explain the idea in a few sentences?

Wouldn't this better fit into the chart source than into the series? The advantage would be that the point elimination would have to be calculated only once (however, this would interfere with the need to probably repeat the calculation whenever the size or zoom level of the chart changes).

I modified your test project by plotting 2 millions of data points rather than just a few so that the speed can be measured. I used the same data points to plot also a standard TLineSeries for comparison. In the unfiltered mode there is a speed advantage of your fast line series by a factor 2-3 compared to TLineSeries, but TFastlineSeries becomes slower than TLineSeries when the filter is activated probably because the arctan2 needed for CalculateAngles is quite expensive.

TFastlineSeries calculates the image points by calling Chart.GraphToImage. But this ignores axis transformations. I thought that the following code (note the inserted AxisToGraph) would be better, but it causes a severe slow-down of the series:

Code: Pascal  [Select][+][-]

1. var P: TDoublePoint;
2. ...
3.     with Source[i]^ do
4.     begin
5.       P := DoublePoint(X, Y);;
6.       P := AxisToGraph(P);  // Deactivate this to ignore axis transformations
7.       points[i] := ParentChart.GraphToImage(P);
8.     end;  

Another problem is that when you zoom into the series (by dragging a smaller rectangle around the read of interest) the time to draw the series decreases in proportion to the number of still visible data points for the TLineSeries while the time to draw a zoomed view of the TFastlineseries remains constant. This is because you do not call PrepareGraphPoints which finds only those datapoints within the visible viewport.

[hedgehog]

I will answer in several messages

Although I did not fully understand your algorithm (what are this CalculateAngles and the Epsilon good for?) I guess that you try to reduce the number of datapoints. Could you explain the idea in a few sentences?

The main idea of my polyline simplification algorithm is in this screenshot.
The algorithm guarantees that all discarded points are located at a distance less than Epsilon from the drawn line.

[wp]

Thanks for clarification. This sounds interesting.

[hedgehog]

Wouldn't this better fit into the chart source than into the series? The advantage would be that the point elimination would have to be calculated only once (however, this would interfere with the need to probably repeat the calculation whenever the size or zoom level of the chart changes).

Firstly, I want to say that I am not at all an expert in TAChart

I modified your test project by plotting 2 millions of data points rather than just a few so that the speed can be measured. I used the same data points to plot also a standard TLineSeries for comparison. In the unfiltered mode there is a speed advantage of your fast line series by a factor 2-3 compared to TLineSeries, but TFastlineSeries becomes slower than TLineSeries when the filter is activated probably because the arctan2 needed for CalculateAngles is quite expensive.

Throwing out “extra” points is, of course, not an end in itself. There are many cases where "you can't see the forest for the trees".
For example, you need to draw a polyline of a million points on a 32*32 pixel bitmap, maintaining all trends.

Yes, Arctan is calculated twice for each point.
This is the price for the fact that the algorithm is one-pass.
The second time arctg is calculated for sufficiently small angles and is approximately equal to the value of the angle itself (in radians).
This can be optimized in the future.

[hedgehog]

I changed your code a little. Added "noise"

Code: Pascal  [Select][+][-]

1.     for i := 0 to Count-1 do
2.       ListChartsource1.Add(i, sin(i/(Count-1)*2*pi)+(random(50)-100)/1000);
3.  

In the screenshot you can see the difference.

[wp]

I see. The speed comes with the noise, i.e. when there is a quick variation of the "angles" from point to point. But: the optimum epsilon depends on the chart size and the zoom level. Proof: Run the modified demo, increase the Epsilon so that the noise in the left chart disappears, then increase the size of the form and the size of the charts along with it --> the noise returns. Or draw a small zoom rectangle around some part of the smoothed curve --> the broad noise band is back.

[hedgehog]

But: the optimum epsilon depends on the chart size and the zoom level.

Of course!
There is no ideal epsilon value!
This is a significant part of computer science.
Every year many articles, dissertations and other scientific works on this topic are published. (I'm keeping track of this a bit).

[wp]

But as a potential user of your series I'd be confused by a series looking differently when I change the size of the chart or when I zoom in. Why don't you do your calculation based on the graph coordinates (TDoublePoint) rather than on the image coordinates (TPoint)? Graph coordinates do not change when the chart size or zoom level changes.

[hedgehog]

I'd be confused by a series looking differently when I change the size of the chart or when I zoom in.

Yes, that's how it was intended.
Isn’t it natural that when you zoom in, you see new small details?
And on the contrary, when you zoom out, some points disappear, but information about the main trends remains.
Have you ever used a regular magnifying glass? It works exactly the same.

Why don't you do your calculation based on the graph coordinates (TDoublePoint) rather than on the image coordinates (TPoint)?

Yes, I understand what you're getting at.

There is one point here.

Simplification by TPoint (screen coordinates) is a universal function.
It does not matter how the set of points that need to be displayed is obtained (earthquake graph, cardiogram, Bitcoin rate, number of rabbits in Australia, etc.)

But, if we want to carry out a preliminary simplification of the original data set, then we must rely on the physical nature of this data set.
Optimal simplification of time series is different from simplification of GIS information.

And I think that preliminary simplification of the data set is not the task of the TChart component. This should be done by the developer based on the physical nature of his data set, and then sent to the TChart to show to the user.

[wp]

I'd be confused by a series looking differently when I change the size of the chart or when I zoom in.

Yes, that's how it was intended.
Isn’t it natural that when you zoom in, you see new small details?
And on the contrary, when you zoom out, some points disappear, but information about the main trends remains.
Have you ever used a regular magnifying glass? It works exactly the same.

Ah, I am slowly understanding what this series is intended for... Was mislead by the "fast" in the series name. Is there a better name? TSimplifyingLineSeries? TFilteredLineSeries?

And there are other series which may benefit from this feature, too. I am thinking of the TPolygonSeries which was primarily added having GIS in mind, and I remember how difficult it was to simplify GIS data in my Corona application to draw the country borders. Therefore, I am returning to the idea of putting this functionality into the ChartSource rather than the series so that all series using this source could benefit. Maybe a new TSimplifyingChartSource or TFilteredChartSource which gets the raw data from another ChartSource via an "Origin" property, or an extension of TCalculatedChartSource.

[hedgehog]

Was mislead by the "fast" in the series name. Is there a better name? TSimplifyingLineSeries? TFilteredLineSeries?

I don't mind. Let it be TFilteredLineSeries

Maybe a new TSimplifyingChartSource or TFilteredChartSource which gets the raw data from another ChartSource via an "Origin" property, or an extension of TCalculatedChartSource.

I note that the general purpose filtering feature for a data source can be dangerous.

I am thinking of the TPolygonSeries which was primarily added having GIS in mind, and I remember how difficult it was to simplify GIS data in my Corona application to draw the country borders.

I have attached two screenshots. This is the result of my modest attempts (please don't laugh)

[wp]

ok, I have to admit that there is one problem with the TPolygonSeries which makes it less suitable for your algorithm: In order to be able to draw polygons with holes the points must be provided in a special way so that not false structures are generated (see https://wiki.freepascal.org/Graphics_-_Working_with_TCanvas#Polygon_with_a_hole, https://wiki.freepascal.org/Graphics_-_Working_with_TCanvas#Polygon_with_several_holes).

[hedgehog]

one problem with the TPolygonSeries which makes it less suitable for your algorithm:
In order to be able to draw polygons with holes the points must be provided in a special way so that not false structures are generated

Can you be more specific? What are false structures?
I didn’t understand this from the Wiki pages you suggested (probably I’m not very smart).

At your suggestion, I renamed it. Now called TFilteredLineSeries. 
I also added three classic simplification algorithms: RadialDistance, DouglasPeucker, Opheim.
See attach.

P.S.
This probably shouldn't be written here, sorry.
In the unit "TAGeometry" there is a function "PointDist" (line 556).
The name hints that the function should return the distance between points.
But it returns the square of the distance.

[wp]

one problem with the TPolygonSeries which makes it less suitable for your algorithm:
In order to be able to draw polygons with holes the points must be provided in a special way so that not false structures are generated

Can you be more specific? What are false structures?

I mean the additional triangles in https://wiki.freepascal.org/images/9/90/Polygon_with_holes_1.png

I didn’t understand this from the Wiki pages you suggested (probably I’m not very smart).

GIS polygons must be able to display holes. In Germany, for example, there are the states Berlin and Brandenburg, and Berlin is fully enclosed within Brandenburg (https://en.wikipedia.org/wiki/Brandenburg), i.e. the state Brandenburg has an outer and an inner boundary. If I want to draw the state Brandenburg the drawing algorithmus must be able to draw a polygon with a hole for Berlin.

The standard Canvas Polygon method accepts only a single array of points as parameter but it is able to draw a hole when the points are arranged in a specific way: At first the outer polygon must be closed by repeating the starting point; the next point will be a point of the inner boundary, and the inner curve must be closed too, i.e. the last point must repeat the first point of the inner curve. Your polygon simplification routine, however, removes points from the polygon, and there is a chance that the control points which close the outer or inner curve are removed - in this case, the drawing will show artificial additional faces.

This issue could be avoided by splitting the single array of points into two subarrays - one for the inner curve, and one for the outer curve. And for painting these two subpolygons should be merged to a new single array duplicting the start points for each subpolygon as described so that the curve can be drawn correctly by the Canvas.Polygon method.

In the unit "TAGeometry" there is a function "PointDist" (line 556).
The name hints that the function should return the distance between points.
But it returns the square of the distance.

I know, it should probably have been named "PointDist2" or similar, but it is difficult to change because it will break the code of somebody who used it.

The reason why the square root is not calculated is that the function is used for comparing distances only, and comparing only the squared distances makes no difference (except that it is a bit faster than calculating the sqrt).