BFLVoronoiMaker Class Reference

#include <BFLVoronoiMaker.h>

List of all members.

Public Member Functions

 BFLVoronoiMaker (BFLWingedEdge *voronoi)
 ~BFLVoronoiMaker ()
void Make (void)

Private Member Functions

void IncreaseEntropy (void)
void AddDistantGenerators (void)
void RemoveRefsToDeletedEdges (void)
Int_t AddNewVtx (Int_t edge, Float_t xv, Float_t yv)
void AddNewPolyg (Int_t EdgeID)
Int_t AddNewEdge (Int_t SVtxID, Int_t EVtxID, Int_t EdgeOfSVtx, Int_t EdgeOfEVtx)
void WingedEdgePatch (void)
void MergeDataStructures (void)
Int_t GetAnotherEdgeAround (Int_t PolygID) const
Int_t GuessNearestNeighbour (void) const
void SubstructureInit (void)
void NewStructureInit (void)
void MarkEdgesToDelete (void)
void MarkVerticesToDelete (void)
void DeleteSubstructure (void)
void Defrag (void)
virtual Int_t RandomToSorted (Int_t SlotAtRandom) const
virtual Int_t SortedToRandom (Int_t SlotAtSorted) const
virtual BFLVorOperatorGetVoronoiOperator (void)

Private Attributes

Int_t fCurrentPolygID
Int_t fGenID
Long_t fN
BFLWingedEdgefVor
BFLWingedEdgefVorPatch
BFLVorOperatorfOp
TObjArray * fGenerators
TIntListfRandomToSorted
TIntListfSortedToRandom
TIntListfEdgesToDelete
TIntListfVerticesToDelete
TIntListfNewEdgesTopology
TIntListfNewVertices
Bool_t debug
Bool_t debug2
TObjArray * fBField

Detailed Description

Definition at line 36 of file BFLVoronoiMaker.h.


Constructor & Destructor Documentation

BFLVoronoiMaker::BFLVoronoiMaker ( BFLWingedEdge voronoi  ) 

Definition at line 34 of file BFLVoronoiMaker.cxx.

00035 {
00036 // Allocate some memory for this instance variables
00037 
00038   fVor = (BFLWingedEdge *) voronoi;
00039 
00040   fGenerators = (TObjArray *) fVor->GetGenerators(); 
00041   fOp = new BFLVorOperator(voronoi);
00042 
00043   fN = 0;
00044   fRandomToSorted = new TIntList();
00045   fSortedToRandom = new TIntList();
00046   fEdgesToDelete = new TIntList();    
00047   fVerticesToDelete = new TIntList();
00048   fNewEdgesTopology = new TIntList();
00049   fNewVertices = new TIntList(); 
00050 }

BFLVoronoiMaker::~BFLVoronoiMaker (  ) 

Definition at line 53 of file BFLVoronoiMaker.cxx.

References fNewEdgesTopology, fNewVertices, fRandomToSorted, and fSortedToRandom.

00054 {
00055   delete fRandomToSorted;
00056   delete fSortedToRandom;  
00057   delete fNewEdgesTopology;
00058   delete fNewVertices;
00059 }


Member Function Documentation

void BFLVoronoiMaker::AddDistantGenerators ( void   )  [private]

Definition at line 102 of file BFLVoronoiMaker.cxx.

References BFLWingedEdge::AddAvailableEdgeID(), BFLWingedEdge::AddAvailableVtxID(), BFLWingedEdge::AddEdge(), BFLWingedEdge::AddPolyg(), BFLWingedEdge::AddVtx(), fGenerators, fVor, kAugmentedGrRadius, kGensRadius, BFLWingedEdge::SetCcwPredecessor(), BFLWingedEdge::SetCcwSuccessor(), BFLWingedEdge::SetCwPredecessor(), BFLWingedEdge::SetCwSuccessor(), BFLWingedEdge::SetEdgeAroundPolyg(), BFLWingedEdge::SetEdgeAroundVtx(), BFLWingedEdge::SetEndVtx(), BFLWingedEdge::SetLeftPolyg(), BFLWingedEdge::SetRightPolyg(), BFLWingedEdge::SetStartVtx(), BFLWingedEdge::SetVtx(), BFLWingedEdge::SetWeight(), BFLWingedEdge::SetX(), and BFLWingedEdge::SetY().

Referenced by Make().

00103 {
00104 // Adds three distant generators to bypass the problem with the 
00105 // infinite extend of some Voronoi edges.
00106 // These generators should be far enough, not only to include all the
00107 // others, but also not disturb their Voronoi polygons.
00108 // This method also computes the Voronoi diagram of the 3 generators
00109 //
00110 // see:                C.Andreopoulos, E.Athanasopoulos, G.Tzanakos,
00111 // "Spatial tesselation techniques ???", Fermilab report, NuMI-L-xxx
00112 //
00113 
00114   Float_t x, y;
00115 
00116   // ======== Add the first 4 Voronoi vertices ========  
00117 
00118   // see NuMI-L-???
00119   x = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);
00120   y = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);
00121 
00122 
00123   // Start vtx of all 3 inner, initial Voronoi edges
00124   fVor->AddVtx(1);   //-------------------- 1st vertex  
00125   fVor->SetX(1,0.);
00126   fVor->SetY(1,0.);
00127   fVor->SetWeight(1,kTRUE);
00128   fVor->SetEdgeAroundVtx(1,1);
00129   
00130   fVor->AddVtx(2);   //-------------------- 2nd vertex
00131   fVor->SetVtx(2);   
00132   fVor->SetX(2,x);   
00133   fVor->SetY(2,y);    
00134   fVor->SetWeight(2,kFALSE);   
00135   fVor->SetEdgeAroundVtx(2,4);
00136   
00137   fVor->AddVtx(3);   //-------------------- 3rd vertex   
00138   fVor->SetX(3,0);   
00139   fVor->SetY(3,-kAugmentedGrRadius);    
00140   fVor->SetWeight(3,kFALSE); 
00141   fVor->SetEdgeAroundVtx(3,5);
00142   
00143   fVor->AddVtx(4);   //-------------------- 4th vertex  
00144   fVor->SetX(4,-x);  
00145   fVor->SetY(4,y);                   
00146   fVor->SetWeight(4,kFALSE); 
00147   fVor->SetEdgeAroundVtx(4,6);
00148   
00149 
00150   //======== Add the first 4 Voronoi polygons ==========
00151   
00152   fVor->AddPolyg(0);              //------ 0 polygon: EXTERNAL REGION
00153   fVor->SetEdgeAroundPolyg(0,4); 
00154   fVor->AddPolyg(1);              //------ 1st polygon
00155   fVor->SetEdgeAroundPolyg(1,1);
00156   fVor->AddPolyg(2);              //------ 2nd polygon
00157   fVor->SetEdgeAroundPolyg(2,2);
00158   fVor->AddPolyg(3);              //------ 3rd polygon
00159   fVor->SetEdgeAroundPolyg(3,3);
00160   //fNPolygs = 4; 
00161 
00162 
00163   // ======== Add the first 6 Voronoi edges ===========
00164   // ---- 3 of them are inner edges
00165   // ---- 3 of them make the outer curved boundary
00166   
00167   // ---------- 1st edge          // ---------- 2nd edge
00168   fVor->AddEdge(1);               fVor->AddEdge(2);       
00169   fVor->SetLeftPolyg(1,1);        fVor->SetLeftPolyg(2,2);
00170   fVor->SetRightPolyg(1,2);       fVor->SetRightPolyg(2,3);
00171   fVor->SetStartVtx(1,1);         fVor->SetStartVtx(2,1);
00172   fVor->SetEndVtx(1,2);           fVor->SetEndVtx(2,3);
00173   fVor->SetCwSuccessor(1,4);      fVor->SetCwSuccessor(2,5);
00174   fVor->SetCcwSuccessor(1,5);     fVor->SetCcwSuccessor(2,6);
00175   fVor->SetCwPredecessor(1,2);    fVor->SetCwPredecessor(2,3);
00176   fVor->SetCcwPredecessor(1,3);   fVor->SetCcwPredecessor(2,1); 
00177 
00178   // ---------- 3rd edge          // ------ 1st curved edge
00179   fVor->AddEdge(3);               fVor->AddEdge(4);        
00180   fVor->SetLeftPolyg(3,3);        fVor->SetLeftPolyg(4,0);
00181   fVor->SetRightPolyg(3,1);       fVor->SetRightPolyg(4,1);
00182   fVor->SetStartVtx(3,1);         fVor->SetStartVtx(4,4);
00183   fVor->SetEndVtx(3,4);           fVor->SetEndVtx(4,2);
00184   fVor->SetCwSuccessor(3,6);      fVor->SetCwSuccessor(4,5);
00185   fVor->SetCcwSuccessor(3,4);     fVor->SetCcwSuccessor(4,1);
00186   fVor->SetCwPredecessor(3,1);    fVor->SetCwPredecessor(4,3);
00187   fVor->SetCcwPredecessor(3,2);   fVor->SetCcwPredecessor(4,6);
00188 
00189   // ------ 2nd curved edge       // ------ 3rd curved edge
00190   fVor->AddEdge(5);               fVor->AddEdge(6);       
00191   fVor->SetLeftPolyg(5,0);        fVor->SetLeftPolyg(6,0);
00192   fVor->SetRightPolyg(5,2);       fVor->SetRightPolyg(6,3);
00193   fVor->SetStartVtx(5,2);         fVor->SetStartVtx(6,3);
00194   fVor->SetEndVtx(5,3);           fVor->SetEndVtx(6,4);
00195   fVor->SetCwSuccessor(5,6);      fVor->SetCwSuccessor(6,4);
00196   fVor->SetCcwSuccessor(5,2);     fVor->SetCcwSuccessor(6,3);
00197   fVor->SetCwPredecessor(5,1);    fVor->SetCwPredecessor(6,2);
00198   fVor->SetCcwPredecessor(5,4);   fVor->SetCcwPredecessor(6,5);
00199 
00200   
00201   // ====== Set the first available vtx/edge ids ======
00202   fVor->AddAvailableEdgeID(7);
00203   fVor->AddAvailableVtxID(5);  
00204 
00205   // ========   Calculate/add the generators corresponding to 
00206   //                     the above "Voronoi seed"   ===========
00207   //
00208   // >> The position of these 3 additional generators is calculated 
00209   // >> by the fact that they are positioned on a circle of radius:
00210   // >> kGensRadius and they form an equilateral triangle. This is
00211   // >> an obvious configuration that creates what we call the 
00212   // >> "reversed-Mercedes Voronoi seed".
00213   // >> We let the first generator be at (x,y)=(0,kGensRadius) and
00214   // >> we get the other by 120 and 240 degrees rotations.        
00215 
00216   fGenerators->AddAt(new BFLNode(0,kGensRadius),0);
00217 
00218   x = kGensRadius * TMath::Sin(4.*TMath::Pi()/6.);
00219   y = kGensRadius * TMath::Cos(4.*TMath::Pi()/6.);
00220   fGenerators->AddAt(new BFLNode(x,y),1);
00221 
00222   x = kGensRadius * TMath::Sin(8.*TMath::Pi()/6.);
00223   y = kGensRadius * TMath::Cos(8.*TMath::Pi()/6.);
00224   fGenerators->AddAt(new BFLNode(x,y),2); 
00225 }

Int_t BFLVoronoiMaker::AddNewEdge ( Int_t  SVtxID,
Int_t  EVtxID,
Int_t  EdgeOfSVtx,
Int_t  EdgeOfEVtx 
) [private]

Definition at line 632 of file BFLVoronoiMaker.cxx.

References BFLWingedEdge::AddEdge(), BFLWingedEdge::DeleteFirstAvailableEdgeID(), fCurrentPolygID, fGenID, BFLWingedEdge::FirstAvailableEdgeID(), fVor, fVorPatch, BFLWingedEdge::SetCcwSuccessor(), BFLWingedEdge::SetCwPredecessor(), BFLWingedEdge::SetEdgeID(), BFLWingedEdge::SetEndVtx(), BFLWingedEdge::SetLeftPolyg(), BFLWingedEdge::SetRightPolyg(), and BFLWingedEdge::SetStartVtx().

Referenced by Make().

00634 {
00635 // Adds a new edge to the Winged Edge data structure.
00636 // At the time this method is called NOT all of the Voronoi edge params
00637 // are known. This is due to the cyclical nature of the boundary growing
00638 // procedure where this edge's parameters depend on the next/previous
00639 // edges. The "previous" edge of the first one is of course the last one
00640 // ( remember the cyclical nature of the procedure ) so not all the info
00641 // is available until the procedure is over. We prefer not to add all
00642 // of the edges at the end of the procedure due to the amount of the
00643 // temporary variables we would have to keep, which would furher 
00644 // complicate the procedure. So we add what we know when we leave the 
00645 // Voronoi region that this edge belongs to, and leave the missing two
00646 // parameters ( see below ) to be added at the WingedEdgePatch method.
00647 // It returns the ID of the newly added edge to be stored at a TIntList
00648 // that help us keeping track of the boundary growing procedure and
00649 // perform the patches later on.
00650 //
00651   Int_t EdgeID, NewPolygID;
00652 
00653   EdgeID = fVor->FirstAvailableEdgeID(); // Get the 1st available id
00654   fVor->DeleteFirstAvailableEdgeID(); // Edge id is not available any more
00655   
00656   fVorPatch->AddEdge(EdgeID); // Creates an BFLEdge object at slot #EdgeID
00657   fVorPatch->SetEdgeID(EdgeID,EdgeID); // MAY NOT NEED THIS
00658   
00659   // Set start & end vertices
00660   fVorPatch->SetStartVtx(EdgeID,SVtxID);
00661   fVorPatch->SetEndVtx(EdgeID,EVtxID);   
00662 
00663   // Set Left & Right polygons.
00664   // >> Remember that the boundary growing procedure happens 
00665   // >> counterclockwisely, so the new polygon is always on the left.
00666   NewPolygID = fGenID; // the ith gen.--> ith Vor. polygon
00667   fVorPatch->SetLeftPolyg(EdgeID,NewPolygID);  
00668   fVorPatch->SetRightPolyg(EdgeID,fCurrentPolygID);
00669 
00670   // Set CcwSuccessor, CwPredecessor.
00671   //CwSuccessor, CcwPredecessor to be filled after the BGP.
00672   fVorPatch->SetCcwSuccessor(EdgeID,EdgeOfEVtx);
00673   fVorPatch->SetCwPredecessor(EdgeID,EdgeOfSVtx);
00674 
00675   return EdgeID;
00676 }

void BFLVoronoiMaker::AddNewPolyg ( Int_t  EdgeID  )  [private]

Definition at line 614 of file BFLVoronoiMaker.cxx.

References BFLWingedEdge::AddPolyg(), fGenID, fVorPatch, BFLWingedEdge::SetEdgeAroundPolyg(), and BFLWingedEdge::SetPolygID().

Referenced by Make().

00615 {
00616 // Adds a new Voronoi region to the Winged Edge data structure.
00617 // All the polygon parameters are known when this method is called - 
00618 // no later patch is neccessary.
00619 //
00620   Int_t NewPolygID;
00621   
00622   // The ith generator corresponds to the ith Voronoi polygon
00623   NewPolygID = fGenID;
00624   
00625   // Add the polygon at the Winged Edge data structure
00626   fVorPatch->AddPolyg(NewPolygID);
00627   fVorPatch->SetPolygID(NewPolygID,NewPolygID); // MAY NOT NEED THIS
00628   fVorPatch->SetEdgeAroundPolyg(NewPolygID,EdgeID); 
00629 }

Int_t BFLVoronoiMaker::AddNewVtx ( Int_t  edge,
Float_t  xv,
Float_t  yv 
) [private]

Definition at line 590 of file BFLVoronoiMaker.cxx.

References BFLWingedEdge::AddVtx(), BFLWingedEdge::DeleteFirstAvailableVtxID(), BFLWingedEdge::FirstAvailableVtxID(), fVor, fVorPatch, BFLWingedEdge::SetEdgeAroundVtx(), BFLWingedEdge::SetVtxID(), BFLWingedEdge::SetWeight(), BFLWingedEdge::SetX(), and BFLWingedEdge::SetY().

Referenced by Make().

00591 {
00592 // Adds a new Voronoi vertex to the Winged Edge data structure.
00593 // At the time this method is called all the vtx parameters are known
00594 // and hence the vtx we add here is complete.
00595 //
00596   Int_t VtxID;
00597 
00598   VtxID = fVor->FirstAvailableVtxID();
00599 
00600   fVorPatch->AddVtx(VtxID); // It creates a Vtx object at slot #vtx
00601   fVorPatch->SetVtxID(VtxID,VtxID); // MAY NOT NEED THIS
00602   fVorPatch->SetEdgeAroundVtx(VtxID,EdgeID);
00603   fVorPatch->SetX(VtxID,x);
00604   fVorPatch->SetY(VtxID,y);
00605   fVorPatch->SetWeight(VtxID,kTRUE);
00606 
00607   fVor->DeleteFirstAvailableVtxID();
00608 
00609   return VtxID; 
00610 }

void BFLVoronoiMaker::Defrag ( void   )  [private]

Definition at line 807 of file BFLVoronoiMaker.cxx.

00808 {
00809 // Eliminate "gaps" in the winged edge data structure.
00810 // --------------- DUMMY IN v_1.0 -------------------
00811 
00812 /*Int_t i, last, SvtxID, EvtxID, EdgeID, MaxEdgeID;
00813   Int_t LeftPolygID, RightPolygID;
00814   Int_t CwSuccID, CcwSuccID, CwPredID, CcwPredID;
00815   Int_t VtxID, MaxVtxID;
00816   BFLEdge * Edge;
00817   BFLVtx * Vtx;
00818   TIntList * IncidentEdges = new TIntList();
00819 
00820   // DEFRAG EDGES
00821   MaxEdgeID = fVor->MaxAvailableEdgeID();
00822 
00823   EdgeID = fVor->FirstAvailableEdgeID();
00824   while(EdgeID != MaxEdgeID) {
00825      // Move the last edge of the Winged Edge DS to empty slot: EdgeID
00826      // and update other objects that refer to this edge.
00827      last = fVor->GetLastEdgeID();  // get the last edge id
00828      Edge = fVor->GetEdgeObj(last); // get the object at the last slot
00829           
00830      // Update other objects using the transfered edge.
00831      
00832      // -------------------- Update edges 
00833      CwSuccID = fVor->GetCwSuccessor(last);
00834      if(fVor->GetCcwSuccessor(CwSuccID) == last) {
00835          fVor->SetCcwSuccessor(CwSuccID,EdgeID);
00836      } else if(fVor->GetCcwPredecessor(CwSuccID) == last) {
00837          fVor->SetCcwPredecessor(CwSuccID,EdgeID);
00838      }
00839 
00840      CcwSuccID = fVor->GetCcwSuccessor(last);
00841      if(fVor->GetCwSuccessor(CcwSuccID) == last) {
00842          fVor->SetCwSuccessor(CcwSuccID,EdgeID);
00843      } else if(fVor->GetCwPredecessor(CcwSuccID) == last) {
00844          fVor->SetCwPredecessor(CcwSuccID,EdgeID);
00845      }
00846 
00847      CwPredID = fVor->GetCwPredecessor(last);
00848      if(fVor->GetCcwSuccessor(CwPredID) == last) {
00849          fVor->SetCcwSuccessor(CwPredID,EdgeID);
00850      } else if(fVor->GetCcwPredecessor(CwPredID) == last) {
00851          fVor->SetCcwPredecessor(CwPredID,EdgeID);
00852      }
00853 
00854      CcwPredID = fVor->GetCcwPredecessor(last);
00855      if(fVor->GetCwSuccessor(CcwPredID) == last) {
00856          fVor->SetCwSuccessor(CcwPredID,EdgeID);
00857      } else if(fVor->GetCwPredecessor(CcwPredID) == last) {     
00858          fVor->SetCwPredecessor(CcwPredID,EdgeID);
00859      }
00860      
00861      // -------------------- Update vertices
00862      SvtxID = fVor->GetStartVtx(last);
00863      if(fVor->GetEdgeAroundVtx(SvtxID) == last) {
00864          fVor->SetEdgeAroundVtx(SvtxID,EdgeID);
00865      }     
00866      EvtxID = fVor->GetEndVtx(last);
00867      if(fVor->GetEdgeAroundVtx(EvtxID) == last) {
00868          fVor->SetEdgeAroundVtx(EvtxID,EdgeID);
00869      }     
00870      
00871      // -------------------- Update polygons
00872      LeftPolygID = fVor->GetLeftPolyg(last);
00873      if(fVor->GetEdgeAroundPolyg(LeftPolygID) == last) {
00874          fVor->SetEdgeAroundPolyg(LeftPolygID,EdgeID);
00875      }
00876      RightPolygID = fVor->GetRightPolyg(last);
00877      if(fVor->GetEdgeAroundPolyg(RightPolygID) == last) {
00878          fVor->SetEdgeAroundPolyg(RightPolygID,EdgeID);
00879      }
00880      
00881      // Transfer the Edge object
00882      fVor->SetEdgeObj(Edge,EdgeID); // set the object to EdgeID slot
00883      fVor->DeleteEdge(last); // delete the object from slot: last
00884      
00885      // Get the next available edge
00886      fVor->DeleteFirstAvailableEdgeID();
00887      EdgeID = fVor->FirstAvailableEdgeID();     
00888   }
00889   
00890   // DEFRAG VERTICES
00891   MaxVtxID = fVor->MaxAvailableVtxID();
00892   
00893   VtxID = fVor->FirstAvailableVtxID();
00894   while(VtxID != MaxVtxID){
00895      // Move the last vtx of the Winged Edge DS to slot VtxID
00896      // and update other objects that refer to this vertex.
00897           
00898      last = fVor->GetLastVtxID();  // get the last vtx id
00899      Vtx = fVor->GetVtxObj(last); // get the object at the last slot
00900 
00901      // Update other objects using the transfered vertex.
00902 
00903      // -------------------- Update edges
00904      IncidentEdges = fOp->RetrieveEdgesIncidentToVtx(last);
00905      for(i = 0; i < IncidentEdges->NumberOfElements(); i++){
00906          EdgeID = IncidentEdges->At(i);
00907          if(fVor->GetStartVtx(EdgeID) == last){
00908               fVor->SetStartVtx(EdgeID,VtxID);
00909          } else if(fVor->GetEndVtx(EdgeID) == last) {
00910               fVor->SetEndVtx(EdgeID,VtxID);
00911          }
00912      }
00913      
00914      // Transfer the Vtx object
00915      fVor->SetVtxObj(Vtx,VtxID); // set the object to EdgeID slot
00916      fVor->DeleteVtx(last); // delete the object from slot: last
00917 
00918      // Get the next available vertex
00919      fVor->DeleteFirstAvailableVtxID();
00920      VtxID = fVor->FirstAvailableVtxID();     
00921   }
00922   
00923   // Explicitly free some allocated memory  
00924   delete IncidentEdges;
00925   delete Edge;
00926   delete Vtx;  */  
00927 }

void BFLVoronoiMaker::DeleteSubstructure ( void   )  [private]

Definition at line 754 of file BFLVoronoiMaker.cxx.

References TIntList::Add(), BFLWingedEdge::AddAvailableEdgeID(), BFLWingedEdge::AddAvailableVtxID(), TIntList::At(), BFLWingedEdge::DeleteEdge(), BFLWingedEdge::DeleteVtx(), TIntList::Exists(), fEdgesToDelete, fVerticesToDelete, fVor, BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetStartVtx(), and TIntList::NumberOfElements().

Referenced by Make().

00755 {
00756 // Deletes any substructure of the Voronoi diagram is left within 
00757 // each new Voronoi region after the boundary growing procedure.
00758 //
00759   Int_t i = 0, EvtxID, SvtxID, EdgeID, VtxID;
00760   Bool_t AlreadyDeleted;
00761   TIntList * DeletedVertices = new TIntList();
00762   
00763   //-------------------- delete vertices @ substructure
00764   
00765   for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){  
00766      SvtxID = fVor->GetStartVtx(fEdgesToDelete->At(i));
00767      EvtxID = fVor->GetEndVtx(fEdgesToDelete->At(i));
00768      
00769      if(! DeletedVertices->Exists(SvtxID)) {
00770          fVor->DeleteVtx(SvtxID);
00771          fVor->AddAvailableVtxID(SvtxID);
00772          DeletedVertices->Add(SvtxID);
00773      }
00774     
00775      if(! DeletedVertices->Exists(EvtxID)) {
00776          fVor->DeleteVtx(EvtxID);
00777          fVor->AddAvailableVtxID(EvtxID);     
00778          DeletedVertices->Add(EvtxID);
00779      }     
00780   }
00781   
00782   //-------------------- delete edges @ substructure
00783 
00784   for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
00785      EdgeID = fEdgesToDelete->At(i);
00786      fVor->DeleteEdge(EdgeID);
00787      fVor->AddAvailableEdgeID(EdgeID);
00788   }
00789 
00790 
00791   //------------------- delete any vertices left on resized edges 
00792   
00793   for(i = 0; i < fVerticesToDelete->NumberOfElements(); i++){
00794      VtxID = fVerticesToDelete->At(i);
00795      AlreadyDeleted = DeletedVertices->Exists(VtxID);
00796      if(!AlreadyDeleted) {
00797          fVor->DeleteVtx(VtxID);
00798          fVor->AddAvailableVtxID(VtxID);
00799          DeletedVertices->Add(VtxID);
00800      }  
00801   }
00802 
00803   delete DeletedVertices;
00804 }

Int_t BFLVoronoiMaker::GetAnotherEdgeAround ( Int_t  PolygID  )  const [private]

Definition at line 490 of file BFLVoronoiMaker.cxx.

References TIntList::At(), TIntList::Exists(), fEdgesToDelete, fOp, TIntList::NumberOfElements(), and BFLVorOperator::RetrieveEdgesSurrPolygon().

Referenced by RemoveRefsToDeletedEdges().

00491 {
00492 // Returns an edge around Voronoi polyg: PolygID that does not belong
00493 // to the substructure to be deleted.
00494 // It is used, when we want to remove from the Voronoi diagram data
00495 // strucrure, any reference to an edge that we are going to delete.
00496 //
00497   Int_t NewEdgeAround = 0;
00498 
00499   TIntList * edges = fOp->RetrieveEdgesSurrPolygon(PolygID);
00500 
00501   for(Int_t j=0; j < edges->NumberOfElements(); j++){
00502      NewEdgeAround = edges->At(j);
00503      if(!fEdgesToDelete->Exists(NewEdgeAround)) break;
00504   }  
00505 
00506   delete edges;
00507 
00508   return NewEdgeAround;
00509 }

virtual BFLVorOperator* BFLVoronoiMaker::GetVoronoiOperator ( void   )  [inline, private, virtual]

Definition at line 74 of file BFLVoronoiMaker.h.

References fOp.

00074 { return fOp; }

Int_t BFLVoronoiMaker::GuessNearestNeighbour ( void   )  const [private]

Definition at line 355 of file BFLVoronoiMaker.cxx.

References fGenID, fN, RandomToSorted(), and SortedToRandom().

00356 {
00357 // It returns the slot number ( at the fGenerators TObjArray ) which
00358 // contains a guess of the nearest generator to the one we have just
00359 // added. 
00360 // The last of the igenerator added generators is at the slot
00361 // igenerator-1 at the reordered fGenerators TObjArray.
00362 // The guessed generator must be already added.
00363 
00364   Int_t k, NeighbourGuess = 1;
00365   Int_t ncount = 1, icount = 0;
00366   Float_t sign; 
00367   
00368   if(fGenID > 1000) {
00369 
00370     Int_t SlotAtSorted = RandomToSorted(fGenID - 1);
00371   
00372     do {        
00373       sign = TMath::Power(-1,(icount%2)+1);
00374       k = ncount * Int_t(sign); //k = +/- 1,+/- 2,+/- 3,+/- 4,... 
00375       
00376       if(SlotAtSorted + k >= 0 && SlotAtSorted + k < fN+3) {
00377         NeighbourGuess = SortedToRandom(SlotAtSorted + k);
00378       }
00379 
00380       if(icount%2 == 1) ncount++;
00381       
00382       icount++; 
00383       
00384     } while(NeighbourGuess > fGenID - 1);
00385     
00386   } else NeighbourGuess = fGenID - 1;    
00387   
00388   return NeighbourGuess;
00389 }

void BFLVoronoiMaker::IncreaseEntropy ( void   )  [private]

Definition at line 62 of file BFLVoronoiMaker.cxx.

References TIntList::AddAt(), fGenerators, fN, fRandomToSorted, and fSortedToRandom.

Referenced by Make().

00063 {
00064 // Reorder generators so as they are randomly distributed.
00065 // This is important as it keeps almost constant the size of the 
00066 // substructure to be deleted ( after the insertion of a new 
00067 // Voronoi polygon.
00068 // Computational complexity ~ N
00069 //
00070   BFLNode * CurrentGen; 
00071   TRandom *rand = new TRandom();
00072   Int_t  i = 0, irandom;
00073   Int_t  NumberOfGenerators = fGenerators->GetEntries(); 
00074 
00075   cout << "number of generators = " << NumberOfGenerators << endl;
00076   fGenerators->Sort();
00077                                                                     
00078   fN = NumberOfGenerators - 1;                                                                      
00079 
00080   TIter next(fGenerators);
00081   while( (CurrentGen = (BFLNode *)next()) ) {
00082     irandom = (Int_t) ( NumberOfGenerators * rand->Rndm() ); 
00083     fGenerators->AddAt((BFLNode *)fGenerators->At(irandom),i);
00084     fGenerators->AddAt(CurrentGen,irandom);
00085 
00086     fSortedToRandom->AddAt(irandom,i);
00087     fRandomToSorted->AddAt(i,irandom);
00088     i++;
00089   }
00090 
00091   // send the first three generators at the end of the container
00092   // ( make space for the _FAR_GENERATORS_ ) 
00093   for (i=0; i<3; i++) fGenerators->Add((BFLNode *)fGenerators->At(i));
00094 
00095   //fGenerators->Print();
00096   
00097   delete CurrentGen;
00098   delete rand; 
00099 }

void BFLVoronoiMaker::Make ( void   ) 

Definition at line 228 of file BFLVoronoiMaker.cxx.

References TIntList::Add(), AddDistantGenerators(), AddNewEdge(), AddNewPolyg(), AddNewVtx(), BaseGeneratorID, DeleteSubstructure(), fCurrentPolygID, fGenerators, fGenID, BFLVorOperator::FindCurrentPolygon(), BFLVorOperator::FindNewVtx(), fN, fNewEdgesTopology, fNewVertices, fOp, fVorPatch, BFLVorOperator::GetFirstIntersectEdge(), BFLVorOperator::GetNextIntersectEdge(), BFLNode::GetX(), BFLNode::GetY(), IncreaseEntropy(), MarkEdgesToDelete(), MarkVerticesToDelete(), MergeDataStructures(), BFLVorOperator::MoveToNextPolygon(), NewStructureInit(), BFLVorOperator::ResetVtxCache(), BFLVorOperator::SetCurrentGen(), BFLVorOperator::SetCurrentPolygID(), SubstructureInit(), and WingedEdgePatch().

00229 {
00230 // It is the main method that coordinates the construction of the
00231 // Voronoi diagram.
00232 //
00233   Int_t EdgeID = 0, iedge = 0, LastEdgeID = 0, AddedEdgeID = 0;
00234   Int_t VtxID = 0, LastVtxID = 0, StartVtxID = 0, StartEdgeID = 0;
00235   Bool_t IsFirstVtx;
00236   BFLNode * CurrentGen;
00237   
00238   fGenID = 0;
00239 
00240   // Keep the size of the substructure to be deleted constant
00241   // by having randomly distributed generators
00242   IncreaseEntropy();
00243 
00244   // Bypass the problem due to infinite extend of some Voronoi edges.     
00245   AddDistantGenerators(); 
00246   
00247   // Adding new generators 1-by-1
00248   TIter next(fGenerators); 
00249   while( (CurrentGen = (BFLNode *)next())) {
00250     fGenID++;
00251 
00252     fOp->SetCurrentGen(CurrentGen);
00253     if(fGenID >= BaseGeneratorID) {
00254 
00255        // ------------------- <Boundary growing procedure/>      
00256        fVorPatch = new BFLWingedEdge(fN + 3);
00257 
00258        cout << "generator " << fGenID << endl; 
00259        
00260        // Initialize the substructure to be deleted after the BGP.
00261        SubstructureInit();
00262        // Initialize the new structure (new vertices, new/resized edges)
00263        NewStructureInit();
00264 
00265        // Get the current polygon
00266        fCurrentPolygID = fOp->FindCurrentPolygon();
00267        fOp->SetCurrentPolygID(fCurrentPolygID);
00268                                 
00269        // Get the 1st intersect edge
00270        EdgeID = fOp->GetFirstIntersectEdge();
00271        StartEdgeID = EdgeID; // keep this id to terminate the next loop
00272        LastEdgeID = 0; // removes dependencies from the previous iteration.
00273        fNewEdgesTopology->Add(EdgeID);
00274        IsFirstVtx = kTRUE;
00275        
00276        do {       
00277            // Mark the substructure to be deleteted after the boundary
00278            // growing procedure.       
00279            MarkEdgesToDelete(); 
00280            
00281            // Get the intersection point -> new vtx.
00282            BFLNode NewVtx = fOp->FindNewVtx(EdgeID);
00283                                                                                                                 
00284            // Add the new vertex.
00285            LastVtxID = VtxID;
00286            VtxID = AddNewVtx(EdgeID,NewVtx.GetX(),NewVtx.GetY());
00287            fNewVertices->Add(VtxID);
00288 
00289            if(IsFirstVtx) {
00290                 StartVtxID = VtxID;
00291                 IsFirstVtx = kFALSE;
00292            }
00293 
00294            // Get the next intersect edge
00295            iedge = fOp->GetNextIntersectEdge(EdgeID);
00296            if (iedge == LastEdgeID ) { 
00297                 // It is time to move to the next polygon.
00298                    
00299                 // Update the Voronoi diagram.
00300                 AddedEdgeID = AddNewEdge(LastVtxID,VtxID,
00301                                          LastEdgeID,EdgeID);
00302                 fNewEdgesTopology->Add(AddedEdgeID);
00303                 fNewEdgesTopology->Add(EdgeID);
00304                                                 
00305                 // Get the next polygon ID.
00306                 fCurrentPolygID = fOp->MoveToNextPolygon(fCurrentPolygID,EdgeID);
00307                 fOp->SetCurrentPolygID(fCurrentPolygID);
00308 
00309                 LastEdgeID = EdgeID;
00310                 EdgeID = fOp->GetNextIntersectEdge(EdgeID);
00311                                               
00312            } else {        
00313                LastEdgeID = EdgeID;
00314                EdgeID = iedge;         
00315            }         
00316                  
00317        } while(EdgeID != StartEdgeID);
00318        
00319        // Add the last Voronoi edge
00320        LastVtxID = VtxID;
00321        VtxID = StartVtxID;
00322        AddedEdgeID = AddNewEdge(LastVtxID,VtxID,LastEdgeID,EdgeID);
00323        fNewEdgesTopology->Add(AddedEdgeID);
00324 
00325        // Add the new Voronoi Polygon
00326        AddNewPolyg(AddedEdgeID);
00327        
00328        // Patch to the substructure to be deleted.
00329        MarkVerticesToDelete(); 
00330        
00331        // Patch to the Winged Edge data structure.
00332        WingedEdgePatch();
00333        MergeDataStructures();
00334        //fVorPatch->Delete();
00335        delete fVorPatch;
00336                   
00337        // Delete any old substructure within the new Voronoi region.
00338        DeleteSubstructure();
00339        
00340        // ------------------- </Boundary growing procedure> 
00341             
00342        // Reset the vtx cache before the new boundary growing procedure
00343        fOp->ResetVtxCache();
00344        
00345     } // if NOT.DistantGenerator 
00346   } // while adding new generators loop 
00347   
00348   //Defrag(); // remove gaps from the Winged Edge data structure.
00349 
00350   // Explicitly free some allocated memory  
00351   delete CurrentGen; 
00352 }

void BFLVoronoiMaker::MarkEdgesToDelete ( void   )  [private]

Definition at line 696 of file BFLVoronoiMaker.cxx.

References TIntList::Add(), TIntList::At(), BFLVorOperator::EdgeIsInsideNewPolygon(), TIntList::Exists(), fCurrentPolygID, fEdgesToDelete, fOp, TIntList::NumberOfElements(), and BFLVorOperator::RetrieveEdgesSurrPolygon().

Referenced by Make().

00697 {
00698   Int_t EdgeID;
00699   Bool_t IsInside, AlreadyExists;
00700   TIntList * EdgesAround = new TIntList();
00701 
00702   EdgesAround = fOp->RetrieveEdgesSurrPolygon(fCurrentPolygID);
00703   
00704   for(Int_t i = 0; i < EdgesAround->NumberOfElements(); i++){
00705      EdgeID = EdgesAround->At(i);
00706      
00707      if(fOp->EdgeIsInsideNewPolygon(EdgeID)) IsInside = kTRUE;
00708      else IsInside = kFALSE;
00709      
00710      if(fEdgesToDelete->Exists(EdgeID)) AlreadyExists = kTRUE;
00711      else AlreadyExists = kFALSE;
00712      
00713      if(IsInside && !AlreadyExists) fEdgesToDelete->Add(EdgeID);
00714   }
00715   
00716   delete EdgesAround; 
00717 }

void BFLVoronoiMaker::MarkVerticesToDelete ( void   )  [private]

Definition at line 720 of file BFLVoronoiMaker.cxx.

References TIntList::Add(), TIntList::At(), TIntList::Exists(), fNewEdgesTopology, fOp, fVerticesToDelete, fVor, BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetStartVtx(), TIntList::NumberOfElements(), and BFLVorOperator::VtxIsInsideNewPolyg().

Referenced by Make().

00721 {
00722 // Marks vertices to be deleted other than start/end vertices of edges
00723 // to be deleted, if any. This is important in the case that none of
00724 // the old Voronoi edges resides totally within the new Voronoi region
00725 // and a vtx to be deleted is on an edge to be resized.
00726 // This search is facilitated by the fact that the even elements of 
00727 // the EdgeTopology TIntList ( used at the Voronoi patches ) are 
00728 // resized edges, so we focus on these edges only.
00729 
00730   Int_t SvtxID, EvtxID, vtxID, EdgeID;
00731   Bool_t AlreadyExists;
00732   
00733   for(Int_t i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2){
00734      EdgeID = fNewEdgesTopology->At(i);
00735      
00736      // One of the vertices is inside the new region.
00737      SvtxID = fVor->GetStartVtx(EdgeID);
00738      EvtxID = fVor->GetEndVtx(EdgeID);
00739 
00740      // Check which one of them is within the new region.
00741      if(fOp->VtxIsInsideNewPolyg(EvtxID)) vtxID = EvtxID;
00742      else vtxID = SvtxID;
00743      
00744      // Check if this vertex already exists.
00745      if(fVerticesToDelete->Exists(vtxID)) AlreadyExists = kTRUE;
00746      else AlreadyExists = kFALSE;
00747      
00748      // ... and if it doesn't, add it.
00749      if(!AlreadyExists) fVerticesToDelete->Add(vtxID);
00750   } 
00751 }

void BFLVoronoiMaker::MergeDataStructures ( void   )  [private]

Definition at line 551 of file BFLVoronoiMaker.cxx.

References fVor, fVorPatch, BFLEdge::GetEdgeID(), BFLWingedEdge::GetEdges(), BFLPolyg::GetPolygID(), BFLWingedEdge::GetPolygons(), BFLWingedEdge::GetVertices(), BFLVtx::GetVtxID(), BFLWingedEdge::SetEdgeObj(), BFLWingedEdge::SetPolygObj(), and BFLWingedEdge::SetVtxObj().

Referenced by Make().

00552 {
00553 // This method merges the fVorPatch (Winged Edge) data structute, which
00554 // has been our workbench during the boundary growing procedure, with
00555 // the fVor data structure which holds the full Voronoi diagram for all
00556 // the previously added generators. 
00557 
00558   // -------------------- Add Edges
00559   TIter NextEdge(fVorPatch->GetEdges()); 
00560   BFLEdge * EdgeObj;
00561   while ((EdgeObj = (BFLEdge *)NextEdge())) { 
00562      BFLEdge *NewEdge = new BFLEdge(EdgeObj->GetEdgeID());
00563      *NewEdge = *EdgeObj; 
00564      fVor->SetEdgeObj(NewEdge, EdgeObj->GetEdgeID());
00565   }
00566   delete EdgeObj;
00567   
00568   // -------------------- Add Vertices    
00569   TIter NextVtx(fVorPatch->GetVertices());
00570   BFLVtx * VtxObj;
00571   while ((VtxObj = (BFLVtx *)NextVtx())) { 
00572      BFLVtx *NewVtx = new BFLVtx(VtxObj->GetVtxID());
00573      *NewVtx = *VtxObj; 
00574      fVor->SetVtxObj(NewVtx, VtxObj->GetVtxID());
00575   }
00576   delete VtxObj;
00577 
00578   // -------------------- Add Polygons  
00579   TIter NextPolyg(fVorPatch->GetPolygons());
00580   BFLPolyg * PolygObj;
00581   while ((PolygObj = (BFLPolyg *)NextPolyg())) { 
00582      BFLPolyg *NewPolyg = new BFLPolyg(PolygObj->GetPolygID());
00583      *NewPolyg = *PolygObj;
00584      fVor->SetPolygObj(NewPolyg, PolygObj->GetPolygID());
00585   }
00586   delete PolygObj; 
00587 }

void BFLVoronoiMaker::NewStructureInit ( void   )  [private]

Definition at line 689 of file BFLVoronoiMaker.cxx.

References TIntList::Delete(), fNewEdgesTopology, and fNewVertices.

Referenced by Make().

00690 { 
00691   fNewEdgesTopology->Delete();
00692   fNewVertices->Delete();
00693 }

virtual Int_t BFLVoronoiMaker::RandomToSorted ( Int_t  SlotAtRandom  )  const [inline, private, virtual]

Definition at line 67 of file BFLVoronoiMaker.h.

References TIntList::At(), and fRandomToSorted.

Referenced by GuessNearestNeighbour().

00067                                                          {
00068     return 3+fRandomToSorted->At(SlotAtRandom);
00069   } 

void BFLVoronoiMaker::RemoveRefsToDeletedEdges ( void   )  [private]

Definition at line 513 of file BFLVoronoiMaker.cxx.

References TIntList::At(), fEdgesToDelete, fVor, GetAnotherEdgeAround(), BFLWingedEdge::GetEdgeAroundPolyg(), BFLWingedEdge::GetLeftPolyg(), BFLWingedEdge::GetRightPolyg(), TIntList::NumberOfElements(), and BFLWingedEdge::SetEdgeAroundPolyg().

Referenced by WingedEdgePatch().

00514 {
00515 // This method removes every reference of a Voronoi diagram data
00516 // structure to edges that belongs to  the substructure to be deleted.
00517 // During the boundary growing procedure such references are carefully
00518 // eliminated. At the point this method is called, the only possible
00519 // reference to an edge "corpse" is at the EdgeAroundPolyg quantity.
00520 // Caution: Since this is a rather trivial change with no impact to
00521 // the undisturbed Voronoi diagram data structure, this change is made
00522 // directly to the fVor winged-edge data structure instead of the
00523 // fVorPatch data structure which is our workbench during the boundary
00524 // growing procedure. This is both simpler and faster.
00525 //
00526   for(Int_t i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
00527 
00528      Int_t EdgeID = fEdgesToDelete->At(i);
00529 
00530      // Check the left polygon of edge: EdgeID for ref. to this edge.
00531 
00532      Int_t LPolygID = fVor->GetLeftPolyg(EdgeID);
00533      if(EdgeID == fVor->GetEdgeAroundPolyg(LPolygID)) {
00534 
00535           Int_t NewEdgeAround = GetAnotherEdgeAround(LPolygID);
00536           fVor->SetEdgeAroundPolyg(LPolygID,NewEdgeAround); 
00537      }
00538 
00539      // Check the right polygon of edge: EdgeID for ref. to this edge.
00540 
00541      Int_t RPolygID = fVor->GetRightPolyg(EdgeID);
00542      if(EdgeID == fVor->GetEdgeAroundPolyg(RPolygID)) {
00543 
00544           Int_t NewEdgeAround = GetAnotherEdgeAround(RPolygID);
00545           fVor->SetEdgeAroundPolyg(RPolygID,NewEdgeAround);
00546      }
00547   }
00548 }

virtual Int_t BFLVoronoiMaker::SortedToRandom ( Int_t  SlotAtSorted  )  const [inline, private, virtual]

Definition at line 70 of file BFLVoronoiMaker.h.

References TIntList::At(), and fSortedToRandom.

Referenced by GuessNearestNeighbour().

00070                                                          {
00071     return 3+fSortedToRandom->At(SlotAtSorted);
00072   } 

void BFLVoronoiMaker::SubstructureInit ( void   )  [private]

Definition at line 679 of file BFLVoronoiMaker.cxx.

References TIntList::Delete(), fEdgesToDelete, and fVerticesToDelete.

Referenced by Make().

00680 {
00681 // Initialize the process of deleting the substructure produced by 
00682 // the boundary growing procedure.
00683 
00684   fEdgesToDelete->Delete();
00685   fVerticesToDelete->Delete();
00686 }

void BFLVoronoiMaker::WingedEdgePatch ( void   )  [private]

Definition at line 392 of file BFLVoronoiMaker.cxx.

References TIntList::At(), fNewEdgesTopology, fNewVertices, fOp, fVor, fVorPatch, BFLWingedEdge::GetEdgeObj(), BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetStartVtx(), TIntList::NumberOfElements(), RemoveRefsToDeletedEdges(), BFLWingedEdge::SetCcwPredecessor(), BFLWingedEdge::SetCcwSuccessor(), BFLWingedEdge::SetCwPredecessor(), BFLWingedEdge::SetCwSuccessor(), BFLWingedEdge::SetEdgeObj(), BFLWingedEdge::SetEndVtx(), BFLWingedEdge::SetStartVtx(), and BFLVorOperator::VtxIsInsideNewPolyg().

Referenced by Make().

00393 {
00394   Int_t ivtx = 0, i = 0, iedge = 0, EdgeID = 0, VtxID = 0;
00395 
00396 
00397   // ======== Set the CwSuccessor of the newly added edges. ======== 
00398   for(i = 1; i < fNewEdgesTopology->NumberOfElements(); i+=2) {
00399      iedge = i+2;
00400      if(iedge > fNewEdgesTopology->NumberOfElements()) {
00401          iedge -= fNewEdgesTopology->NumberOfElements();
00402      }
00403      fVorPatch->SetCwSuccessor(fNewEdgesTopology->At(i),
00404                                fNewEdgesTopology->At(iedge));
00405   } // -> forward loop over new edges
00406 
00407 
00408   // ======== Set the CcwPredecessor of the newly added edges.======== 
00409   for(i = fNewEdgesTopology->NumberOfElements() - 1; i>0; i-=2) {
00410      iedge = i-2;
00411      if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00412      fVorPatch->SetCcwPredecessor(fNewEdgesTopology->At(i),
00413                                   fNewEdgesTopology->At(iedge));
00414   } // <- backward loop over new edges 
00415   
00416 
00417   // ======== Resize edges that have a new vertex on them. ========
00418   
00419   // --------------------- Bring them from fVor to fVorPatch
00420   
00421   for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
00422      EdgeID = fNewEdgesTopology->At(i);     
00423      BFLEdge * ResizedEdge = new BFLEdge(EdgeID);
00424      *ResizedEdge = *(fVor->GetEdgeObj(EdgeID));
00425      fVorPatch->SetEdgeObj(ResizedEdge,EdgeID); 
00426   } 
00427   
00428   ivtx = 0;
00429   for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
00430   
00431      VtxID = fNewVertices->At(ivtx);
00432      EdgeID = fNewEdgesTopology->At(i);
00433           
00434      // Check if the added vtx is the edge's start or end vertex.
00435      // >> Since the edge with EdgeID is to be resized one of
00436      // >> its (two) vertices is within the new Voronoi region
00437      // >> and hence belongs to the substructure to be deleted. 
00438      // >> The new vtx becomes a start vtx for this edge if the 
00439      // >> start vertex is the one we will remove, or otherwise
00440      // >> becomes an end vertex for this edge.
00441      
00442      // -- ADD STUFF FROM FVOR --
00443           
00444      if(fOp->VtxIsInsideNewPolyg(fVor->GetStartVtx(EdgeID))) { 
00445           
00446          fVorPatch->SetStartVtx(EdgeID,VtxID); // Set the new StartVtx.
00447          
00448          // Since the StartVtx has changed, update predecessors.
00449          iedge = i-1;
00450          if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00451          fVorPatch->SetCwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
00452          
00453          iedge = i+1;
00454          if(iedge > fNewEdgesTopology->NumberOfElements()) {
00455               iedge -= fNewEdgesTopology->NumberOfElements();
00456          }
00457          fVorPatch->SetCcwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
00458      
00459      } else if(fOp->VtxIsInsideNewPolyg(fVor->GetEndVtx(EdgeID))) {
00460          
00461          fVorPatch->SetEndVtx(EdgeID,VtxID); // Set the new EndVtx.
00462          
00463          // Since the EndVtx has changed, update successors.
00464          iedge = i-1;
00465          if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00466          fVorPatch->SetCwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));
00467                  
00468          iedge = i+1;
00469          if(iedge > fNewEdgesTopology->NumberOfElements()) {
00470               iedge -= fNewEdgesTopology->NumberOfElements();
00471          }       
00472          fVorPatch->SetCcwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));     
00473      }          
00474      ivtx++;
00475   }
00476 
00477   // ======= Check for potential updates on Voronoi polygons =========
00478 
00479   // We have marked some edges so as to delete them. We do not want any
00480   // reference to these edges left to the Voronoi data structure.
00481   // During the boundary growing procedure any reference to the edges
00482   // of the substructure to be deleted is carefully removed.
00483   // The only possible reference is in the EdgeAround value of a Voronoi
00484   // polygon. If this is the case we choose another EdgeAround value.
00485 
00486   RemoveRefsToDeletedEdges(); 
00487 } 


Member Data Documentation

Bool_t BFLVoronoiMaker::debug [private]

Definition at line 90 of file BFLVoronoiMaker.h.

Bool_t BFLVoronoiMaker::debug2 [private]

Definition at line 91 of file BFLVoronoiMaker.h.

TObjArray* BFLVoronoiMaker::fBField [private]

Definition at line 92 of file BFLVoronoiMaker.h.

Definition at line 76 of file BFLVoronoiMaker.h.

Referenced by AddNewEdge(), Make(), and MarkEdgesToDelete().

TObjArray* BFLVoronoiMaker::fGenerators [private]

Definition at line 82 of file BFLVoronoiMaker.h.

Referenced by AddDistantGenerators(), IncreaseEntropy(), and Make().

Int_t BFLVoronoiMaker::fGenID [private]

Definition at line 77 of file BFLVoronoiMaker.h.

Referenced by AddNewEdge(), AddNewPolyg(), GuessNearestNeighbour(), and Make().

Long_t BFLVoronoiMaker::fN [private]

Definition at line 78 of file BFLVoronoiMaker.h.

Referenced by GuessNearestNeighbour(), IncreaseEntropy(), and Make().

Definition at line 88 of file BFLVoronoiMaker.h.

Referenced by Make(), NewStructureInit(), WingedEdgePatch(), and ~BFLVoronoiMaker().

Definition at line 83 of file BFLVoronoiMaker.h.

Referenced by IncreaseEntropy(), RandomToSorted(), and ~BFLVoronoiMaker().

Definition at line 84 of file BFLVoronoiMaker.h.

Referenced by IncreaseEntropy(), SortedToRandom(), and ~BFLVoronoiMaker().

Definition at line 86 of file BFLVoronoiMaker.h.

Referenced by DeleteSubstructure(), MarkVerticesToDelete(), and SubstructureInit().


The documentation for this class was generated from the following files:

Generated on 2 Nov 2017 for loon by  doxygen 1.6.1