Nearest Point tool has bad performance for big series

TeeChart VCL for Borland/CodeGear/Embarcadero RAD Studio, Delphi and C++ Builder.
Post Reply
SiA
Newbie
Newbie
Posts: 43
Joined: Wed Mar 10, 2004 5:00 am

Nearest Point tool has bad performance for big series

Post by SiA » Thu Dec 21, 2006 3:01 pm

Hi Narcis,

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

:arrow: 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?

:idea: I have pushed an example in newsgroup

Best Regards
Gerald

Narcís
Site Admin
Site Admin
Posts: 14730
Joined: Mon Jun 09, 2003 4:00 am
Location: Banyoles, Catalonia
Contact:

Post by Narcís » Thu Dec 21, 2006 4:38 pm

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;
Best Regards,
Narcís Calvet / Development & Support
Steema Software
Avinguda Montilivi 33, 17003 Girona, Catalonia
Tel: 34 972 218 797
http://www.steema.com
Image Image Image Image Image Image
Instructions - How to post in this forum

SiA
Newbie
Newbie
Posts: 43
Joined: Wed Mar 10, 2004 5:00 am

Post by SiA » Thu Dec 21, 2006 4:51 pm

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
Advanced
Posts: 132
Joined: Sun Sep 07, 2003 4:00 am

Post by SteveP » Thu Dec 21, 2006 7:55 pm

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
Site Admin
Site Admin
Posts: 14730
Joined: Mon Jun 09, 2003 4:00 am
Location: Banyoles, Catalonia
Contact:

Post by Narcís » Fri Dec 22, 2006 9:15 am

Hi SteveP,
SteveP wrote: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.
Best Regards,
Narcís Calvet / Development & Support
Steema Software
Avinguda Montilivi 33, 17003 Girona, Catalonia
Tel: 34 972 218 797
http://www.steema.com
Image Image Image Image Image Image
Instructions - How to post in this forum

SiA
Newbie
Newbie
Posts: 43
Joined: Wed Mar 10, 2004 5:00 am

Post by SiA » Fri Dec 22, 2006 9:21 am

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
Site Admin
Site Admin
Posts: 14730
Joined: Mon Jun 09, 2003 4:00 am
Location: Banyoles, Catalonia
Contact:

Post by Narcís » Fri Dec 22, 2006 9:34 am

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.
Best Regards,
Narcís Calvet / Development & Support
Steema Software
Avinguda Montilivi 33, 17003 Girona, Catalonia
Tel: 34 972 218 797
http://www.steema.com
Image Image Image Image Image Image
Instructions - How to post in this forum

SiA
Newbie
Newbie
Posts: 43
Joined: Wed Mar 10, 2004 5:00 am

Post by SiA » Fri Dec 22, 2006 10:40 am

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
Site Admin
Site Admin
Posts: 14730
Joined: Mon Jun 09, 2003 4:00 am
Location: Banyoles, Catalonia
Contact:

Post by Narcís » Fri Dec 22, 2006 11:39 am

Hi Gerald,

Other pen colors will also work fine, this basically depends on the chart color.
Best Regards,
Narcís Calvet / Development & Support
Steema Software
Avinguda Montilivi 33, 17003 Girona, Catalonia
Tel: 34 972 218 797
http://www.steema.com
Image Image Image Image Image Image
Instructions - How to post in this forum

Andy
Newbie
Newbie
Posts: 32
Joined: Wed Apr 18, 2007 12:00 am
Location: Germany Oldenburg
Contact:

Post by Andy » Thu Jan 31, 2008 9:51 am

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.


9336299 wrote: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
Site Admin
Site Admin
Posts: 14730
Joined: Mon Jun 09, 2003 4:00 am
Location: Banyoles, Catalonia
Contact:

Post by Narcís » Mon Feb 04, 2008 12:04 pm

Hi Andy,

Thanks for the information. I've added it to our wish-list to be reviewed and considered for inclusion in next releases.
Best Regards,
Narcís Calvet / Development & Support
Steema Software
Avinguda Montilivi 33, 17003 Girona, Catalonia
Tel: 34 972 218 797
http://www.steema.com
Image Image Image Image Image Image
Instructions - How to post in this forum

Post Reply