class TGraphDelaunay: public TNamed


 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.
/*
This applet gives a nice practical view of Delaunay triangulation and Voronoi diagram. */ 







Function Members (Methods)


public:



TGraphDelaunay()


TGraphDelaunay(TGraph2D* g)


 virtual~TGraphDelaunay()


voidTObject::AbstractMethod(const char* method) const


virtual voidTObject::AppendPad(Option_t* option = "")


virtual voidTObject::Browse(TBrowser* b)


static TClass*Class()


virtual const char*TObject::ClassName() const


virtual voidTNamed::Clear(Option_t* option = "")


virtual TObject*TNamed::Clone(const char* newname = "") const


virtual Int_tTNamed::Compare(const TObject* obj) const


Double_tComputeZ(Double_t x, Double_t y)


virtual voidTNamed::Copy(TObject& named) const


virtual voidTObject::Delete(Option_t* option = "")MENU 


virtual Int_tTObject::DistancetoPrimitive(Int_t px, Int_t py)


virtual voidTObject::Draw(Option_t* option = "")


virtual voidTObject::DrawClass() constMENU 


virtual TObject*TObject::DrawClone(Option_t* option = "") constMENU 


virtual voidTObject::Dump() constMENU 


virtual voidTObject::Error(const char* method, const char* msgfmt) const


virtual voidTObject::Execute(const char* method, const char* params, Int_t* error = 0)


virtual voidTObject::Execute(TMethod* method, TObjArray* params, Int_t* error = 0)


virtual voidTObject::ExecuteEvent(Int_t event, Int_t px, Int_t py)


virtual voidTObject::Fatal(const char* method, const char* msgfmt) const


virtual voidTNamed::FillBuffer(char*& buffer)


voidFindAllTriangles()


virtual TObject*TObject::FindObject(const char* name) const


virtual TObject*TObject::FindObject(const TObject* obj) const


virtual Option_t*TObject::GetDrawOption() const


static Long_tTObject::GetDtorOnly()


TGraph2D*GetGraph2D() const


virtual const char*TObject::GetIconName() const


Double_tGetMarginBinsContent() const


Int_t*GetMTried() const


virtual const char*TNamed::GetName() const


Int_tGetNdt() const


Int_t*GetNTried() const


virtual char*TObject::GetObjectInfo(Int_t px, Int_t py) const


static Bool_tTObject::GetObjectStat()


virtual Option_t*TObject::GetOption() const


Int_t*GetPTried() const


virtual const char*TNamed::GetTitle() const


virtual UInt_tTObject::GetUniqueID() const


Double_t*GetXN() const


Double_tGetXNmax() const


Double_tGetXNmin() const


Double_t*GetYN() const


Double_tGetYNmax() const


Double_tGetYNmin() const


virtual Bool_tTObject::HandleTimer(TTimer* timer)


virtual ULong_tTNamed::Hash() const


virtual voidTObject::Info(const char* method, const char* msgfmt) const


virtual Bool_tTObject::InheritsFrom(const char* classname) const


virtual Bool_tTObject::InheritsFrom(const TClass* cl) const


virtual voidTObject::Inspect() constMENU 


Double_tInterpolate(Double_t x, Double_t y)


voidTObject::InvertBit(UInt_t f)


virtual TClass*IsA() const


virtual Bool_tTObject::IsEqual(const TObject* obj) const


virtual Bool_tTObject::IsFolder() const


Bool_tTObject::IsOnHeap() const


virtual Bool_tTNamed::IsSortable() const


Bool_tTObject::IsZombie() const


virtual voidTNamed::ls(Option_t* option = "") const


voidTObject::MayNotUse(const char* method) const


virtual Bool_tTObject::Notify()


static voidTObject::operator delete(void* ptr)


static voidTObject::operator delete(void* ptr, void* vp)


static voidTObject::operator delete[](void* ptr)


static voidTObject::operator delete[](void* ptr, void* vp)


void*TObject::operator new(size_t sz)


void*TObject::operator new(size_t sz, void* vp)


void*TObject::operator new[](size_t sz)


void*TObject::operator new[](size_t sz, void* vp)


virtual voidTObject::Paint(Option_t* option = "")


virtual voidTObject::Pop()


virtual voidTNamed::Print(Option_t* option = "") const


virtual Int_tTObject::Read(const char* name)


virtual voidTObject::RecursiveRemove(TObject* obj)


voidTObject::ResetBit(UInt_t f)


virtual voidTObject::SaveAs(const char* filename = "", Option_t* option = "") constMENU 


virtual voidTObject::SavePrimitive(basic_ostream<char,char_traits<char> >& out, Option_t* option = "")


voidTObject::SetBit(UInt_t f)


voidTObject::SetBit(UInt_t f, Bool_t set)


virtual voidTObject::SetDrawOption(Option_t* option = "")MENU 


static voidTObject::SetDtorOnly(void* obj)


voidSetMarginBinsContent(Double_t z = 0.)


voidSetMaxIter(Int_t n = 100000)


virtual voidTNamed::SetName(const char* name)MENU 


virtual voidTNamed::SetNameTitle(const char* name, const char* title)


static voidTObject::SetObjectStat(Bool_t stat)


virtual voidTNamed::SetTitle(const char* title = "")MENU 


virtual voidTObject::SetUniqueID(UInt_t uid)


virtual voidShowMembers(TMemberInspector& insp, char* parent)


virtual Int_tTNamed::Sizeof() const


virtual voidStreamer(TBuffer& b)


voidStreamerNVirtual(TBuffer& b)


virtual voidTObject::SysError(const char* method, const char* msgfmt) const


Bool_tTObject::TestBit(UInt_t f) const


Int_tTObject::TestBits(UInt_t f) const


virtual voidTObject::UseCurrentStyle()


virtual voidTObject::Warning(const char* method, const char* msgfmt) const


virtual Int_tTObject::Write(const char* name = 0, Int_t option = 0, Int_t bufsize = 0)


virtual Int_tTObject::Write(const char* name = 0, Int_t option = 0, Int_t bufsize = 0) const





protected:



voidCreateTrianglesDataStructure()


virtual voidTObject::DoError(int level, const char* location, const char* fmt, va_list va) const


Bool_tEnclose(Int_t T1, Int_t T2, Int_t T3, Int_t Ex) const


voidFileIt(Int_t P, Int_t N, Int_t M)


voidFindHull()


Bool_tInHull(Int_t E, Int_t X) const


Double_tInterpolateOnPlane(Int_t TI1, Int_t TI2, Int_t TI3, Int_t E) const


voidTObject::MakeZombie()





private:



TGraphDelaunay(const TGraphDelaunay&)


TGraphDelaunay&operator=(const TGraphDelaunay&)










Data Members


public:



enum TObject::EStatusBits { kCanDelete


kMustCleanup


kObjInCanvas


kIsReferenced


kHasUUID


kCannotPick


kNoContextMenu


kInvalidObject


};


enum TObject::[unnamed] { kIsOnHeap


kNotDeleted


kZombie


kBitMask


kSingleKey


kOverwrite


kWriteDelete


};





protected:



Bool_tfAllTri!True if FindAllTriangles() has been performed on fGraph2D


Double_t*fDist!Array used to order mass points by distance


TGraph2D*fGraph2D!2D graph containing the user data


Int_t*fHullPoints!Hull points of size fNhull


Bool_tfInit!True if CreateTrianglesDataStructure() and FindHull() have been performed


Int_t*fMTried!


Int_tfMaxIter!Maximum number of iterations to find Delaunay triangles


Int_t*fNTried!Delaunay triangles storage of size fNdt


TStringTNamed::fNameobject identifier


Int_tfNdt!Number of Delaunay triangles found


Int_tfNhull!Number of points in the hull


Int_tfNpoints!Number of data points in fGraph2D


Int_t*fOrder!Array used to order mass points by distance


Int_t*fPTried!


Double_tfScaleFactor!


TStringTNamed::fTitleobject title


Int_tfTriedSize!Real size of the fxTried arrays


Double_t*fX!Pointer to fGraph2D->fX


Double_t*fXN!fGraph2D vectors normalized of size fNpoints


Double_tfXNmax!Maximum value of fXN


Double_tfXNmin!Minimum value of fXN


Double_tfXoffset!


Double_t*fY!Pointer to fGraph2D->fY


Double_t*fYN!fGraph2D vectors normalized of size fNpoints


Double_tfYNmax!Maximum value of fYN


Double_tfYNmin!Minimum value of fYN


Double_tfYoffset!Parameters used to normalize user data


Double_t*fZ!Pointer to fGraph2D->fZ


Double_tfZout!Histogram bin height for points lying outside the convex hull







Class Charts

























Inheritance
Inherited Members
Includes
Libraries



Class Charts


Function documentation


 TGraphDelaunay()


 TGraphDelaunay default constructor





 TGraphDelaunay(TGraph2D *g)


 TGraphDelaunay default constructor





 ~TGraphDelaunay()


 TGraphDelaunay destructor.





Double_t ComputeZ(Double_t x, Double_t y)


 Return the z value corresponding to the (x,y) point in fGraph2D





void CreateTrianglesDataStructure()


 Fonction used internally only. It creates the data structures needed to
 compute the Delaunay triangles.





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 ?





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. If these arrays are to small they are automatically
 expanded.





void 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.





void 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.





Bool_t InHull(Int_t E, Int_t X) const


 Is point e inside the hull defined by all points apart from x ?





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 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 linearly interpolating the z-values that
 make up that triangle.





void SetMaxIter(Int_t n = 100000)


 Defines the number of triangles tested for a Delaunay triangle
 (number of iterations) before abandoning the search





void SetMarginBinsContent(Double_t z = 0.)


 Sets the histogram bin height for points lying outside the convex hull ie:
 the bins in the margin.





 TGraphDelaunay(const TGraphDelaunay&)




TGraphDelaunay& operator=(const TGraphDelaunay& )




TGraph2D * GetGraph2D()



{return fGraph2D;}






Double_t GetMarginBinsContent()



{return fZout;}






Int_t GetNdt()



{return fNdt;}






Int_t    * GetPTried()



{return fPTried;}






Int_t    * GetNTried()



{return fNTried;}






Int_t    * GetMTried()



{return fMTried;}






Double_t * GetXN()



{return fXN;}






Double_t * GetYN()



{return fYN;}






Double_t GetXNmin()



{return fXNmin;}






Double_t GetXNmax()



{return fXNmax;}






Double_t GetYNmin()



{return fYNmin;}






Double_t GetYNmax()



{return fYNmax;}









Author:  Olivier Couet,  Luke Jones (Royal Holloway,  University of London)

Last change: root/hist:$Id: TGraphDelaunay.h,v 1.00

Last generated: 2008-06-25 08:46

Copyright   (C) 1995-2000, Rene Brun and Fons Rademakers.               *




This page has been automatically generated. If you have any comments or suggestions about the page layout send a mail to ROOT support, or contact the developers with any questions or problems regarding ROOT.