TGraph2D;DelaunayTriangle; Voronoid diagram

Hi,

I am trying to use ROOT to creat a crystal lookup table for a pixelated gamma ray detector, by creating Voronoid diagrams of the pixels. There are two issues in using ROOT for the task.

Issue 1:

ROOT has the Delaunay Triangulation method implemented for points in 3D space (TGraph2D class). Initially, I thought the 3D triangulation segmentation method should still applies if the data points have a zero for the z coordinate (i.e.z=0). However, the 3D graphic initiialisation does not like z=0 for all points. Error messages were given out. (try the attached file graph2D_mod1.C). However setting z=1.0 seems to overcome the problem.

Issue 2:

Presently, ROOT 5.08 does not implement the complementary method to creat a Voronoid diagram. To creat the Voronoid diagram, one has to:

  1. find the positions of the vertices for all the Delaunay triangles that have been found.
  2. Calculate the centroids of these triangles, and
  3. obtain the Delaunay triangles using these centroid positions.

I am trying to implement the above. However, I cannot find a way to get the vertice positions of each triangles that have been found. I have browsed all the mentods for both the TGraph2d class and TGraphDelaunay class. Only TGraphDelaunay appears to offer methods (GetMTried(), GetNTried() and GetPTried()) to access the indices to the vertice positions. But for some reason, I am not getting sensible returned values. See attached file (Graph2D_mod2.C) for my effort in this regard.

Can some body point out a way for me to retrieve the vertice positions of each triangle found, so that I can calculate the centroids of the triangles?

Solving issue 2 is much more important than 1, since I plan to plot the triangles as polygons on a separate 2D pad rather than on a 3D graphics pad. (similar to the example Triangles.C in the tutorials)

Note: Grapg2D_Mod1 &2 are derived from Graph2D.C in the tutorials.

Thanks very much for your help.

Tim

forget to attach files. Sorry. Here they are.

Tim
graph2D_mod2.C (1.02 KB)
graph2D_mod1.C (620 Bytes)

GetMTried(), GetNTried() and GetPTried() return the pointer to the arrays holding the triangles. They are integer arrays.
The number of triangles is return by GetNdt().
For any integer value “i” between 0 and Ndt-1, you can find a triplet m = Mtried[i], n = Ntried[i], p = Ptried[i] defining a triangle.
(m,n,p) are indices in the arrays returned by GetXN() and GetYN().

These methods are use mainly for internal communications between TGraphDelaunay and TGraph2D. Initially they were not intented to be used directly. But why not …

Up to now the Delaunay triangles are used only for interpolation and drawing purpose in the TGraph2D context. We did not need the Voronoi diagram for that. I know they are closely related, and going from one representation to an other is “quite easy”. If you extent TGraphDelaunay to Voronoi diagram. I will be very pleased to introduce that code in TGraphDelaunay.

We will need more interactions to define a such implementation. For that, I suggest you contact me directly at Olivier.Couet@cern.ch.

As I said in my previous post, TGraphDelaunay was initially intented to be used only via TGraph2D. FindAllTriangles does not work the way you used it because before calling it, two private functions of TGraphDelaunay should be called. One to initialize the triangles data structure and an other one to find the hull in which all triangles lie. For the time being these two functions are accessible only via the Interpolate() method. The following code works the way you want (I just added a call to Interpolate):

[code]void graph2D_mod2() {
TCanvas *c = new TCanvas(“c”,“Graph2D example”,0,0,700,600);
Double_t x, y, z, P = 15.;
Int_t np = 100;
TGraph2D *graph = new TGraph2D();
TRandom *r = new TRandom();

for (Int_t N=0; N<np; N++) {
x = 2P(r->Rndm(N))-P;
y = 2P(r->Rndm(N))-P;
z=1.0; // this is ok, but is not ideal suitable for 2D image segmentation
graph->SetPoint(N,x,y,z);
}

TGraphDelaunay *triangle=new TGraphDelaunay(graph);
triangle->Interpolate(0.,0.);
triangle->FindAllTriangles(); // try to get all the triangles

Int_t nfound= triangle->GetNdt();
printf(“Number of triangles found=%d\n”,nfound);
Int_t* m= triangle->GetMTried();
Int_t* n=triangle->GetNTried();
Int_t* p=triangle->GetPTried();
for (Int_t k=0; k<np; k++)
printf(“m=%d n=%d p=%d\n”,(m+k),(n+k),*(p+k));
}

[/code]

Hi Olivier,

Thank you for your help. I can now get the normalised coordinates for the triangles. The call “triangle->Interpolate(0.,0.);” was critical.

I am looking into more details how Voronoid diagrams are formed. It is not as simple as I first thought (typical). Any how, I will look into it further, and when I have a clearer strategy on how to do it, I will then discuss with you.

Tim