BFLVorOperator Class Reference

#include <BFLVorOperator.h>

List of all members.

Public Member Functions

 BFLVorOperator ()
 BFLVorOperator (BFLWingedEdge *vor)
 ~BFLVorOperator ()
TIntListRetrieveEdgesIncidentToVtx (Int_t vtx) const
TIntListRetrievePolygonsIncidentToVtx (Int_t vtx) const
TIntListRetrieveEdgesSurrPolygon (Int_t poly) const
TIntListRetrieveVtxSurrPolygon (Int_t poly) const
Int_t IsInTheCircle (TObjArray *CirclePoints, BFLNode *point) const
BFLNode VtxPosition (TObjArray *PointsOnCircle) const
BFLNode FindNewVtx (Int_t EdgeID) const
Int_t FindCurrentPolygon (Int_t GuessedID=-1) const
Int_t MoveToNextPolygon (Int_t PolygID, Int_t EdgeID) const
Bool_t EdgeHasNewVtx (Int_t EdgeID) const
Bool_t EdgeIsInsideNewPolygon (Int_t EdgeID) const
Bool_t VtxIsInsideNewPolyg (Int_t VtxID) const
void ResetVtxCache (void)
Float_t GeneratorsDist (Int_t igen, Int_t jgen) const
Float_t DistanceFrom (Int_t igen) const
Int_t GetFirstIntersectEdge (void) const
Int_t GetNextIntersectEdge (Int_t PrEdgeID) const
Int_t Clockwise (BFLNode *nA, BFLNode *nB, BFLNode *nC) const
virtual void SetCurrentPolygID (Int_t pid)
virtual Int_t GetCurrentPolygID (void) const
virtual void SetCurrentGen (BFLNode *gen)
virtual BFLNodeGetCurrentGen (void) const

Private Attributes

Int_t fCurrentPolygID
BFLNodefCurrentGen
TObjArray * fGenerators
BFLWingedEdgefVor
TIntListfInVtxCache
TIntListfOutVtxCache

Detailed Description

Definition at line 26 of file BFLVorOperator.h.


Constructor & Destructor Documentation

BFLVorOperator::BFLVorOperator (  )  [inline]

Definition at line 30 of file BFLVorOperator.h.

00030 { }

BFLVorOperator::BFLVorOperator ( BFLWingedEdge vor  ) 

Definition at line 31 of file BFLVorOperator.cxx.

00032 {
00033 // Allocate some memory for this instance variables
00034   fVor = (BFLWingedEdge *) voronoi;
00035   fInVtxCache = new TIntList();
00036   fOutVtxCache = new TIntList(); 
00037 }

BFLVorOperator::~BFLVorOperator (  ) 

Definition at line 40 of file BFLVorOperator.cxx.

References fInVtxCache, and fOutVtxCache.

00041 {
00042   delete fInVtxCache;
00043   delete fOutVtxCache;
00044 }


Member Function Documentation

Int_t BFLVorOperator::Clockwise ( BFLNode nA,
BFLNode nB,
BFLNode nC 
) const

Definition at line 197 of file BFLVorOperator.cxx.

References BFLNode::GetX(), and BFLNode::GetY().

Referenced by GetFirstIntersectEdge(), BFLInterpolation::IsInsideANSYSCell(), and BFLInterpolation::NNInterpolation().

00199 {
00200 // Returns 1 if going from node nA -> nB -> nC is clockwise
00201 // and -1 if its counterclockwise.
00202 // Special cases : 
00203 //  1 if nB between nA,nC 
00204 // -1 if nA between nB,nC
00205 //  0 if nC between nA,nB
00206 // --------- Adapted from "Algorithms", R.Hedgewick
00207 
00208   Int_t cwise;
00209   Float_t dxa, dya, dxb, dyb; 
00210 
00211   dxa = ( nB->GetX() ) - ( nA->GetX() );
00212   dxb = ( nC->GetX() ) - ( nA->GetX() );
00213   dya = ( nB->GetY() ) - ( nA->GetY() );
00214   dyb = ( nC->GetY() ) - ( nA->GetY() );
00215 
00216   if (dxa*dyb > dya*dxb) cwise = -1; 
00217   else if (dxa*dyb < dya*dxb) cwise = 1; 
00218   else { /* dxa*dyb == dya*dxb */
00219     if (dxa*dxb < 0 || dya*dyb < 0 ) cwise = -1;
00220         else if (dxa*dxa + dya*dya >= dxb*dxb + dyb*dyb) cwise = 0; 
00221         else cwise = 1;
00222   } 
00223   
00224   return cwise;
00225 }

Float_t BFLVorOperator::DistanceFrom ( Int_t  igen  )  const

Definition at line 538 of file BFLVorOperator.cxx.

References fCurrentGen, fVor, BFLWingedEdge::GetGeneratorX(), BFLWingedEdge::GetGeneratorY(), BFLNode::GetX(), and BFLNode::GetY().

Referenced by FindCurrentPolygon().

00539 {
00540 // Returns the distance between the ith and jth generators.
00541 // 
00542 
00543    Float_t x = fVor->GetGeneratorX(igen) - fCurrentGen->GetX();
00544    Float_t y = fVor->GetGeneratorY(igen) - fCurrentGen->GetY();
00545   return TMath::Sqrt(
00546 //       TMath::Power(fVor->GetGeneratorX(igen)- fCurrentGen->GetX(),2) +
00547 //       TMath::Power(fVor->GetGeneratorY(igen)- fCurrentGen->GetY(),2) );  
00548      x*x + y*y);
00549 }

Bool_t BFLVorOperator::EdgeHasNewVtx ( Int_t  EdgeID  )  const

Definition at line 257 of file BFLVorOperator.cxx.

References fVor, BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetStartVtx(), and VtxIsInsideNewPolyg().

Referenced by GetFirstIntersectEdge(), and GetNextIntersectEdge().

00258 {
00259 // Returns TRUE if the edge: EdgeID has a vtx of the region to be
00260 // assigned to the new generator: igen (and hence has to be resized).
00261 // It happens when one of the vertices in within the new region 
00262 // while the other is outside.
00263 //
00264   Int_t SVtxID, EVtxID;
00265   Bool_t SVtxIsInside, EVtxIsInside, HasNewVtx;
00266 
00267   // Get start/end vertex IDs of the edge.
00268   SVtxID = fVor->GetStartVtx(EdgeID);
00269   EVtxID = fVor->GetEndVtx(EdgeID);
00270 
00271   // Check whether the above vertices are within the region
00272   // to be assigned to generator : igen. 
00273   SVtxIsInside = VtxIsInsideNewPolyg(SVtxID); 
00274   EVtxIsInside = VtxIsInsideNewPolyg(EVtxID);  
00275    
00276   // Decide whether edge: EdgeID is to be resized.
00277   if((SVtxIsInside && !EVtxIsInside)||(!SVtxIsInside && EVtxIsInside)){
00278      HasNewVtx = kTRUE;
00279   } else {
00280      HasNewVtx = kFALSE;
00281   }
00282   
00283   return HasNewVtx;
00284 }

Bool_t BFLVorOperator::EdgeIsInsideNewPolygon ( Int_t  EdgeID  )  const

Definition at line 287 of file BFLVorOperator.cxx.

References fVor, BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetStartVtx(), and VtxIsInsideNewPolyg().

Referenced by BFLVoronoiMaker::MarkEdgesToDelete().

00288 {
00289 // Returns TRUE if the edge: EdgeID has both of its vertices within
00290 // the region to be assigned to the new generator: igen ( and hence
00291 // belongs to the substructure to be deleted ).
00292 //
00293   Int_t SVtxID, EVtxID;
00294   Bool_t SVtxIsInside, EVtxIsInside, IsInside;
00295   
00296   // Get start/end vertex IDs of the edge.
00297   SVtxID = fVor->GetStartVtx(EdgeID);
00298   EVtxID = fVor->GetEndVtx(EdgeID);
00299   
00300   // Check whether the above vertices are within the region
00301   // to be assigned to generator : igen.
00302   SVtxIsInside = VtxIsInsideNewPolyg(SVtxID);
00303   EVtxIsInside = VtxIsInsideNewPolyg(EVtxID);  
00304     
00305   // Decide whether edge: EdgeID belongs to the substructure
00306   // to be deleted.
00307   if(SVtxIsInside && EVtxIsInside) IsInside = kTRUE;
00308   else IsInside = kFALSE;
00309   
00310   return IsInside;
00311 }

Int_t BFLVorOperator::FindCurrentPolygon ( Int_t  GuessedID = -1  )  const

Definition at line 569 of file BFLVorOperator.cxx.

References DistanceFrom(), fVor, BFLWingedEdge::GeneratorToPolygon(), MoveToNextPolygon(), BFLWingedEdge::PolygonToGenerator(), and RetrieveEdgesSurrPolygon().

Referenced by BFLInterpolation::BilinearInterpolation(), BFLInterpolation::CNInterpolation(), BFLInterpolation::FormVoronoiCell(), BFLVoronoiMaker::Make(), and BFLInterpolation::PlanarInterpolation().

00570 {
00571 // Returns the Voronoi polygon that contains the added generator.
00572 // In a straightforward implementation the computational complexitity
00573 // is ~ N, but within a ~ N loop it gives a computational complexity
00574 // of ~ N**2. This is what we want to avoid since N ~ 100k.
00575 // 
00576 // igenerator is the id of the added generator 
00577         
00578   Int_t i, NearestGenID, Nedges, AdjacentPolygonID;
00579   Int_t PolygID, EdgeID, AdjGen;
00580   Bool_t IsNearest;
00581   Float_t Dist, DistMin;
00582   TIntList * SurroundingEdges;
00583 
00584   // Get a guess of the nearest generator (if any). 
00585   if(GuessedPolygID != -1 ) NearestGenID = GuessedPolygID;
00586   else NearestGenID = 1;
00587 
00588   // Distance between current and "nearest" generators.
00589   DistMin = DistanceFrom(NearestGenID);
00590   
00591   // Look for a closer generator than our guess. 
00592   do {  
00593     IsNearest = kTRUE;
00594 
00595     // Voronoi polygon corresponding to "nearest" generator.    
00596     PolygID = fVor->GeneratorToPolygon(NearestGenID);
00597 
00598     // Get the edges surrounding the polygon that belongs to the
00599     // closest generator.    
00600     //cout << "...surrounding edges" << endl;
00601     SurroundingEdges = RetrieveEdgesSurrPolygon(PolygID);
00602    
00603     // Loop over surrounding edges.    
00604     //cout << "... loop over surrounding edges" << endl;
00605     Nedges = SurroundingEdges -> NumberOfElements();
00606     for(i=0; i<Nedges; i++) {
00607 
00608        // Get the edge and the adjacent polygon (other than PolygID).
00609        EdgeID = SurroundingEdges -> At(i); 
00610        AdjacentPolygonID = MoveToNextPolygon(PolygID,EdgeID); 
00611     
00612        if(AdjacentPolygonID !=0 ) {
00613            // Get the generator of the adjacent polygon
00614            // and its coordinates.
00615            AdjGen = fVor->PolygonToGenerator(AdjacentPolygonID);
00616 
00617            // Distance between the current and adjacent polygon's 
00618            // generators.
00619            //cout << "Adjacent Gen = " << AdjGen << endl;
00620            Dist = DistanceFrom(AdjGen);
00621            
00622            // Decide if this is a closer generator.
00623            if ( Dist < DistMin - 0.0001) {
00624                 DistMin = Dist;
00625                 NearestGenID = AdjGen;
00626                 IsNearest = kFALSE;
00627            }       
00628        } // if polygid != 0       
00629     } // from loop over edges
00630     
00631     // Explicitly free some allocated memory
00632     delete SurroundingEdges;
00633    
00634   } while(!IsNearest);
00635   
00636   return fVor->GeneratorToPolygon(NearestGenID);
00637 }

BFLNode BFLVorOperator::FindNewVtx ( Int_t  EdgeID  )  const

Definition at line 478 of file BFLVorOperator.cxx.

References fCurrentGen, fVor, BFLWingedEdge::GeneratorToPolygon(), BFLWingedEdge::GetGeneratorX(), BFLWingedEdge::GetGeneratorY(), BFLWingedEdge::GetLeftPolyg(), BFLWingedEdge::GetRightPolyg(), BFLNode::GetX(), BFLNode::GetY(), and VtxPosition().

Referenced by BFLInterpolation::FormVoronoiCell(), GetFirstIntersectEdge(), and BFLVoronoiMaker::Make().

00479 {
00480 // This method returns the new vertex coordinate on the edge: EdgeID.
00481 // It defines the circle that passes through the generators of the
00482 // left and right polygons ( with respect to EdgeID ) and the newly
00483 // added generator, and then calls the VtxPosition method.
00484 //  
00485   Int_t LeftPolygID, RightPolygID;
00486   Int_t LeftPolygGenID, RightPolygGenID;
00487   Float_t x,y;
00488   BFLNode vtx;
00489   TObjArray * PointsOnCircle = new TObjArray(3); 
00490 
00491   // Get the left and right polygon of the edge: EdgeID   
00492   LeftPolygID = fVor->GetLeftPolyg(EdgeID);
00493   RightPolygID = fVor->GetRightPolyg(EdgeID);
00494   
00495   // Get the IDs of the left and right polygon's generators
00496   LeftPolygGenID = fVor->GeneratorToPolygon(LeftPolygID);
00497   RightPolygGenID = fVor->GeneratorToPolygon(RightPolygID);
00498   
00499   // The above generators + the current generator define a circle
00500   // whose center is the new vertex on edge: EdgeID
00501   x = fVor->GetGeneratorX(LeftPolygGenID);
00502   y = fVor->GetGeneratorY(LeftPolygGenID);
00503   PointsOnCircle->Add(new BFLNode(x,y));
00504 
00505   x = fVor->GetGeneratorX(RightPolygGenID);
00506   y = fVor->GetGeneratorY(RightPolygGenID);
00507   PointsOnCircle->Add(new BFLNode(x,y));
00508 
00509   x = fCurrentGen->GetX();
00510   y = fCurrentGen->GetY();
00511   PointsOnCircle->Add(new BFLNode(x,y)); 
00512 
00513   vtx = VtxPosition(PointsOnCircle); // get the circle's center
00514 
00515   // Explicitly free some allocated memory
00516   PointsOnCircle->Delete(); 
00517   delete PointsOnCircle; 
00518     
00519   return vtx;
00520 }

Float_t BFLVorOperator::GeneratorsDist ( Int_t  igen,
Int_t  jgen 
) const

Definition at line 523 of file BFLVorOperator.cxx.

References fVor, BFLWingedEdge::GetGeneratorX(), and BFLWingedEdge::GetGeneratorY().

00524 {
00525 // Returns the distance between the ith and jth generators.
00526 
00527    Float_t x = fVor->GetGeneratorX(igen) - fVor->GetGeneratorX(jgen);
00528    Float_t y = fVor->GetGeneratorY(igen) - fVor->GetGeneratorY(jgen);
00529   return TMath::Sqrt(
00530 //         TMath::Power(fVor->GetGeneratorX(igen)- 
00531 //                      fVor->GetGeneratorX(jgen),2) +
00532 //         TMath::Power(fVor->GetGeneratorY(igen)- 
00533 //                      fVor->GetGeneratorY(jgen),2) );  
00534      x*x + y*y);
00535 }

virtual BFLNode* BFLVorOperator::GetCurrentGen ( void   )  const [inline, virtual]

Definition at line 58 of file BFLVorOperator.h.

References fCurrentGen.

00058 { return fCurrentGen; }

virtual Int_t BFLVorOperator::GetCurrentPolygID ( void   )  const [inline, virtual]

Definition at line 55 of file BFLVorOperator.h.

References fCurrentPolygID.

00055 { return fCurrentPolygID; }

Int_t BFLVorOperator::GetFirstIntersectEdge ( void   )  const

Definition at line 152 of file BFLVorOperator.cxx.

References TIntList::Add(), TIntList::At(), Clockwise(), EdgeHasNewVtx(), fCurrentGen, fCurrentPolygID, FindNewVtx(), TIntList::NumberOfElements(), and RetrieveEdgesSurrPolygon().

Referenced by BFLInterpolation::FormVoronoiCell(), and BFLVoronoiMaker::Make().

00153 {
00154 // Returns the first edge of the polygon: fCurrentPolygID that intersects
00155 // the new Voronoi edge in this polygon. It initiates the boundary 
00156 // growing procedure and is also used to terminate it ( when we return
00157 // back to the edge we had begun from ).
00158 //
00159   Int_t FirstIntersectEdgeID = 0;
00160   TIntList * IntersectEdges = new TIntList();
00161 
00162   // Get a list of current polygon's edges 
00163   TIntList * PolyEdgeIDs = RetrieveEdgesSurrPolygon(fCurrentPolygID);  
00164 
00165   // Select the (2) edges that intersect with the new Voronoi edge 
00166   // at this region. 
00167   for(Int_t i=0; i<PolyEdgeIDs->NumberOfElements(); i++){
00168     Int_t iedge = PolyEdgeIDs->At(i); 
00169     if(EdgeHasNewVtx(iedge)) IntersectEdges->Add(iedge);
00170   }
00171   // check possible fealure (there MUST be 2 intersections)
00172   if(IntersectEdges->NumberOfElements() != 2) {
00173      delete PolyEdgeIDs;
00174      delete IntersectEdges;
00175      return -1;
00176   }
00177  
00178   // Select the intersect edge that will allow the boundary growing
00179   // procedure to be performed counterclockwisely with respect to  
00180   // the newly added generator.
00181 
00182   BFLNode VtxOnFirstEdge = FindNewVtx(IntersectEdges->At(0));
00183   BFLNode VtxOnSecondEdge = FindNewVtx(IntersectEdges->At(1));  
00184 
00185   if(Clockwise(fCurrentGen,&VtxOnFirstEdge,&VtxOnSecondEdge) == -1) {
00186      FirstIntersectEdgeID = IntersectEdges->At(0);
00187   } else FirstIntersectEdgeID = IntersectEdges->At(1);
00188                                              
00189   // Explicitly free some allocated memory.  
00190   delete PolyEdgeIDs;
00191   delete IntersectEdges;
00192   
00193   return FirstIntersectEdgeID;
00194 }

Int_t BFLVorOperator::GetNextIntersectEdge ( Int_t  PrEdgeID  )  const

Definition at line 228 of file BFLVorOperator.cxx.

References TIntList::At(), EdgeHasNewVtx(), fCurrentPolygID, TIntList::NumberOfElements(), TIntList::Remove(), and RetrieveEdgesSurrPolygon().

Referenced by BFLInterpolation::FormVoronoiCell(), and BFLVoronoiMaker::Make().

00229 {
00230 // Returns the edge ( other than edge: PrEdgeID) that intersects with 
00231 // the new Voronoi edge on the polygon: fCurrentPolygID. The boundary
00232 // growing procedure is based on successive calls of this methods
00233 // until we return to the edge we had begun from ( and hence the new
00234 // - closed - Voronoi region is formed ).
00235 //
00236   Int_t NextEdgeID = 0, iedge;
00237   TIntList * PolyEdgeIDs;
00238 
00239   // Get a list of current polygon's edges
00240   PolyEdgeIDs = RetrieveEdgesSurrPolygon(fCurrentPolygID);  
00241 
00242   // Remove the previous intersect edge from the list   
00243   PolyEdgeIDs->Remove(PrEdgeID);
00244 
00245   // Get the intersect edge ( other than PrEdgeID ).
00246   for(Int_t i = 0; i < PolyEdgeIDs->NumberOfElements(); i++){
00247     iedge = PolyEdgeIDs->At(i);
00248     if(EdgeHasNewVtx(iedge)) NextEdgeID = iedge;
00249   }
00250 
00251   delete PolyEdgeIDs;
00252 
00253   return NextEdgeID;
00254 }

Int_t BFLVorOperator::IsInTheCircle ( TObjArray *  CirclePoints,
BFLNode point 
) const

Definition at line 375 of file BFLVorOperator.cxx.

References det, BFLNode::GetX(), and BFLNode::GetY().

Referenced by VtxIsInsideNewPolyg().

00377 { 
00378 // Checks the position of a point relative to the circle defined
00379 // by the 3 points in the PointOnCircle container.
00380 // It checks the determinant :
00381 //
00382 //             | 1   x1   y1   x1**2+y1**2 |
00383 //             | 1   x2   y2   x2**2+y2**2 |
00384 //        H =  | 1   x3   y3   x3**2+y3**2 |
00385 //             | 1   x    y    x**2+y**2   |
00386 //
00387 // and returns:   1 if the point is within the circle
00388 //                0 if the point is on the circle
00389 //               -1 if the point is outside the circle.
00390 //
00391 // CAUTION: points (x1,y1), (x2,y2), (x3,y3) are placed in the xy 
00392 // plane counterclockwisely ( when view from above this plane ).
00393 //
00394   Int_t irow, InCircle;  
00395   Double_t det;
00396   BFLNode * PointOnCircle;
00397   
00398   TMatrix H = TMatrix(4,4);  
00399 
00400   // fill 1st column with 1's
00401   for(irow=0; irow<H.GetNrows(); irow++)  H(irow,0) = 1;
00402   
00403   TIter next(PointsOnCircle);
00404   irow = 0;
00405   while( (PointOnCircle = (BFLNode *)next())) {
00406      H(irow,1) = PointOnCircle->GetX();
00407      H(irow,2) = PointOnCircle->GetY();
00408 //     H(irow,3) = TMath::Power(PointOnCircle->GetX(),2)+
00409 //                         TMath::Power(PointOnCircle->GetY(),2);
00410      H(irow,3) = PointOnCircle->GetX()*PointOnCircle->GetX() +
00411                  PointOnCircle->GetY()*PointOnCircle->GetY();
00412      irow++;                         
00413   }
00414   
00415   // Fill the last row with point's distance from the origin
00416   H(3,1) = point->GetX();
00417   H(3,2) = point->GetY();
00418 //  H(3,3) = TMath::Power(point->GetX(),2)+
00419 //               TMath::Power(point->GetY(),2);
00420   H(3,3) = point->GetX()*point->GetX() + point->GetY()*point->GetY();
00421                        
00422   // Calculate the determinant(H)
00423   det = H.Determinant();                    
00424  
00425   if      (det == 0)  InCircle =  0;  // The point is on the circle
00426   else if (det  > 0)  InCircle = -1;  // The point is outside the circle
00427   else                InCircle =  1;  // The point is inside the circle
00428   
00429   // Explicitly free some allocated memory  
00430   delete PointOnCircle;
00431 
00432   return InCircle;
00433 }

Int_t BFLVorOperator::MoveToNextPolygon ( Int_t  PolygID,
Int_t  EdgeID 
) const

Definition at line 552 of file BFLVorOperator.cxx.

References fVor, BFLWingedEdge::GetLeftPolyg(), and BFLWingedEdge::GetRightPolyg().

Referenced by FindCurrentPolygon(), BFLInterpolation::FormVoronoiCell(), and BFLVoronoiMaker::Make().

00553 {
00554 // Returns the polygon that shares the Voronoi Edge: EdgeID  other 
00555 // than the Voronoi Polygon: PolygID.
00556 
00557   Int_t LeftPolygID, RightPolygID, NextPolygID;
00558   
00559   LeftPolygID = fVor->GetLeftPolyg(EdgeID);
00560   RightPolygID = fVor->GetRightPolyg(EdgeID);
00561 
00562   if(LeftPolygID != PolygID) NextPolygID = LeftPolygID;
00563   else NextPolygID = RightPolygID;
00564 
00565   return NextPolygID;
00566 }

void BFLVorOperator::ResetVtxCache ( void   ) 

Definition at line 314 of file BFLVorOperator.cxx.

References TIntList::Delete(), fInVtxCache, and fOutVtxCache.

Referenced by BFLVoronoiMaker::Make(), and BFLInterpolation::NNInterpolation().

00315 { 
00316   fInVtxCache->Delete();
00317   fOutVtxCache->Delete();
00318 }

TIntList * BFLVorOperator::RetrieveEdgesIncidentToVtx ( Int_t  vtx  )  const

Definition at line 47 of file BFLVorOperator.cxx.

References TIntList::AddLast(), fVor, BFLWingedEdge::GetCcwPredecessor(), BFLWingedEdge::GetCcwSuccessor(), BFLWingedEdge::GetEdgeAroundVtx(), and BFLWingedEdge::GetStartVtx().

00048 {
00049 // Input  : vertex id
00050 // Output : a pointer to a TList that contains the edges incident
00051 //          to the vertex ( in counterclockwise order )
00052 //
00053   Int_t k, kstart;
00054   TIntList * IncidentEdges = new TIntList();
00055 
00056   k = fVor->GetEdgeAroundVtx(vtx);
00057   kstart = k;
00058 
00059   do {
00060 
00061     IncidentEdges->AddLast(k);
00062     if( vtx == fVor->GetStartVtx(k) ) {
00063            k = fVor->GetCcwPredecessor(k);
00064         } else {
00065            k = fVor->GetCcwSuccessor(k);
00066         }
00067 
00068   } while ( k != kstart );
00069 
00070   return IncidentEdges;
00071 }

TIntList * BFLVorOperator::RetrieveEdgesSurrPolygon ( Int_t  poly  )  const

Definition at line 103 of file BFLVorOperator.cxx.

References TIntList::AddLast(), fVor, BFLWingedEdge::GetCwPredecessor(), BFLWingedEdge::GetCwSuccessor(), BFLWingedEdge::GetEdgeAroundPolyg(), and BFLWingedEdge::GetLeftPolyg().

Referenced by FindCurrentPolygon(), BFLVoronoiMaker::GetAnotherEdgeAround(), GetFirstIntersectEdge(), GetNextIntersectEdge(), BFLVoronoiMaker::MarkEdgesToDelete(), and BFLInterpolation::PlanarInterpolation().

00104 {
00105   Int_t k, kstart;
00106   TIntList * SurroundingEdges = new TIntList();
00107 
00108   k = fVor->GetEdgeAroundPolyg(poly);
00109   kstart = k;
00110 
00111   do {
00112 
00113     SurroundingEdges->AddLast(k);
00114 
00115     if(poly == fVor->GetLeftPolyg(k)){
00116        k = fVor->GetCwSuccessor(k);
00117      } else {
00118        k = fVor->GetCwPredecessor(k);
00119      } 
00120   } while( k!=kstart );
00121 
00122   return SurroundingEdges;
00123 }

TIntList * BFLVorOperator::RetrievePolygonsIncidentToVtx ( Int_t  vtx  )  const

Definition at line 74 of file BFLVorOperator.cxx.

References fVor, BFLWingedEdge::GetCcwPredecessor(), BFLWingedEdge::GetCcwSuccessor(), BFLWingedEdge::GetEdgeAroundVtx(), BFLWingedEdge::GetLeftPolyg(), BFLWingedEdge::GetRightPolyg(), and BFLWingedEdge::GetStartVtx().

Referenced by VtxIsInsideNewPolyg().

00075 {
00076 // Input  : vertex id
00077 // Output : a pointer to a TList that contains the polygons
00078 //          incident to the vertex ( in counterclockwise order )
00079 //
00080   Int_t k, kstart, poly;
00081   TIntList * IncidentPolygons = new TIntList();
00082 
00083   k = fVor->GetEdgeAroundVtx(vtx);  
00084   kstart = k;
00085 
00086   do {
00087 
00088     if( vtx == fVor->GetStartVtx(k) ) {
00089            poly = fVor->GetLeftPolyg(k);
00090            k = fVor->GetCcwPredecessor(k);
00091     } else {
00092            poly = fVor->GetRightPolyg(k);
00093            k = fVor->GetCcwSuccessor(k);
00094     }
00095     IncidentPolygons -> AddLast(poly);
00096 
00097   } while( k != kstart);
00098 
00099   return IncidentPolygons;
00100 }

TIntList * BFLVorOperator::RetrieveVtxSurrPolygon ( Int_t  poly  )  const

Definition at line 127 of file BFLVorOperator.cxx.

References TIntList::AddLast(), fVor, BFLWingedEdge::GetCwPredecessor(), BFLWingedEdge::GetCwSuccessor(), BFLWingedEdge::GetEdgeAroundPolyg(), BFLWingedEdge::GetEndVtx(), BFLWingedEdge::GetLeftPolyg(), and BFLWingedEdge::GetStartVtx().

Referenced by BFLInterpolation::NNInterpolation().

00128 {
00129   Int_t k, kstart;
00130   TIntList * SurrVertices = new TIntList();
00131 
00132   k = fVor->GetEdgeAroundPolyg(poly);
00133   kstart = k;
00134 
00135   do {
00136 
00137     if(poly == fVor->GetLeftPolyg(k)){
00138        SurrVertices->AddLast(fVor->GetEndVtx(k));
00139        k = fVor->GetCwSuccessor(k);
00140     } else {
00141        SurrVertices->AddLast(fVor->GetStartVtx(k));
00142        k = fVor->GetCwPredecessor(k);   
00143     }
00144 
00145   } while( k!=kstart );
00146 
00147   return SurrVertices;
00148 }

virtual void BFLVorOperator::SetCurrentGen ( BFLNode gen  )  [inline, virtual]
virtual void BFLVorOperator::SetCurrentPolygID ( Int_t  pid  )  [inline, virtual]

Definition at line 54 of file BFLVorOperator.h.

References fCurrentPolygID.

Referenced by BFLInterpolation::FormVoronoiCell(), and BFLVoronoiMaker::Make().

00054 { fCurrentPolygID = pid; }

Bool_t BFLVorOperator::VtxIsInsideNewPolyg ( Int_t  VtxID  )  const

Definition at line 321 of file BFLVorOperator.cxx.

References TIntList::AddLast(), TIntList::At(), TIntList::Delete(), TIntList::Exists(), fCurrentGen, fInVtxCache, fOutVtxCache, fVor, BFLWingedEdge::GetGeneratorX(), BFLWingedEdge::GetGeneratorY(), BFLWingedEdge::GetWeight(), IsInTheCircle(), TIntList::NumberOfElements(), BFLWingedEdge::PolygonToGenerator(), and RetrievePolygonsIncidentToVtx().

Referenced by EdgeHasNewVtx(), EdgeIsInsideNewPolygon(), BFLVoronoiMaker::MarkVerticesToDelete(), and BFLVoronoiMaker::WingedEdgePatch().

00322 {
00323 // Returns TRUE if the vertex : VtxID is inside the Voronoi
00324 // region that will be assigned to the new generator : igen.
00325 // 
00326   Bool_t IsInside;
00327 
00328   // Check if Vtx is in our cache
00329   if (fInVtxCache->Exists(VtxID)) return kTRUE; 
00330   else if (fOutVtxCache->Exists(VtxID))  return kFALSE; 
00331   else { // not in cache.
00332     if (fVor->GetWeight(VtxID)) {  // If it is an ordinary point.
00333 
00334        TIntList * PolygsAround;  
00335        TObjArray * PointsOnCircle = new TObjArray(3); 
00336 
00337        // Get the number of polygons incident to vtx.
00338        // Should be 3, since we consistently avoid degeneracy.
00339        PolygsAround = RetrievePolygonsIncidentToVtx(VtxID);
00340        
00341        // Get the generators of these polygons.
00342        for(Int_t i=0; i < PolygsAround->NumberOfElements(); i++) { 
00343            Int_t GenID = fVor->PolygonToGenerator(PolygsAround->At(i));
00344            Float_t x = fVor->GetGeneratorX(GenID);
00345            Float_t y = fVor->GetGeneratorY(GenID);  
00346            PointsOnCircle->Add(new BFLNode(x,y));
00347        }
00348 
00349        // Check if the new generator is in the circle defined by
00350        // the points on the PointsOnCircle container.                       
00351        if (IsInTheCircle(PointsOnCircle,fCurrentGen) == 1) {
00352           IsInside = kTRUE;     
00353           fInVtxCache->AddLast(VtxID);
00354        } else {
00355           IsInside = kFALSE;
00356           fOutVtxCache->AddLast(VtxID);
00357        }
00358        
00359        // Explicitly free some allocated memory  
00360        delete PolygsAround;   
00361        PointsOnCircle->Delete();
00362        delete PointsOnCircle;
00363 
00364     } else { // point at infinity.     
00365        IsInside = kFALSE; 
00366        fOutVtxCache->AddLast(VtxID);
00367     } 
00368   } 
00369   
00370   return IsInside;  
00371 } 

BFLNode BFLVorOperator::VtxPosition ( TObjArray *  PointsOnCircle  )  const

Definition at line 436 of file BFLVorOperator.cxx.

References BFLNode::GetX(), and BFLNode::GetY().

Referenced by FindNewVtx().

00437 {
00438 // Returns an BFLNode that holds the coordinates of the center of a
00439 // circle that is described by the points on it ( PointsOnCirce 
00440 // container of BFLNodes ).
00441 // Actually, this is the way we calculate a vtx position as the center
00442 // of the circle that passes through the generators of the three
00443 // Voronoi regions around this vertex.
00444 //
00445   Int_t i=0;
00446   Float_t A, B, C, Xvtx, Yvtx;
00447   Float_t x[3], y[3], r[3];
00448   BFLNode * PointOnCircle;
00449   
00450   TIter next(PointsOnCircle);
00451   while( (PointOnCircle = (BFLNode *)next())) {  
00452      x[i]=PointOnCircle->GetX();
00453      y[i]=PointOnCircle->GetY();
00454 //     r[i]=TMath::Power(x[i],2)+TMath::Power(y[i],2);
00455      r[i]=x[i]*x[i] + y[i]*y[i];
00456      i++;
00457   }
00458   
00459   A = x[1]*y[2] - x[2]*y[1] - x[0]*y[2] +
00460       x[2]*y[0] + x[0]*y[1] - x[1]*y[0];
00461       
00462   B = y[1]*r[2] - y[2]*r[1] - y[0]*r[2] + 
00463       y[2]*r[0] + y[0]*r[1] - y[1]*r[0];
00464       
00465   C = - x[0]*r[1] - x[1]*r[2] - x[2]*r[0] + 
00466         x[0]*r[2] + x[1]*r[0] + x[2]*r[1];
00467       
00468   if(A !=0 ) {
00469      Xvtx = -B/(2*A);
00470      Yvtx = -C/(2*A);
00471      return BFLNode(Xvtx,Yvtx); 
00472   } else {
00473      return BFLNode(0.,0.);
00474   }     
00475 }


Member Data Documentation

TObjArray* BFLVorOperator::fGenerators [private]

Definition at line 63 of file BFLVorOperator.h.

Definition at line 65 of file BFLVorOperator.h.

Referenced by ResetVtxCache(), VtxIsInsideNewPolyg(), and ~BFLVorOperator().

Definition at line 66 of file BFLVorOperator.h.

Referenced by ResetVtxCache(), VtxIsInsideNewPolyg(), and ~BFLVorOperator().


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

Generated on 19 Jun 2017 for loon by  doxygen 1.6.1