Fastline series with simplification lazarus / 55-TAChart ---------------------------------------------------------------------- hedgehog · 2024-01-01 08:24 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 · 2024-01-02 11:33 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var P: TDoublePoint;...    with Source[i]^ do    begin      P := DoublePoint(X, Y);;      P := AxisToGraph(P);  // Deactivate this to ignore axis transformations      points[i] := ParentChart.GraphToImage(P);    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 · 2024-01-02 13:05 I will answer in several messages Quote from: wp on January 02, 2024, 12:33:53 pmAlthough 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 · 2024-01-02 13:22 Thanks for clarification. This sounds interesting. ---------------------------------------------------------------------- hedgehog · 2024-01-02 13:29 Quote from: wp on January 02, 2024, 12:33:53 pmWouldn'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 Quote from: wp linkI 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 · 2024-01-02 13:42 I changed your code a little. Added "noise" Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i     for i := 0 to Count-1 do      ListChartsource1.Add(i, sin(i/(Count-1)*2*pi)+(random(50)-100)/1000); In the screenshot you can see the difference. ---------------------------------------------------------------------- wp · 2024-01-02 14:30 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 · 2024-01-03 06:49 QuoteBut: 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 · 2024-01-03 08:59 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 · 2024-01-03 09:54 QuoteI'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. QuoteWhy 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 · 2024-01-03 11:17 Quote from: hedgehog on January 03, 2024, 10:54:21 amQuoteI'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 · 2024-01-03 14:12 QuoteWas mislead by the "fast" in the series name. Is there a better name? TSimplifyingLineSeries? TFilteredLineSeries? I don't mind. Let it be TFilteredLineSeries QuoteMaybe 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. QuoteI 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 · 2024-01-03 16:53 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 · 2024-01-09 15:05 Quote from: wp on January 03, 2024, 05:53:43 pmone 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 · 2024-01-09 15:44 Quote from: hedgehog on January 09, 2024, 04:05:26 pmQuote from: wp on January 03, 2024, 05:53:43 pmone 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 Quote from: hedgehog on January 09, 2024, 04:05:26 pmI 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. Quote from: hedgehog on January 09, 2024, 04:05:26 pmIn 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). ---------------------------------------------------------------------- hedgehog · 2024-01-10 11:15 My first idea: we could easily modify the Douglas-Peuker algorithm so that some points always end up in the final array. My second idea: don't draw polygons with a hole. You can sort all the polygons (by area value) and draw them starting with the largest. Quote from: wp on January 09, 2024, 04:44:21 pmI 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. function PointDist(...); deprecated; // use PointDist2 ??? ---------------------------------------------------------------------- wp · 2024-01-10 13:09 Quote from: hedgehog on January 10, 2024, 12:15:54 pmMy second idea: don't draw polygons with a hole. You can sort all the polygons (by area value) and draw them starting with the largest. This does not work when the background is non-uniform, a bitmap for example, because the bitmap should be visible through the hole. Quote from: wp on January 09, 2024, 04:44:21 pmI 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. Code: [Select]function PointDist(...); deprecated; // use PointDist2 ???Done, but named it PointDistSq rather than Point2. Same with PointLineDist. (https://wiki.freepascal.org/Lazarus_4.0_release_notes#TAChart_2) ---------------------------------------------------------------------- hedgehog · 2024-01-14 11:28 Quotewp I made a small demo (in attach). That is, it was surprising to me, but this method (Canvas.DrawPolygon) really works. As you can see in the screenshots, there is a hole! Even if polyline simplification works. You can see how the number of dots is dramatically reduced (by a factor of 100..1000), and yet the map remains recognizable. ---------------------------------------------------------------------- wp · 2024-01-14 13:56 Nice. And now I know why it's working, or better: I know the conditions when it's working: - The map provider must provide the outer and inner (and maybe more inner) polygons separately. - Each polygon must be closed. - The point order must flipped in each level of polygons, i.e. if the outer-most polygon is clockwise, the next inner polygon must be counter-clockwise, etc. The attachment contains a small project demonstrating the principle. The polygon order is not changed by the polygon simplification, and the fact that the polygon is closed is not changed either. Therefore, the hole remains after simplification. There is one issue left which prevents me from including this in TAChart. As I already said, it is not only the line series or polygon series which could benefit, an area series, a spline series and maybe some others might need it too and thus would have to duplicate the algorithm. This is not good. It would be better if the algorithm were implemented in the ChartSource which provides the data for the series. One idea how to do this: Create a new TFilteredChartSource (or a new option in TCalculatedChartsource, but this looks more complicated to me)This source gets a property Origin: TCustomChartSource to which the user must "hook" the original source containing the dataThis source gets in integer list in which all the data point indices from the original source will be stored which are included after the filtering process.The FilterChartSource must implement the filtering algorithm. It gets the data from the Origin source as pointers to TChartDataItem records (type TChartDataItem = record X, Y: Double; ...; end) and stores the accepted index in the mentioned list.As any other chartsoure, TFilteredChartSource must override the function GetItem(AIndex: Integer): PChartDataItem. AIndex is the data point index that the series wants to plot. The filtered source must lookup the original point index in its integer list and then finds the PChartDataItem under this index in the original source.One problem, maybe, of this approach: Since filtering is done on the original data the effect might be not be suitable for visual presentation. Suppose a time series in which the y data are plotted logarithmically... Maybe it's better to provide a filter directly in the series as "plug- in component" filter which operates on the points obtained after world-to-screen transformation. But something like this has not been provided in the TAChart infrastructure...