BFLVoronoiMaker.cxx

Go to the documentation of this file.

//                                                                   //
//authors: Costas Andreopoulos, Elias Athanasopoulos, George Tzanakos//
//                Physics Department, University of Athens           //

#include <fstream>
//#include "TObjArray.h"                                               
//#include "TObjectTable.h"
#include "TRandom.h"
#include "TMatrix.h"
//#include "TMath.h"
//#include "TVector2.h"

#include "BField/TIntList.h"
#include "BField/BFLNode.h"
#include "BField/BFLVtx.h"
#include "BField/BFLEdge.h"
#include "BField/BFLPolyg.h"
#include "BField/BFLWingedEdge.h"
#include "BField/BFLVorOperator.h"
#include "BField/BFLVoronoiMaker.h"
   
ClassImp(BFLVoronoiMaker)
ClassImp(BFLVtx) 
ClassImp(BFLEdge)    
ClassImp(BFLPolyg) 

// CONSTRUCTOR & DESTRUCTOR
//

BFLVoronoiMaker::BFLVoronoiMaker(BFLWingedEdge * voronoi)
{
// Allocate some memory for this instance variables

  fVor = (BFLWingedEdge *) voronoi;

  fGenerators = (TObjArray *) fVor->GetGenerators(); 
  fOp = new BFLVorOperator(voronoi);

  fN = 0;
  fRandomToSorted = new TIntList();
  fSortedToRandom = new TIntList();
  fEdgesToDelete = new TIntList();    
  fVerticesToDelete = new TIntList();
  fNewEdgesTopology = new TIntList();
  fNewVertices = new TIntList(); 
}

BFLVoronoiMaker::~BFLVoronoiMaker()
{
  delete fRandomToSorted;
  delete fSortedToRandom;  
  delete fNewEdgesTopology;
  delete fNewVertices;
}

void BFLVoronoiMaker::IncreaseEntropy(void)
{
// Reorder generators so as they are randomly distributed.
// This is important as it keeps almost constant the size of the 
// substructure to be deleted ( after the insertion of a new 
// Voronoi polygon.
// Computational complexity ~ N
//
  BFLNode * CurrentGen; 
  TRandom *rand = new TRandom();
  Int_t  i = 0, irandom;
  Int_t  NumberOfGenerators = fGenerators->GetEntries(); 

  cout << "number of generators = " << NumberOfGenerators << endl;
  fGenerators->Sort();
                                                                    
  fN = NumberOfGenerators - 1;                                                                      

  TIter next(fGenerators);
  while( (CurrentGen = (BFLNode *)next()) ) {
    irandom = (Int_t) ( NumberOfGenerators * rand->Rndm() ); 
    fGenerators->AddAt((BFLNode *)fGenerators->At(irandom),i);
    fGenerators->AddAt(CurrentGen,irandom);

    fSortedToRandom->AddAt(irandom,i);
    fRandomToSorted->AddAt(i,irandom);
    i++;
  }

  // send the first three generators at the end of the container
  // ( make space for the _FAR_GENERATORS_ ) 
  for (i=0; i<3; i++) fGenerators->Add((BFLNode *)fGenerators->At(i));

  //fGenerators->Print();
  
  delete CurrentGen;
  delete rand; 
}

void BFLVoronoiMaker::AddDistantGenerators(void)
{
// Adds three distant generators to bypass the problem with the 
// infinite extend of some Voronoi edges.
// These generators should be far enough, not only to include all the
// others, but also not disturb their Voronoi polygons.
// This method also computes the Voronoi diagram of the 3 generators
//
// see:                C.Andreopoulos, E.Athanasopoulos, G.Tzanakos,
// "Spatial tesselation techniques ???", Fermilab report, NuMI-L-xxx
//

  Float_t x, y;

  // ======== Add the first 4 Voronoi vertices ========  

  // see NuMI-L-???
  x = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);
  y = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);


  // Start vtx of all 3 inner, initial Voronoi edges
  fVor->AddVtx(1);   //-------------------- 1st vertex  
  fVor->SetX(1,0.);
  fVor->SetY(1,0.);
  fVor->SetWeight(1,kTRUE);
  fVor->SetEdgeAroundVtx(1,1);
  
  fVor->AddVtx(2);   //-------------------- 2nd vertex
  fVor->SetVtx(2);   
  fVor->SetX(2,x);   
  fVor->SetY(2,y);    
  fVor->SetWeight(2,kFALSE);   
  fVor->SetEdgeAroundVtx(2,4);
  
  fVor->AddVtx(3);   //-------------------- 3rd vertex   
  fVor->SetX(3,0);   
  fVor->SetY(3,-kAugmentedGrRadius);    
  fVor->SetWeight(3,kFALSE); 
  fVor->SetEdgeAroundVtx(3,5);
  
  fVor->AddVtx(4);   //-------------------- 4th vertex  
  fVor->SetX(4,-x);  
  fVor->SetY(4,y);                   
  fVor->SetWeight(4,kFALSE); 
  fVor->SetEdgeAroundVtx(4,6);
  

  //======== Add the first 4 Voronoi polygons ==========
  
  fVor->AddPolyg(0);              //------ 0 polygon: EXTERNAL REGION
  fVor->SetEdgeAroundPolyg(0,4); 
  fVor->AddPolyg(1);              //------ 1st polygon
  fVor->SetEdgeAroundPolyg(1,1);
  fVor->AddPolyg(2);              //------ 2nd polygon
  fVor->SetEdgeAroundPolyg(2,2);
  fVor->AddPolyg(3);              //------ 3rd polygon
  fVor->SetEdgeAroundPolyg(3,3);
  //fNPolygs = 4; 


  // ======== Add the first 6 Voronoi edges ===========
  // ---- 3 of them are inner edges
  // ---- 3 of them make the outer curved boundary
  
  // ---------- 1st edge          // ---------- 2nd edge
  fVor->AddEdge(1);               fVor->AddEdge(2);       
  fVor->SetLeftPolyg(1,1);        fVor->SetLeftPolyg(2,2);
  fVor->SetRightPolyg(1,2);       fVor->SetRightPolyg(2,3);
  fVor->SetStartVtx(1,1);         fVor->SetStartVtx(2,1);
  fVor->SetEndVtx(1,2);           fVor->SetEndVtx(2,3);
  fVor->SetCwSuccessor(1,4);      fVor->SetCwSuccessor(2,5);
  fVor->SetCcwSuccessor(1,5);     fVor->SetCcwSuccessor(2,6);
  fVor->SetCwPredecessor(1,2);    fVor->SetCwPredecessor(2,3);
  fVor->SetCcwPredecessor(1,3);   fVor->SetCcwPredecessor(2,1); 

  // ---------- 3rd edge          // ------ 1st curved edge
  fVor->AddEdge(3);               fVor->AddEdge(4);        
  fVor->SetLeftPolyg(3,3);        fVor->SetLeftPolyg(4,0);
  fVor->SetRightPolyg(3,1);       fVor->SetRightPolyg(4,1);
  fVor->SetStartVtx(3,1);         fVor->SetStartVtx(4,4);
  fVor->SetEndVtx(3,4);           fVor->SetEndVtx(4,2);
  fVor->SetCwSuccessor(3,6);      fVor->SetCwSuccessor(4,5);
  fVor->SetCcwSuccessor(3,4);     fVor->SetCcwSuccessor(4,1);
  fVor->SetCwPredecessor(3,1);    fVor->SetCwPredecessor(4,3);
  fVor->SetCcwPredecessor(3,2);   fVor->SetCcwPredecessor(4,6);

  // ------ 2nd curved edge       // ------ 3rd curved edge
  fVor->AddEdge(5);               fVor->AddEdge(6);       
  fVor->SetLeftPolyg(5,0);        fVor->SetLeftPolyg(6,0);
  fVor->SetRightPolyg(5,2);       fVor->SetRightPolyg(6,3);
  fVor->SetStartVtx(5,2);         fVor->SetStartVtx(6,3);
  fVor->SetEndVtx(5,3);           fVor->SetEndVtx(6,4);
  fVor->SetCwSuccessor(5,6);      fVor->SetCwSuccessor(6,4);
  fVor->SetCcwSuccessor(5,2);     fVor->SetCcwSuccessor(6,3);
  fVor->SetCwPredecessor(5,1);    fVor->SetCwPredecessor(6,2);
  fVor->SetCcwPredecessor(5,4);   fVor->SetCcwPredecessor(6,5);

  
  // ====== Set the first available vtx/edge ids ======
  fVor->AddAvailableEdgeID(7);
  fVor->AddAvailableVtxID(5);  

  // ========   Calculate/add the generators corresponding to 
  //                     the above "Voronoi seed"   ===========
  //
  // >> The position of these 3 additional generators is calculated 
  // >> by the fact that they are positioned on a circle of radius:
  // >> kGensRadius and they form an equilateral triangle. This is
  // >> an obvious configuration that creates what we call the 
  // >> "reversed-Mercedes Voronoi seed".
  // >> We let the first generator be at (x,y)=(0,kGensRadius) and
  // >> we get the other by 120 and 240 degrees rotations.        

  fGenerators->AddAt(new BFLNode(0,kGensRadius),0);

  x = kGensRadius * TMath::Sin(4.*TMath::Pi()/6.);
  y = kGensRadius * TMath::Cos(4.*TMath::Pi()/6.);
  fGenerators->AddAt(new BFLNode(x,y),1);

  x = kGensRadius * TMath::Sin(8.*TMath::Pi()/6.);
  y = kGensRadius * TMath::Cos(8.*TMath::Pi()/6.);
  fGenerators->AddAt(new BFLNode(x,y),2); 
}

void BFLVoronoiMaker::Make(void)
{
// It is the main method that coordinates the construction of the
// Voronoi diagram.
//
  Int_t EdgeID = 0, iedge = 0, LastEdgeID = 0, AddedEdgeID = 0;
  Int_t VtxID = 0, LastVtxID = 0, StartVtxID = 0, StartEdgeID = 0;
  Bool_t IsFirstVtx;
  BFLNode * CurrentGen;
  
  fGenID = 0;

  // Keep the size of the substructure to be deleted constant
  // by having randomly distributed generators
  IncreaseEntropy();

  // Bypass the problem due to infinite extend of some Voronoi edges.     
  AddDistantGenerators(); 
  
  // Adding new generators 1-by-1
  TIter next(fGenerators); 
  while( (CurrentGen = (BFLNode *)next())) {
    fGenID++;

    fOp->SetCurrentGen(CurrentGen);
    if(fGenID >= BaseGeneratorID) {

       // ------------------- <Boundary growing procedure/>      
       fVorPatch = new BFLWingedEdge(fN + 3);

       cout << "generator " << fGenID << endl; 
       
       // Initialize the substructure to be deleted after the BGP.
       SubstructureInit();
       // Initialize the new structure (new vertices, new/resized edges)
       NewStructureInit();

       // Get the current polygon
       fCurrentPolygID = fOp->FindCurrentPolygon();
       fOp->SetCurrentPolygID(fCurrentPolygID);
                                
       // Get the 1st intersect edge
       EdgeID = fOp->GetFirstIntersectEdge();
       StartEdgeID = EdgeID; // keep this id to terminate the next loop
       LastEdgeID = 0; // removes dependencies from the previous iteration.
       fNewEdgesTopology->Add(EdgeID);
       IsFirstVtx = kTRUE;
       
       do {       
           // Mark the substructure to be deleteted after the boundary
           // growing procedure.       
           MarkEdgesToDelete(); 
           
           // Get the intersection point -> new vtx.
           BFLNode NewVtx = fOp->FindNewVtx(EdgeID);
                                                                                                                
           // Add the new vertex.
           LastVtxID = VtxID;
           VtxID = AddNewVtx(EdgeID,NewVtx.GetX(),NewVtx.GetY());
           fNewVertices->Add(VtxID);

           if(IsFirstVtx) {
                StartVtxID = VtxID;
                IsFirstVtx = kFALSE;
           }

           // Get the next intersect edge
           iedge = fOp->GetNextIntersectEdge(EdgeID);
           if (iedge == LastEdgeID ) { 
                // It is time to move to the next polygon.
                   
                // Update the Voronoi diagram.
                AddedEdgeID = AddNewEdge(LastVtxID,VtxID,
                                         LastEdgeID,EdgeID);
                fNewEdgesTopology->Add(AddedEdgeID);
                fNewEdgesTopology->Add(EdgeID);
                                                
                // Get the next polygon ID.
                fCurrentPolygID = fOp->MoveToNextPolygon(fCurrentPolygID,EdgeID);
                fOp->SetCurrentPolygID(fCurrentPolygID);

                LastEdgeID = EdgeID;
                EdgeID = fOp->GetNextIntersectEdge(EdgeID);
                                              
           } else {        
               LastEdgeID = EdgeID;
               EdgeID = iedge;         
           }         
                 
       } while(EdgeID != StartEdgeID);
       
       // Add the last Voronoi edge
       LastVtxID = VtxID;
       VtxID = StartVtxID;
       AddedEdgeID = AddNewEdge(LastVtxID,VtxID,LastEdgeID,EdgeID);
       fNewEdgesTopology->Add(AddedEdgeID);

       // Add the new Voronoi Polygon
       AddNewPolyg(AddedEdgeID);
       
       // Patch to the substructure to be deleted.
       MarkVerticesToDelete(); 
       
       // Patch to the Winged Edge data structure.
       WingedEdgePatch();
       MergeDataStructures();
       //fVorPatch->Delete();
       delete fVorPatch;
                  
       // Delete any old substructure within the new Voronoi region.
       DeleteSubstructure();
       
       // ------------------- </Boundary growing procedure> 
            
       // Reset the vtx cache before the new boundary growing procedure
       fOp->ResetVtxCache();
       
    } // if NOT.DistantGenerator 
  } // while adding new generators loop 
  
  //Defrag(); // remove gaps from the Winged Edge data structure.

  // Explicitly free some allocated memory  
  delete CurrentGen; 
}

Int_t BFLVoronoiMaker::GuessNearestNeighbour(void) const
{
// It returns the slot number ( at the fGenerators TObjArray ) which
// contains a guess of the nearest generator to the one we have just
// added. 
// The last of the igenerator added generators is at the slot
// igenerator-1 at the reordered fGenerators TObjArray.
// The guessed generator must be already added.

  Int_t k, NeighbourGuess = 1;
  Int_t ncount = 1, icount = 0;
  Float_t sign; 
  
  if(fGenID > 1000) {

    Int_t SlotAtSorted = RandomToSorted(fGenID - 1);
  
    do {        
      sign = TMath::Power(-1,(icount%2)+1);
      k = ncount * Int_t(sign); //k = +/- 1,+/- 2,+/- 3,+/- 4,... 
      
      if(SlotAtSorted + k >= 0 && SlotAtSorted + k < fN+3) {
        NeighbourGuess = SortedToRandom(SlotAtSorted + k);
      }

      if(icount%2 == 1) ncount++;
      
      icount++; 
      
    } while(NeighbourGuess > fGenID - 1);
    
  } else NeighbourGuess = fGenID - 1;    
  
  return NeighbourGuess;
}

void BFLVoronoiMaker::WingedEdgePatch(void)
{
  Int_t ivtx = 0, i = 0, iedge = 0, EdgeID = 0, VtxID = 0;


  // ======== Set the CwSuccessor of the newly added edges. ======== 
  for(i = 1; i < fNewEdgesTopology->NumberOfElements(); i+=2) {
     iedge = i+2;
     if(iedge > fNewEdgesTopology->NumberOfElements()) {
         iedge -= fNewEdgesTopology->NumberOfElements();
     }
     fVorPatch->SetCwSuccessor(fNewEdgesTopology->At(i),
                               fNewEdgesTopology->At(iedge));
  } // -> forward loop over new edges


  // ======== Set the CcwPredecessor of the newly added edges.======== 
  for(i = fNewEdgesTopology->NumberOfElements() - 1; i>0; i-=2) {
     iedge = i-2;
     if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
     fVorPatch->SetCcwPredecessor(fNewEdgesTopology->At(i),
                                  fNewEdgesTopology->At(iedge));
  } // <- backward loop over new edges 
  

  // ======== Resize edges that have a new vertex on them. ========
  
  // --------------------- Bring them from fVor to fVorPatch
  
  for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
     EdgeID = fNewEdgesTopology->At(i);     
     BFLEdge * ResizedEdge = new BFLEdge(EdgeID);
     *ResizedEdge = *(fVor->GetEdgeObj(EdgeID));
     fVorPatch->SetEdgeObj(ResizedEdge,EdgeID); 
  } 
  
  ivtx = 0;
  for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
  
     VtxID = fNewVertices->At(ivtx);
     EdgeID = fNewEdgesTopology->At(i);
          
     // Check if the added vtx is the edge's start or end vertex.
     // >> Since the edge with EdgeID is to be resized one of
     // >> its (two) vertices is within the new Voronoi region
     // >> and hence belongs to the substructure to be deleted. 
     // >> The new vtx becomes a start vtx for this edge if the 
     // >> start vertex is the one we will remove, or otherwise
     // >> becomes an end vertex for this edge.
     
     // -- ADD STUFF FROM FVOR --
          
     if(fOp->VtxIsInsideNewPolyg(fVor->GetStartVtx(EdgeID))) { 
          
         fVorPatch->SetStartVtx(EdgeID,VtxID); // Set the new StartVtx.
         
         // Since the StartVtx has changed, update predecessors.
         iedge = i-1;
         if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
         fVorPatch->SetCwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
         
         iedge = i+1;
         if(iedge > fNewEdgesTopology->NumberOfElements()) {
              iedge -= fNewEdgesTopology->NumberOfElements();
         }
         fVorPatch->SetCcwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
     
     } else if(fOp->VtxIsInsideNewPolyg(fVor->GetEndVtx(EdgeID))) {
         
         fVorPatch->SetEndVtx(EdgeID,VtxID); // Set the new EndVtx.
         
         // Since the EndVtx has changed, update successors.
         iedge = i-1;
         if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
         fVorPatch->SetCwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));
                 
         iedge = i+1;
         if(iedge > fNewEdgesTopology->NumberOfElements()) {
              iedge -= fNewEdgesTopology->NumberOfElements();
         }       
         fVorPatch->SetCcwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));     
     }          
     ivtx++;
  }

  // ======= Check for potential updates on Voronoi polygons =========

  // We have marked some edges so as to delete them. We do not want any
  // reference to these edges left to the Voronoi data structure.
  // During the boundary growing procedure any reference to the edges
  // of the substructure to be deleted is carefully removed.
  // The only possible reference is in the EdgeAround value of a Voronoi
  // polygon. If this is the case we choose another EdgeAround value.

  RemoveRefsToDeletedEdges(); 
} 

Int_t BFLVoronoiMaker::GetAnotherEdgeAround(Int_t PolygID) const 
{
// Returns an edge around Voronoi polyg: PolygID that does not belong
// to the substructure to be deleted.
// It is used, when we want to remove from the Voronoi diagram data
// strucrure, any reference to an edge that we are going to delete.
//
  Int_t NewEdgeAround = 0;

  TIntList * edges = fOp->RetrieveEdgesSurrPolygon(PolygID);

  for(Int_t j=0; j < edges->NumberOfElements(); j++){
     NewEdgeAround = edges->At(j);
     if(!fEdgesToDelete->Exists(NewEdgeAround)) break;
  }  

  delete edges;

  return NewEdgeAround;
}


void  BFLVoronoiMaker::RemoveRefsToDeletedEdges(void)
{
// This method removes every reference of a Voronoi diagram data
// structure to edges that belongs to  the substructure to be deleted.
// During the boundary growing procedure such references are carefully
// eliminated. At the point this method is called, the only possible
// reference to an edge "corpse" is at the EdgeAroundPolyg quantity.
// Caution: Since this is a rather trivial change with no impact to
// the undisturbed Voronoi diagram data structure, this change is made
// directly to the fVor winged-edge data structure instead of the
// fVorPatch data structure which is our workbench during the boundary
// growing procedure. This is both simpler and faster.
//
  for(Int_t i = 0; i < fEdgesToDelete->NumberOfElements(); i++){

     Int_t EdgeID = fEdgesToDelete->At(i);

     // Check the left polygon of edge: EdgeID for ref. to this edge.

     Int_t LPolygID = fVor->GetLeftPolyg(EdgeID);
     if(EdgeID == fVor->GetEdgeAroundPolyg(LPolygID)) {

          Int_t NewEdgeAround = GetAnotherEdgeAround(LPolygID);
          fVor->SetEdgeAroundPolyg(LPolygID,NewEdgeAround); 
     }

     // Check the right polygon of edge: EdgeID for ref. to this edge.

     Int_t RPolygID = fVor->GetRightPolyg(EdgeID);
     if(EdgeID == fVor->GetEdgeAroundPolyg(RPolygID)) {

          Int_t NewEdgeAround = GetAnotherEdgeAround(RPolygID);
          fVor->SetEdgeAroundPolyg(RPolygID,NewEdgeAround);
     }
  }
}

void BFLVoronoiMaker::MergeDataStructures(void)
{
// This method merges the fVorPatch (Winged Edge) data structute, which
// has been our workbench during the boundary growing procedure, with
// the fVor data structure which holds the full Voronoi diagram for all
// the previously added generators. 

  // -------------------- Add Edges
  TIter NextEdge(fVorPatch->GetEdges()); 
  BFLEdge * EdgeObj;
  while ((EdgeObj = (BFLEdge *)NextEdge())) { 
     BFLEdge *NewEdge = new BFLEdge(EdgeObj->GetEdgeID());
     *NewEdge = *EdgeObj; 
     fVor->SetEdgeObj(NewEdge, EdgeObj->GetEdgeID());
  }
  delete EdgeObj;
  
  // -------------------- Add Vertices    
  TIter NextVtx(fVorPatch->GetVertices());
  BFLVtx * VtxObj;
  while ((VtxObj = (BFLVtx *)NextVtx())) { 
     BFLVtx *NewVtx = new BFLVtx(VtxObj->GetVtxID());
     *NewVtx = *VtxObj; 
     fVor->SetVtxObj(NewVtx, VtxObj->GetVtxID());
  }
  delete VtxObj;

  // -------------------- Add Polygons  
  TIter NextPolyg(fVorPatch->GetPolygons());
  BFLPolyg * PolygObj;
  while ((PolygObj = (BFLPolyg *)NextPolyg())) { 
     BFLPolyg *NewPolyg = new BFLPolyg(PolygObj->GetPolygID());
     *NewPolyg = *PolygObj;
     fVor->SetPolygObj(NewPolyg, PolygObj->GetPolygID());
  }
  delete PolygObj; 
}

Int_t  BFLVoronoiMaker::AddNewVtx(Int_t EdgeID, Float_t x, Float_t y)
{
// Adds a new Voronoi vertex to the Winged Edge data structure.
// At the time this method is called all the vtx parameters are known
// and hence the vtx we add here is complete.
//
  Int_t VtxID;

  VtxID = fVor->FirstAvailableVtxID();

  fVorPatch->AddVtx(VtxID); // It creates a Vtx object at slot #vtx
  fVorPatch->SetVtxID(VtxID,VtxID); // MAY NOT NEED THIS
  fVorPatch->SetEdgeAroundVtx(VtxID,EdgeID);
  fVorPatch->SetX(VtxID,x);
  fVorPatch->SetY(VtxID,y);
  fVorPatch->SetWeight(VtxID,kTRUE);

  fVor->DeleteFirstAvailableVtxID();

  return VtxID; 
}


void BFLVoronoiMaker::AddNewPolyg(Int_t EdgeID)
{
// Adds a new Voronoi region to the Winged Edge data structure.
// All the polygon parameters are known when this method is called - 
// no later patch is neccessary.
//
  Int_t NewPolygID;
  
  // The ith generator corresponds to the ith Voronoi polygon
  NewPolygID = fGenID;
  
  // Add the polygon at the Winged Edge data structure
  fVorPatch->AddPolyg(NewPolygID);
  fVorPatch->SetPolygID(NewPolygID,NewPolygID); // MAY NOT NEED THIS
  fVorPatch->SetEdgeAroundPolyg(NewPolygID,EdgeID); 
}

Int_t BFLVoronoiMaker::AddNewEdge(Int_t SVtxID, Int_t EVtxID,
                                  Int_t EdgeOfSVtx, Int_t EdgeOfEVtx)
{
// Adds a new edge to the Winged Edge data structure.
// At the time this method is called NOT all of the Voronoi edge params
// are known. This is due to the cyclical nature of the boundary growing
// procedure where this edge's parameters depend on the next/previous
// edges. The "previous" edge of the first one is of course the last one
// ( remember the cyclical nature of the procedure ) so not all the info
// is available until the procedure is over. We prefer not to add all
// of the edges at the end of the procedure due to the amount of the
// temporary variables we would have to keep, which would furher 
// complicate the procedure. So we add what we know when we leave the 
// Voronoi region that this edge belongs to, and leave the missing two
// parameters ( see below ) to be added at the WingedEdgePatch method.
// It returns the ID of the newly added edge to be stored at a TIntList
// that help us keeping track of the boundary growing procedure and
// perform the patches later on.
//
  Int_t EdgeID, NewPolygID;

  EdgeID = fVor->FirstAvailableEdgeID(); // Get the 1st available id
  fVor->DeleteFirstAvailableEdgeID(); // Edge id is not available any more
  
  fVorPatch->AddEdge(EdgeID); // Creates an BFLEdge object at slot #EdgeID
  fVorPatch->SetEdgeID(EdgeID,EdgeID); // MAY NOT NEED THIS
  
  // Set start & end vertices
  fVorPatch->SetStartVtx(EdgeID,SVtxID);
  fVorPatch->SetEndVtx(EdgeID,EVtxID);   

  // Set Left & Right polygons.
  // >> Remember that the boundary growing procedure happens 
  // >> counterclockwisely, so the new polygon is always on the left.
  NewPolygID = fGenID; // the ith gen.--> ith Vor. polygon
  fVorPatch->SetLeftPolyg(EdgeID,NewPolygID);  
  fVorPatch->SetRightPolyg(EdgeID,fCurrentPolygID);

  // Set CcwSuccessor, CwPredecessor.
  //CwSuccessor, CcwPredecessor to be filled after the BGP.
  fVorPatch->SetCcwSuccessor(EdgeID,EdgeOfEVtx);
  fVorPatch->SetCwPredecessor(EdgeID,EdgeOfSVtx);

  return EdgeID;
}

void BFLVoronoiMaker::SubstructureInit(void)
{
// Initialize the process of deleting the substructure produced by 
// the boundary growing procedure.

  fEdgesToDelete->Delete();
  fVerticesToDelete->Delete();
}

void BFLVoronoiMaker::NewStructureInit(void)
{ 
  fNewEdgesTopology->Delete();
  fNewVertices->Delete();
}

void BFLVoronoiMaker::MarkEdgesToDelete(void)
{
  Int_t EdgeID;
  Bool_t IsInside, AlreadyExists;
  TIntList * EdgesAround = new TIntList();

  EdgesAround = fOp->RetrieveEdgesSurrPolygon(fCurrentPolygID);
  
  for(Int_t i = 0; i < EdgesAround->NumberOfElements(); i++){
     EdgeID = EdgesAround->At(i);
     
     if(fOp->EdgeIsInsideNewPolygon(EdgeID)) IsInside = kTRUE;
     else IsInside = kFALSE;
     
     if(fEdgesToDelete->Exists(EdgeID)) AlreadyExists = kTRUE;
     else AlreadyExists = kFALSE;
     
     if(IsInside && !AlreadyExists) fEdgesToDelete->Add(EdgeID);
  }
  
  delete EdgesAround; 
}

void BFLVoronoiMaker::MarkVerticesToDelete(void)
{
// Marks vertices to be deleted other than start/end vertices of edges
// to be deleted, if any. This is important in the case that none of
// the old Voronoi edges resides totally within the new Voronoi region
// and a vtx to be deleted is on an edge to be resized.
// This search is facilitated by the fact that the even elements of 
// the EdgeTopology TIntList ( used at the Voronoi patches ) are 
// resized edges, so we focus on these edges only.

  Int_t SvtxID, EvtxID, vtxID, EdgeID;
  Bool_t AlreadyExists;
  
  for(Int_t i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2){
     EdgeID = fNewEdgesTopology->At(i);
     
     // One of the vertices is inside the new region.
     SvtxID = fVor->GetStartVtx(EdgeID);
     EvtxID = fVor->GetEndVtx(EdgeID);

     // Check which one of them is within the new region.
     if(fOp->VtxIsInsideNewPolyg(EvtxID)) vtxID = EvtxID;
     else vtxID = SvtxID;
     
     // Check if this vertex already exists.
     if(fVerticesToDelete->Exists(vtxID)) AlreadyExists = kTRUE;
     else AlreadyExists = kFALSE;
     
     // ... and if it doesn't, add it.
     if(!AlreadyExists) fVerticesToDelete->Add(vtxID);
  } 
}

void BFLVoronoiMaker::DeleteSubstructure(void)
{
// Deletes any substructure of the Voronoi diagram is left within 
// each new Voronoi region after the boundary growing procedure.
//
  Int_t i = 0, EvtxID, SvtxID, EdgeID, VtxID;
  Bool_t AlreadyDeleted;
  TIntList * DeletedVertices = new TIntList();
  
  //-------------------- delete vertices @ substructure
  
  for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){  
     SvtxID = fVor->GetStartVtx(fEdgesToDelete->At(i));
     EvtxID = fVor->GetEndVtx(fEdgesToDelete->At(i));
     
     if(! DeletedVertices->Exists(SvtxID)) {
         fVor->DeleteVtx(SvtxID);
         fVor->AddAvailableVtxID(SvtxID);
         DeletedVertices->Add(SvtxID);
     }
    
     if(! DeletedVertices->Exists(EvtxID)) {
         fVor->DeleteVtx(EvtxID);
         fVor->AddAvailableVtxID(EvtxID);     
         DeletedVertices->Add(EvtxID);
     }     
  }
  
  //-------------------- delete edges @ substructure

  for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
     EdgeID = fEdgesToDelete->At(i);
     fVor->DeleteEdge(EdgeID);
     fVor->AddAvailableEdgeID(EdgeID);
  }


  //------------------- delete any vertices left on resized edges 
  
  for(i = 0; i < fVerticesToDelete->NumberOfElements(); i++){
     VtxID = fVerticesToDelete->At(i);
     AlreadyDeleted = DeletedVertices->Exists(VtxID);
     if(!AlreadyDeleted) {
         fVor->DeleteVtx(VtxID);
         fVor->AddAvailableVtxID(VtxID);
         DeletedVertices->Add(VtxID);
     }  
  }

  delete DeletedVertices;
}

void BFLVoronoiMaker::Defrag(void)
{
// Eliminate "gaps" in the winged edge data structure.
// --------------- DUMMY IN v_1.0 -------------------

/*Int_t i, last, SvtxID, EvtxID, EdgeID, MaxEdgeID;
  Int_t LeftPolygID, RightPolygID;
  Int_t CwSuccID, CcwSuccID, CwPredID, CcwPredID;
  Int_t VtxID, MaxVtxID;
  BFLEdge * Edge;
  BFLVtx * Vtx;
  TIntList * IncidentEdges = new TIntList();

  // DEFRAG EDGES
  MaxEdgeID = fVor->MaxAvailableEdgeID();

  EdgeID = fVor->FirstAvailableEdgeID();
  while(EdgeID != MaxEdgeID) {
     // Move the last edge of the Winged Edge DS to empty slot: EdgeID
     // and update other objects that refer to this edge.
     last = fVor->GetLastEdgeID();  // get the last edge id
     Edge = fVor->GetEdgeObj(last); // get the object at the last slot
          
     // Update other objects using the transfered edge.
     
     // -------------------- Update edges 
     CwSuccID = fVor->GetCwSuccessor(last);
     if(fVor->GetCcwSuccessor(CwSuccID) == last) {
         fVor->SetCcwSuccessor(CwSuccID,EdgeID);
     } else if(fVor->GetCcwPredecessor(CwSuccID) == last) {
         fVor->SetCcwPredecessor(CwSuccID,EdgeID);
     }

     CcwSuccID = fVor->GetCcwSuccessor(last);
     if(fVor->GetCwSuccessor(CcwSuccID) == last) {
         fVor->SetCwSuccessor(CcwSuccID,EdgeID);
     } else if(fVor->GetCwPredecessor(CcwSuccID) == last) {
         fVor->SetCwPredecessor(CcwSuccID,EdgeID);
     }

     CwPredID = fVor->GetCwPredecessor(last);
     if(fVor->GetCcwSuccessor(CwPredID) == last) {
         fVor->SetCcwSuccessor(CwPredID,EdgeID);
     } else if(fVor->GetCcwPredecessor(CwPredID) == last) {
         fVor->SetCcwPredecessor(CwPredID,EdgeID);
     }

     CcwPredID = fVor->GetCcwPredecessor(last);
     if(fVor->GetCwSuccessor(CcwPredID) == last) {
         fVor->SetCwSuccessor(CcwPredID,EdgeID);
     } else if(fVor->GetCwPredecessor(CcwPredID) == last) {     
         fVor->SetCwPredecessor(CcwPredID,EdgeID);
     }
     
     // -------------------- Update vertices
     SvtxID = fVor->GetStartVtx(last);
     if(fVor->GetEdgeAroundVtx(SvtxID) == last) {
         fVor->SetEdgeAroundVtx(SvtxID,EdgeID);
     }     
     EvtxID = fVor->GetEndVtx(last);
     if(fVor->GetEdgeAroundVtx(EvtxID) == last) {
         fVor->SetEdgeAroundVtx(EvtxID,EdgeID);
     }     
     
     // -------------------- Update polygons
     LeftPolygID = fVor->GetLeftPolyg(last);
     if(fVor->GetEdgeAroundPolyg(LeftPolygID) == last) {
         fVor->SetEdgeAroundPolyg(LeftPolygID,EdgeID);
     }
     RightPolygID = fVor->GetRightPolyg(last);
     if(fVor->GetEdgeAroundPolyg(RightPolygID) == last) {
         fVor->SetEdgeAroundPolyg(RightPolygID,EdgeID);
     }
     
     // Transfer the Edge object
     fVor->SetEdgeObj(Edge,EdgeID); // set the object to EdgeID slot
     fVor->DeleteEdge(last); // delete the object from slot: last
     
     // Get the next available edge
     fVor->DeleteFirstAvailableEdgeID();
     EdgeID = fVor->FirstAvailableEdgeID();     
  }
  
  // DEFRAG VERTICES
  MaxVtxID = fVor->MaxAvailableVtxID();
  
  VtxID = fVor->FirstAvailableVtxID();
  while(VtxID != MaxVtxID){
     // Move the last vtx of the Winged Edge DS to slot VtxID
     // and update other objects that refer to this vertex.
          
     last = fVor->GetLastVtxID();  // get the last vtx id
     Vtx = fVor->GetVtxObj(last); // get the object at the last slot

     // Update other objects using the transfered vertex.

     // -------------------- Update edges
     IncidentEdges = fOp->RetrieveEdgesIncidentToVtx(last);
     for(i = 0; i < IncidentEdges->NumberOfElements(); i++){
         EdgeID = IncidentEdges->At(i);
         if(fVor->GetStartVtx(EdgeID) == last){
              fVor->SetStartVtx(EdgeID,VtxID);
         } else if(fVor->GetEndVtx(EdgeID) == last) {
              fVor->SetEndVtx(EdgeID,VtxID);
         }
     }
     
     // Transfer the Vtx object
     fVor->SetVtxObj(Vtx,VtxID); // set the object to EdgeID slot
     fVor->DeleteVtx(last); // delete the object from slot: last

     // Get the next available vertex
     fVor->DeleteFirstAvailableVtxID();
     VtxID = fVor->FirstAvailableVtxID();     
  }
  
  // Explicitly free some allocated memory  
  delete IncidentEdges;
  delete Edge;
  delete Vtx;  */  
}

---