Nearest Point tool has bad performance for big series

[SiA]

Hi Narcis,

Our References :
Defect ID : 5607
Headline : [FGP Temporal] [TChartPro] Performance issue with the nearest point tool

Nearest Point tool has bad performance when series contains many points. Display Performance is very bad with 100000 points.
How can we obtain best performances using nearest tool and many points in series?

I have pushed an example in newsgroup

Best Regards
Gerald

[Narcís]

Hi Gerald,

Thanks for the example. NearestPoint tool performance is highly improved setting FullRepaint property to false, have you tried this?

Code: Select all

procedure TForm1.Button1Click(Sender: TObject);
begin
  self.Series1.FillSampleValues(strtoint(Edit1.Text));

  ChartTool1.FullRepaint:=false;
end;

[SiA]

Thanks Narcis,

I have tried this solution and effectively performances are highly improved. But in this case, the circle around focused point is not painted . In our application, we always need a black circle around nearest point.
So, do you have another solution to propose?

Regards
Gerald

[SteveP]

I ahve not looked in the source code, but does the Nearest Point tool always begin its search from the beginning or end of the data array ? If not, it might be faster to begin from the previous nearest point index and search away from that in both directions. This assumes linearity in values.

[Narcís]

Hi SteveP,

I ahve not looked in the source code, but does the Nearest Point tool always begin its search from the beginning or end of the data array ? If not, it might be faster to begin from the previous nearest point index and search away from that in both directions. This assumes linearity in values.

Yes, Nearest Point tool searches points from beginning to the end. I've added your request to our wish-list for series ordered in ascending or descending mode.

[SiA]

Thanks SteveP,

You are right. I have looked in source code TNearestTool.GetNearestPoint and TNearestTool.ChartMouseEvent and it seems that search is always performed from beginning to end of series each time user moves mouse in chart. It is not acceptable for performance when we have more than 20000 data in series. Moreover, search algorithm in GetNearestPoint is basic. Why this GetNearestPoint method does not use a dichotomy search algorithm or more advanced search algorithm? Algorithm may be different for each kind of series to improve performance in different cases.

Code: Select all

class Function TNearestTool.GetNearestPoint(Series:TChartSeries; X,Y:Integer; IncludeNulls:Boolean):Integer;
var t      : Integer;
    Dif    : Integer;
    Dist   : Integer;
    tmpMin : Integer;
    tmpMax : Integer;
    tmpX   : Integer;
    tmpY   : Integer;
    tmpZList : TChartValueList;
    tmpZ   : Integer;
begin
  result:=-1;
  Dif:=10000;

  if TeeGetFirstLastSeries(Series,tmpMin,tmpMax) then
  begin
    tmpZList:=Series.GetYValueList('Z'); // 7.0

    for t:=tmpMin to tmpMax do { <-- traverse all points in a Series... }
    if IncludeNulls or (not Series.IsNull(t)) then // 7.0
    begin
      { calculate position in pixels }
      tmpX:=Series.CalcXPos(t);
      tmpY:=Series.CalcYPos(t);

      if Series.HasZValues then
      begin
        tmpZ:=Series.ParentChart.Axes.Depth.CalcPosValue(tmpZList.Value[t]);

        with Series.ParentChart.Canvas.Calculate3DPosition(tmpX,tmpY,tmpZ) do
        begin
          tmpX:=X;
          tmpY:=Y;
        end;
      end;

      if PointInRect(Series.ParentChart.ChartRect,tmpX,tmpY) then { 5.01 }
      begin
        { calculate distance in pixels... }
        Dist:=Round(TeeDistance(X-tmpX,Y-tmpY));

        if Dist<Dif then { store if distance is lower... }
        begin
          Dif:=Dist;
          result:=t;  { <-- set this point to be the nearest... }
        end;
      end;
    end;
  end;
end;

procedure TNearestTool.ChartMouseEvent(AEvent: TChartMouseEvent;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  inherited;

  if (AEvent=cmeMove) and Assigned(Series) then
  begin
    if not FullRepaint then PaintHint;
    Point:=GetNearestPoint(Series,X,Y);
    IMouse:=TeePoint(x,y);
    if not FullRepaint then PaintHint;
    if Assigned(FOnChange) then FOnChange(Self);
    if FullRepaint then Repaint;
  end;
end;

Narcis, Does Steema expects to deliver a new release fixing this performance defect?

Regards
Gerald

[Narcís]

Hi Gerald,

I have tried this solution and effectively performances are highly improved. But in this case, the circle around focused point is not painted. In our application, we always need a black circle around nearest point. So, do you have another solution to propose?

This is because when FullRepaint=false the circle pen makes and XOR with its pixels and the pixels under it. However it works changing the circle pen color:

Code: Select all

procedure TForm1.FormCreate(Sender: TObject);
begin
  Series1.FillSampleValues(10000);

  With ChartTool1 do
  begin
    FullRepaint:=false;
    Pen.Color:=clBlack;
  end;
end;

Anyway, we will try to enhance this behavior for the next TeeChart releases.

Narcis, Does Steema expects to deliver a new release fixing this performance defect?

As I already told to SteveP, I've added the request to our wish-list to be enhanced for future releases. In the meantime, you can also FullRepaint=false.

[SiA]

Thanks Narcis,

We will set the FullRepaint property to false and Nearest Tool Pen Color to Black. This change fixes defect in our application.

Best Regards
Gerald

[Narcís]

Hi Gerald,

Other pen colors will also work fine, this basically depends on the chart color.

[Andy]

Tuning idear:

slow sqrt in TeeDistance not needed to find minimal distance
and for what is the round

If on can find out that the chart has not changed
(The normal case during mouse move)
on can store the values
tmpX:=Series.CalcXPos(t);
tmpY:=Series.CalcYPos(t);
in the tool to avoid its calculation again.

Thanks SteveP,

You are right. I have looked in source code TNearestTool.GetNearestPoint and TNearestTool.ChartMouseEvent and it seems that search is always performed from beginning to end of series each time user moves mouse in chart. It is not acceptable for performance when we have more than 20000 data in series. Moreover, search algorithm in GetNearestPoint is basic. Why this GetNearestPoint method does not use a dichotomy search algorithm or more advanced search algorithm? Algorithm may be different for each kind of series to improve performance in different cases.

Code: Select all

class Function TNearestTool.GetNearestPoint(Series:TChartSeries; X,Y:Integer; IncludeNulls:Boolean):Integer;
var t      : Integer;
    Dif    : Integer;
    Dist   : Integer;
    tmpMin : Integer;
    tmpMax : Integer;
    tmpX   : Integer;
    tmpY   : Integer;
    tmpZList : TChartValueList;
    tmpZ   : Integer;
begin
  result:=-1;
  Dif:=10000;

  if TeeGetFirstLastSeries(Series,tmpMin,tmpMax) then
  begin
    tmpZList:=Series.GetYValueList('Z'); // 7.0

    for t:=tmpMin to tmpMax do { <-- traverse all points in a Series... }
    if IncludeNulls or (not Series.IsNull(t)) then // 7.0
    begin
      { calculate position in pixels }
      tmpX:=Series.CalcXPos(t);
      tmpY:=Series.CalcYPos(t);

      if Series.HasZValues then
      begin
        tmpZ:=Series.ParentChart.Axes.Depth.CalcPosValue(tmpZList.Value[t]);

        with Series.ParentChart.Canvas.Calculate3DPosition(tmpX,tmpY,tmpZ) do
        begin
          tmpX:=X;
          tmpY:=Y;
        end;
      end;

      if PointInRect(Series.ParentChart.ChartRect,tmpX,tmpY) then { 5.01 }
      begin
        { calculate distance in pixels... }
        Dist:=Round(TeeDistance(X-tmpX,Y-tmpY));

        if Dist<Dif then { store if distance is lower... }
        begin
          Dif:=Dist;
          result:=t;  { <-- set this point to be the nearest... }
        end;
      end;
    end;
  end;
end;

procedure TNearestTool.ChartMouseEvent(AEvent: TChartMouseEvent;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  inherited;

  if (AEvent=cmeMove) and Assigned(Series) then
  begin
    if not FullRepaint then PaintHint;
    Point:=GetNearestPoint(Series,X,Y);
    IMouse:=TeePoint(x,y);
    if not FullRepaint then PaintHint;
    if Assigned(FOnChange) then FOnChange(Self);
    if FullRepaint then Repaint;
  end;
end;

Narcis, Does Steema expects to deliver a new release fixing this performance defect?

Regards
Gerald

[Narcís]

Hi Andy,

Thanks for the information. I've added it to our wish-list to be reviewed and considered for inclusion in next releases.