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 BFLVorOperator *	GetVoronoiOperator (void)
Private Attributes
Int_t	fCurrentPolygID
Int_t	fGenID
Long_t	fN
BFLWingedEdge *	fVor
BFLWingedEdge *	fVorPatch
BFLVorOperator *	fOp
TObjArray *	fGenerators
TIntList *	fRandomToSorted
TIntList *	fSortedToRandom
TIntList *	fEdgesToDelete
TIntList *	fVerticesToDelete
TIntList *	fNewEdgesTopology
TIntList *	fNewVertices
Bool_t	debug
Bool_t	debug2
TObjArray *	fBField

---

Constructor & Destructor Documentation

BFLVoronoiMaker::BFLVoronoiMaker (  BFLWingedEdge *  voronoi  )

Definition at line 34 of file BFLVoronoiMaker.cxx. { // 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 (   )

Definition at line 53 of file BFLVoronoiMaker.cxx. { delete fRandomToSorted; delete fSortedToRandom; delete fNewEdgesTopology; delete fNewVertices; }

---

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(). { // 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); }

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, BFLWingedEdge::FirstAvailableEdgeID(), fVor, fVorPatch, BFLWingedEdge::SetCcwSuccessor(), BFLWingedEdge::SetCwPredecessor(), BFLWingedEdge::SetEdgeID(), BFLWingedEdge::SetEndVtx(), BFLWingedEdge::SetLeftPolyg(), BFLWingedEdge::SetRightPolyg(), and BFLWingedEdge::SetStartVtx(). Referenced by Make(). { // 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::AddNewPolyg (  Int_t  EdgeID  )  [private]

Definition at line 614 of file BFLVoronoiMaker.cxx. References BFLWingedEdge::AddPolyg(), fVorPatch, BFLWingedEdge::SetEdgeAroundPolyg(), and BFLWingedEdge::SetPolygID(). Referenced by Make(). { // 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::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(). { // 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::Defrag (  void   )  [private]

Definition at line 807 of file BFLVoronoiMaker.cxx. { // 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; */ }

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(). { // 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; }

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(). { // 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; }

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

Definition at line 74 of file BFLVoronoiMaker.h. { return fOp; }

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

Definition at line 355 of file BFLVoronoiMaker.cxx. References fGenID, fN, RandomToSorted(), and SortedToRandom(). { // 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::IncreaseEntropy (  void   )  [private]

Definition at line 62 of file BFLVoronoiMaker.cxx. References TIntList::Add(), TIntList::AddAt(), fGenerators, fN, fRandomToSorted, and fSortedToRandom. Referenced by Make(). { // 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::Make (  void   )

Definition at line 228 of file BFLVoronoiMaker.cxx. References TIntList::Add(), AddDistantGenerators(), AddNewEdge(), AddNewPolyg(), AddNewVtx(), 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(). { // 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; }

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(). { 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   )  [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(). { // 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::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(). { // 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; }

void BFLVoronoiMaker::NewStructureInit (  void   )  [private]

Definition at line 689 of file BFLVoronoiMaker.cxx. References TIntList::Delete(), fNewEdgesTopology, and fNewVertices. Referenced by Make(). { fNewEdgesTopology->Delete(); fNewVertices->Delete(); }

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(). { return 3+fRandomToSorted->At(SlotAtRandom); }

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(). { // 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); } } }

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(). { return 3+fSortedToRandom->At(SlotAtSorted); }

void BFLVoronoiMaker::SubstructureInit (  void   )  [private]

Definition at line 679 of file BFLVoronoiMaker.cxx. References TIntList::Delete(), fEdgesToDelete, and fVerticesToDelete. Referenced by Make(). { // Initialize the process of deleting the substructure produced by // the boundary growing procedure. fEdgesToDelete->Delete(); fVerticesToDelete->Delete(); }

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(). { 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(); }

---

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.

Int_t BFLVoronoiMaker::fCurrentPolygID [private]

Definition at line 76 of file BFLVoronoiMaker.h. Referenced by AddNewEdge(), Make(), and MarkEdgesToDelete().

TIntList* BFLVoronoiMaker::fEdgesToDelete [private]

Definition at line 85 of file BFLVoronoiMaker.h. Referenced by DeleteSubstructure(), GetAnotherEdgeAround(), MarkEdgesToDelete(), RemoveRefsToDeletedEdges(), and SubstructureInit().

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 GuessNearestNeighbour(), and Make().

Long_t BFLVoronoiMaker::fN [private]

Definition at line 78 of file BFLVoronoiMaker.h. Referenced by GuessNearestNeighbour(), IncreaseEntropy(), and Make().

TIntList* BFLVoronoiMaker::fNewEdgesTopology [private]

Definition at line 87 of file BFLVoronoiMaker.h. Referenced by Make(), MarkVerticesToDelete(), NewStructureInit(), and WingedEdgePatch().

TIntList* BFLVoronoiMaker::fNewVertices [private]

Definition at line 88 of file BFLVoronoiMaker.h. Referenced by Make(), NewStructureInit(), and WingedEdgePatch().

BFLVorOperator* BFLVoronoiMaker::fOp [private]

Definition at line 81 of file BFLVoronoiMaker.h. Referenced by GetAnotherEdgeAround(), Make(), MarkEdgesToDelete(), MarkVerticesToDelete(), and WingedEdgePatch().

TIntList* BFLVoronoiMaker::fRandomToSorted [private]

Definition at line 83 of file BFLVoronoiMaker.h. Referenced by IncreaseEntropy(), and RandomToSorted().

TIntList* BFLVoronoiMaker::fSortedToRandom [private]

Definition at line 84 of file BFLVoronoiMaker.h. Referenced by IncreaseEntropy(), and SortedToRandom().

TIntList* BFLVoronoiMaker::fVerticesToDelete [private]

Definition at line 86 of file BFLVoronoiMaker.h. Referenced by DeleteSubstructure(), MarkVerticesToDelete(), and SubstructureInit().

BFLWingedEdge* BFLVoronoiMaker::fVor [private]

Definition at line 79 of file BFLVoronoiMaker.h. Referenced by AddDistantGenerators(), AddNewEdge(), AddNewVtx(), DeleteSubstructure(), MarkVerticesToDelete(), MergeDataStructures(), RemoveRefsToDeletedEdges(), and WingedEdgePatch().

BFLWingedEdge* BFLVoronoiMaker::fVorPatch [private]

Definition at line 80 of file BFLVoronoiMaker.h. Referenced by AddNewEdge(), AddNewPolyg(), AddNewVtx(), Make(), MergeDataStructures(), and WingedEdgePatch().

---

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

• BFLVoronoiMaker.h
• BFLVoronoiMaker.cxx

---