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]

Definition at line 57 of file BFLVorOperator.h.

References fCurrentGen.

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

00057 { fCurrentGen = gen; }  

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::Exists(), fCurrentGen, fInVtxCache, fOutVtxCache, fVor, BFLWingedEdge::GetGeneratorX(), BFLWingedEdge::GetGeneratorY(), BFLWingedEdge::GetWeight(), IsInTheCircle(), 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

BFLNode* BFLVorOperator::fCurrentGen [private]

Definition at line 62 of file BFLVorOperator.h.

Referenced by DistanceFrom(), FindNewVtx(), GetCurrentGen(), GetFirstIntersectEdge(), SetCurrentGen(), and VtxIsInsideNewPolyg().

Int_t BFLVorOperator::fCurrentPolygID [private]

Definition at line 61 of file BFLVorOperator.h.

Referenced by GetCurrentPolygID(), GetFirstIntersectEdge(), GetNextIntersectEdge(), and SetCurrentPolygID().

TObjArray* BFLVorOperator::fGenerators [private]

Definition at line 63 of file BFLVorOperator.h.

TIntList* BFLVorOperator::fInVtxCache [private]

Definition at line 65 of file BFLVorOperator.h.

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

TIntList* BFLVorOperator::fOutVtxCache [private]

Definition at line 66 of file BFLVorOperator.h.

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

BFLWingedEdge* BFLVorOperator::fVor [private]

Definition at line 64 of file BFLVorOperator.h.

Referenced by DistanceFrom(), EdgeHasNewVtx(), EdgeIsInsideNewPolygon(), FindCurrentPolygon(), FindNewVtx(), GeneratorsDist(), MoveToNextPolygon(), RetrieveEdgesIncidentToVtx(), RetrieveEdgesSurrPolygon(), RetrievePolygonsIncidentToVtx(), RetrieveVtxSurrPolygon(), and VtxIsInsideNewPolyg().


The documentation for this class was generated from the following files:
Generated on Mon Aug 11 01:05:32 2014 for loon by  doxygen 1.4.7