87 :
TNamed(
"TGraphDelaunay",
"TGraphDelaunay")
240 Int_t tmp, ps = p, ns =
n, ms =
m;
245 if (ns > ps) { tmp = ps; ps = ns; ns = tmp; swap =
kTRUE;}
246 if (ms > ns) { tmp = ns; ns = ms; ms = tmp; swap =
kTRUE;}
259 memset(&saven[fTriedSize],0,(newN-fTriedSize)*
sizeof(
Int_t));
262 memset(&savem[fTriedSize],0,(newN-fTriedSize)*
sizeof(
Int_t));
296 Int_t t1,
t2,pa,
na,ma,pb,nb,mb,
p1=0,
p2=0,
m,
n,
p3=0;
306 for (n=1; n<=
fNhull; n++) {
308 ycntr = ycntr+
fYN[fHullPoints[n-1]];
310 xcntr = xcntr/
fNhull+alittlebit;
311 ycntr = ycntr/
fNhull+alittlebit;
331 for (t2=1; t2<=
fNdt; t2++) {
338 if ((pa==pb && na==nb) || (pa==pb && na==mb) || (pa==nb && na==mb)) {
341 }
else if ((pa==pb && ma==nb) || (pa==pb && ma==mb) || (pa==nb && ma==mb)) {
344 }
else if ((na==pb && ma==nb) || (na==pb && ma==mb) || (na==nb && ma==mb)) {
351 if (s[0] && s[1] && s[2])
continue;
357 for (
m=1;
m<=3;
m++) {
451 Double_t lastdphi,dd1,dd2,dx1,dx2,dx3,dy1,dy2,dy3;
452 Double_t u,
v,vNv1,vNv2,phi1,phi2,dphi,xx,yy;
478 }
else if (n2 == x) {
492 for (n=1; n<=ntry; n++) {
499 if ((m!=n1) && (m!=n2) && (m!=x)) {
509 dd1 = (dx2*dy1-dx1*dy2);
510 dd2 = (dx1*dy2-dx2*dy1);
513 u = (dx2*dy3-dx3*dy2)/dd1;
514 v = (dx1*dy3-dx3*dy1)/dd2;
515 if ((u<0) || (v<0)) {
520 vNv1 = (dx1*dx3+dy1*dy3)/
TMath::Sqrt(dx1*dx1+dy1*dy1);
521 vNv2 = (dx2*dx3+dy2*dy3)/
TMath::Sqrt(dx2*dx2+dy2*dy2);
531 dphi = (phi1-phi2)-((
Int_t)((phi1-phi2)/TMath::TwoPi())*TMath::TwoPi());
560 Double_t x1,
x2,
x3,y1,y2,y3,
f1,
f2,
f3,u,
v,
w;
569 if (t2 > t1) { tmp =
t1; t1 =
t2; t2 = tmp; swap =
kTRUE;}
570 if (t3 > t2) { tmp =
t2; t2 =
t3; t3 = tmp; swap =
kTRUE;}
582 u = (f1*(y2-y3)+f2*(y3-y1)+f3*(y1-y2))/(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
583 v = (f1*(x2-
x3)+f2*(x3-x1)+f3*(x1-
x2))/(y1*(x2-
x3)+y2*(x3-x1)+y3*(x1-
x2));
599 Int_t it, ntris_tried, p,
n,
m;
600 Int_t i,j,k,
l,
z,
f,
d,o1,o2,
a,b,
t1,
t2,
t3;
601 Int_t ndegen=0,degen=0,fdegen=0,o1degen=0,o2degen=0;
604 Double_t dfo2,sin_sum,cfo1k,co2o1k,co2o1f;
607 Double_t dx1,dx2,dx3,dy1,dy2,dy3,u,
v,dxz[3],dyz[3];
636 for (it=1; it<=
fNdt; it++) {
650 shouldbein =
InHull(0,-1);
651 if (!shouldbein)
return thevalue;
670 for (j=2; j<=k-1; j++) {
672 for (i=1; i<=j-1; i++) {
686 if ((d1+d2<=d3) || (d1+d3<=d2) || (d2+d3<=d1))
goto L90;
689 if (!
Enclose(p,n,m,0))
goto L90;
700 if ((z==p) || (z==n) || (z==m))
goto L50;
708 if ((l<i) || (l<j) || (l<k)) {
713 if (
Enclose(p,n,m,z))
goto L90;
751 Warning(
"Interpolate",
"Two of these three points are coincident %d %d %d",a,b,z);
758 Warning(
"Interpolate",
"Two of these three points are coincident %d %d %d",a,b,z);
771 dxz[1] = fXN[
n]-fXN[
z];
772 dyz[1] = fYN[
n]-fYN[
z];
773 dxz[2] = fXN[
m]-fXN[
z];
774 dyz[2] = fYN[
m]-fYN[
z];
775 for(l=1; l<=3; l++) {
787 u = (dy3*dx2-dx3*dy2)*(dy1*dx2-dx1*dy2);
788 v = (dy3*dx1-dx3*dy1)*(dy2*dx1-dx2*dy1);
790 if ((u>=0) && (v>=0)) {
818 cfo1k = ((fXN[
f]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[
f]-fYN[o1])*(fYN[z]-fYN[o1]))/
819 TMath::Sqrt(((fXN[f]-fXN[o1])*(fXN[
f]-fXN[o1])+(fYN[f]-fYN[o1])*(fYN[
f]-fYN[o1]))*
820 ((fXN[
z]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[
z]-fYN[o1])*(fYN[z]-fYN[o1])));
821 co2o1k = ((fXN[o2]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[z]-fYN[o1]))/
822 TMath::Sqrt(((fXN[o2]-fXN[o1])*(fXN[o2]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[o2]-fYN[o1]))*
823 ((fXN[
z]-fXN[o1])*(fXN[z]-fXN[o1]) + (fYN[
z]-fYN[o1])*(fYN[z]-fYN[o1])));
824 co2o1f = ((fXN[o2]-fXN[o1])*(fXN[f]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[f]-fYN[o1]))/
825 TMath::Sqrt(((fXN[o2]-fXN[o1])*(fXN[o2]-fXN[o1])+(fYN[o2]-fYN[o1])*(fYN[o2]-fYN[o1]))*
826 ((fXN[
f]-fXN[o1])*(fXN[f]-fXN[o1]) + (fYN[
f]-fYN[o1])*(fYN[f]-fYN[o1]) ));
827 if ((cfo1k>co2o1k) || (cfo1k>co2o1f)) {
834 dko1 =
TMath::Sqrt((fXN[z]-fXN[o1])*(fXN[z]-fXN[o1])+(fYN[z]-fYN[o1])*(fYN[z]-fYN[o1]));
835 dko2 =
TMath::Sqrt((fXN[z]-fXN[o2])*(fXN[z]-fXN[o2])+(fYN[z]-fYN[o2])*(fYN[z]-fYN[o2]));
836 dfo1 =
TMath::Sqrt((fXN[f]-fXN[o1])*(fXN[f]-fXN[o1])+(fYN[f]-fYN[o1])*(fYN[f]-fYN[o1]));
837 dfo2 =
TMath::Sqrt((fXN[f]-fXN[o2])*(fXN[f]-fXN[o2])+(fYN[f]-fYN[o2])*(fYN[f]-fYN[o2]));
838 c1 = ((fXN[
z]-fXN[o1])*(fXN[z]-fXN[o2])+(fYN[
z]-fYN[o1])*(fYN[z]-fYN[o2]))/dko1/dko2;
839 c2 = ((fXN[
f]-fXN[o1])*(fXN[f]-fXN[o2])+(fYN[
f]-fYN[o1])*(fYN[f]-fYN[o2]))/dfo1/dfo2;
843 if (sin_sum < -1.
E-6) {
880 if ((
fZ[o1-1]+
fZ[o2-1]) > (
fZ[d-1]+
fZ[f-1])) {
921 "Point outside hull when expected inside: this point could be dodgy %g %g %d",
922 xx, yy, ntris_tried);
Double_t 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. ...
Double_t * fZ
Pointer to fGraph2D->fY.
void SetMaxIter(Int_t n=100000)
Defines the number of triangles tested for a Delaunay triangle (number of iterations) before abandoni...
static double p3(double t, double a, double b, double c, double d)
Double_t * fYN
fGraph2D vectors normalized of size fNpoints
Double_t * fX
Number of points in the hull.
Double_t GetXmax() const
Returns the X maximum.
Bool_t Enclose(Int_t T1, Int_t T2, Int_t T3, Int_t Ex) const
Is point e inside the triangle t1-t2-t3 ?
Double_t fYNmin
Maximum value of fXN.
Double_t GetYmax() const
Returns the Y maximum.
Int_t fNhull
Number of data points in fGraph2D.
Double_t fYNmax
Minimum value of fYN.
Int_t fTriedSize
Maximum number of iterations to find Delaunay triangles.
Double_t * fDist
Histogram bin height for points lying outside the convex hull.
Double_t * fXN
Pointer to fGraph2D->fZ.
Double_t fXoffset
Maximum value of fYN.
Double_t GetXmin() const
Returns the X minimum.
void 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.
static const double x2[5]
Bool_t InHull(Int_t E, Int_t X) const
Is point e inside the hull defined by all points apart from x ?
static void swap(double &a, double &b)
Double_t ComputeZ(Double_t x, Double_t y)
Return the z value corresponding to the (x,y) point in fGraph2D.
The TNamed class is the base class for all named ROOT classes.
Double_t fXNmax
Minimum value of fXN.
void SetMarginBinsContent(Double_t z=0.)
Sets the histogram bin height for points lying outside the convex hull ie: the bins in the margin...
static double p2(double t, double a, double b, double c)
void Sort(Index n, const Element *a, Index *index, Bool_t down=kTRUE)
Double_t ATan2(Double_t, Double_t)
Bool_t IsInside(T xp, T yp, Int_t np, T *x, T *y)
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Int_t fNpoints
Number of Delaunay triangles found.
Double_t GetYmin() const
Returns the Y minimum.
Double_t fXScaleFactor
Parameters used to normalize user data.
Int_t * fOrder
Hull points of size fNhull.
Double_t fXNmin
fGraph2D vectors normalized of size fNpoints
static double p1(double t, double a, double b)
void CreateTrianglesDataStructure()
2D graph containing the user data
Double_t * fY
Pointer to fGraph2D->fX.
Bool_t fInit
True if FindAllTriangles() has been performed on fGraph2D.
static const double x1[5]
TGraph2D * fGraph2D
True if CreateTrianglesDataStructure() and FindHull() have been performed.
Bool_t fAllTri
Array used to order mass points by distance.
Int_t * fPTried
Real size of the fxTried arrays.
Short_t Max(Short_t a, Short_t b)
Int_t * fMTried
Delaunay triangles storage of size fNdt.
Double_t Sqrt(Double_t x)
void FindAllTriangles()
Attempt to find all the Delaunay triangles of the point set.
Graphics object made of three arrays X, Y and Z with the same number of points each.
virtual ~TGraphDelaunay()
TGraphDelaunay destructor.
Int_t fMaxIter
Array used to order mass points by distance.
TGraphDelaunay generates a Delaunay triangulation of a TGraph2D.
void FindHull()
Finds those points which make up the convex hull of the set.
Double_t Interpolate(Double_t x, Double_t y)
Finds the Delaunay triangle that the point (xi,yi) sits in (if any) and calculate a z-value for it by...
static const double x3[11]
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.