GetContourList extremely slow, Is there a Solution?

Hi Rooters,

I’m working with TGraph2D and am hitting a wall in terms of performance when running the GetContourList function. When using >50x50 set of points, performance becomes unbearably slow (ie, upwards of 15min for a 80x80 data set on a Dual processor Mac G4 1.4Ghz). Also, that is when using a fully compiled application, using scripts increases this time considerably.

However, I believe the performance problems reside in whatever set up Root is doing BEFORE running the Contour Algo. My reasoning is that it can take upwards of 15min to extract the first coutour, but subsequent requests happen practically instantaneously.

My problem is that I would like to increase the number of points far beyond 80x80, but I can’t wait 30+ mins. Can anyone shed some light on whether this is unusual performance, why it’s happenening, and perhaps suggest a solution?

Many thanks,

Josh de Bever
CSI Medical Physics Group
The University of Western Ontario
London, Ontario, Canada

You are right, the contour computation is not time consuming, all the time is spend to create the 2D histogram using the Delaunay triangulation algorithm. This alrogithm finds all the Delaunay triangles and uses as interpolation planes to filll the 2D histogram. Depending on the number of points and the points positions, it can take a lot of time. This technic may be hopeless in some cases. You can try to use the method SetMaxIter in TGraph2D to reduce the maximum number of iterations to find one triangle (default is 100000). Note that making it to small may produce bad results. May be you can send me a small example showing your problem.

Olivier

Thanks very much for your reply.

I’ve put together a short script which shows the idea of what I’m trying to do and attached it to this post. There’s a lot of other stuff going on that I cut out, so this script isn’t attempting to do anything useful, but it serves as a good Tech Demo.

Essentially, I have a TGraph2D with a series of Z and Phi points. I fill the graph, and then call a function I wrote for this test script called DoGetContour(). You give it a the graph, and the # of levels you want, and it returns the # of graphs in all the contours. Not too useful, but it demonstrates my problem.

For 20x20-50x50 performance is decent. But crank it up to 80x80, and you run into serious problems. Also note how long it takes to draw at these higher sample rates. Eventually, I’d like to crank this up WAY higher, ideally 512x512 or even 1024x1024 (although I believe TGraph2D actually has a limit of 500 pts or something, which is another problem…).

Anyway, I really appreciate you taking a look at this for me, and if you have any suggestions, I’m all ears.

Thanks again,

Josh de Bever
CSI Medical Physics Group
The University of Western Ontario
London, Ontario, Canada
CERNtest.C (3.97 KB)

Thanks for your example.

Seems to me your are not using the appropriate object to store your data. Your data are regularly distributed on a grid, a 2D histogram would be much more efficient to manipulate them. TGraph2d are meant to work on “small” amount of randomly distributed points. It allows to interpolate them and compute the surface they are laying on. You are not it this case I would suggest you to use a 2D histogram.

I remember playing around with the TH2D, but the reason I went with the Graph2D was because I needed the actual data points on each contour level graph. GetContourList() seemed the most direct way.

Now that I’ve taken a closer look at TH2D, can I get the same info by doing:

if (!fPainter)
fPainter = fHistogram->GetPainter();

return fPainter->GetContourList(contour);
}

Does that look right? If so, it might be worth considering adding GetContourList() to the 2D histogram class (unless of course I missed that too!).

Many thanks for your help.

Josh de Bever
CSI Medical Physics Group
The University of Western Ontario
London, Ontario, Canada

From a 2D histogram you can use the option list when you paint it with the contour option as it is explain in THistPainter::PaintContour:

void THistPainter::PaintContour(Option_t *option)
{
//    *-*-*-*-*-*Control function to draw a table as a contour plot*-*-*-*-*-*
//               =================================================
//     Hoption.Contour may have the following values:
//        1  The contour is drawn with filled colour levels. ("cont")
//       11  Use colour to distinguish contours. ("cont1")
//       12  Use line style to distinguish contours. ("cont2")
//       13  Line style and colour are the same for all contours. ("cont3")
//       14  Same as 1 but uses the "SURF" algorithm ("cont4")
//       15  Use Delaunay triangles to compute the contours
//
//     When option "List" is specified together with option "cont",
//     the points used to draw the contours are saved in the TGraph format
//     and are accessible in the following way:
//    TObjArray *contours =
//            (TObjArray*)gROOT->GetListOfSpecials()->FindObject("contours")
//    Int_t ncontours = contours->GetSize();
//    TList *list = (TList*)contours->At(i); //where i is a contour number
//    list contains a list of TGraph objects. For one given contour, more than  
//    one disjoint polyline may be generated. The number of TGraphs per
//    countour is given by list->GetSize().
//    Here we show only the case to access the first graph in the list.
//       TGraph *gr1 = (TGraph*)list->First();

See also the maco tutorials/FirstContour.C

Is there a way to extract the contour graphs without drawning anything?

Thanks,

Josh de Bever
CSI Medical Physics Group
The University of Western Ontario
London, Ontario, Canada

Not for the time being. PaintContour always paint the contours even with the option LIST.