View Issue Details

IDProjectCategoryView StatusLast Update
0035268LazarusTAChartpublic2019-04-05 11:38
ReporterMarcin WiazowskiAssigned Towp 
PrioritynormalSeverityminorReproducibilityalways
Status closedResolutionfixed 
Product Version2.1 (SVN)Product Build60763 
Target Version2.2Fixed in Version 
Summary0035268: TAChart: TCubicSplineSeries may omit some points when drawing
DescriptionHere comes a bug report, that I promised in 0035250.

Due to nature of the cubic spline interpolation, the interpolated curve crosses every existing data point. But, currently, TCubicSplineSeries doesn't guarantee this.

As described in detail in 0035250, TCubicSplineSeries - and also three other series classes - use an internal TIntervalList object when drawing. These are:
- TExpressionSeries - doesn't use a data source, so doesn't have any data points,
- TFuncSeries - as above,
- TFitSeries - uses data source for calculations, and the curve is allowed to run smoothly between data points,
- TCubicSplineSeries - uses data source for calculations, and the curve is required to cross every data point.

So the problem described here is specific to TCubicSplineSeries only, because only TCubicSplineSeries is required to cross every data point.




As described in detail in 0035250, TCubicSplineSeries has a Step property. When drawing the series, for every pixel on the horizontal axis (when Step = 1) / every second pixel on the horizontal axis (when Step = 2) / etc. / etc., function's Y value is calculated, and a straight line is drawn to the last calculated (X, Y) point; TIntervalList implements this behavior.

But this means, that - when there is a local data peak between two adjacent X pixels - this peak can be omitted when drawing; the attached Explanation.png shows this case.

This effect can be easily achieved in practice. For example, when horizontal axis' range is one week (604800 seconds) and chart's width is 1000 pixels, we have about 605 seconds (10 minutes) per one X pixel (assuming the most demanding setting Step = 1) - so peak in data, that lasts only 5 minutes, in many cases will be omitted - or drawn only partially. And, for the default TCubicSplineSeries' setting Step = 4, things are even worse.

The attached Reproduce application shows symptoms of the problem. Chart1 reproduces the behavior presented in Explanation.png. On Chart2, at the right side, we can see a strange effect for some chart widths - this is because horizontal axis' end is exactly at X = 1000, and X = 1000 is located somewhere between two pixels, so - in fact - function's value is calculated not for X = 1000, but for the last visible pixel, which may be for example at X = 1000.8 - and func(1000.8) is much greater than func(1000), so the curve finishes its drawing much higher than it should.




Thanks to changes introduced in 0035250, solution is quite simple: we may create an exclusion range - of width 0 - around every existing data point:

  for ...
    FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd])

This way, curve drawing will be ended - and then also restarted - exactly at each ( FX[i], func(FX[i]) ) point, where - because we are exactly at the data point - func(FX[i]) = FY[i]. So we will effectively visit every data point when drawing the curve - which is exactly what we needed.




Surprisingly, this still doesn't work properly. Short investigation shows, that TIntervalList reveals some unexpected behavior. Let's assume, that we defined two excluded ranges in TIntervalList:

  [10 .. 20] [30 .. 40]

Now we call TIntervalList.Intersect() to ask for a 0 .. 100 range.

Expected behavior: Intersect() returns a 10 .. 20 range - which means, that we should draw a line from X = 0 to X = 10, and then the next line should start at X = 20. Consecutive call to Intersect() should return a 30 .. 40 range, so the line should end at X = 30 and then the next-next line should start at X = 40.

Current behavior: Intersect() returns a 10 .. 40 range - which means, that we should draw a line from X = 0 to X = 10, and then the next line should start at X = 40.

This way, we omitted the 20 .. 30 range when drawing. The described behavior has been probably assumed to be an optimization when drawing: since we asked about range 0 .. 100, this probably means that our pixel N is at X = 0 and pixel N+1 is at X = 100 - so it may seem that there is no need to draw a line between X = 20 and X = 30.

In addition, making "AHint" parameter - that is passed to Intersect() call - larger than usual (although still in range), may change the returned range from 10 .. 40 to 30 .. 40 - this is definitely is a bug, since AHint is only to make the execution potentially faster, and not to change the returned result.




Fortunately, we can safely remove the described optimization. After removing, we will be also drawing the line between X = 20 and X = 30. In most cases, points (20, func(20)) and (30, func(30)) will be mapped to the same pixel on the chart, so MoveTo() and LineTo() calls will operate on the same pixel - which will effectively draw nothing for the X range from 20 to 30 - exactly as it is now.

But, sometimes, points (20, func(20)) and (30, func(30)) will be mapped to different pixels, so a line will be drawn - this will be for cases, when there is a large change in function's value between consecutive X pixels. For these cases, the line should really be drawn - exactly as in our TCubicSplineSeries example.

Currently, TAChart's code uses - internally - only two exclusion ranges: -INF .. FirstPointX and LastPointX .. +INF (for TFitSeries and TCubicSplineSeries). So the change will not affect currently existing TAChart's internals in any way.




And this is everything that is required, from the functional point of view, to solve the problem with drawing TCubicSplineSeries.

The attached patch1.diff implements the solution.




But it's good to take a look at one more thing: when drawing, many calls to TIntervalList.Intersect() are made - but this call is highly optimized. On the contrary, TIntervalList.AddRange() is not optimized in any way, so adding many data points is slow. The fix is quite simple: in TIntervalList.AddRange(), there are two "while" loops: one searches the already existing ranges from first to last, and the other from last to first. But, in all practical cases - including our TCubicSplineSeries case - ranges will be added in the ascending order, i.e. at the end of the currently existing range list. Making both the "while" loops working from the last to the first item, makes things dramatically faster.

The attached patch2.diff implements this improvement - and also fully includes patch1.diff.




There is still one thing to improve: in our case, each AddRange() call executes "SetLength(FIntervals, Length(FIntervals) + 1)", so memory is reallocated a lot of times. This is of course slow.

So the attached patch3.diff implements a commonly known "capacity" functionality - and also fully includes patch1.diff and patch2.diff.



====



There are some speed measurement applications attached here. Testing algorithm is:

0) Launch "IntervalsSpeedTest0and1and2" (it adds 50000 ranges to TIntervalList) without any patches.

1) Launch "IntervalsSpeedTest0and1and2" (it adds 50000 ranges to TIntervalList) with patch1.diff.

2) Launch "IntervalsSpeedTest0and1and2" (it adds 50000 ranges to TIntervalList) with patch2.diff.

Results on a low-end laptop:

0) 5820 ms
1) 5820 ms
2) 15 ms



3) Launch "IntervalsSpeedTest3" (it adds 2000000 ranges to TIntervalList) with patch3.diff.

Results on a low-end laptop:

3a) without using "capacity" feature (nevertheless, there are still much less memory reallocations than with patch2.diff): 2465 ms
3b) with using "capacity" feature (there are no memory reallocations at all): 125 ms



4a) Launch "DrawingSpeedTest" without any patches.

4b) Launch "DrawingSpeedTest" with patch3.diff.

Results on a low-end laptop:

4a) 3.28 ms per drawing
4b) 5.00 ms per drawing

"DrawingSpeedTest" uses 2000000 data points, but displays only about 500 of them due to horizontal axis' Range settings - this simulates a situation, when we have many data points collected (for example from few years), but display only some subrange of them (for example only from one week). Drawing is repeated 100 times and the result is averaged. There is a noticeable difference in drawing speed between 4a) - where TIntervalList holds 2 ranges, i.e from -INF to 1 and from 2000000 to +INF, and 4b) - where TIntervalList holds 2000000 ranges, but the difference is acceptable. This means, that internally executed TIntervalList.Intersect() calls, even when operating on 2000000 ranges, are still optimized enough to not introduce too much slow down.



As expected, the best solution is patch3.diff.
TagsNo tags attached.
Fixed in Revision60785, 60788, 60791, 60809, 60819, 60820, 60821
LazTarget2.2
WidgetsetWin32/Win64
Attached Files
  • Reproduce.zip (2,784 bytes)
  • Reproduce.gif (63,293 bytes)
    Reproduce.gif (63,293 bytes)
  • Explanation.png (10,186 bytes)
    Explanation.png (10,186 bytes)
  • IntervalsSpeedTest0and1and2.zip (2,513 bytes)
  • IntervalsSpeedTest3.zip (2,476 bytes)
  • DrawingSpeedTest.zip (2,829 bytes)
  • patch1.diff (3,651 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60763)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -774,14 +774,12 @@
     
     function TIntervalList.Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
    -var
    -  fi, li: Integer;
     begin
       Result := false;
    -  if Length(FIntervals) = 0 then exit;
    +  if (Length(FIntervals) = 0) or (ALeft > ARight) then exit;
     
       AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
    +  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
         Dec(AHint);
     
       while
    @@ -788,17 +786,12 @@
         (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
       do begin
         if FIntervals[AHint].FEnd > ALeft then begin
    -      if not Result then fi := AHint;
    -      li := AHint;
    -      Result := true;
    +      ALeft := FIntervals[AHint].FStart;
    +      ARight := FIntervals[AHint].FEnd;
    +      exit(true);
         end;
         Inc(AHint);
       end;
    -
    -  if Result then begin
    -    ALeft := FIntervals[fi].FStart;
    -    ARight := FIntervals[li].FEnd;
    -  end;
     end;
     
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60763)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -1312,13 +1312,29 @@
     end;
     
     procedure TCubicSplineSeries.TSpline.PrepareIntervals;
    +var
    +  i: Integer;
     begin
       FIntervals := TIntervalList.Create;
       try
    +    // Cubic spline interpolation is required to cross each data point.
    +    // To guarantee this when drawing, we create an exclusion range -
    +    // of width 0 - around each data point. Thanks to this, series line
    +    // will be finished - and then restarted - exactly at each data point,
    +    // even when data point's X value is located somewhere between pixels.
    +
         if not (csoExtrapolateLeft in FOwner.Options) then
    -      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
    +
    +    for i := 1 to High(FX) - 1 do
    +      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
    +
         if not (csoExtrapolateRight in FOwner.Options) then
    -      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
       except
         FreeAndNil(FIntervals);
         raise;
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60763)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -151,6 +151,23 @@
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(501.0, l);
       AssertEquals(502.0, r);
    +  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
    +
    +  FIList.Clear;
    +  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
    +  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 0;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 1;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    patch1.diff (3,651 bytes)
  • patch2.diff (4,625 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60763)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -715,16 +715,24 @@
       if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
       if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
       if AStart > AEnd then exit;
    -  i := 0;
    -  while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
    -    i += 1;
    +
    +  // In most cases we will be adding ranges in the ascending order,
    +  // so the code here is optimized for this case
    +
    +  // Find index of the first interval, having its FEnd >= AStart
    +  i := High(FIntervals) + 1;
    +  while (i > 0) and (FIntervals[i-1].FEnd >= AStart) do
    +    i -= 1;
       if i <= High(FIntervals) then
         AStart := Min(AStart, FIntervals[i].FStart);
    +
    +  // Find index of the last interval, having its FStart <= AEnd
       j := High(FIntervals);
       while (j >= 0) and (FIntervals[j].FStart > AEnd) do
         j -= 1;
       if j >= 0 then
         AEnd := Max(AEnd, FIntervals[j].FEnd);
    +
       if i < j then begin
         for k := j + 1 to High(FIntervals) do
           FIntervals[i + k - j] := FIntervals[j];
    @@ -774,14 +782,12 @@
     
     function TIntervalList.Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
    -var
    -  fi, li: Integer;
     begin
       Result := false;
    -  if Length(FIntervals) = 0 then exit;
    +  if (Length(FIntervals) = 0) or (ALeft > ARight) then exit;
     
       AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
    +  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
         Dec(AHint);
     
       while
    @@ -788,17 +794,12 @@
         (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
       do begin
         if FIntervals[AHint].FEnd > ALeft then begin
    -      if not Result then fi := AHint;
    -      li := AHint;
    -      Result := true;
    +      ALeft := FIntervals[AHint].FStart;
    +      ARight := FIntervals[AHint].FEnd;
    +      exit(true);
         end;
         Inc(AHint);
       end;
    -
    -  if Result then begin
    -    ALeft := FIntervals[fi].FStart;
    -    ARight := FIntervals[li].FEnd;
    -  end;
     end;
     
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60763)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -1312,13 +1312,29 @@
     end;
     
     procedure TCubicSplineSeries.TSpline.PrepareIntervals;
    +var
    +  i: Integer;
     begin
       FIntervals := TIntervalList.Create;
       try
    +    // Cubic spline interpolation is required to cross each data point.
    +    // To guarantee this when drawing, we create an exclusion range -
    +    // of width 0 - around each data point. Thanks to this, series line
    +    // will be finished - and then restarted - exactly at each data point,
    +    // even when data point's X value is located somewhere between pixels.
    +
         if not (csoExtrapolateLeft in FOwner.Options) then
    -      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
    +
    +    for i := 1 to High(FX) - 1 do
    +      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
    +
         if not (csoExtrapolateRight in FOwner.Options) then
    -      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
       except
         FreeAndNil(FIntervals);
         raise;
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60763)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -151,6 +151,23 @@
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(501.0, l);
       AssertEquals(502.0, r);
    +  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
    +
    +  FIList.Clear;
    +  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
    +  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 0;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 1;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    patch2.diff (4,625 bytes)
  • patch3.diff (7,518 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60763)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -126,10 +126,13 @@
       private
         FEpsilon: Double;
         FIntervals: array of TDoubleInterval;
    +    FIntervalCount: Integer;
         FOnChange: TNotifyEvent;
         procedure Changed;
         function GetInterval(AIndex: Integer): TDoubleInterval;
    -    function GetIntervalCount: Integer;
    +    function GetIntervalCapacity: Integer; inline;
    +    procedure GrowIntervals;
    +    procedure SetIntervalCapacity(AValue: Integer);
         procedure SetOnChange(AValue: TNotifyEvent);
       public
         procedure Assign(ASource: TIntervalList);
    @@ -143,7 +146,8 @@
       public
         property Epsilon: Double read FEpsilon write FEpsilon;
         property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
    -    property IntervalCount: Integer read GetIntervalCount;
    +    property IntervalCount: Integer read FIntervalCount;
    +    property IntervalCapacity: Integer read GetIntervalCapacity write SetIntervalCapacity;
         property OnChange: TNotifyEvent read FOnChange write SetOnChange;
       end;
     
    @@ -715,24 +719,32 @@
       if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
       if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
       if AStart > AEnd then exit;
    -  i := 0;
    -  while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
    -    i += 1;
    -  if i <= High(FIntervals) then
    +
    +  // In most cases we will be adding ranges in the ascending order,
    +  // so the code here is optimized for this case
    +
    +  // Find index of the first interval, having its FEnd >= AStart
    +  i := FIntervalCount; // not FIntervalCount - 1 !
    +  while (i > 0) and (FIntervals[i-1].FEnd >= AStart) do
    +    i -= 1;
    +  if i < FIntervalCount then
         AStart := Min(AStart, FIntervals[i].FStart);
    -  j := High(FIntervals);
    +
    +  // Find index of the last interval, having its FStart <= AEnd
    +  j := FIntervalCount - 1;
       while (j >= 0) and (FIntervals[j].FStart > AEnd) do
         j -= 1;
       if j >= 0 then
         AEnd := Max(AEnd, FIntervals[j].FEnd);
    +
       if i < j then begin
    -    for k := j + 1 to High(FIntervals) do
    +    for k := j + 1 to FIntervalCount - 1 do
           FIntervals[i + k - j] := FIntervals[j];
    -    SetLength(FIntervals, Length(FIntervals) - j + i);
    +    Dec(FIntervalCount, j - i);
       end
       else if i > j then begin
    -    SetLength(FIntervals, Length(FIntervals) + 1);
    -    for k := High(FIntervals) downto i + 1 do
    +    GrowIntervals;
    +    for k := FIntervalCount - 1 downto i + 1 do
           FIntervals[k] := FIntervals[k - 1];
       end;
       FIntervals[i] := DoubleInterval(AStart, AEnd);
    @@ -743,6 +755,7 @@
     begin
       FEpsilon := ASource.FEpsilon;
       FIntervals := Copy(ASource.FIntervals);
    +  FIntervalCount := ASource.FIntervalCount;
     end;
     
     procedure TIntervalList.Changed;
    @@ -753,6 +766,7 @@
     
     procedure TIntervalList.Clear;
     begin
    +  FIntervalCount := 0;
       FIntervals := nil;
       Changed;
     end;
    @@ -764,41 +778,52 @@
     
     function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
     begin
    +  if not InRange(AIndex, 0, FIntervalCount - 1) then
    +    raise EChartError.CreateFmt('[%s.%s] Index out of range.', [ClassName, 'GetInterval']);
       Result := FIntervals[AIndex];
     end;
     
    -function TIntervalList.GetIntervalCount: Integer;
    +function TIntervalList.GetIntervalCapacity: Integer; inline;
     begin
       Result := Length(FIntervals);
     end;
     
    +procedure TIntervalList.SetIntervalCapacity(AValue: Integer);
    +begin
    +  if AValue > Length(FIntervals) then
    +    SetLength(FIntervals, AValue);
    +end;
    +
    +procedure TIntervalList.GrowIntervals;
    +begin
    +  Inc(FIntervalCount);
    +  if FIntervalCount > Length(FIntervals) then
    +    if FIntervalCount < 8 then
    +      SetLength(FIntervals, 8)
    +    else
    +      SetLength(FIntervals, Min((FIntervalCount - 1) * 2, FIntervalCount + 8191));
    +end;
    +
     function TIntervalList.Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
    -var
    -  fi, li: Integer;
     begin
       Result := false;
    -  if Length(FIntervals) = 0 then exit;
    +  if (FIntervalCount = 0) or (ALeft > ARight) then exit;
     
    -  AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
    +  AHint := EnsureRange(AHint, 0, FIntervalCount - 1);
    +  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
         Dec(AHint);
     
       while
    -    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
    +    (AHint < FIntervalCount) and (FIntervals[AHint].FStart < ARight)
       do begin
         if FIntervals[AHint].FEnd > ALeft then begin
    -      if not Result then fi := AHint;
    -      li := AHint;
    -      Result := true;
    +      ALeft := FIntervals[AHint].FStart;
    +      ARight := FIntervals[AHint].FEnd;
    +      exit(true);
         end;
         Inc(AHint);
       end;
    -
    -  if Result then begin
    -    ALeft := FIntervals[fi].FStart;
    -    ARight := FIntervals[li].FEnd;
    -  end;
     end;
     
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60763)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -1,4 +1,4 @@
    -{
    +{
     
      Function series for TAChart.
     
    @@ -1312,13 +1312,31 @@
     end;
     
     procedure TCubicSplineSeries.TSpline.PrepareIntervals;
    +var
    +  i: Integer;
     begin
       FIntervals := TIntervalList.Create;
       try
    +    // Cubic spline interpolation is required to cross each data point.
    +    // To guarantee this when drawing, we create an exclusion range -
    +    // of width 0 - around each data point. Thanks to this, series line
    +    // will be finished - and then restarted - exactly at each data point,
    +    // even when data point's X value is located somewhere between pixels.
    +
    +    FIntervals.IntervalCapacity := Length(FX);
    +
         if not (csoExtrapolateLeft in FOwner.Options) then
    -      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
    +
    +    for i := 1 to High(FX) - 1 do
    +      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
    +
         if not (csoExtrapolateRight in FOwner.Options) then
    -      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
    +      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
    +    else
    +      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
       except
         FreeAndNil(FIntervals);
         raise;
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60763)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -151,6 +151,23 @@
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(501.0, l);
       AssertEquals(502.0, r);
    +  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
    +
    +  FIList.Clear;
    +  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
    +  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 0;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
    +  l := 0.0;
    +  r := 100.0;
    +  hint := 1;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(10.0, l);
    +  AssertEquals(20.0, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    patch3.diff (7,518 bytes)
  • DrawingSpeedTestNaN.zip (2,904 bytes)
  • Extrapolation.zip (2,478 bytes)
  • Extrapolation.png (23,526 bytes)
    Extrapolation.png (23,526 bytes)
  • update.diff (8,386 bytes)
    Index: components/tachart/tacustomfuncseries.pas
    ===================================================================
    --- components/tachart/tacustomfuncseries.pas	(revision 60792)
    +++ components/tachart/tacustomfuncseries.pas	(working copy)
    @@ -297,7 +297,11 @@
     { TPointsDrawFuncHelper }
     
     type
    -  TBasicPointSeriesAccess = class(TBasicPointSeries);
    +  TBasicPointSeriesAccess = class(TBasicPointSeries)
    +  public
    +    property GraphPoints: TDoublePointArray read FGraphPoints;
    +    property LoBound: Integer read FLoBound;
    +  end;
     
     constructor TPointsDrawFuncHelper.Create(
       ASeries: TBasicPointSeries; AMinX, AMaxX: Double; AStartIndex: Integer;
    @@ -325,13 +329,13 @@
         );
     
       ser := TBasicPointSeriesAccess(FSeries);
    -  n := Length(ser.FGraphPoints);
    +  n := Length(ser.GraphPoints);
       dx := abs(FGraphStep);
     
       xa := FAxisToGraphXr(AXg);
    -  j := FStartIndex - ser.FLoBound;
    -  while (j < n) and (xa > ser.FGraphPoints[j].X) do inc(j);
    -  if j < n then xfg := ser.FGraphPoints[j].X else exit;
    +  j := FStartIndex - ser.LoBound;
    +  while (j < n) and (xa > ser.GraphPoints[j].X) do inc(j);
    +  if j < n then xfg := ser.GraphPoints[j].X else exit;
       AOnMoveTo(AXg, xa);
     
       while AXg < AXMax do begin
    @@ -339,10 +343,10 @@
         xa1 := FGraphToAxisXr(xg1);
         if (j >= 0) and (xg1 > xfg) then begin
           xg1 := xfg;
    -      xa1 := ser.GetXValue(j + ser.FLoBound);
    +      xa1 := ser.GetXValue(j + ser.LoBound);
           inc(j);
    -      while (j < n) and (xfg > ser.FGraphPoints[j].X) do inc(j);   // skip unordered points
    -      if j < n then xfg := ser.FGraphPoints[j].X else xfg := Infinity;
    +      while (j < n) and (xfg > ser.GraphPoints[j].X) do inc(j);   // skip unordered points
    +      if j < n then xfg := ser.GraphPoints[j].X else xfg := Infinity;
         end;
         AOnLineTo(xg1, xa1);
         AXg := xg1;
    Index: components/tachart/tacustomseries.pas
    ===================================================================
    --- components/tachart/tacustomseries.pas	(revision 60792)
    +++ components/tachart/tacustomseries.pas	(working copy)
    @@ -279,8 +279,7 @@
         procedure SetPointer(AValue: TSeriesPointer);
         procedure SetStacked(AValue: Boolean);
         procedure SetStackedNaN(AValue: TStackedNaN);
    -  //strict
    -  protected
    +  strict protected
         FGraphPoints: array of TDoublePoint;
         FLoBound: Integer;
         FMinXRange: Double;
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60792)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -208,10 +208,11 @@
         procedure SetStep(AValue: TFuncSeriesStep);
       strict private
       type
    +    TArbFloatArray = array of ArbFloat;
         TSpline = class
         public
           FOwner: TCubicSplineSeries;
    -      FCoeff, FX, FY: array of ArbFloat;
    +      FCoeff, FX, FY: TArbFloatArray;
           FIntervals: TIntervalList;
           FIsUnorderedX: Boolean;
           FStartIndex: Integer;
    @@ -220,13 +221,14 @@
           function Calculate(AX: Double): Double;
           function IsFewPoints: Boolean; inline;
           function PrepareCoeffs(
    -        ASource: TCustomChartSource; var AIndex: Integer): Boolean;
    +        ASource: TCustomChartSource; var AIndex: Integer;
    +        var FXCache, FYCache: TArbFloatArray): Boolean;
         end;
     
       var
         FSplines: array of TSpline;
         procedure FreeSplines;
    -    procedure GetSplineXRange(ASpline: TSpline; out AXMin, AXMax: Double);
    +    function GetSplineXRange(ASpline: TSpline; out AXMin, AXMax: Double): Boolean;
         function IsUnorderedVisible: Boolean; inline;
         procedure PrepareCoeffs;
         procedure SetBadDataPen(AValue: TBadDataChartPen);
    @@ -1273,14 +1275,11 @@
     end;
     
     function TCubicSplineSeries.TSpline.PrepareCoeffs(
    -  ASource: TCustomChartSource; var AIndex: Integer): Boolean;
    +  ASource: TCustomChartSource; var AIndex: Integer;
    +  var FXCache, FYCache: TArbFloatArray): Boolean;
     var
       n, ok: Integer;
     begin
    -  n := ASource.Count - AIndex;
    -  SetLength(FX, n);
    -  SetLength(FY, n);
    -  SetLength(FCoeff, n);
       FIsUnorderedX := false;
       while (AIndex < ASource.Count) and IsNan(ASource[AIndex]^.Point) do
         AIndex += 1;
    @@ -1288,17 +1287,17 @@
       n := 0;
       while (AIndex < ASource.Count) and not IsNan(ASource[AIndex]^.Point) do begin
         with ASource[AIndex]^ do
    -      if (n > 0) and (FX[n - 1] >= X) then
    +      if (n > 0) and (FXCache[n - 1] >= X) then
             FIsUnorderedX := true
           else begin
    -        FX[n] := X;
    -        FY[n] := Y;
    +        FXCache[n] := X;
    +        FYCache[n] := Y;
             n += 1;
           end;
         AIndex += 1;
       end;
    -  SetLength(FX, n);
    -  SetLength(FY, n);
    +  FX := Copy(FXCache, 0, n);
    +  FY := Copy(FYCache, 0, n);
       SetLength(FCoeff, n);
       if n = 0 then exit(false);
       if IsFewPoints then exit(true);
    @@ -1319,8 +1318,11 @@
     begin
       if ASource is TCubicSplineSeries then
         with TCubicSplineSeries(ASource) do begin
    +      Self.BadDataPen := FBadDataPen;
    +      Self.Options := FOptions;
           Self.Pen := FPen;
    -      Self.FStep := FStep;
    +      Self.SplineType := FSplineType;
    +      Self.Step := FStep;
         end;
       inherited Assign(ASource);
     end;
    @@ -1350,6 +1352,7 @@
       FPen.OnChange := @StyleChanged;
       FPointer := TSeriesPointer.Create(ParentChart);
       FStep := DEF_SPLINE_STEP;
    +  FCachedExtent := EmptyExtent;
     end;
     
     destructor TCubicSplineSeries.Destroy;
    @@ -1375,8 +1378,7 @@
           if not Pen.EffVisible then exit;
           ADrawer.Pen := Pen;
         end;
    -    GetSplineXRange(ASpline, xmin, xmax);
    -    if xmin > xmax then
    +    if not GetSplineXRange(ASpline, xmin, xmax) then
           exit;
         with TPointsDrawFuncHelper.Create(Self, xmin, xmax, ASpline.FStartIndex, @ASpline.Calculate, Step) do
           try
    @@ -1417,7 +1419,7 @@
       if SplineType = cstHermiteMonotone then
         exit;
     
    -  if not (FCachedExtent = EmptyExtent) then begin
    +  if FCachedExtent <> EmptyExtent then begin
         Result := FCachedExtent;
         exit;
       end;
    @@ -1488,9 +1490,8 @@
           if s.IsFewPoints or (s.FIsUnorderedX and not IsUnorderedVisible) then
             continue;
     
    -      GetSplineXRange(s, xmin, xmax);
    -      if xmax > xmin then
    -        exit;
    +      if not GetSplineXRange(s, xmin, xmax) then
    +        continue;
           with TPointsDrawFuncHelper.Create(Self, xmin, xmax, s.FStartIndex, @s.Calculate, Step) do
             try
               if not GetNearestPoint(AParams, r) or
    @@ -1507,20 +1508,27 @@
       end;
     end;
     
    -procedure TCubicSplineSeries.GetSplineXRange(ASpline: TSpline;
    -  out AXMin, AXMax: Double);
    +function TCubicSplineSeries.GetSplineXRange(ASpline: TSpline;
    +  out AXMin, AXMax: Double): Boolean;
     var
       ext: TDoubleRect;
     begin
       ext := FChart.CurrentExtent;
    -  AXmin := IfThen(
    -    (csoExtrapolateLeft in FOptions) and (ASpline = FSplines[0]),
    -    ext.a.x, Max(ext.a.x, AxisToGraphX(ASpline.FX[0]))
    -  );
    -  AXmax := IfThen(
    -    (csoExtrapolateRight in FOptions) and (ASpline = FSplines[High(FSplines)]),
    -    ext.b.x, Min(ext.b.x, AxisToGraphX(ASpline.FX[High(ASpline.FX)]))
    -  );
    +
    +  if csoExtrapolateLeft in FOptions then
    +    AXmin := ext.a.x
    +  else
    +    AXmin := Max(ext.a.x, AxisToGraphX(ASpline.FX[0]));
    +
    +  if AXmin > ext.b.x then
    +    exit(false);
    +
    +  if csoExtrapolateRight in FOptions then
    +    AXmax := ext.b.x
    +  else
    +    AXmax := Min(ext.b.x, AxisToGraphX(ASpline.FX[High(ASpline.FX)]));
    +
    +  Result := AXMin <= AXMax;
     end;
     
     function TCubicSplineSeries.IsUnorderedVisible: Boolean;
    @@ -1532,17 +1540,26 @@
     var
       i: Integer = 0;
       s: TSpline;
    +  FSplinesLength: Integer = 0;
    +  FXCache, FYCache: array of ArbFloat;
     begin
       FreeSplines;
    -  while i < Source.Count do begin
    -    s := TSpline.Create(self);
    -    if s.PrepareCoeffs(Source, i) then begin
    -      //s.PrepareIntervals;
    -      SetLength(FSplines, Length(FSplines) + 1);
    -      FSplines[High(FSplines)] := s;
    -    end
    -    else
    -      s.Free;
    +  try
    +    SetLength(FXCache, Source.Count);
    +    SetLength(FYCache, Source.Count);
    +    while i < Source.Count do begin
    +      s := TSpline.Create(self);
    +      if s.PrepareCoeffs(Source, i, FXCache, FYCache) then begin
    +        if FSplinesLength >= Length(FSplines) then
    +          SetLength(FSplines, FSplinesLength + 1024);
    +        FSplines[FSplinesLength] := s;
    +        Inc(FSplinesLength);
    +      end
    +      else
    +        s.Free;
    +    end;
    +  finally
    +    SetLength(FSplines, FSplinesLength);
       end;
     end;
     
    
    update.diff (8,386 bytes)
  • Assign.zip (2,534 bytes)
  • test.diff (3,401 bytes)
    Index: components/tachart/tacustomseries.pas
    ===================================================================
    --- components/tachart/tacustomseries.pas	(revision 60818)
    +++ components/tachart/tacustomseries.pas	(working copy)
    @@ -79,6 +79,7 @@
         procedure SetParentComponent(AParent: TComponent); override;
     
       strict protected
    +    FPropUpdateCount: Integer;
         // Set series bounds in axis coordinates.
         // Some or all bounds may be left unset, in which case they will be ignored.
         procedure GetBounds(var ABounds: TDoubleRect); virtual; abstract;
    @@ -110,6 +111,9 @@
         procedure Assign(ASource: TPersistent); override;
         constructor Create(AOwner: TComponent); override;
         destructor Destroy; override;
    +    procedure BeginPropUpdate; virtual;
    +    procedure EndPropUpdate; virtual;
    +    function IsPropUpdating: Boolean; inline;
         function GetNearestPoint(
           const AParams: TNearestPointParams;
           out AResults: TNearestPointResults): Boolean; virtual;
    @@ -435,6 +439,23 @@
       inherited;
     end;
     
    +procedure TCustomChartSeries.BeginPropUpdate;
    +begin
    +  Inc(FPropUpdateCount);
    +end;
    +
    +procedure TCustomChartSeries.EndPropUpdate;
    +begin
    +  Dec(FPropUpdateCount);
    +  if FPropUpdateCount > 0 then exit;
    +  UpdateParentChart;
    +end;
    +
    +function TCustomChartSeries.IsPropUpdating: Boolean; inline;
    +begin
    +  Result := FPropUpdateCount > 0;
    +end;
    +
     function TCustomChartSeries.GetAxisBounds(AAxis: TChartAxis;
       out AMin, AMax: Double): Boolean;
     var
    @@ -720,8 +741,9 @@
     
     procedure TCustomChartSeries.UpdateParentChart;
     begin
    -  if ParentChart <> nil then
    -    ParentChart.StyleChanged(Self);
    +  if not IsPropUpdating then
    +    if ParentChart <> nil then
    +      ParentChart.StyleChanged(Self);
     end;
     
     { TChartSeries }
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60818)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -1271,7 +1271,7 @@
     
     function TCubicSplineSeries.TSpline.IsFewPoints: Boolean;
     begin
    -  Result := Length(FOwner.FX) < 2;
    +  Result := FLastCacheIndex <= FFirstCacheIndex;
     end;
     
     function TCubicSplineSeries.TSpline.PrepareCoeffs(ASource: TCustomChartSource;
    @@ -1296,7 +1296,7 @@
         ASourceIndex += 1;
       end;
       FLastCacheIndex := ACacheIndex - 1;
    -  if FLastCacheIndex = FFirstCacheIndex then exit(false);
    +  if FLastCacheIndex < FFirstCacheIndex then exit(false);
       if IsFewPoints then exit(true);
       ok := 0;
       n := ACacheIndex - FFirstCacheIndex;
    @@ -1315,15 +1315,20 @@
     
     procedure TCubicSplineSeries.Assign(ASource: TPersistent);
     begin
    -  if ASource is TCubicSplineSeries then
    -    with TCubicSplineSeries(ASource) do begin
    -      Self.BadDataPen.Assign(FBadDataPen);
    -      Self.FOptions := FOptions;
    -      Self.FPen.Assign(FPen);
    -      Self.FSplineType := FSplineType;
    -      Self.FStep := FStep;
    -    end;
    -  inherited Assign(ASource);
    +  BeginPropUpdate;
    +  try
    +    if ASource is TCubicSplineSeries then
    +      with TCubicSplineSeries(ASource) do begin
    +        Self.BadDataPen := FBadDataPen;
    +        Self.Options := FOptions;
    +        Self.Pen := FPen;
    +        Self.SplineType := FSplineType;
    +        Self.Step := FStep;
    +      end;
    +    inherited Assign(ASource);
    +  finally
    +    EndPropUpdate;
    +  end;
     end;
     
     function TCubicSplineSeries.Calculate(AX: Double): Double;
    
    test.diff (3,401 bytes)
  • improvement.diff (1,206 bytes)
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60820)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -1541,22 +1541,31 @@
     var
       i: Integer = 0;
       j: Integer = 0;
    +  sCount: Integer = 0;
       s: TSpline;
     begin
       FreeSplines;
       SetLength(FX, Source.Count);
       SetLength(FY, Source.Count);
    -  while i < Source.Count do begin
    -    s := TSpline.Create(self);
    -    if s.PrepareCoeffs(Source, i, j) then begin
    -      SetLength(FSplines, Length(FSplines) + 1);
    -      FSplines[High(FSplines)] := s;
    -    end
    -    else
    -      s.Free;
    +  SetLength(FSplines, Source.Count);
    +  try
    +    while i < Source.Count do begin
    +      s := TSpline.Create(self);
    +      try
    +        if s.PrepareCoeffs(Source, i, j) then begin
    +          FSplines[sCount] := s;
    +          s := nil;
    +          sCount += 1;
    +        end;
    +      finally
    +        s.Free;
    +      end;
    +    end;
    +    SetLength(FX, j);
    +    SetLength(FY, j);
    +  finally
    +    SetLength(FSplines, sCount);
       end;
    -  SetLength(FX, j);
    -  SetLength(FY, j);
     end;
     
     procedure TCubicSplineSeries.SetBadDataPen(AValue: TBadDataChartPen);
    
    improvement.diff (1,206 bytes)

Relationships

related to 0035313 closedwp TAChart: added caching for cumulative and list extents 

Activities

Marcin Wiazowski

2019-03-24 20:06

reporter  

Reproduce.zip (2,784 bytes)

Marcin Wiazowski

2019-03-24 20:07

reporter  

Reproduce.gif (63,293 bytes)
Reproduce.gif (63,293 bytes)

Marcin Wiazowski

2019-03-24 20:07

reporter  

Explanation.png (10,186 bytes)
Explanation.png (10,186 bytes)

Marcin Wiazowski

2019-03-24 20:08

reporter  

IntervalsSpeedTest0and1and2.zip (2,513 bytes)

Marcin Wiazowski

2019-03-24 20:08

reporter  

IntervalsSpeedTest3.zip (2,476 bytes)

Marcin Wiazowski

2019-03-24 20:08

reporter  

DrawingSpeedTest.zip (2,829 bytes)

Marcin Wiazowski

2019-03-24 20:08

reporter  

patch1.diff (3,651 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60763)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -774,14 +774,12 @@
 
 function TIntervalList.Intersect(
   var ALeft, ARight: Double; var AHint: Integer): Boolean;
-var
-  fi, li: Integer;
 begin
   Result := false;
-  if Length(FIntervals) = 0 then exit;
+  if (Length(FIntervals) = 0) or (ALeft > ARight) then exit;
 
   AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
+  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
     Dec(AHint);
 
   while
@@ -788,17 +786,12 @@
     (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
   do begin
     if FIntervals[AHint].FEnd > ALeft then begin
-      if not Result then fi := AHint;
-      li := AHint;
-      Result := true;
+      ALeft := FIntervals[AHint].FStart;
+      ARight := FIntervals[AHint].FEnd;
+      exit(true);
     end;
     Inc(AHint);
   end;
-
-  if Result then begin
-    ALeft := FIntervals[fi].FStart;
-    ARight := FIntervals[li].FEnd;
-  end;
 end;
 
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60763)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -1312,13 +1312,29 @@
 end;
 
 procedure TCubicSplineSeries.TSpline.PrepareIntervals;
+var
+  i: Integer;
 begin
   FIntervals := TIntervalList.Create;
   try
+    // Cubic spline interpolation is required to cross each data point.
+    // To guarantee this when drawing, we create an exclusion range -
+    // of width 0 - around each data point. Thanks to this, series line
+    // will be finished - and then restarted - exactly at each data point,
+    // even when data point's X value is located somewhere between pixels.
+
     if not (csoExtrapolateLeft in FOwner.Options) then
-      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
+
+    for i := 1 to High(FX) - 1 do
+      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
+
     if not (csoExtrapolateRight in FOwner.Options) then
-      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
   except
     FreeAndNil(FIntervals);
     raise;
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60763)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -151,6 +151,23 @@
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(501.0, l);
   AssertEquals(502.0, r);
+  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
+
+  FIList.Clear;
+  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
+  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
+  l := 0.0;
+  r := 100.0;
+  hint := 0;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
+  l := 0.0;
+  r := 100.0;
+  hint := 1;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
 end;
 
 procedure TIntervalListTest.Merge;
patch1.diff (3,651 bytes)

Marcin Wiazowski

2019-03-24 20:08

reporter  

patch2.diff (4,625 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60763)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -715,16 +715,24 @@
   if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
   if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
   if AStart > AEnd then exit;
-  i := 0;
-  while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
-    i += 1;
+
+  // In most cases we will be adding ranges in the ascending order,
+  // so the code here is optimized for this case
+
+  // Find index of the first interval, having its FEnd >= AStart
+  i := High(FIntervals) + 1;
+  while (i > 0) and (FIntervals[i-1].FEnd >= AStart) do
+    i -= 1;
   if i <= High(FIntervals) then
     AStart := Min(AStart, FIntervals[i].FStart);
+
+  // Find index of the last interval, having its FStart <= AEnd
   j := High(FIntervals);
   while (j >= 0) and (FIntervals[j].FStart > AEnd) do
     j -= 1;
   if j >= 0 then
     AEnd := Max(AEnd, FIntervals[j].FEnd);
+
   if i < j then begin
     for k := j + 1 to High(FIntervals) do
       FIntervals[i + k - j] := FIntervals[j];
@@ -774,14 +782,12 @@
 
 function TIntervalList.Intersect(
   var ALeft, ARight: Double; var AHint: Integer): Boolean;
-var
-  fi, li: Integer;
 begin
   Result := false;
-  if Length(FIntervals) = 0 then exit;
+  if (Length(FIntervals) = 0) or (ALeft > ARight) then exit;
 
   AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
+  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
     Dec(AHint);
 
   while
@@ -788,17 +794,12 @@
     (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
   do begin
     if FIntervals[AHint].FEnd > ALeft then begin
-      if not Result then fi := AHint;
-      li := AHint;
-      Result := true;
+      ALeft := FIntervals[AHint].FStart;
+      ARight := FIntervals[AHint].FEnd;
+      exit(true);
     end;
     Inc(AHint);
   end;
-
-  if Result then begin
-    ALeft := FIntervals[fi].FStart;
-    ARight := FIntervals[li].FEnd;
-  end;
 end;
 
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60763)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -1312,13 +1312,29 @@
 end;
 
 procedure TCubicSplineSeries.TSpline.PrepareIntervals;
+var
+  i: Integer;
 begin
   FIntervals := TIntervalList.Create;
   try
+    // Cubic spline interpolation is required to cross each data point.
+    // To guarantee this when drawing, we create an exclusion range -
+    // of width 0 - around each data point. Thanks to this, series line
+    // will be finished - and then restarted - exactly at each data point,
+    // even when data point's X value is located somewhere between pixels.
+
     if not (csoExtrapolateLeft in FOwner.Options) then
-      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
+
+    for i := 1 to High(FX) - 1 do
+      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
+
     if not (csoExtrapolateRight in FOwner.Options) then
-      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
   except
     FreeAndNil(FIntervals);
     raise;
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60763)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -151,6 +151,23 @@
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(501.0, l);
   AssertEquals(502.0, r);
+  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
+
+  FIList.Clear;
+  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
+  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
+  l := 0.0;
+  r := 100.0;
+  hint := 0;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
+  l := 0.0;
+  r := 100.0;
+  hint := 1;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
 end;
 
 procedure TIntervalListTest.Merge;
patch2.diff (4,625 bytes)

Marcin Wiazowski

2019-03-24 20:09

reporter  

patch3.diff (7,518 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60763)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -126,10 +126,13 @@
   private
     FEpsilon: Double;
     FIntervals: array of TDoubleInterval;
+    FIntervalCount: Integer;
     FOnChange: TNotifyEvent;
     procedure Changed;
     function GetInterval(AIndex: Integer): TDoubleInterval;
-    function GetIntervalCount: Integer;
+    function GetIntervalCapacity: Integer; inline;
+    procedure GrowIntervals;
+    procedure SetIntervalCapacity(AValue: Integer);
     procedure SetOnChange(AValue: TNotifyEvent);
   public
     procedure Assign(ASource: TIntervalList);
@@ -143,7 +146,8 @@
   public
     property Epsilon: Double read FEpsilon write FEpsilon;
     property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
-    property IntervalCount: Integer read GetIntervalCount;
+    property IntervalCount: Integer read FIntervalCount;
+    property IntervalCapacity: Integer read GetIntervalCapacity write SetIntervalCapacity;
     property OnChange: TNotifyEvent read FOnChange write SetOnChange;
   end;
 
@@ -715,24 +719,32 @@
   if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
   if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
   if AStart > AEnd then exit;
-  i := 0;
-  while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
-    i += 1;
-  if i <= High(FIntervals) then
+
+  // In most cases we will be adding ranges in the ascending order,
+  // so the code here is optimized for this case
+
+  // Find index of the first interval, having its FEnd >= AStart
+  i := FIntervalCount; // not FIntervalCount - 1 !
+  while (i > 0) and (FIntervals[i-1].FEnd >= AStart) do
+    i -= 1;
+  if i < FIntervalCount then
     AStart := Min(AStart, FIntervals[i].FStart);
-  j := High(FIntervals);
+
+  // Find index of the last interval, having its FStart <= AEnd
+  j := FIntervalCount - 1;
   while (j >= 0) and (FIntervals[j].FStart > AEnd) do
     j -= 1;
   if j >= 0 then
     AEnd := Max(AEnd, FIntervals[j].FEnd);
+
   if i < j then begin
-    for k := j + 1 to High(FIntervals) do
+    for k := j + 1 to FIntervalCount - 1 do
       FIntervals[i + k - j] := FIntervals[j];
-    SetLength(FIntervals, Length(FIntervals) - j + i);
+    Dec(FIntervalCount, j - i);
   end
   else if i > j then begin
-    SetLength(FIntervals, Length(FIntervals) + 1);
-    for k := High(FIntervals) downto i + 1 do
+    GrowIntervals;
+    for k := FIntervalCount - 1 downto i + 1 do
       FIntervals[k] := FIntervals[k - 1];
   end;
   FIntervals[i] := DoubleInterval(AStart, AEnd);
@@ -743,6 +755,7 @@
 begin
   FEpsilon := ASource.FEpsilon;
   FIntervals := Copy(ASource.FIntervals);
+  FIntervalCount := ASource.FIntervalCount;
 end;
 
 procedure TIntervalList.Changed;
@@ -753,6 +766,7 @@
 
 procedure TIntervalList.Clear;
 begin
+  FIntervalCount := 0;
   FIntervals := nil;
   Changed;
 end;
@@ -764,41 +778,52 @@
 
 function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
 begin
+  if not InRange(AIndex, 0, FIntervalCount - 1) then
+    raise EChartError.CreateFmt('[%s.%s] Index out of range.', [ClassName, 'GetInterval']);
   Result := FIntervals[AIndex];
 end;
 
-function TIntervalList.GetIntervalCount: Integer;
+function TIntervalList.GetIntervalCapacity: Integer; inline;
 begin
   Result := Length(FIntervals);
 end;
 
+procedure TIntervalList.SetIntervalCapacity(AValue: Integer);
+begin
+  if AValue > Length(FIntervals) then
+    SetLength(FIntervals, AValue);
+end;
+
+procedure TIntervalList.GrowIntervals;
+begin
+  Inc(FIntervalCount);
+  if FIntervalCount > Length(FIntervals) then
+    if FIntervalCount < 8 then
+      SetLength(FIntervals, 8)
+    else
+      SetLength(FIntervals, Min((FIntervalCount - 1) * 2, FIntervalCount + 8191));
+end;
+
 function TIntervalList.Intersect(
   var ALeft, ARight: Double; var AHint: Integer): Boolean;
-var
-  fi, li: Integer;
 begin
   Result := false;
-  if Length(FIntervals) = 0 then exit;
+  if (FIntervalCount = 0) or (ALeft > ARight) then exit;
 
-  AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
+  AHint := EnsureRange(AHint, 0, FIntervalCount - 1);
+  while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do
     Dec(AHint);
 
   while
-    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
+    (AHint < FIntervalCount) and (FIntervals[AHint].FStart < ARight)
   do begin
     if FIntervals[AHint].FEnd > ALeft then begin
-      if not Result then fi := AHint;
-      li := AHint;
-      Result := true;
+      ALeft := FIntervals[AHint].FStart;
+      ARight := FIntervals[AHint].FEnd;
+      exit(true);
     end;
     Inc(AHint);
   end;
-
-  if Result then begin
-    ALeft := FIntervals[fi].FStart;
-    ARight := FIntervals[li].FEnd;
-  end;
 end;
 
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60763)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -1,4 +1,4 @@
-{
+{
 
  Function series for TAChart.
 
@@ -1312,13 +1312,31 @@
 end;
 
 procedure TCubicSplineSeries.TSpline.PrepareIntervals;
+var
+  i: Integer;
 begin
   FIntervals := TIntervalList.Create;
   try
+    // Cubic spline interpolation is required to cross each data point.
+    // To guarantee this when drawing, we create an exclusion range -
+    // of width 0 - around each data point. Thanks to this, series line
+    // will be finished - and then restarted - exactly at each data point,
+    // even when data point's X value is located somewhere between pixels.
+
+    FIntervals.IntervalCapacity := Length(FX);
+
     if not (csoExtrapolateLeft in FOwner.Options) then
-      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[0], FX[0], [ioOpenStart, ioOpenEnd]);
+
+    for i := 1 to High(FX) - 1 do
+      FIntervals.AddRange(FX[i], FX[i], [ioOpenStart, ioOpenEnd]);
+
     if not (csoExtrapolateRight in FOwner.Options) then
-      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
+      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd])
+    else
+      FIntervals.AddRange(FX[High(FX)], FX[High(FX)], [ioOpenStart, ioOpenEnd]);
   except
     FreeAndNil(FIntervals);
     raise;
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60763)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -151,6 +151,23 @@
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(501.0, l);
   AssertEquals(502.0, r);
+  FIList.Epsilon := DEFAULT_EPSILON; // don't alter other tests
+
+  FIList.Clear;
+  FIList.AddRange(10.0, 20.0, [ioOpenStart, ioOpenEnd]);
+  FIList.AddRange(30.0, 40.0, [ioOpenStart, ioOpenEnd]);
+  l := 0.0;
+  r := 100.0;
+  hint := 0;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
+  l := 0.0;
+  r := 100.0;
+  hint := 1;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(10.0, l);
+  AssertEquals(20.0, r);
 end;
 
 procedure TIntervalListTest.Merge;
patch3.diff (7,518 bytes)

wp

2019-03-26 23:46

developer   ~0115072

Thanks for reporting and your detailed analysis.

I did not follow your solution because I think it is an overkill having to add 2000000 domain exclusions in your speedtest demo although this particular series is not affected by the issue reported at all.

After refactoring the TDrawFuncHelper I introduced a TPointsDrawFuncHelper for TCubicSplineSeries which addresses the issue without domain exclusions in a more natural way by checking directly whether a data point falls into the curve segment to be drawn and splitting the segment at this point like in your solution.

I did not yet look at the IntervalList patches, maybe they are not needed any more because usually the count of intervals will stay low.

Marcin Wiazowski

2019-03-27 00:59

reporter   ~0115074

Nice.

I haven't yet tested your solution, so I'm now placing only a quick note.

In TIntervalList.Intersect(), in my patch:

a) "if Length(FIntervals) = 0 then exit" has been changed to "if (Length(FIntervals) = 0) or (ALeft > ARight) then exit" - I think that this "ALeft > ARight" test should be added in any case, since Intersect() is a public method, and placing invalid parameters may confuse the algorithm.

b) "while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do" has been changed to "while (AHint > 0) and (FIntervals[AHint].FStart > ALeft) do" to solve the problem with AHint parameter (i.e. returning invalid range in case of larger AHint values) - so this should be also implemented.

c) Last change in Intersect() is to avoid merging ranges, as in my example with [10 .. 20] [30 .. 40] - I think it should also be implemented, because TIntervalList may be used for any purposes, and not only drawing (and even when drawing this still may be a problem for rapid changes in Y values).

wp

2019-03-27 11:17

developer   ~0115077

> has been changed to "if (Length(FIntervals) = 0) or (ALeft > ARight) then exit"

I'd prefer raising an exception, I think when this happens there is a program error, and the programmer should be notified instead of doing nothing (or putting ALeft and Right in the correct order - which might be another option).

There is another similar situation in "AddRange".

BTW: What happens in "AddRange" when AStart=AEnd and Epsilon < 0 (IIRC this is not forbidden ATM)? Is it intended that the function is exited at the beginning in this case?

Marcin Wiazowski

2019-03-27 14:36

reporter   ~0115079

Yes, that code in AddRange() is intentional. Let's consider a small example:

- range [10 .. 20] - this is obvious,
- range [5 .. 5] - just a single point,
- range [20 .. 10] - this is an EMPTY range.

This makes in fact no difference, if the range was empty initially, or become empty inside of the AddRange() call, due to negative Epsilon - both cases should be handled in the same way.


So the only question is: how should be the empty range handled? I think that the "classic" empty range in TAChart (well, even two empty ranges) is EmptyExtent defined in TAChartUtils, where we have two [+INF .. -INF] empty ranges.


When we call:

  AddRange(Extent.a.X, Extent.b.Y)

and the range is empty, there is in fact nothing that should be done, so we can just exit (but empty range is still a valid range from the mathematical point of view, so we shouldn't raise an exception...)


When we call:

  Intersect(Extent.a.X, Extent.b.Y)

we want to check, if the given range intersects some region - and if our given range is empty, it - of course - intersects nothing, so we should just get False returned from the Intersect() call.


So AddRange() and Intersect() are specific in sense, that they shouldn't raise an exception in case of invalid range; or, from the other point of view (the right one...), empty range is still a valid range, so exception should not be raised.

wp

2019-03-27 15:12

developer   ~0115080

> range [20 .. 10] - this is an EMPTY range.

How do you know that? What if the 20 and 10 are results of some lengthy calculation and the programmer got fooled and entered the values in false order?

------

> AddRange(Extent.a.X, Extent.b.Y)

You lost me. Why do you mix up X and Y here?

Marcin Wiazowski

2019-03-27 16:50

reporter   ~0115084

> AddRange(Extent.a.X, Extent.b.Y)
You lost me. Why do you mix up X and Y here?

Sorry, my mistake, of course. It should be: AddRange(Extent.a.X, Extent.b.X)



> How do you know that? What if the 20 and 10 are results of some lengthy calculation and the programmer got fooled and entered the values in false order?

Ok, I can't be sure. I can see two cases:

In case of passing the range inversely by mistake, the programmer will see its mistake, regardless of having exception or not (probably immediately, because he will see nothing on the chart, for example).

In case of passing the range in the natural order, there may be sill a case, when negative epsilon will make the range inverted (i.e. empty - this can only occur in case of setting the epsilon to negative value deliberately) - but, in practical cases, I suppose that it is expected to get just an empty range instead of exception. For example:

- when I want to cut out pieces of some material, I need to include some margins for saw; getting a negative available width means, that I just cannot cut anything;

- when I have some available time intervals (of different width) on a production line, I need to use some time margins for safety (to avoid tools collision); negative available time means that I just can't do anything at this moment.


Having an unwanted exception can be overcame by inherting from TIntervalList and placing try...except..end around the "inherited" call.

Not having a wanted exception can be overcame by inherting from TIntervalList and raising the exception when needed.


I just suppose that - in practice - there are more cases when the exception is not wanted.

Marcin Wiazowski

2019-03-27 16:52

reporter   ~0115085

I have some observations:



A) There is: TPointsDrawFuncHelper = class(TDrawFuncHelper)

Is this intentional to inherit from TDrawFuncHelper, not directly from TCustomDrawFuncHelper? FDomainExclusions, implemented in TDrawFuncHelper, is not used; and it seems that class compatibility between TPointsDrawFuncHelper and TDrawFuncHelper is not needed.



B) TDrawFuncHelper.ForEachPoint() contains unused variables: fxg, i, j.



C) In TPointsDrawFuncHelper.ForEachPoint() there is:

  raise EChartError.Create('[TPointsDrawFuncHelper.ForEachPoint] Series must be a TBasicPointSeries');

It would be better to change it to:

  raise EChartError.CreateFmt('[%s.ForEachPoint] Series must be a TBasicPointSeries', [ClassName]);



D) As far as I understand, TPointsDrawFuncHelper.ForEachPoint() operates on all data points of the series. This is quite unoptimal in case of TCubicSplineSeries. For example, if our data points are:

(1,1)
(2,2)
(3,3)
(4,NaN)
(5,5)
(6,6)
(7,7)

then TCubicSplineSeries operates on two separate splines (FSplines: array of TSpline): (1,1)(2,2)(3,3) and (5,5)(6,6)(7,7). Each of them uses its own range of data points, so enumerating all the available series data points in each spline is not too good.

I can see some potential solution: each spline has its "FX, FY: array of ArbFloat" - where FX and FY are data points belonging to this spline (they are used, for example, in TCubicSplineSeries.TSpline.PrepareIntervals()). Additionally, it seems that FX and FY are also sorted. Maybe it would be good just to use FX?

wp

2019-03-27 23:58

developer   ~0115088

Applied the part of patch2 which is related to the merging of intervals.
Did not apply patch3 - I think it is no longer needed (your speedtest1+2 shows 6 ms on my system, while it was 2 ms with your complete patch - but who cares?

------

D) Fixed partly. I did not want to use the spline's FX array because it is in axis units, but we already have graph units in the FGraphPoints of the TBasicPointSeries. The drawing limits are defined by the spline's outermost FX values now. Only for finding the index of the first point to be used, before the drawing loop, the helper scans over the entire data set and repeats this for every spline of the series. Could be handled by catching and storing the index in the preparation phase, but requires some rearrangements. And I am not very motivated to spend my time in optimization for the unrealistic case of many, many NaNs in the chartsource.

wp

2019-03-28 09:12

developer   ~0115089

Reopening because of severe performance issue when a very large source contains a NaN value.

wp

2019-03-28 10:02

developer   ~0115090

Last edited: 2019-03-28 10:03

View 2 revisions

Fixed incl index search.

Marcin Wiazowski

2019-03-29 23:19

reporter  

DrawingSpeedTestNaN.zip (2,904 bytes)

Marcin Wiazowski

2019-03-29 23:19

reporter  

Extrapolation.zip (2,478 bytes)

Marcin Wiazowski

2019-03-29 23:19

reporter  

Extrapolation.png (23,526 bytes)
Extrapolation.png (23,526 bytes)

Marcin Wiazowski

2019-03-29 23:20

reporter  

update.diff (8,386 bytes)
Index: components/tachart/tacustomfuncseries.pas
===================================================================
--- components/tachart/tacustomfuncseries.pas	(revision 60792)
+++ components/tachart/tacustomfuncseries.pas	(working copy)
@@ -297,7 +297,11 @@
 { TPointsDrawFuncHelper }
 
 type
-  TBasicPointSeriesAccess = class(TBasicPointSeries);
+  TBasicPointSeriesAccess = class(TBasicPointSeries)
+  public
+    property GraphPoints: TDoublePointArray read FGraphPoints;
+    property LoBound: Integer read FLoBound;
+  end;
 
 constructor TPointsDrawFuncHelper.Create(
   ASeries: TBasicPointSeries; AMinX, AMaxX: Double; AStartIndex: Integer;
@@ -325,13 +329,13 @@
     );
 
   ser := TBasicPointSeriesAccess(FSeries);
-  n := Length(ser.FGraphPoints);
+  n := Length(ser.GraphPoints);
   dx := abs(FGraphStep);
 
   xa := FAxisToGraphXr(AXg);
-  j := FStartIndex - ser.FLoBound;
-  while (j < n) and (xa > ser.FGraphPoints[j].X) do inc(j);
-  if j < n then xfg := ser.FGraphPoints[j].X else exit;
+  j := FStartIndex - ser.LoBound;
+  while (j < n) and (xa > ser.GraphPoints[j].X) do inc(j);
+  if j < n then xfg := ser.GraphPoints[j].X else exit;
   AOnMoveTo(AXg, xa);
 
   while AXg < AXMax do begin
@@ -339,10 +343,10 @@
     xa1 := FGraphToAxisXr(xg1);
     if (j >= 0) and (xg1 > xfg) then begin
       xg1 := xfg;
-      xa1 := ser.GetXValue(j + ser.FLoBound);
+      xa1 := ser.GetXValue(j + ser.LoBound);
       inc(j);
-      while (j < n) and (xfg > ser.FGraphPoints[j].X) do inc(j);   // skip unordered points
-      if j < n then xfg := ser.FGraphPoints[j].X else xfg := Infinity;
+      while (j < n) and (xfg > ser.GraphPoints[j].X) do inc(j);   // skip unordered points
+      if j < n then xfg := ser.GraphPoints[j].X else xfg := Infinity;
     end;
     AOnLineTo(xg1, xa1);
     AXg := xg1;
Index: components/tachart/tacustomseries.pas
===================================================================
--- components/tachart/tacustomseries.pas	(revision 60792)
+++ components/tachart/tacustomseries.pas	(working copy)
@@ -279,8 +279,7 @@
     procedure SetPointer(AValue: TSeriesPointer);
     procedure SetStacked(AValue: Boolean);
     procedure SetStackedNaN(AValue: TStackedNaN);
-  //strict
-  protected
+  strict protected
     FGraphPoints: array of TDoublePoint;
     FLoBound: Integer;
     FMinXRange: Double;
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60792)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -208,10 +208,11 @@
     procedure SetStep(AValue: TFuncSeriesStep);
   strict private
   type
+    TArbFloatArray = array of ArbFloat;
     TSpline = class
     public
       FOwner: TCubicSplineSeries;
-      FCoeff, FX, FY: array of ArbFloat;
+      FCoeff, FX, FY: TArbFloatArray;
       FIntervals: TIntervalList;
       FIsUnorderedX: Boolean;
       FStartIndex: Integer;
@@ -220,13 +221,14 @@
       function Calculate(AX: Double): Double;
       function IsFewPoints: Boolean; inline;
       function PrepareCoeffs(
-        ASource: TCustomChartSource; var AIndex: Integer): Boolean;
+        ASource: TCustomChartSource; var AIndex: Integer;
+        var FXCache, FYCache: TArbFloatArray): Boolean;
     end;
 
   var
     FSplines: array of TSpline;
     procedure FreeSplines;
-    procedure GetSplineXRange(ASpline: TSpline; out AXMin, AXMax: Double);
+    function GetSplineXRange(ASpline: TSpline; out AXMin, AXMax: Double): Boolean;
     function IsUnorderedVisible: Boolean; inline;
     procedure PrepareCoeffs;
     procedure SetBadDataPen(AValue: TBadDataChartPen);
@@ -1273,14 +1275,11 @@
 end;
 
 function TCubicSplineSeries.TSpline.PrepareCoeffs(
-  ASource: TCustomChartSource; var AIndex: Integer): Boolean;
+  ASource: TCustomChartSource; var AIndex: Integer;
+  var FXCache, FYCache: TArbFloatArray): Boolean;
 var
   n, ok: Integer;
 begin
-  n := ASource.Count - AIndex;
-  SetLength(FX, n);
-  SetLength(FY, n);
-  SetLength(FCoeff, n);
   FIsUnorderedX := false;
   while (AIndex < ASource.Count) and IsNan(ASource[AIndex]^.Point) do
     AIndex += 1;
@@ -1288,17 +1287,17 @@
   n := 0;
   while (AIndex < ASource.Count) and not IsNan(ASource[AIndex]^.Point) do begin
     with ASource[AIndex]^ do
-      if (n > 0) and (FX[n - 1] >= X) then
+      if (n > 0) and (FXCache[n - 1] >= X) then
         FIsUnorderedX := true
       else begin
-        FX[n] := X;
-        FY[n] := Y;
+        FXCache[n] := X;
+        FYCache[n] := Y;
         n += 1;
       end;
     AIndex += 1;
   end;
-  SetLength(FX, n);
-  SetLength(FY, n);
+  FX := Copy(FXCache, 0, n);
+  FY := Copy(FYCache, 0, n);
   SetLength(FCoeff, n);
   if n = 0 then exit(false);
   if IsFewPoints then exit(true);
@@ -1319,8 +1318,11 @@
 begin
   if ASource is TCubicSplineSeries then
     with TCubicSplineSeries(ASource) do begin
+      Self.BadDataPen := FBadDataPen;
+      Self.Options := FOptions;
       Self.Pen := FPen;
-      Self.FStep := FStep;
+      Self.SplineType := FSplineType;
+      Self.Step := FStep;
     end;
   inherited Assign(ASource);
 end;
@@ -1350,6 +1352,7 @@
   FPen.OnChange := @StyleChanged;
   FPointer := TSeriesPointer.Create(ParentChart);
   FStep := DEF_SPLINE_STEP;
+  FCachedExtent := EmptyExtent;
 end;
 
 destructor TCubicSplineSeries.Destroy;
@@ -1375,8 +1378,7 @@
       if not Pen.EffVisible then exit;
       ADrawer.Pen := Pen;
     end;
-    GetSplineXRange(ASpline, xmin, xmax);
-    if xmin > xmax then
+    if not GetSplineXRange(ASpline, xmin, xmax) then
       exit;
     with TPointsDrawFuncHelper.Create(Self, xmin, xmax, ASpline.FStartIndex, @ASpline.Calculate, Step) do
       try
@@ -1417,7 +1419,7 @@
   if SplineType = cstHermiteMonotone then
     exit;
 
-  if not (FCachedExtent = EmptyExtent) then begin
+  if FCachedExtent <> EmptyExtent then begin
     Result := FCachedExtent;
     exit;
   end;
@@ -1488,9 +1490,8 @@
       if s.IsFewPoints or (s.FIsUnorderedX and not IsUnorderedVisible) then
         continue;
 
-      GetSplineXRange(s, xmin, xmax);
-      if xmax > xmin then
-        exit;
+      if not GetSplineXRange(s, xmin, xmax) then
+        continue;
       with TPointsDrawFuncHelper.Create(Self, xmin, xmax, s.FStartIndex, @s.Calculate, Step) do
         try
           if not GetNearestPoint(AParams, r) or
@@ -1507,20 +1508,27 @@
   end;
 end;
 
-procedure TCubicSplineSeries.GetSplineXRange(ASpline: TSpline;
-  out AXMin, AXMax: Double);
+function TCubicSplineSeries.GetSplineXRange(ASpline: TSpline;
+  out AXMin, AXMax: Double): Boolean;
 var
   ext: TDoubleRect;
 begin
   ext := FChart.CurrentExtent;
-  AXmin := IfThen(
-    (csoExtrapolateLeft in FOptions) and (ASpline = FSplines[0]),
-    ext.a.x, Max(ext.a.x, AxisToGraphX(ASpline.FX[0]))
-  );
-  AXmax := IfThen(
-    (csoExtrapolateRight in FOptions) and (ASpline = FSplines[High(FSplines)]),
-    ext.b.x, Min(ext.b.x, AxisToGraphX(ASpline.FX[High(ASpline.FX)]))
-  );
+
+  if csoExtrapolateLeft in FOptions then
+    AXmin := ext.a.x
+  else
+    AXmin := Max(ext.a.x, AxisToGraphX(ASpline.FX[0]));
+
+  if AXmin > ext.b.x then
+    exit(false);
+
+  if csoExtrapolateRight in FOptions then
+    AXmax := ext.b.x
+  else
+    AXmax := Min(ext.b.x, AxisToGraphX(ASpline.FX[High(ASpline.FX)]));
+
+  Result := AXMin <= AXMax;
 end;
 
 function TCubicSplineSeries.IsUnorderedVisible: Boolean;
@@ -1532,17 +1540,26 @@
 var
   i: Integer = 0;
   s: TSpline;
+  FSplinesLength: Integer = 0;
+  FXCache, FYCache: array of ArbFloat;
 begin
   FreeSplines;
-  while i < Source.Count do begin
-    s := TSpline.Create(self);
-    if s.PrepareCoeffs(Source, i) then begin
-      //s.PrepareIntervals;
-      SetLength(FSplines, Length(FSplines) + 1);
-      FSplines[High(FSplines)] := s;
-    end
-    else
-      s.Free;
+  try
+    SetLength(FXCache, Source.Count);
+    SetLength(FYCache, Source.Count);
+    while i < Source.Count do begin
+      s := TSpline.Create(self);
+      if s.PrepareCoeffs(Source, i, FXCache, FYCache) then begin
+        if FSplinesLength >= Length(FSplines) then
+          SetLength(FSplines, FSplinesLength + 1024);
+        FSplines[FSplinesLength] := s;
+        Inc(FSplinesLength);
+      end
+      else
+        s.Free;
+    end;
+  finally
+    SetLength(FSplines, FSplinesLength);
   end;
 end;
 
update.diff (8,386 bytes)

Marcin Wiazowski

2019-03-29 23:23

reporter   ~0115113

I'm reopening to fix some issues. The attached update.diff fixes the following problems:


a) An additional DrawingSpeedTestNaN test application has been attached here; currently, it starts for about 15 seconds. This is due to large memory allocations in every TCubicSplineSeries.TSpline.PrepareCoeffs() call - which is called many times. So some simple caching has been introduced in TCubicSplineSeries.PrepareCoeffs() and TCubicSplineSeries.TSpline.PrepareCoeffs(), which solves the problem.


b) By the way, lacking assignments have been added in TCubicSplineSeries.Assign()


c) The newly introduced FCachedExtent is now properly initialized in TCubicSplineSeries.Create()


d) Some problems with GetSplineXRange() have been fixed:
- it has been changed to a function, to avoid additional "if xmin > xmax then" checks after each call
- in TCubicSplineSeries.GetNearestPoint(), there was "exit" instead of "continue"
- csoExtrapolateLeft was applied only to first spline, and csoExtrapolateRight only to last spline - see the attached Extrapolation application and Extrapolation.png
- additional optimization "if AXmin > ext.b.x then" has been added
- IfThen() calls have been slowing the execution down, so have been changed to normal "if .. then .. else" statements. Explanation: when we have:

  function GetValue1(); // executes 2 seconds
  function GetValue2(); // executes 3 seconds

then calling:

  if SomeCondition then
    Result := GetValue1()
  else
    Result := GetValue2()

will consume either 2 seconds, or 3 seconds. But:

  Result := IfThen(SomeCondition, GetValue1(), GetValue2())

will always consume 5 seconds, because both GetValue1() and GetValue2() must be called before passing their results to IfThen().

In our case, we have AxisToGraphX() calls - they are time-consuming, so we can avoid them if not needed.

In fact, IfThen() is a good (i.e. fast) solution only for simple alternatives, like IfThen(SomeCondition, SomeVariable + 1.0, 0.0), where no (complicated) functions need to be called.



In addition, TBasicPointSeriesAccess have been modified, so TBasicPointSeries can use "strict protected" declaration again, instead of the last introduced "protected". This is just an experiment, please reject if you don't like it.



Test results for r60763:
DrawingSpeedTest: 3.28 ms
DrawingSpeedTestNaN: 34.8 ms + very long waiting during application start (up to 15 seconds)


Test results for r60792:
DrawingSpeedTest: 4.22 ms
DrawingSpeedTestNaN: 26.8 ms + very long waiting during application start (up to 15 seconds)


Test results for r60792 + update.diff:
DrawingSpeedTest: 4.22 ms
DrawingSpeedTestNaN: 18.5 ms, application starts immediately (thanks to optimizations in TCubicSplineSeries.PrepareCoeffs())



I like the solution with TPointsDrawFuncHelper: more elegant, less complicated, and also faster than intervals.

Marcin Wiazowski

2019-03-31 16:39

reporter   ~0115145

Just a simple additional note: the case a) above (the long application start) is my real-life case - I have a lot of measurement data, where lacking measurements (due to measuring failure) have Y=NaN. So I have a lot of separate splines, instead of one big spline.

wp

2019-03-31 23:54

developer   ~0115155

Last edited: 2019-03-31 23:58

View 2 revisions

> b) By the way, lacking assignments have been added in TCubicSplineSeries.Assign()

I had seen this, but forgot it again... I prefer setting the internal variables directly, like throughout the library, instead of setting the properties, though, to avoid activating the notification broadcasts via the property setters.

------------

> c) The newly introduced FCachedExtent is now properly initialized in
> TCubicSplineSeries.Create()

I did not replace "not (FCachedExtent = EmptyExtent)" by "(FCachedExtent <> EmptyExtent)" because we don't have an overload of the "<>" operator (it could be added of course, but is it really needed?). FPC does seem to negate the result of the "=" operator here, but I don't know if this is by intention or by incidence, FPC at least is not consistent here. Look at "<": we do have TDoublePoint overloads for "<=" and "=" (unit TAGeometry), but here FPC does not assume that "<" can be constructed from the logical combination ("<=" and not "="). So, using the "<>" operator here poses some (small) risk for future compilability.

------------

> d) - csoExtrapolateLeft was applied only to first spline, and csoExtrapolateRight
> only to last spline - see the attached Extrapolation application and Extrapolation.png

Seems to work correctly for me. The intention behind applying csoExtrapolateLeft to the first (and csoExtrapolateRight to the last spline) was that these are the only splines where extrapolation can have an effect. The problem in your "extrapolation" demo is a result of your removal of these conditions here.

-------------

> An additional DrawingSpeedTestNaN test application has been attached here; currently, it starts for about 15 seconds.

I don't have code for it ATM, I plan to follow your solution but I want to avoid copying the cached FX and FY arrays back into the spline. The NumLib spline routines require x and y as separate arrays, but these arrays do not have to begin with index 0 - that's one of the big advantages of the way arrays are passed to NumLib routines which took me a long time to understand. Therefore, we can keep a single x and y array in the series and just pass the first and last index to the splines. There is already an index, FStartIndex, but this refers to the data points - the indexes in FX and FY can be different because of NaN values and values skipped due to unordered x.

wp

2019-04-01 12:45

developer   ~0115158

Done as described in prev note.

Marcin Wiazowski

2019-04-02 01:18

reporter  

Assign.zip (2,534 bytes)

Marcin Wiazowski

2019-04-02 01:19

reporter  

test.diff (3,401 bytes)
Index: components/tachart/tacustomseries.pas
===================================================================
--- components/tachart/tacustomseries.pas	(revision 60818)
+++ components/tachart/tacustomseries.pas	(working copy)
@@ -79,6 +79,7 @@
     procedure SetParentComponent(AParent: TComponent); override;
 
   strict protected
+    FPropUpdateCount: Integer;
     // Set series bounds in axis coordinates.
     // Some or all bounds may be left unset, in which case they will be ignored.
     procedure GetBounds(var ABounds: TDoubleRect); virtual; abstract;
@@ -110,6 +111,9 @@
     procedure Assign(ASource: TPersistent); override;
     constructor Create(AOwner: TComponent); override;
     destructor Destroy; override;
+    procedure BeginPropUpdate; virtual;
+    procedure EndPropUpdate; virtual;
+    function IsPropUpdating: Boolean; inline;
     function GetNearestPoint(
       const AParams: TNearestPointParams;
       out AResults: TNearestPointResults): Boolean; virtual;
@@ -435,6 +439,23 @@
   inherited;
 end;
 
+procedure TCustomChartSeries.BeginPropUpdate;
+begin
+  Inc(FPropUpdateCount);
+end;
+
+procedure TCustomChartSeries.EndPropUpdate;
+begin
+  Dec(FPropUpdateCount);
+  if FPropUpdateCount > 0 then exit;
+  UpdateParentChart;
+end;
+
+function TCustomChartSeries.IsPropUpdating: Boolean; inline;
+begin
+  Result := FPropUpdateCount > 0;
+end;
+
 function TCustomChartSeries.GetAxisBounds(AAxis: TChartAxis;
   out AMin, AMax: Double): Boolean;
 var
@@ -720,8 +741,9 @@
 
 procedure TCustomChartSeries.UpdateParentChart;
 begin
-  if ParentChart <> nil then
-    ParentChart.StyleChanged(Self);
+  if not IsPropUpdating then
+    if ParentChart <> nil then
+      ParentChart.StyleChanged(Self);
 end;
 
 { TChartSeries }
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60818)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -1271,7 +1271,7 @@
 
 function TCubicSplineSeries.TSpline.IsFewPoints: Boolean;
 begin
-  Result := Length(FOwner.FX) < 2;
+  Result := FLastCacheIndex <= FFirstCacheIndex;
 end;
 
 function TCubicSplineSeries.TSpline.PrepareCoeffs(ASource: TCustomChartSource;
@@ -1296,7 +1296,7 @@
     ASourceIndex += 1;
   end;
   FLastCacheIndex := ACacheIndex - 1;
-  if FLastCacheIndex = FFirstCacheIndex then exit(false);
+  if FLastCacheIndex < FFirstCacheIndex then exit(false);
   if IsFewPoints then exit(true);
   ok := 0;
   n := ACacheIndex - FFirstCacheIndex;
@@ -1315,15 +1315,20 @@
 
 procedure TCubicSplineSeries.Assign(ASource: TPersistent);
 begin
-  if ASource is TCubicSplineSeries then
-    with TCubicSplineSeries(ASource) do begin
-      Self.BadDataPen.Assign(FBadDataPen);
-      Self.FOptions := FOptions;
-      Self.FPen.Assign(FPen);
-      Self.FSplineType := FSplineType;
-      Self.FStep := FStep;
-    end;
-  inherited Assign(ASource);
+  BeginPropUpdate;
+  try
+    if ASource is TCubicSplineSeries then
+      with TCubicSplineSeries(ASource) do begin
+        Self.BadDataPen := FBadDataPen;
+        Self.Options := FOptions;
+        Self.Pen := FPen;
+        Self.SplineType := FSplineType;
+        Self.Step := FStep;
+      end;
+    inherited Assign(ASource);
+  finally
+    EndPropUpdate;
+  end;
 end;
 
 function TCubicSplineSeries.Calculate(AX: Double): Double;
test.diff (3,401 bytes)

Marcin Wiazowski

2019-04-02 01:23

reporter   ~0115177

Ad b)

> I prefer setting the internal variables directly, like throughout the library, instead of setting the properties, though, to avoid activating the notification broadcasts via the property setters.

Unfortunately, this leads us to trouble. Please launch the attached Assign application:
- Press the "Assign series from Chart2 to Chart1" button; unfortunately, Chart1 is not redrawn, because UpdateParentChart() has not been called at all,
- So minimize the application and restore it again (or press the "Force Chart1 redrawing" button): now Chart1 is redrawn, but series shape is still improper (i.e. not as on Chart2) - this is because FreeSplines() has not been called at all, so splines have not been freed, so splines cannot be recalculated - which is required, because SplineType property has been changed,
- So press the "Force Chart1 series settings being applied" button: at last, everything is drawn properly.

Solution: don't assign series fields directly, but only by using properties.

BUT: this calls UpdateParentChart() many times, which is not good.

I attached here a simple, experimental solution in test.diff: it adds BeginPropUpdate / EndPropUpdate methods to TCustomChartSeries - which is similar to BeginUpdate / EndUpdate in TChartSeries (but there it is related to updating series source, not series properties).

So the patch contains:

  procedure TCubicSplineSeries.Assign(ASource: TPersistent);
  begin
    BeginPropUpdate;
    try
      if ASource is TCubicSplineSeries then
        with TCubicSplineSeries(ASource) do begin
          Self.BadDataPen := FBadDataPen;
          Self.Options := FOptions;
          Self.Pen := FPen;
          Self.SplineType := FSplineType;
          Self.Step := FStep;
        end;
      inherited Assign(ASource);
    finally
      EndPropUpdate;
    end;
  end;

The best solution would be to:
- add BeginPropUpdate / EndPropUpdate calls to Assign() methods of all existing series,
- make assignments always to properties - and not directly to fields - in the Assign() code (although some exceptions to this rule may be needed).




Ad c)

> FPC at least is not consistent here. Look at "<": we do have TDoublePoint overloads for "<=" and "=" (unit TAGeometry), but here FPC does not assume that "<" can be constructed from the logical combination ("<=" and not "=").

I think that FPC does its work as it should.

For the "=" operator, things are quite simple: "=" is true when "<>" is not true, which is equal to: "<>" is true when "=" is not true.

But for the "<=" case, things are more complicated in the 2D coordinate space:

we have:

[1, 1] <= [2, 2] ? -> Yes
[1, 2] <= [2, 2] ? -> Yes
[2, 1] <= [2, 2] ? -> Yes
[2, 2] <= [2, 2] ? -> Yes

[1, 1] = [2, 2] ? -> No
[1, 2] = [2, 2] ? -> No
[2, 1] = [2, 2] ? -> No
[2, 2] = [2, 2] ? -> Yes

so:

[1, 1] <= and not = [2, 2] ? -> Yes
[1, 2] <= and not = [2, 2] ? -> Yes
[2, 1] <= and not = [2, 2] ? -> Yes
[2, 2] <= and not = [2, 2] ? -> No

while:

[1, 1] < [2, 2] ? -> Yes
[1, 2] < [2, 2] ? -> No
[2, 1] < [2, 2] ? -> No
[2, 2] < [2, 2] ? -> No

So FPC just cannot construct the "<" operation from the logical combination of: "<=" and not "=".




Ad d)

When we launch the Extrapolation application under Lazarus 2.0 final, we get the look like on the UPPER part of Extrapolation.png.

Currently (r60818), we get the look like on the LOWER part of Extrapolation.png, so we lost the compatibility.

After removing "ASpline = FSplines[0]" and "ASpline = FSplines[High(FSplines)]" conditions in TCubicSplineSeries.GetSplineXRange(), things are again as in Lazarus 2.0 final. So these conditions should be removed for compatibility reasons...




> these arrays do not have to begin with index 0 - that's one of the big advantages of the way arrays are passed to NumLib routines which took me a long time to understand.

Many thanks for your explanation! I couldn't see a reason for this unusual array passing convention. Indeed, now TCubicSplineSeries calculations are implemented in the best possible way.




IMPORTANT: The attached test.diff fixes also two problems:


1) TCubicSplineSeries.TSpline.IsFewPoints() should be now defined as:

  Result := FLastCacheIndex <= FFirstCacheIndex;


2) In TCubicSplineSeries.TSpline.PrepareCoeffs(), there is:

  if FLastCacheIndex = FFirstCacheIndex then exit(false);

but there should be:

  if FLastCacheIndex < FFirstCacheIndex then exit(false);

The intention of this code is to exit when there are exactly 0 points - in r60804 we have: "if n = 0 then exit(false)".

Currently, for 0 points, FLastCacheIndex is lower than FFirstCacheIndex, which can be tested by setting Y = NaN in the source's last data point.

wp

2019-04-02 07:08

developer   ~0115178

Last edited: 2019-04-02 09:16

View 2 revisions

Applied the IsFewPoint patch and related changes.

Found the official documentation that the "=" operator is negated automatically to obtain the "<>" operator, and this gives me a better feeling to apply your code. (Interestingly the "=" is NOT derived from an existing "<>" operator, https://www.freepascal.org/docs-html/ref/refse103.html).

I fixed Assign not calling FreeSplines by doing it exactly here. This does not repaint the chart. But I do not know if this is intended: no Assign methods found throughout TAChart notify the chart of the changes; I could imagine that for one class this was forgotten, but for all? Not knowing the intent of the original authors I would like to keep it this way: A user calling Assign must call Chart.Invalidate himself as it has been all the time.

If you do not agree with this decision open another report; the Assign issue does not belong here, and I should not have applied the related patch in the first place. This is a different topic. Having it here will blow up this report to another endless story.

Marcin Wiazowski

2019-04-02 20:07

reporter  

improvement.diff (1,206 bytes)
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60820)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -1541,22 +1541,31 @@
 var
   i: Integer = 0;
   j: Integer = 0;
+  sCount: Integer = 0;
   s: TSpline;
 begin
   FreeSplines;
   SetLength(FX, Source.Count);
   SetLength(FY, Source.Count);
-  while i < Source.Count do begin
-    s := TSpline.Create(self);
-    if s.PrepareCoeffs(Source, i, j) then begin
-      SetLength(FSplines, Length(FSplines) + 1);
-      FSplines[High(FSplines)] := s;
-    end
-    else
-      s.Free;
+  SetLength(FSplines, Source.Count);
+  try
+    while i < Source.Count do begin
+      s := TSpline.Create(self);
+      try
+        if s.PrepareCoeffs(Source, i, j) then begin
+          FSplines[sCount] := s;
+          s := nil;
+          sCount += 1;
+        end;
+      finally
+        s.Free;
+      end;
+    end;
+    SetLength(FX, j);
+    SetLength(FY, j);
+  finally
+    SetLength(FSplines, sCount);
   end;
-  SetLength(FX, j);
-  SetLength(FY, j);
 end;
 
 procedure TCubicSplineSeries.SetBadDataPen(AValue: TBadDataChartPen);
improvement.diff (1,206 bytes)

Marcin Wiazowski

2019-04-02 20:09

reporter   ~0115183

I'm reopening to attach some additional improvement for the last modified code, and to ask some question.


The attached improvement.diff is for TCubicSplineSeries.PrepareCoeffs() method:
- execution is a bit faster (nothing big - about 5% when testing with modified DrawingSpeedTestNaN) thanks to avoiding memory reallocations - this is inspired by the way, in which FX and FY are currently handled,
- due to added try..finally statement, a potential exception will not leave us with "s" object dangling.
To avoid having uninitialized entries in the "FSplines" object table, its final length is enforced in a try..finally statement.


About Assign() methods: I will take a look at them; in case of finding something that is worth reporting, I'll create a separate bug report.


Now the question. Current handling of csoExtrapolateLeft / csoExtrapolateRight options is incompatible with the last official Lazarus release (I described this in my previous post). So I just wanted to ask, if this is intentional: if so, I have anything against (it should be only listed as an incompatible change); if not, the solution is described in my previous post.

wp

2019-04-02 22:49

developer   ~0115184

Applied, thanks.

> Current handling of csoExtrapolateLeft / csoExtrapolateRight options is
> incompatible with the last official Lazarus release (I described this in my
> previous post). So I just wanted to ask, if this is intentional

Yes, the v2 behavior is a bug. We have one series and these options allow to extrapolate the series beyond its range to the left and/or to the right. It does not matter what happens inside the series. The extrapolation refers to the overall series, not to the individual splines the series may be composed of.

Since after fixing a bug the product is always "incompatible" to the previous version and behaves differently I do not think it is necessary to list it as an incompatible change in the wiki.

Marcin Wiazowski

2019-04-02 22:57

reporter   ~0115185

In fact, you are right. Extrapolation options should be applied only to first/last spline. The user, in most cases, will not even know about splines - he looks at the whole series, not at series' parts. Thanks.

Issue History

Date Modified Username Field Change
2019-03-24 20:06 Marcin Wiazowski New Issue
2019-03-24 20:06 Marcin Wiazowski File Added: Reproduce.zip
2019-03-24 20:07 Marcin Wiazowski File Added: Reproduce.gif
2019-03-24 20:07 Marcin Wiazowski File Added: Explanation.png
2019-03-24 20:08 Marcin Wiazowski File Added: IntervalsSpeedTest0and1and2.zip
2019-03-24 20:08 Marcin Wiazowski File Added: IntervalsSpeedTest3.zip
2019-03-24 20:08 Marcin Wiazowski File Added: DrawingSpeedTest.zip
2019-03-24 20:08 Marcin Wiazowski File Added: patch1.diff
2019-03-24 20:08 Marcin Wiazowski File Added: patch2.diff
2019-03-24 20:09 Marcin Wiazowski File Added: patch3.diff
2019-03-26 23:21 wp Assigned To => wp
2019-03-26 23:21 wp Status new => assigned
2019-03-26 23:46 wp Note Added: 0115072
2019-03-27 00:59 Marcin Wiazowski Note Added: 0115074
2019-03-27 11:17 wp Note Added: 0115077
2019-03-27 14:36 Marcin Wiazowski Note Added: 0115079
2019-03-27 15:12 wp Note Added: 0115080
2019-03-27 16:50 Marcin Wiazowski Note Added: 0115084
2019-03-27 16:52 Marcin Wiazowski Note Added: 0115085
2019-03-27 23:58 wp Note Added: 0115088
2019-03-27 23:59 wp Fixed in Revision => 60785, 60788
2019-03-27 23:59 wp LazTarget => 2.2
2019-03-27 23:59 wp Status assigned => resolved
2019-03-27 23:59 wp Resolution open => fixed
2019-03-27 23:59 wp Target Version => 2.2
2019-03-28 09:12 wp Note Added: 0115089
2019-03-28 09:12 wp Status resolved => assigned
2019-03-28 09:12 wp Resolution fixed => reopened
2019-03-28 10:02 wp Fixed in Revision 60785, 60788 => 60785, 60788, 60791
2019-03-28 10:02 wp Note Added: 0115090
2019-03-28 10:02 wp Status assigned => resolved
2019-03-28 10:02 wp Resolution reopened => fixed
2019-03-28 10:03 wp Status resolved => assigned
2019-03-28 10:03 wp Resolution fixed => reopened
2019-03-28 10:03 wp Note Edited: 0115090 View Revisions
2019-03-28 10:03 wp Status assigned => resolved
2019-03-28 10:03 wp Resolution reopened => fixed
2019-03-29 23:19 Marcin Wiazowski File Added: DrawingSpeedTestNaN.zip
2019-03-29 23:19 Marcin Wiazowski File Added: Extrapolation.zip
2019-03-29 23:19 Marcin Wiazowski File Added: Extrapolation.png
2019-03-29 23:20 Marcin Wiazowski File Added: update.diff
2019-03-29 23:23 Marcin Wiazowski Note Added: 0115113
2019-03-29 23:23 Marcin Wiazowski Status resolved => assigned
2019-03-29 23:23 Marcin Wiazowski Resolution fixed => reopened
2019-03-31 16:39 Marcin Wiazowski Note Added: 0115145
2019-03-31 23:54 wp Note Added: 0115155
2019-03-31 23:58 wp Note Edited: 0115155 View Revisions
2019-04-01 12:45 wp Fixed in Revision 60785, 60788, 60791 => 60785, 60788, 60791, 60809
2019-04-01 12:45 wp Note Added: 0115158
2019-04-01 12:45 wp Status assigned => resolved
2019-04-01 12:45 wp Resolution reopened => fixed
2019-04-02 01:18 Marcin Wiazowski File Added: Assign.zip
2019-04-02 01:19 Marcin Wiazowski File Added: test.diff
2019-04-02 01:23 Marcin Wiazowski Note Added: 0115177
2019-04-02 01:23 Marcin Wiazowski Status resolved => assigned
2019-04-02 01:23 Marcin Wiazowski Resolution fixed => reopened
2019-04-02 07:08 wp Fixed in Revision 60785, 60788, 60791, 60809 => 60785, 60788, 60791, 60809, 60819
2019-04-02 07:08 wp Note Added: 0115178
2019-04-02 07:08 wp Status assigned => resolved
2019-04-02 07:08 wp Resolution reopened => fixed
2019-04-02 09:10 wp Status resolved => assigned
2019-04-02 09:10 wp Resolution fixed => reopened
2019-04-02 09:16 wp Note Edited: 0115178 View Revisions
2019-04-02 09:17 wp Fixed in Revision 60785, 60788, 60791, 60809, 60819 => 60785, 60788, 60791, 60809, 60819, 60820
2019-04-02 09:17 wp Status assigned => resolved
2019-04-02 09:17 wp Resolution reopened => fixed
2019-04-02 20:07 Marcin Wiazowski File Added: improvement.diff
2019-04-02 20:09 Marcin Wiazowski Note Added: 0115183
2019-04-02 20:09 Marcin Wiazowski Status resolved => assigned
2019-04-02 20:09 Marcin Wiazowski Resolution fixed => reopened
2019-04-02 22:49 wp Note Added: 0115184
2019-04-02 22:49 wp Fixed in Revision 60785, 60788, 60791, 60809, 60819, 60820 => 60785, 60788, 60791, 60809, 60819, 60820, 60821
2019-04-02 22:49 wp Status assigned => resolved
2019-04-02 22:49 wp Resolution reopened => fixed
2019-04-02 22:57 Marcin Wiazowski Note Added: 0115185
2019-04-02 22:57 Marcin Wiazowski Status resolved => closed
2019-04-05 11:38 wp Relationship added related to 0035313