```// @(#)root/hist:\$Id: TGraphDelaunay.cxx,v 1.00
// Author: Olivier Couet, Luke Jones (Royal Holloway, University of London)

/*************************************************************************
*                                                                       *
* For the licensing terms see \$ROOTSYS/LICENSE.                         *
* For the list of contributors see \$ROOTSYS/README/CREDITS.             *
*************************************************************************/

#include "TMath.h"
#include "TGraph2D.h"
#include "TGraphDelaunay.h"

ClassImp(TGraphDelaunay)

//______________________________________________________________________________
//
// TGraphDelaunay generates a Delaunay triangulation of a TGraph2D. This
// triangulation code derives from an implementation done by Luke Jones
// (Royal Holloway, University of London) in April 2002 in the PAW context.
//
// This software cannot be guaranteed to work under all circumstances. They
// were originally written to work with a few hundred points in an XY space
// with similar X and Y ranges.
//
// Definition of Delaunay triangulation (After B. Delaunay):
// For a set S of points in the Euclidean plane, the unique triangulation DT(S)
// of S such that no point in S is inside the circumcircle of any triangle in
// DT(S). DT(S) is the dual of the Voronoi diagram of S. If n is the number of
// points in S, the Voronoi diagram of S is the partitioning of the plane
// containing S points into n convex polygons such that each polygon contains
// exactly one point and every point in a given polygon is closer to its
// central point than to any other. A Voronoi diagram is sometimes also known
// as a Dirichlet tessellation.
//Begin_Html
/*
<img src="gif/dtvd.gif">
<br>
<a href="http://www.cs.cornell.edu/Info/People/chew/Delaunay.html">This applet</a>
gives a nice practical view of Delaunay triangulation and Voronoi diagram.
*/
//End_Html

//______________________________________________________________________________
TGraphDelaunay::TGraphDelaunay()
: TNamed("TGraphDelaunay","TGraphDelaunay")
{
// TGraphDelaunay default constructor

fGraph2D      = 0;
fX            = 0;
fY            = 0;
fZ            = 0;
fNpoints      = 0;
fTriedSize    = 0;
fZout         = 0.;
fNdt          = 0;
fNhull        = 0;
fHullPoints   = 0;
fXN           = 0;
fYN           = 0;
fOrder        = 0;
fDist         = 0;
fPTried       = 0;
fNTried       = 0;
fMTried       = 0;
fInit         = kFALSE;
fXNmin        = 0.;
fXNmax        = 0.;
fYNmin        = 0.;
fYNmax        = 0.;
fXoffset      = 0.;
fYoffset      = 0.;
fXScaleFactor = 0.;
fYScaleFactor = 0.;

SetMaxIter();
}

//______________________________________________________________________________
TGraphDelaunay::TGraphDelaunay(TGraph2D *g)
: TNamed("TGraphDelaunay","TGraphDelaunay")
{
// TGraphDelaunay normal constructor

fGraph2D      = g;
fX            = fGraph2D->GetX();
fY            = fGraph2D->GetY();
fZ            = fGraph2D->GetZ();
fNpoints      = fGraph2D->GetN();
fTriedSize    = 0;
fZout         = 0.;
fNdt          = 0;
fNhull        = 0;
fHullPoints   = 0;
fXN           = 0;
fYN           = 0;
fOrder        = 0;
fDist         = 0;
fPTried       = 0;
fNTried       = 0;
fMTried       = 0;
fInit         = kFALSE;
fXNmin        = 0.;
fXNmax        = 0.;
fYNmin        = 0.;
fYNmax        = 0.;
fXoffset      = 0.;
fYoffset      = 0.;
fXScaleFactor = 0.;
fYScaleFactor = 0.;

SetMaxIter();
}

//______________________________________________________________________________
TGraphDelaunay::~TGraphDelaunay()
{
// TGraphDelaunay destructor.

if (fPTried)     delete [] fPTried;
if (fNTried)     delete [] fNTried;
if (fMTried)     delete [] fMTried;
if (fHullPoints) delete [] fHullPoints;
if (fOrder)      delete [] fOrder;
if (fDist)       delete [] fDist;
if (fXN)         delete [] fXN;
if (fYN)         delete [] fYN;

fPTried     = 0;
fNTried     = 0;
fMTried     = 0;
fHullPoints = 0;
fOrder      = 0;
fDist       = 0;
fXN         = 0;
fYN         = 0;
}

//______________________________________________________________________________
Double_t TGraphDelaunay::ComputeZ(Double_t x, Double_t y)
{
// Return the z value corresponding to the (x,y) point in fGraph2D

// Initialise the Delaunay algorithm if needed.
// CreateTrianglesDataStructure computes fXoffset, fYoffset,
// fXScaleFactor and fYScaleFactor;
// needed in this function.
if (!fInit) {
CreateTrianglesDataStructure();
FindHull();
fInit = kTRUE;
}

// Find the z value corresponding to the point (x,y).
Double_t xx, yy;
xx = (x+fXoffset)*fXScaleFactor;
yy = (y+fYoffset)*fYScaleFactor;
Double_t zz = Interpolate(xx, yy);

// Wrong zeros may appear when points sit on a regular grid.
// The following line try to avoid this problem.
if (zz==0) zz = Interpolate(xx+0.0001, yy);

return zz;
}

//______________________________________________________________________________
void TGraphDelaunay::CreateTrianglesDataStructure()
{
// Function used internally only. It creates the data structures needed to
// compute the Delaunay triangles.

// Offset fX and fY so they average zero, and scale so the average
// of the X and Y ranges is one. The normalized version of fX and fY used
// in Interpolate.
Double_t xmax = fGraph2D->GetXmax();
Double_t ymax = fGraph2D->GetYmax();
Double_t xmin = fGraph2D->GetXmin();
Double_t ymin = fGraph2D->GetYmin();
fXoffset      = -(xmax+xmin)/2.;
fYoffset      = -(ymax+ymin)/2.;
fXScaleFactor  = 1./(xmax-xmin);
fYScaleFactor  = 1./(ymax-ymin);
fXNmax        = (xmax+fXoffset)*fXScaleFactor;
fXNmin        = (xmin+fXoffset)*fXScaleFactor;
fYNmax        = (ymax+fYoffset)*fYScaleFactor;
fYNmin        = (ymin+fYoffset)*fYScaleFactor;
fXN           = new Double_t[fNpoints+1];
fYN           = new Double_t[fNpoints+1];
for (Int_t n=0; n<fNpoints; n++) {
fXN[n+1] = (fX[n]+fXoffset)*fXScaleFactor;
fYN[n+1] = (fY[n]+fYoffset)*fYScaleFactor;
}

// If needed, creates the arrays to hold the Delaunay triangles.
// A maximum number of 2*fNpoints is guessed. If more triangles will be
// find, FillIt will automatically enlarge these arrays.
fTriedSize = 2*fNpoints;
fPTried    = new Int_t[fTriedSize];
fNTried    = new Int_t[fTriedSize];
fMTried    = new Int_t[fTriedSize];
}

//______________________________________________________________________________
Bool_t TGraphDelaunay::Enclose(Int_t t1, Int_t t2, Int_t t3, Int_t e) const
{
// Is point e inside the triangle t1-t2-t3 ?

Double_t x[4],y[4],xp, yp;
x[0] = fXN[t1];
x[1] = fXN[t2];
x[2] = fXN[t3];
x[3] = x[0];
y[0] = fYN[t1];
y[1] = fYN[t2];
y[2] = fYN[t3];
y[3] = y[0];
xp   = fXN[e];
yp   = fYN[e];
return TMath::IsInside(xp, yp, 4, x, y);
}

//______________________________________________________________________________
void TGraphDelaunay::FileIt(Int_t p, Int_t n, Int_t m)
{
// Files the triangle defined by the 3 vertices p, n and m into the
// fxTried arrays. If these arrays are to small they are automatically
// expanded.

Bool_t swap;
Int_t tmp, ps = p, ns = n, ms = m;

// order the vertices before storing them
L1:
swap = kFALSE;
if (ns > ps) { tmp = ps; ps = ns; ns = tmp; swap = kTRUE;}
if (ms > ns) { tmp = ns; ns = ms; ms = tmp; swap = kTRUE;}
if (swap) goto L1;

// expand the triangles storage if needed
if (fNdt>=fTriedSize) {
Int_t newN   = 2*fTriedSize;
Int_t *savep = new Int_t [newN];
Int_t *saven = new Int_t [newN];
Int_t *savem = new Int_t [newN];
memcpy(savep,fPTried,fTriedSize*sizeof(Int_t));
memset(&savep[fTriedSize],0,(newN-fTriedSize)*sizeof(Int_t));
delete [] fPTried;
memcpy(saven,fNTried,fTriedSize*sizeof(Int_t));
memset(&saven[fTriedSize],0,(newN-fTriedSize)*sizeof(Int_t));
delete [] fNTried;
memcpy(savem,fMTried,fTriedSize*sizeof(Int_t));
memset(&savem[fTriedSize],0,(newN-fTriedSize)*sizeof(Int_t));
delete [] fMTried;
fPTried    = savep;
fNTried    = saven;
fMTried    = savem;
fTriedSize = newN;
}

// store a new Delaunay triangle
fNdt++;
fPTried[fNdt-1] = ps;
fNTried[fNdt-1] = ns;
fMTried[fNdt-1] = ms;
}

//______________________________________________________________________________
void TGraphDelaunay::FindAllTriangles()
{
// Attempt to find all the Delaunay triangles of the point set. It is not
// guaranteed that it will fully succeed, and no check is made that it has
// fully succeeded (such a check would be possible by referencing the points
// that make up the convex hull). The method is to check if each triangle
// shares all three of its sides with other triangles. If not, a point is
// generated just outside the triangle on the side(s) not shared, and a new
// triangle is found for that point. If this method is not working properly
// (many triangles are not being found) it's probably because the new points
// are too far beyond or too close to the non-shared sides. Fiddling with
// the size of the `alittlebit' parameter may help.

if (fAllTri) return; else fAllTri = kTRUE;

Double_t xcntr,ycntr,xm,ym,xx,yy;
Double_t sx,sy,nx,ny,mx,my,mdotn,nn,a;
Int_t t1,t2,pa,na,ma,pb,nb,mb,p1=0,p2=0,m,n,p3=0;
Bool_t s[3];
Double_t alittlebit = 0.0001;

// start with a point that is guaranteed to be inside the hull (the
// centre of the hull). The starting point is shifted "a little bit"
// otherwise, in case of triangles aligned on a regular grid, we may
// found none of them.
xcntr = 0;
ycntr = 0;
for (n=1; n<=fNhull; n++) {
xcntr = xcntr+fXN[fHullPoints[n-1]];
ycntr = ycntr+fYN[fHullPoints[n-1]];
}
xcntr = xcntr/fNhull+alittlebit;
ycntr = ycntr/fNhull+alittlebit;
// and calculate it's triangle
Interpolate(xcntr,ycntr);

// loop over all Delaunay triangles (including those constantly being
// produced within the loop) and check to see if their 3 sides also
// correspond to the sides of other Delaunay triangles, i.e. that they
// have all their neighbours.
t1 = 1;
while (t1 <= fNdt) {
// get the three points that make up this triangle
pa = fPTried[t1-1];
na = fNTried[t1-1];
ma = fMTried[t1-1];

// produce three integers which will represent the three sides
s[0]  = kFALSE;
s[1]  = kFALSE;
s[2]  = kFALSE;
// loop over all other Delaunay triangles
for (t2=1; t2<=fNdt; t2++) {
if (t2 != t1) {
// get the points that make up this triangle
pb = fPTried[t2-1];
nb = fNTried[t2-1];
mb = fMTried[t2-1];
// do triangles t1 and t2 share a side?
if ((pa==pb && na==nb) || (pa==pb && na==mb) || (pa==nb && na==mb)) {
// they share side 1
s[0] = kTRUE;
} else if ((pa==pb && ma==nb) || (pa==pb && ma==mb) || (pa==nb && ma==mb)) {
// they share side 2
s[1] = kTRUE;
} else if ((na==pb && ma==nb) || (na==pb && ma==mb) || (na==nb && ma==mb)) {
// they share side 3
s[2] = kTRUE;
}
}
// if t1 shares all its sides with other Delaunay triangles then
if (s[0] && s[1] && s[2]) continue;
}
// Looks like t1 is missing a neighbour on at least one side.
// For each side, take a point a little bit beyond it and calculate
// the Delaunay triangle for that point, this should be the triangle
// which shares the side.
for (m=1; m<=3; m++) {
if (!s[m-1]) {
// get the two points that make up this side
if (m == 1) {
p1 = pa;
p2 = na;
p3 = ma;
} else if (m == 2) {
p1 = pa;
p2 = ma;
p3 = na;
} else if (m == 3) {
p1 = na;
p2 = ma;
p3 = pa;
}
// get the coordinates of the centre of this side
xm = (fXN[p1]+fXN[p2])/2.;
ym = (fYN[p1]+fYN[p2])/2.;
// we want to add a little to these coordinates to get a point just
// outside the triangle; (sx,sy) will be the vector that represents
// the side
sx = fXN[p1]-fXN[p2];
sy = fYN[p1]-fYN[p2];
// (nx,ny) will be the normal to the side, but don't know if it's
// pointing in or out yet
nx    = sy;
ny    = -sx;
nn    = TMath::Sqrt(nx*nx+ny*ny);
nx    = nx/nn;
ny    = ny/nn;
mx    = fXN[p3]-xm;
my    = fYN[p3]-ym;
mdotn = mx*nx+my*ny;
if (mdotn > 0) {
// (nx,ny) is pointing in, we want it pointing out
nx = -nx;
ny = -ny;
}
// increase/decrease xm and ym a little to produce a point
// just outside the triangle (ensuring that the amount added will
// be large enough such that it won't be lost in rounding errors)
a  = TMath::Abs(TMath::Max(alittlebit*xm,alittlebit*ym));
xx = xm+nx*a;
yy = ym+ny*a;
// try and find a new Delaunay triangle for this point
Interpolate(xx,yy);

// this side of t1 should now, hopefully, if it's not part of the
// hull, be shared with a new Delaunay triangle just calculated by Interpolate
}
}
t1++;
}
}

//______________________________________________________________________________
void TGraphDelaunay::FindHull()
{
// Finds those points which make up the convex hull of the set. If the xy
// plane were a sheet of wood, and the points were nails hammered into it
// at the respective coordinates, then if an elastic band were stretched
// over all the nails it would form the shape of the convex hull. Those
// nails in contact with it are the points that make up the hull.

Int_t n,nhull_tmp;
Bool_t in;

if (!fHullPoints) fHullPoints = new Int_t[fNpoints];

nhull_tmp = 0;
for(n=1; n<=fNpoints; n++) {
// if the point is not inside the hull of the set of all points
// bar it, then it is part of the hull of the set of all points
// including it
in = InHull(n,n);
if (!in) {
// cannot increment fNhull directly - InHull needs to know that
// the hull has not yet been completely found
nhull_tmp++;
fHullPoints[nhull_tmp-1] = n;
}
}
fNhull = nhull_tmp;
}

//______________________________________________________________________________
Bool_t TGraphDelaunay::InHull(Int_t e, Int_t x) const
{
// Is point e inside the hull defined by all points apart from x ?

Int_t n1,n2,n,m,ntry;
Double_t lastdphi,dd1,dd2,dx1,dx2,dx3,dy1,dy2,dy3;
Double_t u,v,vNv1,vNv2,phi1,phi2,dphi,xx,yy;

Bool_t deTinhull = kFALSE;

xx = fXN[e];
yy = fYN[e];

if (fNhull > 0) {
//  The hull has been found - no need to use any points other than
//  those that make up the hull
ntry = fNhull;
} else {
//  The hull has not yet been found, will have to try every point
ntry = fNpoints;
}

//  n1 and n2 will represent the two points most separated by angle
//  from point e. Initially the angle between them will be <180 degs.
//  But subsequent points will increase the n1-e-n2 angle. If it
//  increases above 180 degrees then point e must be surrounded by
//  points - it is not part of the hull.
n1 = 1;
n2 = 2;
if (n1 == x) {
n1 = n2;
n2++;
} else if (n2 == x) {
n2++;
}

//  Get the angle n1-e-n2 and set it to lastdphi
dx1  = xx-fXN[n1];
dy1  = yy-fYN[n1];
dx2  = xx-fXN[n2];
dy2  = yy-fYN[n2];
phi1 = TMath::ATan2(dy1,dx1);
phi2 = TMath::ATan2(dy2,dx2);
dphi = (phi1-phi2)-((Int_t)((phi1-phi2)/TMath::TwoPi())*TMath::TwoPi());
if (dphi < 0) dphi = dphi+TMath::TwoPi();
lastdphi = dphi;
for (n=1; n<=ntry; n++) {
if (fNhull > 0) {
// Try hull point n
m = fHullPoints[n-1];
} else {
m = n;
}
if ((m!=n1) && (m!=n2) && (m!=x)) {
// Can the vector e->m be represented as a sum with positive
// coefficients of vectors e->n1 and e->n2?
dx1 = xx-fXN[n1];
dy1 = yy-fYN[n1];
dx2 = xx-fXN[n2];
dy2 = yy-fYN[n2];
dx3 = xx-fXN[m];
dy3 = yy-fYN[m];

dd1 = (dx2*dy1-dx1*dy2);
dd2 = (dx1*dy2-dx2*dy1);

if (dd1*dd2!=0) {
u = (dx2*dy3-dx3*dy2)/dd1;
v = (dx1*dy3-dx3*dy1)/dd2;
if ((u<0) || (v<0)) {
// No, it cannot - point m does not lie inbetween n1 and n2 as
// viewed from e. Replace either n1 or n2 to increase the
// n1-e-n2 angle. The one to replace is the one which makes the
// smallest angle with e->m
vNv1 = (dx1*dx3+dy1*dy3)/TMath::Sqrt(dx1*dx1+dy1*dy1);
vNv2 = (dx2*dx3+dy2*dy3)/TMath::Sqrt(dx2*dx2+dy2*dy2);
if (vNv1 > vNv2) {
n1   = m;
phi1 = TMath::ATan2(dy3,dx3);
phi2 = TMath::ATan2(dy2,dx2);
} else {
n2   = m;
phi1 = TMath::ATan2(dy1,dx1);
phi2 = TMath::ATan2(dy3,dx3);
}
dphi = (phi1-phi2)-((Int_t)((phi1-phi2)/TMath::TwoPi())*TMath::TwoPi());
if (dphi < 0) dphi = dphi+TMath::TwoPi();
if (((dphi-TMath::Pi())*(lastdphi-TMath::Pi())) < 0) {
// The addition of point m means the angle n1-e-n2 has risen
// above 180 degs, the point is in the hull.
goto L10;
}
lastdphi = dphi;
}
}
}
}
// Point e is not surrounded by points - it is not in the hull.
goto L999;
L10:
deTinhull = kTRUE;
L999:
return deTinhull;
}

//______________________________________________________________________________
Double_t TGraphDelaunay::InterpolateOnPlane(Int_t TI1, Int_t TI2, Int_t TI3, Int_t e) const
{
// Finds the z-value at point e given that it lies
// on the plane defined by t1,t2,t3

Int_t tmp;
Bool_t swap;
Double_t x1,x2,x3,y1,y2,y3,f1,f2,f3,u,v,w;

Int_t t1 = TI1;
Int_t t2 = TI2;
Int_t t3 = TI3;

// order the vertices
L1:
swap = kFALSE;
if (t2 > t1) { tmp = t1; t1 = t2; t2 = tmp; swap = kTRUE;}
if (t3 > t2) { tmp = t2; t2 = t3; t3 = tmp; swap = kTRUE;}
if (swap) goto L1;

x1 = fXN[t1];
x2 = fXN[t2];
x3 = fXN[t3];
y1 = fYN[t1];
y2 = fYN[t2];
y3 = fYN[t3];
f1 = fZ[t1-1];
f2 = fZ[t2-1];
f3 = fZ[t3-1];
u  = (f1*(y2-y3)+f2*(y3-y1)+f3*(y1-y2))/(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
v  = (f1*(x2-x3)+f2*(x3-x1)+f3*(x1-x2))/(y1*(x2-x3)+y2*(x3-x1)+y3*(x1-x2));
w  = f1-u*x1-v*y1;

return u*fXN[e]+v*fYN[e]+w;
}

//______________________________________________________________________________
Double_t TGraphDelaunay::Interpolate(Double_t xx, Double_t yy)
{
// Finds the Delaunay triangle that the point (xi,yi) sits in (if any) and
// calculate a z-value for it by linearly interpolating the z-values that
// make up that triangle.

Double_t thevalue;

Int_t it, ntris_tried, p, n, m;
Int_t i,j,k,l,z,f,d,o1,o2,a,b,t1,t2,t3;
Int_t ndegen=0,degen=0,fdegen=0,o1degen=0,o2degen=0;
Double_t vxN,vyN;
Double_t d1,d2,d3,c1,c2,dko1,dko2,dfo1;
Double_t dfo2,sin_sum,cfo1k,co2o1k,co2o1f;

Bool_t shouldbein;
Double_t dx1,dx2,dx3,dy1,dy2,dy3,u,v,dxz[3],dyz[3];

// initialise the Delaunay algorithm if needed
if (!fInit) {
CreateTrianglesDataStructure();
FindHull();
fInit = kTRUE;
}

// create vectors needed for sorting
if (!fOrder) {
fOrder = new Int_t[fNpoints];
fDist  = new Double_t[fNpoints];
}

// the input point will be point zero.
fXN[0] = xx;
fYN[0] = yy;

// set the output value to the default value for now
thevalue = fZout;

// some counting
ntris_tried = 0;

// no point in proceeding if xx or yy are silly
if ((xx>fXNmax) || (xx<fXNmin) || (yy>fYNmax) || (yy<fYNmin)) return thevalue;

// check existing Delaunay triangles for a good one
for (it=1; it<=fNdt; it++) {
p = fPTried[it-1];
n = fNTried[it-1];
m = fMTried[it-1];
// p, n and m form a previously found Delaunay triangle, does it
// enclose the point?
if (Enclose(p,n,m,0)) {
// yes, we have the triangle
thevalue = InterpolateOnPlane(p,n,m,0);
return thevalue;
}
}

// is this point inside the convex hull?
shouldbein = InHull(0,-1);
if (!shouldbein) return thevalue;

// it must be in a Delaunay triangle - find it...

// order mass points by distance in mass plane from desired point
for (it=1; it<=fNpoints; it++) {
vxN = fXN[it];
vyN = fYN[it];
fDist[it-1] = TMath::Sqrt((xx-vxN)*(xx-vxN)+(yy-vyN)*(yy-vyN));
}

// sort array 'fDist' to find closest points
TMath::Sort(fNpoints, fDist, fOrder, kFALSE);
for (it=0; it<fNpoints; it++) fOrder[it]++;

// loop over triplets of close points to try to find a triangle that
// encloses the point.
for (k=3; k<=fNpoints; k++) {
m = fOrder[k-1];
for (j=2; j<=k-1; j++) {
n = fOrder[j-1];
for (i=1; i<=j-1; i++) {
p = fOrder[i-1];
if (ntris_tried > fMaxIter) {
// perhaps this point isn't in the hull after all
///            Warning("Interpolate",
///                    "Abandoning the effort to find a Delaunay triangle (and thus interpolated z-value) for point %g %g"
///                    ,xx,yy);
return thevalue;
}
ntris_tried++;
// check the points aren't colinear
d1 = TMath::Sqrt((fXN[p]-fXN[n])*(fXN[p]-fXN[n])+(fYN[p]-fYN[n])*(fYN[p]-fYN[n]));
d2 = TMath::Sqrt((fXN[p]-fXN[m])*(fXN[p]-fXN[m])+(fYN[p]-fYN[m])*(fYN[p]-fYN[m]));
d3 = TMath::Sqrt((fXN[n]-fXN[m])*(fXN[n]-fXN[m])+(fYN[n]-fYN[m])*(fYN[n]-fYN[m]));
if ((d1+d2<=d3) || (d1+d3<=d2) || (d2+d3<=d1)) goto L90;

// does the triangle enclose the point?
if (!Enclose(p,n,m,0)) goto L90;

// is it a Delaunay triangle? (ie. are there any other points
// inside the circle that is defined by its vertices?)

// test the triangle for Delaunay'ness

// loop over all other points testing each to see if it's
// inside the triangle's circle
ndegen = 0;
for ( z=1; z<=fNpoints; z++) {
if ((z==p) || (z==n) || (z==m)) goto L50;
// An easy first check is to see if point z is inside the triangle
// (if it's in the triangle it's also in the circle)

// point z cannot be inside the triangle if it's further from (xx,yy)
// than the furthest pointing making up the triangle - test this
for (l=1; l<=fNpoints; l++) {
if (fOrder[l-1] == z) {
if ((l<i) || (l<j) || (l<k)) {
// point z is nearer to (xx,yy) than m, n or p - it could be in the
// triangle so call enclose to find out

// if it is inside the triangle this can't be a Delaunay triangle
if (Enclose(p,n,m,z)) goto L90;
} else {
// there's no way it could be in the triangle so there's no point
// calling enclose
goto L1;
}
}
}
// is point z colinear with any pair of the triangle points?
L1:
if (((fXN[p]-fXN[z])*(fYN[p]-fYN[n])) == ((fYN[p]-fYN[z])*(fXN[p]-fXN[n]))) {
// z is colinear with p and n
a = p;
b = n;
} else if (((fXN[p]-fXN[z])*(fYN[p]-fYN[m])) == ((fYN[p]-fYN[z])*(fXN[p]-fXN[m]))) {
// z is colinear with p and m
a = p;
b = m;
} else if (((fXN[n]-fXN[z])*(fYN[n]-fYN[m])) == ((fYN[n]-fYN[z])*(fXN[n]-fXN[m]))) {
// z is colinear with n and m
a = n;
b = m;
} else {
a = 0;
b = 0;
}
if (a != 0) {
// point z is colinear with 2 of the triangle points, if it lies
// between them it's in the circle otherwise it's outside
if (fXN[a] != fXN[b]) {
if (((fXN[z]-fXN[a])*(fXN[z]-fXN[b])) < 0) {
goto L90;
} else if (((fXN[z]-fXN[a])*(fXN[z]-fXN[b])) == 0) {
// At least two points are sitting on top of each other, we will
// treat these as one and not consider this a 'multiple points lying
// on a common circle' situation. It is a sign something could be
// wrong though, especially if the two coincident points have
// different fZ's. If they don't then this is harmless.
Warning("Interpolate", "Two of these three points are coincident %d %d %d",a,b,z);
}
} else {
if (((fYN[z]-fYN[a])*(fYN[z]-fYN[b])) < 0) {
goto L90;
} else if (((fYN[z]-fYN[a])*(fYN[z]-fYN[b])) == 0) {
// At least two points are sitting on top of each other - see above.
Warning("Interpolate", "Two of these three points are coincident %d %d %d",a,b,z);
}
}
// point is outside the circle, move to next point
goto L50;
}

// if point z were to look at the triangle, which point would it see
// lying between the other two? (we're going to form a quadrilateral
// from the points, and then demand certain properties of that
dxz[0] = fXN[p]-fXN[z];
dyz[0] = fYN[p]-fYN[z];
dxz[1] = fXN[n]-fXN[z];
dyz[1] = fYN[n]-fYN[z];
dxz[2] = fXN[m]-fXN[z];
dyz[2] = fYN[m]-fYN[z];
for(l=1; l<=3; l++) {
dx1 = dxz[l-1];
dx2 = dxz[l%3];
dx3 = dxz[(l+1)%3];
dy1 = dyz[l-1];
dy2 = dyz[l%3];
dy3 = dyz[(l+1)%3];

// u et v are used only to know their sign. The previous
// code computed them with a division which was long and
// might be a division by 0. It is now replaced by a
// multiplication.
u = (dy3*dx2-dx3*dy2)*(dy1*dx2-dx1*dy2);
v = (dy3*dx1-dx3*dy1)*(dy2*dx1-dx2*dy1);

if ((u>=0) && (v>=0)) {
// vector (dx3,dy3) is expressible as a sum of the other two vectors
// with positive coefficents -> i.e. it lies between the other two vectors
if (l == 1) {
f  = m;
o1 = p;
o2 = n;
} else if (l == 2) {
f  = p;
o1 = n;
o2 = m;
} else {
f  = n;
o1 = m;
o2 = p;
}
goto L2;
}
}
///            Error("Interpolate", "Should not get to here");
// may as well soldier on
f  = m;
o1 = p;
o2 = n;
L2:
// this is not a valid quadrilateral if the diagonals don't cross,
// check that points f and z lie on opposite side of the line o1-o2,
// this is true if the angle f-o1-z is greater than o2-o1-z and o2-o1-f
cfo1k  = ((fXN[f]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[f]-fYN[o1])*(fYN[z]-fYN[o1]))/
TMath::Sqrt(((fXN[f]-fXN[o1])*(fXN[f]-fXN[o1])+(fYN[f]-fYN[o1])*(fYN[f]-fYN[o1]))*
((fXN[z]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[z]-fYN[o1])*(fYN[z]-fYN[o1])));
co2o1k = ((fXN[o2]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[z]-fYN[o1]))/
TMath::Sqrt(((fXN[o2]-fXN[o1])*(fXN[o2]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[o2]-fYN[o1]))*
((fXN[z]-fXN[o1])*(fXN[z]-fXN[o1])  + (fYN[z]-fYN[o1])*(fYN[z]-fYN[o1])));
co2o1f = ((fXN[o2]-fXN[o1])*(fXN[f]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[f]-fYN[o1]))/
TMath::Sqrt(((fXN[o2]-fXN[o1])*(fXN[o2]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[o2]-fYN[o1]))*
((fXN[f]-fXN[o1])*(fXN[f]-fXN[o1]) + (fYN[f]-fYN[o1])*(fYN[f]-fYN[o1]) ));
if ((cfo1k>co2o1k) || (cfo1k>co2o1f)) {
// not a valid quadrilateral - point z is definitely outside the circle
goto L50;
}
// calculate the 2 internal angles of the quadrangle formed by joining
// points z and f to points o1 and o2, at z and f. If they sum to less
// than 180 degrees then z lies outside the circle
dko1    = TMath::Sqrt((fXN[z]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[z]-fYN[o1])*(fYN[z]-fYN[o1]));
dko2    = TMath::Sqrt((fXN[z]-fXN[o2])*(fXN[z]-fXN[o2])+(fYN[z]-fYN[o2])*(fYN[z]-fYN[o2]));
dfo1    = TMath::Sqrt((fXN[f]-fXN[o1])*(fXN[f]-fXN[o1])+(fYN[f]-fYN[o1])*(fYN[f]-fYN[o1]));
dfo2    = TMath::Sqrt((fXN[f]-fXN[o2])*(fXN[f]-fXN[o2])+(fYN[f]-fYN[o2])*(fYN[f]-fYN[o2]));
c1      = ((fXN[z]-fXN[o1])*(fXN[z]-fXN[o2])+(fYN[z]-fYN[o1])*(fYN[z]-fYN[o2]))/dko1/dko2;
c2      = ((fXN[f]-fXN[o1])*(fXN[f]-fXN[o2])+(fYN[f]-fYN[o1])*(fYN[f]-fYN[o2]))/dfo1/dfo2;
sin_sum = c1*TMath::Sqrt(1-c2*c2)+c2*TMath::Sqrt(1-c1*c1);

// sin_sum doesn't always come out as zero when it should do.
if (sin_sum < -1.E-6) {
// z is inside the circle, this is not a Delaunay triangle
goto L90;
} else if (TMath::Abs(sin_sum) <= 1.E-6) {
// point z lies on the circumference of the circle (within rounding errors)
// defined by the triangle, so there is potential for degeneracy in the
// triangle set (Delaunay triangulation does not give a unique way to split
// a polygon whose points lie on a circle into constituent triangles). Make
// a note of the additional point number.
ndegen++;
degen   = z;
fdegen  = f;
o1degen = o1;
o2degen = o2;
}
L50:
continue;
}
// This is a good triangle
if (ndegen > 0) {
// but is degenerate with at least one other,
// haven't figured out what to do if more than 4 points are involved
///            if (ndegen > 1) {
///               Error("Interpolate",
///                     "More than 4 points lying on a circle. No decision making process formulated for triangulating this region in a non-arbitrary way %d %d %d %d",
///                     p,n,m,degen);
///               return thevalue;
///            }

// we have a quadrilateral which can be split down either diagonal
// (d<->f or o1<->o2) to form valid Delaunay triangles. Choose diagonal
// with highest average z-value. Whichever we choose we will have
// verified two triangles as good and two as bad, only note the good ones
d  = degen;
f  = fdegen;
o1 = o1degen;
o2 = o2degen;
if ((fZ[o1-1]+fZ[o2-1]) > (fZ[d-1]+fZ[f-1])) {
// best diagonalisation of quadrilateral is current one, we have
// the triangle
t1 = p;
t2 = n;
t3 = m;
// file the good triangles
FileIt(p, n, m);
FileIt(d, o1, o2);
} else {
// use other diagonal to split quadrilateral, use triangle formed by
// point f, the degnerate point d and whichever of o1 and o2 create
// an enclosing triangle
t1 = f;
t2 = d;
if (Enclose(f,d,o1,0)) {
t3 = o1;
} else {
t3 = o2;
}
// file the good triangles
FileIt(f, d, o1);
FileIt(f, d, o2);
}
} else {
// this is a Delaunay triangle, file it
FileIt(p, n, m);
t1 = p;
t2 = n;
t3 = m;
}
// do the interpolation
thevalue = InterpolateOnPlane(t1,t2,t3,0);
return thevalue;
L90:
continue;
}
}
}
if (shouldbein) {
Error("Interpolate",
"Point outside hull when expected inside: this point could be dodgy %g %g %d",
xx, yy, ntris_tried);
}
return thevalue;
}

//______________________________________________________________________________
void TGraphDelaunay::SetMaxIter(Int_t n)
{
// Defines the number of triangles tested for a Delaunay triangle
// (number of iterations) before abandoning the search

fAllTri  = kFALSE;
fMaxIter = n;
}

//______________________________________________________________________________
void TGraphDelaunay::SetMarginBinsContent(Double_t z)
{
// Sets the histogram bin height for points lying outside the convex hull ie:
// the bins in the margin.

fZout = z;
}
```
TGraphDelaunay.cxx:1
TGraphDelaunay.cxx:2
TGraphDelaunay.cxx:3
TGraphDelaunay.cxx:4
TGraphDelaunay.cxx:5
TGraphDelaunay.cxx:6
TGraphDelaunay.cxx:7
TGraphDelaunay.cxx:8
TGraphDelaunay.cxx:9
TGraphDelaunay.cxx:10
TGraphDelaunay.cxx:11
TGraphDelaunay.cxx:12
TGraphDelaunay.cxx:13
TGraphDelaunay.cxx:14
TGraphDelaunay.cxx:15
TGraphDelaunay.cxx:16
TGraphDelaunay.cxx:17
TGraphDelaunay.cxx:18
TGraphDelaunay.cxx:19
TGraphDelaunay.cxx:20
TGraphDelaunay.cxx:21
TGraphDelaunay.cxx:22
TGraphDelaunay.cxx:23
TGraphDelaunay.cxx:24
TGraphDelaunay.cxx:25
TGraphDelaunay.cxx:26
TGraphDelaunay.cxx:27
TGraphDelaunay.cxx:28
TGraphDelaunay.cxx:29
TGraphDelaunay.cxx:30
TGraphDelaunay.cxx:31
TGraphDelaunay.cxx:32
TGraphDelaunay.cxx:33
TGraphDelaunay.cxx:34
TGraphDelaunay.cxx:35
TGraphDelaunay.cxx:36
TGraphDelaunay.cxx:37
TGraphDelaunay.cxx:38
TGraphDelaunay.cxx:39
TGraphDelaunay.cxx:40
TGraphDelaunay.cxx:41
TGraphDelaunay.cxx:42
TGraphDelaunay.cxx:43
TGraphDelaunay.cxx:44
TGraphDelaunay.cxx:45
TGraphDelaunay.cxx:46
TGraphDelaunay.cxx:47
TGraphDelaunay.cxx:48
TGraphDelaunay.cxx:49
TGraphDelaunay.cxx:50
TGraphDelaunay.cxx:51
TGraphDelaunay.cxx:52
TGraphDelaunay.cxx:53
TGraphDelaunay.cxx:54
TGraphDelaunay.cxx:55
TGraphDelaunay.cxx:56
TGraphDelaunay.cxx:57
TGraphDelaunay.cxx:58
TGraphDelaunay.cxx:59
TGraphDelaunay.cxx:60
TGraphDelaunay.cxx:61
TGraphDelaunay.cxx:62
TGraphDelaunay.cxx:63
TGraphDelaunay.cxx:64
TGraphDelaunay.cxx:65
TGraphDelaunay.cxx:66
TGraphDelaunay.cxx:67
TGraphDelaunay.cxx:68
TGraphDelaunay.cxx:69
TGraphDelaunay.cxx:70
TGraphDelaunay.cxx:71
TGraphDelaunay.cxx:72
TGraphDelaunay.cxx:73
TGraphDelaunay.cxx:74
TGraphDelaunay.cxx:75
TGraphDelaunay.cxx:76
TGraphDelaunay.cxx:77
TGraphDelaunay.cxx:78
TGraphDelaunay.cxx:79
TGraphDelaunay.cxx:80
TGraphDelaunay.cxx:81
TGraphDelaunay.cxx:82
TGraphDelaunay.cxx:83
TGraphDelaunay.cxx:84
TGraphDelaunay.cxx:85
TGraphDelaunay.cxx:86
TGraphDelaunay.cxx:87
TGraphDelaunay.cxx:88
TGraphDelaunay.cxx:89
TGraphDelaunay.cxx:90
TGraphDelaunay.cxx:91
TGraphDelaunay.cxx:92
TGraphDelaunay.cxx:93
TGraphDelaunay.cxx:94
TGraphDelaunay.cxx:95
TGraphDelaunay.cxx:96
TGraphDelaunay.cxx:97
TGraphDelaunay.cxx:98
TGraphDelaunay.cxx:99
TGraphDelaunay.cxx:100
TGraphDelaunay.cxx:101
TGraphDelaunay.cxx:102
TGraphDelaunay.cxx:103
TGraphDelaunay.cxx:104
TGraphDelaunay.cxx:105
TGraphDelaunay.cxx:106
TGraphDelaunay.cxx:107
TGraphDelaunay.cxx:108
TGraphDelaunay.cxx:109
TGraphDelaunay.cxx:110
TGraphDelaunay.cxx:111
TGraphDelaunay.cxx:112
TGraphDelaunay.cxx:113
TGraphDelaunay.cxx:114
TGraphDelaunay.cxx:115
TGraphDelaunay.cxx:116
TGraphDelaunay.cxx:117
TGraphDelaunay.cxx:118
TGraphDelaunay.cxx:119
TGraphDelaunay.cxx:120
TGraphDelaunay.cxx:121
TGraphDelaunay.cxx:122
TGraphDelaunay.cxx:123
TGraphDelaunay.cxx:124
TGraphDelaunay.cxx:125
TGraphDelaunay.cxx:126
TGraphDelaunay.cxx:127
TGraphDelaunay.cxx:128
TGraphDelaunay.cxx:129
TGraphDelaunay.cxx:130
TGraphDelaunay.cxx:131
TGraphDelaunay.cxx:132
TGraphDelaunay.cxx:133
TGraphDelaunay.cxx:134
TGraphDelaunay.cxx:135
TGraphDelaunay.cxx:136
TGraphDelaunay.cxx:137
TGraphDelaunay.cxx:138
TGraphDelaunay.cxx:139
TGraphDelaunay.cxx:140
TGraphDelaunay.cxx:141
TGraphDelaunay.cxx:142
TGraphDelaunay.cxx:143
TGraphDelaunay.cxx:144
TGraphDelaunay.cxx:145
TGraphDelaunay.cxx:146
TGraphDelaunay.cxx:147
TGraphDelaunay.cxx:148
TGraphDelaunay.cxx:149
TGraphDelaunay.cxx:150
TGraphDelaunay.cxx:151
TGraphDelaunay.cxx:152
TGraphDelaunay.cxx:153
TGraphDelaunay.cxx:154
TGraphDelaunay.cxx:155
TGraphDelaunay.cxx:156
TGraphDelaunay.cxx:157
TGraphDelaunay.cxx:158
TGraphDelaunay.cxx:159
TGraphDelaunay.cxx:160
TGraphDelaunay.cxx:161
TGraphDelaunay.cxx:162
TGraphDelaunay.cxx:163
TGraphDelaunay.cxx:164
TGraphDelaunay.cxx:165
TGraphDelaunay.cxx:166
TGraphDelaunay.cxx:167
TGraphDelaunay.cxx:168
TGraphDelaunay.cxx:169
TGraphDelaunay.cxx:170
TGraphDelaunay.cxx:171
TGraphDelaunay.cxx:172
TGraphDelaunay.cxx:173
TGraphDelaunay.cxx:174
TGraphDelaunay.cxx:175
TGraphDelaunay.cxx:176
TGraphDelaunay.cxx:177
TGraphDelaunay.cxx:178
TGraphDelaunay.cxx:179
TGraphDelaunay.cxx:180
TGraphDelaunay.cxx:181
TGraphDelaunay.cxx:182
TGraphDelaunay.cxx:183
TGraphDelaunay.cxx:184
TGraphDelaunay.cxx:185
TGraphDelaunay.cxx:186
TGraphDelaunay.cxx:187
TGraphDelaunay.cxx:188
TGraphDelaunay.cxx:189
TGraphDelaunay.cxx:190
TGraphDelaunay.cxx:191
TGraphDelaunay.cxx:192
TGraphDelaunay.cxx:193
TGraphDelaunay.cxx:194
TGraphDelaunay.cxx:195
TGraphDelaunay.cxx:196
TGraphDelaunay.cxx:197
TGraphDelaunay.cxx:198
TGraphDelaunay.cxx:199
TGraphDelaunay.cxx:200
TGraphDelaunay.cxx:201
TGraphDelaunay.cxx:202
TGraphDelaunay.cxx:203
TGraphDelaunay.cxx:204
TGraphDelaunay.cxx:205
TGraphDelaunay.cxx:206
TGraphDelaunay.cxx:207
TGraphDelaunay.cxx:208
TGraphDelaunay.cxx:209
TGraphDelaunay.cxx:210
TGraphDelaunay.cxx:211
TGraphDelaunay.cxx:212
TGraphDelaunay.cxx:213
TGraphDelaunay.cxx:214
TGraphDelaunay.cxx:215
TGraphDelaunay.cxx:216
TGraphDelaunay.cxx:217
TGraphDelaunay.cxx:218
TGraphDelaunay.cxx:219
TGraphDelaunay.cxx:220
TGraphDelaunay.cxx:221
TGraphDelaunay.cxx:222
TGraphDelaunay.cxx:223
TGraphDelaunay.cxx:224
TGraphDelaunay.cxx:225
TGraphDelaunay.cxx:226
TGraphDelaunay.cxx:227
TGraphDelaunay.cxx:228
TGraphDelaunay.cxx:229
TGraphDelaunay.cxx:230
TGraphDelaunay.cxx:231
TGraphDelaunay.cxx:232
TGraphDelaunay.cxx:233
TGraphDelaunay.cxx:234
TGraphDelaunay.cxx:235
TGraphDelaunay.cxx:236
TGraphDelaunay.cxx:237
TGraphDelaunay.cxx:238
TGraphDelaunay.cxx:239
TGraphDelaunay.cxx:240
TGraphDelaunay.cxx:241
TGraphDelaunay.cxx:242
TGraphDelaunay.cxx:243
TGraphDelaunay.cxx:244
TGraphDelaunay.cxx:245
TGraphDelaunay.cxx:246
TGraphDelaunay.cxx:247
TGraphDelaunay.cxx:248
TGraphDelaunay.cxx:249
TGraphDelaunay.cxx:250
TGraphDelaunay.cxx:251
TGraphDelaunay.cxx:252
TGraphDelaunay.cxx:253
TGraphDelaunay.cxx:254
TGraphDelaunay.cxx:255
TGraphDelaunay.cxx:256
TGraphDelaunay.cxx:257
TGraphDelaunay.cxx:258
TGraphDelaunay.cxx:259
TGraphDelaunay.cxx:260
TGraphDelaunay.cxx:261
TGraphDelaunay.cxx:262
TGraphDelaunay.cxx:263
TGraphDelaunay.cxx:264
TGraphDelaunay.cxx:265
TGraphDelaunay.cxx:266
TGraphDelaunay.cxx:267
TGraphDelaunay.cxx:268
TGraphDelaunay.cxx:269
TGraphDelaunay.cxx:270
TGraphDelaunay.cxx:271
TGraphDelaunay.cxx:272
TGraphDelaunay.cxx:273
TGraphDelaunay.cxx:274
TGraphDelaunay.cxx:275
TGraphDelaunay.cxx:276
TGraphDelaunay.cxx:277
TGraphDelaunay.cxx:278
TGraphDelaunay.cxx:279
TGraphDelaunay.cxx:280
TGraphDelaunay.cxx:281
TGraphDelaunay.cxx:282
TGraphDelaunay.cxx:283
TGraphDelaunay.cxx:284
TGraphDelaunay.cxx:285
TGraphDelaunay.cxx:286
TGraphDelaunay.cxx:287
TGraphDelaunay.cxx:288
TGraphDelaunay.cxx:289
TGraphDelaunay.cxx:290
TGraphDelaunay.cxx:291
TGraphDelaunay.cxx:292
TGraphDelaunay.cxx:293
TGraphDelaunay.cxx:294
TGraphDelaunay.cxx:295
TGraphDelaunay.cxx:296
TGraphDelaunay.cxx:297
TGraphDelaunay.cxx:298
TGraphDelaunay.cxx:299
TGraphDelaunay.cxx:300
TGraphDelaunay.cxx:301
TGraphDelaunay.cxx:302
TGraphDelaunay.cxx:303
TGraphDelaunay.cxx:304
TGraphDelaunay.cxx:305
TGraphDelaunay.cxx:306
TGraphDelaunay.cxx:307
TGraphDelaunay.cxx:308
TGraphDelaunay.cxx:309
TGraphDelaunay.cxx:310
TGraphDelaunay.cxx:311
TGraphDelaunay.cxx:312
TGraphDelaunay.cxx:313
TGraphDelaunay.cxx:314
TGraphDelaunay.cxx:315
TGraphDelaunay.cxx:316
TGraphDelaunay.cxx:317
TGraphDelaunay.cxx:318
TGraphDelaunay.cxx:319
TGraphDelaunay.cxx:320
TGraphDelaunay.cxx:321
TGraphDelaunay.cxx:322
TGraphDelaunay.cxx:323
TGraphDelaunay.cxx:324
TGraphDelaunay.cxx:325
TGraphDelaunay.cxx:326
TGraphDelaunay.cxx:327
TGraphDelaunay.cxx:328
TGraphDelaunay.cxx:329
TGraphDelaunay.cxx:330
TGraphDelaunay.cxx:331
TGraphDelaunay.cxx:332
TGraphDelaunay.cxx:333
TGraphDelaunay.cxx:334
TGraphDelaunay.cxx:335
TGraphDelaunay.cxx:336
TGraphDelaunay.cxx:337
TGraphDelaunay.cxx:338
TGraphDelaunay.cxx:339
TGraphDelaunay.cxx:340
TGraphDelaunay.cxx:341
TGraphDelaunay.cxx:342
TGraphDelaunay.cxx:343
TGraphDelaunay.cxx:344
TGraphDelaunay.cxx:345
TGraphDelaunay.cxx:346
TGraphDelaunay.cxx:347
TGraphDelaunay.cxx:348
TGraphDelaunay.cxx:349
TGraphDelaunay.cxx:350
TGraphDelaunay.cxx:351
TGraphDelaunay.cxx:352
TGraphDelaunay.cxx:353
TGraphDelaunay.cxx:354
TGraphDelaunay.cxx:355
TGraphDelaunay.cxx:356
TGraphDelaunay.cxx:357
TGraphDelaunay.cxx:358
TGraphDelaunay.cxx:359
TGraphDelaunay.cxx:360
TGraphDelaunay.cxx:361
TGraphDelaunay.cxx:362
TGraphDelaunay.cxx:363
TGraphDelaunay.cxx:364
TGraphDelaunay.cxx:365
TGraphDelaunay.cxx:366
TGraphDelaunay.cxx:367
TGraphDelaunay.cxx:368
TGraphDelaunay.cxx:369
TGraphDelaunay.cxx:370
TGraphDelaunay.cxx:371
TGraphDelaunay.cxx:372
TGraphDelaunay.cxx:373
TGraphDelaunay.cxx:374
TGraphDelaunay.cxx:375
TGraphDelaunay.cxx:376
TGraphDelaunay.cxx:377
TGraphDelaunay.cxx:378
TGraphDelaunay.cxx:379
TGraphDelaunay.cxx:380
TGraphDelaunay.cxx:381
TGraphDelaunay.cxx:382
TGraphDelaunay.cxx:383
TGraphDelaunay.cxx:384
TGraphDelaunay.cxx:385
TGraphDelaunay.cxx:386
TGraphDelaunay.cxx:387
TGraphDelaunay.cxx:388
TGraphDelaunay.cxx:389
TGraphDelaunay.cxx:390
TGraphDelaunay.cxx:391
TGraphDelaunay.cxx:392
TGraphDelaunay.cxx:393
TGraphDelaunay.cxx:394
TGraphDelaunay.cxx:395
TGraphDelaunay.cxx:396
TGraphDelaunay.cxx:397
TGraphDelaunay.cxx:398
TGraphDelaunay.cxx:399
TGraphDelaunay.cxx:400
TGraphDelaunay.cxx:401
TGraphDelaunay.cxx:402
TGraphDelaunay.cxx:403
TGraphDelaunay.cxx:404
TGraphDelaunay.cxx:405
TGraphDelaunay.cxx:406
TGraphDelaunay.cxx:407
TGraphDelaunay.cxx:408
TGraphDelaunay.cxx:409
TGraphDelaunay.cxx:410
TGraphDelaunay.cxx:411
TGraphDelaunay.cxx:412
TGraphDelaunay.cxx:413
TGraphDelaunay.cxx:414
TGraphDelaunay.cxx:415
TGraphDelaunay.cxx:416
TGraphDelaunay.cxx:417
TGraphDelaunay.cxx:418
TGraphDelaunay.cxx:419
TGraphDelaunay.cxx:420
TGraphDelaunay.cxx:421
TGraphDelaunay.cxx:422
TGraphDelaunay.cxx:423
TGraphDelaunay.cxx:424
TGraphDelaunay.cxx:425
TGraphDelaunay.cxx:426
TGraphDelaunay.cxx:427
TGraphDelaunay.cxx:428
TGraphDelaunay.cxx:429
TGraphDelaunay.cxx:430
TGraphDelaunay.cxx:431
TGraphDelaunay.cxx:432
TGraphDelaunay.cxx:433
TGraphDelaunay.cxx:434
TGraphDelaunay.cxx:435
TGraphDelaunay.cxx:436
TGraphDelaunay.cxx:437
TGraphDelaunay.cxx:438
TGraphDelaunay.cxx:439
TGraphDelaunay.cxx:440
TGraphDelaunay.cxx:441
TGraphDelaunay.cxx:442
TGraphDelaunay.cxx:443
TGraphDelaunay.cxx:444
TGraphDelaunay.cxx:445
TGraphDelaunay.cxx:446
TGraphDelaunay.cxx:447
TGraphDelaunay.cxx:448
TGraphDelaunay.cxx:449
TGraphDelaunay.cxx:450
TGraphDelaunay.cxx:451
TGraphDelaunay.cxx:452
TGraphDelaunay.cxx:453
TGraphDelaunay.cxx:454
TGraphDelaunay.cxx:455
TGraphDelaunay.cxx:456
TGraphDelaunay.cxx:457
TGraphDelaunay.cxx:458
TGraphDelaunay.cxx:459
TGraphDelaunay.cxx:460
TGraphDelaunay.cxx:461
TGraphDelaunay.cxx:462
TGraphDelaunay.cxx:463
TGraphDelaunay.cxx:464
TGraphDelaunay.cxx:465
TGraphDelaunay.cxx:466
TGraphDelaunay.cxx:467
TGraphDelaunay.cxx:468
TGraphDelaunay.cxx:469
TGraphDelaunay.cxx:470
TGraphDelaunay.cxx:471
TGraphDelaunay.cxx:472
TGraphDelaunay.cxx:473
TGraphDelaunay.cxx:474
TGraphDelaunay.cxx:475
TGraphDelaunay.cxx:476
TGraphDelaunay.cxx:477
TGraphDelaunay.cxx:478
TGraphDelaunay.cxx:479
TGraphDelaunay.cxx:480
TGraphDelaunay.cxx:481
TGraphDelaunay.cxx:482
TGraphDelaunay.cxx:483
TGraphDelaunay.cxx:484
TGraphDelaunay.cxx:485
TGraphDelaunay.cxx:486
TGraphDelaunay.cxx:487
TGraphDelaunay.cxx:488
TGraphDelaunay.cxx:489
TGraphDelaunay.cxx:490
TGraphDelaunay.cxx:491
TGraphDelaunay.cxx:492
TGraphDelaunay.cxx:493
TGraphDelaunay.cxx:494
TGraphDelaunay.cxx:495
TGraphDelaunay.cxx:496
TGraphDelaunay.cxx:497
TGraphDelaunay.cxx:498
TGraphDelaunay.cxx:499
TGraphDelaunay.cxx:500
TGraphDelaunay.cxx:501
TGraphDelaunay.cxx:502
TGraphDelaunay.cxx:503
TGraphDelaunay.cxx:504
TGraphDelaunay.cxx:505
TGraphDelaunay.cxx:506
TGraphDelaunay.cxx:507
TGraphDelaunay.cxx:508
TGraphDelaunay.cxx:509
TGraphDelaunay.cxx:510
TGraphDelaunay.cxx:511
TGraphDelaunay.cxx:512
TGraphDelaunay.cxx:513
TGraphDelaunay.cxx:514
TGraphDelaunay.cxx:515
TGraphDelaunay.cxx:516
TGraphDelaunay.cxx:517
TGraphDelaunay.cxx:518
TGraphDelaunay.cxx:519
TGraphDelaunay.cxx:520
TGraphDelaunay.cxx:521
TGraphDelaunay.cxx:522
TGraphDelaunay.cxx:523
TGraphDelaunay.cxx:524
TGraphDelaunay.cxx:525
TGraphDelaunay.cxx:526
TGraphDelaunay.cxx:527
TGraphDelaunay.cxx:528
TGraphDelaunay.cxx:529
TGraphDelaunay.cxx:530
TGraphDelaunay.cxx:531
TGraphDelaunay.cxx:532
TGraphDelaunay.cxx:533
TGraphDelaunay.cxx:534
TGraphDelaunay.cxx:535
TGraphDelaunay.cxx:536
TGraphDelaunay.cxx:537
TGraphDelaunay.cxx:538
TGraphDelaunay.cxx:539
TGraphDelaunay.cxx:540
TGraphDelaunay.cxx:541
TGraphDelaunay.cxx:542
TGraphDelaunay.cxx:543
TGraphDelaunay.cxx:544
TGraphDelaunay.cxx:545
TGraphDelaunay.cxx:546
TGraphDelaunay.cxx:547
TGraphDelaunay.cxx:548
TGraphDelaunay.cxx:549
TGraphDelaunay.cxx:550
TGraphDelaunay.cxx:551
TGraphDelaunay.cxx:552
TGraphDelaunay.cxx:553
TGraphDelaunay.cxx:554
TGraphDelaunay.cxx:555
TGraphDelaunay.cxx:556
TGraphDelaunay.cxx:557
TGraphDelaunay.cxx:558
TGraphDelaunay.cxx:559
TGraphDelaunay.cxx:560
TGraphDelaunay.cxx:561
TGraphDelaunay.cxx:562
TGraphDelaunay.cxx:563
TGraphDelaunay.cxx:564
TGraphDelaunay.cxx:565
TGraphDelaunay.cxx:566
TGraphDelaunay.cxx:567
TGraphDelaunay.cxx:568
TGraphDelaunay.cxx:569
TGraphDelaunay.cxx:570
TGraphDelaunay.cxx:571
TGraphDelaunay.cxx:572
TGraphDelaunay.cxx:573
TGraphDelaunay.cxx:574
TGraphDelaunay.cxx:575
TGraphDelaunay.cxx:576
TGraphDelaunay.cxx:577
TGraphDelaunay.cxx:578
TGraphDelaunay.cxx:579
TGraphDelaunay.cxx:580
TGraphDelaunay.cxx:581
TGraphDelaunay.cxx:582
TGraphDelaunay.cxx:583
TGraphDelaunay.cxx:584
TGraphDelaunay.cxx:585
TGraphDelaunay.cxx:586
TGraphDelaunay.cxx:587
TGraphDelaunay.cxx:588
TGraphDelaunay.cxx:589
TGraphDelaunay.cxx:590
TGraphDelaunay.cxx:591
TGraphDelaunay.cxx:592
TGraphDelaunay.cxx:593
TGraphDelaunay.cxx:594
TGraphDelaunay.cxx:595
TGraphDelaunay.cxx:596
TGraphDelaunay.cxx:597
TGraphDelaunay.cxx:598
TGraphDelaunay.cxx:599
TGraphDelaunay.cxx:600
TGraphDelaunay.cxx:601
TGraphDelaunay.cxx:602
TGraphDelaunay.cxx:603
TGraphDelaunay.cxx:604
TGraphDelaunay.cxx:605
TGraphDelaunay.cxx:606
TGraphDelaunay.cxx:607
TGraphDelaunay.cxx:608
TGraphDelaunay.cxx:609
TGraphDelaunay.cxx:610
TGraphDelaunay.cxx:611
TGraphDelaunay.cxx:612
TGraphDelaunay.cxx:613
TGraphDelaunay.cxx:614
TGraphDelaunay.cxx:615
TGraphDelaunay.cxx:616
TGraphDelaunay.cxx:617
TGraphDelaunay.cxx:618
TGraphDelaunay.cxx:619
TGraphDelaunay.cxx:620
TGraphDelaunay.cxx:621
TGraphDelaunay.cxx:622
TGraphDelaunay.cxx:623
TGraphDelaunay.cxx:624
TGraphDelaunay.cxx:625
TGraphDelaunay.cxx:626
TGraphDelaunay.cxx:627
TGraphDelaunay.cxx:628
TGraphDelaunay.cxx:629
TGraphDelaunay.cxx:630
TGraphDelaunay.cxx:631
TGraphDelaunay.cxx:632
TGraphDelaunay.cxx:633
TGraphDelaunay.cxx:634
TGraphDelaunay.cxx:635
TGraphDelaunay.cxx:636
TGraphDelaunay.cxx:637
TGraphDelaunay.cxx:638
TGraphDelaunay.cxx:639
TGraphDelaunay.cxx:640
TGraphDelaunay.cxx:641
TGraphDelaunay.cxx:642
TGraphDelaunay.cxx:643
TGraphDelaunay.cxx:644
TGraphDelaunay.cxx:645
TGraphDelaunay.cxx:646
TGraphDelaunay.cxx:647
TGraphDelaunay.cxx:648
TGraphDelaunay.cxx:649
TGraphDelaunay.cxx:650
TGraphDelaunay.cxx:651
TGraphDelaunay.cxx:652
TGraphDelaunay.cxx:653
TGraphDelaunay.cxx:654
TGraphDelaunay.cxx:655
TGraphDelaunay.cxx:656
TGraphDelaunay.cxx:657
TGraphDelaunay.cxx:658
TGraphDelaunay.cxx:659
TGraphDelaunay.cxx:660
TGraphDelaunay.cxx:661
TGraphDelaunay.cxx:662
TGraphDelaunay.cxx:663
TGraphDelaunay.cxx:664
TGraphDelaunay.cxx:665
TGraphDelaunay.cxx:666
TGraphDelaunay.cxx:667
TGraphDelaunay.cxx:668
TGraphDelaunay.cxx:669
TGraphDelaunay.cxx:670
TGraphDelaunay.cxx:671
TGraphDelaunay.cxx:672
TGraphDelaunay.cxx:673
TGraphDelaunay.cxx:674
TGraphDelaunay.cxx:675
TGraphDelaunay.cxx:676
TGraphDelaunay.cxx:677
TGraphDelaunay.cxx:678
TGraphDelaunay.cxx:679
TGraphDelaunay.cxx:680
TGraphDelaunay.cxx:681
TGraphDelaunay.cxx:682
TGraphDelaunay.cxx:683
TGraphDelaunay.cxx:684
TGraphDelaunay.cxx:685
TGraphDelaunay.cxx:686
TGraphDelaunay.cxx:687
TGraphDelaunay.cxx:688
TGraphDelaunay.cxx:689
TGraphDelaunay.cxx:690
TGraphDelaunay.cxx:691
TGraphDelaunay.cxx:692
TGraphDelaunay.cxx:693
TGraphDelaunay.cxx:694
TGraphDelaunay.cxx:695
TGraphDelaunay.cxx:696
TGraphDelaunay.cxx:697
TGraphDelaunay.cxx:698
TGraphDelaunay.cxx:699
TGraphDelaunay.cxx:700
TGraphDelaunay.cxx:701
TGraphDelaunay.cxx:702
TGraphDelaunay.cxx:703
TGraphDelaunay.cxx:704
TGraphDelaunay.cxx:705
TGraphDelaunay.cxx:706
TGraphDelaunay.cxx:707
TGraphDelaunay.cxx:708
TGraphDelaunay.cxx:709
TGraphDelaunay.cxx:710
TGraphDelaunay.cxx:711
TGraphDelaunay.cxx:712
TGraphDelaunay.cxx:713
TGraphDelaunay.cxx:714
TGraphDelaunay.cxx:715
TGraphDelaunay.cxx:716
TGraphDelaunay.cxx:717
TGraphDelaunay.cxx:718
TGraphDelaunay.cxx:719
TGraphDelaunay.cxx:720
TGraphDelaunay.cxx:721
TGraphDelaunay.cxx:722
TGraphDelaunay.cxx:723
TGraphDelaunay.cxx:724
TGraphDelaunay.cxx:725
TGraphDelaunay.cxx:726
TGraphDelaunay.cxx:727
TGraphDelaunay.cxx:728
TGraphDelaunay.cxx:729
TGraphDelaunay.cxx:730
TGraphDelaunay.cxx:731
TGraphDelaunay.cxx:732
TGraphDelaunay.cxx:733
TGraphDelaunay.cxx:734
TGraphDelaunay.cxx:735
TGraphDelaunay.cxx:736
TGraphDelaunay.cxx:737
TGraphDelaunay.cxx:738
TGraphDelaunay.cxx:739
TGraphDelaunay.cxx:740
TGraphDelaunay.cxx:741
TGraphDelaunay.cxx:742
TGraphDelaunay.cxx:743
TGraphDelaunay.cxx:744
TGraphDelaunay.cxx:745
TGraphDelaunay.cxx:746
TGraphDelaunay.cxx:747
TGraphDelaunay.cxx:748
TGraphDelaunay.cxx:749
TGraphDelaunay.cxx:750
TGraphDelaunay.cxx:751
TGraphDelaunay.cxx:752
TGraphDelaunay.cxx:753
TGraphDelaunay.cxx:754
TGraphDelaunay.cxx:755
TGraphDelaunay.cxx:756
TGraphDelaunay.cxx:757
TGraphDelaunay.cxx:758
TGraphDelaunay.cxx:759
TGraphDelaunay.cxx:760
TGraphDelaunay.cxx:761
TGraphDelaunay.cxx:762
TGraphDelaunay.cxx:763
TGraphDelaunay.cxx:764
TGraphDelaunay.cxx:765
TGraphDelaunay.cxx:766
TGraphDelaunay.cxx:767
TGraphDelaunay.cxx:768
TGraphDelaunay.cxx:769
TGraphDelaunay.cxx:770
TGraphDelaunay.cxx:771
TGraphDelaunay.cxx:772
TGraphDelaunay.cxx:773
TGraphDelaunay.cxx:774
TGraphDelaunay.cxx:775
TGraphDelaunay.cxx:776
TGraphDelaunay.cxx:777
TGraphDelaunay.cxx:778
TGraphDelaunay.cxx:779
TGraphDelaunay.cxx:780
TGraphDelaunay.cxx:781
TGraphDelaunay.cxx:782
TGraphDelaunay.cxx:783
TGraphDelaunay.cxx:784
TGraphDelaunay.cxx:785
TGraphDelaunay.cxx:786
TGraphDelaunay.cxx:787
TGraphDelaunay.cxx:788
TGraphDelaunay.cxx:789
TGraphDelaunay.cxx:790
TGraphDelaunay.cxx:791
TGraphDelaunay.cxx:792
TGraphDelaunay.cxx:793
TGraphDelaunay.cxx:794
TGraphDelaunay.cxx:795
TGraphDelaunay.cxx:796
TGraphDelaunay.cxx:797
TGraphDelaunay.cxx:798
TGraphDelaunay.cxx:799
TGraphDelaunay.cxx:800
TGraphDelaunay.cxx:801
TGraphDelaunay.cxx:802
TGraphDelaunay.cxx:803
TGraphDelaunay.cxx:804
TGraphDelaunay.cxx:805
TGraphDelaunay.cxx:806
TGraphDelaunay.cxx:807
TGraphDelaunay.cxx:808
TGraphDelaunay.cxx:809
TGraphDelaunay.cxx:810
TGraphDelaunay.cxx:811
TGraphDelaunay.cxx:812
TGraphDelaunay.cxx:813
TGraphDelaunay.cxx:814
TGraphDelaunay.cxx:815
TGraphDelaunay.cxx:816
TGraphDelaunay.cxx:817
TGraphDelaunay.cxx:818
TGraphDelaunay.cxx:819
TGraphDelaunay.cxx:820
TGraphDelaunay.cxx:821
TGraphDelaunay.cxx:822
TGraphDelaunay.cxx:823
TGraphDelaunay.cxx:824
TGraphDelaunay.cxx:825
TGraphDelaunay.cxx:826
TGraphDelaunay.cxx:827
TGraphDelaunay.cxx:828
TGraphDelaunay.cxx:829
TGraphDelaunay.cxx:830
TGraphDelaunay.cxx:831
TGraphDelaunay.cxx:832
TGraphDelaunay.cxx:833
TGraphDelaunay.cxx:834
TGraphDelaunay.cxx:835
TGraphDelaunay.cxx:836
TGraphDelaunay.cxx:837
TGraphDelaunay.cxx:838
TGraphDelaunay.cxx:839
TGraphDelaunay.cxx:840
TGraphDelaunay.cxx:841
TGraphDelaunay.cxx:842
TGraphDelaunay.cxx:843
TGraphDelaunay.cxx:844
TGraphDelaunay.cxx:845
TGraphDelaunay.cxx:846
TGraphDelaunay.cxx:847
TGraphDelaunay.cxx:848
TGraphDelaunay.cxx:849
TGraphDelaunay.cxx:850
TGraphDelaunay.cxx:851
TGraphDelaunay.cxx:852
TGraphDelaunay.cxx:853
TGraphDelaunay.cxx:854
TGraphDelaunay.cxx:855
TGraphDelaunay.cxx:856
TGraphDelaunay.cxx:857
TGraphDelaunay.cxx:858
TGraphDelaunay.cxx:859
TGraphDelaunay.cxx:860
TGraphDelaunay.cxx:861
TGraphDelaunay.cxx:862
TGraphDelaunay.cxx:863
TGraphDelaunay.cxx:864
TGraphDelaunay.cxx:865
TGraphDelaunay.cxx:866
TGraphDelaunay.cxx:867
TGraphDelaunay.cxx:868
TGraphDelaunay.cxx:869
TGraphDelaunay.cxx:870
TGraphDelaunay.cxx:871
TGraphDelaunay.cxx:872
TGraphDelaunay.cxx:873
TGraphDelaunay.cxx:874
TGraphDelaunay.cxx:875
TGraphDelaunay.cxx:876
TGraphDelaunay.cxx:877
TGraphDelaunay.cxx:878
TGraphDelaunay.cxx:879
TGraphDelaunay.cxx:880
TGraphDelaunay.cxx:881
TGraphDelaunay.cxx:882
TGraphDelaunay.cxx:883
TGraphDelaunay.cxx:884
TGraphDelaunay.cxx:885
TGraphDelaunay.cxx:886
TGraphDelaunay.cxx:887
TGraphDelaunay.cxx:888
TGraphDelaunay.cxx:889
TGraphDelaunay.cxx:890
TGraphDelaunay.cxx:891
TGraphDelaunay.cxx:892
TGraphDelaunay.cxx:893
TGraphDelaunay.cxx:894
TGraphDelaunay.cxx:895
TGraphDelaunay.cxx:896
TGraphDelaunay.cxx:897
TGraphDelaunay.cxx:898
TGraphDelaunay.cxx:899
TGraphDelaunay.cxx:900
TGraphDelaunay.cxx:901
TGraphDelaunay.cxx:902
TGraphDelaunay.cxx:903
TGraphDelaunay.cxx:904
TGraphDelaunay.cxx:905
TGraphDelaunay.cxx:906
TGraphDelaunay.cxx:907
TGraphDelaunay.cxx:908
TGraphDelaunay.cxx:909
TGraphDelaunay.cxx:910
TGraphDelaunay.cxx:911
TGraphDelaunay.cxx:912
TGraphDelaunay.cxx:913
TGraphDelaunay.cxx:914
TGraphDelaunay.cxx:915
TGraphDelaunay.cxx:916
TGraphDelaunay.cxx:917
TGraphDelaunay.cxx:918
TGraphDelaunay.cxx:919
TGraphDelaunay.cxx:920
TGraphDelaunay.cxx:921
TGraphDelaunay.cxx:922
TGraphDelaunay.cxx:923
TGraphDelaunay.cxx:924
TGraphDelaunay.cxx:925
TGraphDelaunay.cxx:926
TGraphDelaunay.cxx:927
TGraphDelaunay.cxx:928
TGraphDelaunay.cxx:929
TGraphDelaunay.cxx:930
TGraphDelaunay.cxx:931
TGraphDelaunay.cxx:932
TGraphDelaunay.cxx:933
TGraphDelaunay.cxx:934
TGraphDelaunay.cxx:935
TGraphDelaunay.cxx:936
TGraphDelaunay.cxx:937
TGraphDelaunay.cxx:938
TGraphDelaunay.cxx:939
TGraphDelaunay.cxx:940
TGraphDelaunay.cxx:941
TGraphDelaunay.cxx:942
TGraphDelaunay.cxx:943
TGraphDelaunay.cxx:944
TGraphDelaunay.cxx:945
TGraphDelaunay.cxx:946
TGraphDelaunay.cxx:947
TGraphDelaunay.cxx:948