Steema Central

Posted: **Thu Feb 09, 2012 2:20 pm**

I need to calculate y=y(x) for arbitrary x value. This is not a problem for normal line series, I can use interpolation. But for showing serie on chart I use Smoothing function. How to calculate y value for x when using B-Spline alghoritm.

Thank you for your answer.

Matjaz Urank

Posted: **Fri Feb 10, 2012 6:18 am**

Hello Urank,

I am guessing that your series values will contain all additional points calculated by the smoothing function so you can find Y as the intersection of 2 line segments. You just need to find the index value so that XValues < Your_X < XValues[i+1] and test the intersection of this line segment with the (X-1E16. X+1E16). Just a quick thought

Regards

Posted: **Fri Feb 10, 2012 3:34 pm**

Hi,

If you set it with the "source" TLineSeries Smoothed property to true, this same series will have the new values, so the interpolation can be applied to it.
If you create a second TLineSeries linked to a TSmoothingFunction, this second series will have the new values, and the interpolation could be calculated over it.

Reference examples in the features demo:
- What's New ?\Welcome !\New in Series\Custom\Smoothed
- All features\Welcome !\Functions\Extended\Smoothing SpLine
- All features\Welcome !\Chart styles\Standard\Line(Strip)\Interpolating Line series

Posted: **Thu Feb 16, 2012 11:35 am**

Thank you, that information helps.

Best regards.

Posted: **Sun Jan 18, 2015 11:33 am**

This is rather old post but I think it's still interesting problem.

Here is the code of base interpolation algorithm:

Code: Select all

  
function InterpolateSeries(Series: TCustomMultiSeries; XValue: Double; var DataIdx: Integer): Double;
var
  Index: Integer;
  dx, dy: Double;
  FirstIdx, LastIdx: Integer;

begin
  FirstIdx := Series.FirstDisplayedIndex;
  LastIdx := Series.LastDisplayedIndex;

  if FirstIdx < 0 then exit;
  if LastIdx < 0 then exit;

  for Index := FirstIdx to LastIdx do
    if Series.XValues.Value[Index] > XValue then break;

  // safeguard
  if (Index < 1) then Index := 1
  else if (Index >= Series.Count) then Index := Series.Count - 1;

  // y=(y2-y1)/(x2-x1)*(x-x1)+y1
  dx := Series.XValues.Value[Index] - Series.XValues.Value[Index - 1];
  dy := Series.YValues.Value[Index] - Series.YValues.Value[Index - 1];

  if (dx <> 0) then
  begin
    Result := (dy / dx) * (XValue - Series.XValues.Value[Index - 1]) + Series.YValues.Value[Index - 1];
    DataIdx := Index - 1;
  end else begin
    Result := 0;
    DataIdx := - 1;
  end;
end;

You can notice there is for-loop to find first Index of X data which is greater than our X value. This loop can be quite slow when series contains a lot of data. And the worst case is N count of loops.

I improved interpolation algorithm to use binary seach algorithm instead of regular for-loop. Condition which allows to use binary search is that data must be sorted. I am always generating X data which go from low value to high value (0... 10000 or whatever) so it's basically always already sorted. Binary search algorithm works on conquer and divide principle. So it will always divide series into two halfes and check to which half of data our X value belongs. In next step it will take that new part and divide it into two halfes again and so on... until it results to closest Index. (Refrence: http://en.wikipedia.org/wiki/Binary_search_algorithm)

This algorithm can be written as a recursive algorithm but it's so simple there is no need for recursion and can be imrpoved with itereative approach. Recursive apporach has a drawback that each function call needs to reserve some stack which again takes some time and memory. While binary search is so simple it can be easily written in a iterative way which is much better performance wise. Binary search takes in worst case scenario only LOG(N) + 1 steps to find index for X value. So if you have 2048 data it will take max of 12 steps to find index while regular for-loop can take 2048 steps.

Binary search code:

Code: Select all

function TCustomMultiSeries.BinarySearch(Values: TChartValues; NewMin, NewMax: Integer; XValue: double): Integer;
var Index: Integer;
    Value: Double;
begin
  while NewMax > NewMin do
  begin
    Index := (NewMax + NewMin) shr 1;
    Value := Values[Index];

    if SameValue(Values[NewMin], XValue) then
    begin
      Result  := NewMin;
      exit;
    end else
    if SameValue(Value, XValue) then
    begin
      Result  := Index;
      exit;
    end else
    if SameValue(Values[NewMax], XValue) then
    begin
      Result  := NewMax;
      exit;
    end else
    if Value > XValue then
    begin
      if NewMax = Index then
      begin
        Result := NewMin;
        exit;
      end;
      NewMax := Index;
    end else
    begin
      if NewMin = Index then
      begin
        Result  := NewMin;
        exit;
      end;
      NewMin := Index;
    end;

  end;

  Result := NewMin;
end;

And now interpolation looks like:

Code: Select all

function InterpolateSeries(Series: TCustomMultiSeries; XValue: Double; var DataIdx: Integer): Double;
var
  Index: Integer;
  dx, dy: Double;
  FirstIdx, LastIdx: Integer;

begin

  Index := BinarySearch(Series.XData, Series.FirstDisplayedIndex, Series.LastDisplayedIndex, XValue);

  // safeguard
  if (Index < 1) then Index := 1
  else if (Index >= Series.Count) then Index := Series.Count - 1;

  // y=(y2-y1)/(x2-x1)*(x-x1)+y1
  dx := Series.XValues.Value[Index] - Series.XValues.Value[Index - 1];
  dy := Series.YValues.Value[Index] - Series.YValues.Value[Index - 1];

  if (dx <> 0) then
  begin
    Result := (dy / dx) * (XValue - Series.XValues.Value[Index - 1]) + Series.YValues.Value[Index - 1];
    DataIdx := Index - 1;
  end else begin
    Result := 0;
    DataIdx := - 1;
  end;
end;

I also measure time of interpolation algorithm execution for different amount of data.
Data count/Interpolation(For-Loop)/Interpolation(Binary Search)
522/3,13us/1,99us
2000/4,54us/2,28us
2825/5,12us/0,28us

Posted: **Mon Jan 19, 2015 10:31 am**

Hi,

Thanks for the contribution!
This will hopefully help other users to improve their algorithms and the performance of their applications when having large datasets.

Steema Central

How to calculate Y from X value (LineSeries with Smoothing)

How to calculate Y from X value (LineSeries with Smoothing)

Re: How to calculate Y from X value (LineSeries with Smoothing)

Re: How to calculate Y from X value (LineSeries with Smoothing)

Re: How to calculate Y from X value (LineSeries with Smoothing)

Re: How to calculate Y from X value (LineSeries with Smoothing)

Re: How to calculate Y from X value (LineSeries with Smoothing)