#include <BFLVorOperator.h>
Public Member Functions | |
| BFLVorOperator () | |
| BFLVorOperator (BFLWingedEdge *vor) | |
| ~BFLVorOperator () | |
| TIntList * | RetrieveEdgesIncidentToVtx (Int_t vtx) const |
| TIntList * | RetrievePolygonsIncidentToVtx (Int_t vtx) const |
| TIntList * | RetrieveEdgesSurrPolygon (Int_t poly) const |
| TIntList * | RetrieveVtxSurrPolygon (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 BFLNode * | GetCurrentGen (void) const |
Private Attributes | |
| Int_t | fCurrentPolygID |
| BFLNode * | fCurrentGen |
| TObjArray * | fGenerators |
| BFLWingedEdge * | fVor |
| TIntList * | fInVtxCache |
| TIntList * | fOutVtxCache |
|
|
Definition at line 30 of file BFLVorOperator.h. 00030 { }
|
|
|
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 }
|
|
|
Definition at line 40 of file BFLVorOperator.cxx. 00041 {
00042 delete fInVtxCache;
00043 delete fOutVtxCache;
00044 }
|
|
||||||||||||||||
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
||||||||||||
|
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 }
|
|
|
Definition at line 58 of file BFLVorOperator.h. 00058 { return fCurrentGen; }
|
|
|
Definition at line 55 of file BFLVorOperator.h. 00055 { return fCurrentPolygID; }
|
|
|
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 }
|
|
|
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 }
|
|
||||||||||||
|
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 }
|
|
||||||||||||
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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 }
|
|
|
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; }
|
|
|
Definition at line 54 of file BFLVorOperator.h. References fCurrentPolygID. Referenced by BFLInterpolation::FormVoronoiCell(), and BFLVoronoiMaker::Make(). 00054 { fCurrentPolygID = pid; }
|
|
|
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 }
|
|
|
Definition at line 436 of file BFLVorOperator.cxx. References C, 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 }
|
|
|
Definition at line 62 of file BFLVorOperator.h. Referenced by DistanceFrom(), FindNewVtx(), GetFirstIntersectEdge(), SetCurrentGen(), and VtxIsInsideNewPolyg(). |
|
|
Definition at line 61 of file BFLVorOperator.h. Referenced by GetFirstIntersectEdge(), GetNextIntersectEdge(), and SetCurrentPolygID(). |
|
|
Definition at line 63 of file BFLVorOperator.h. |
|
|
Definition at line 65 of file BFLVorOperator.h. Referenced by ResetVtxCache(), and VtxIsInsideNewPolyg(). |
|
|
Definition at line 66 of file BFLVorOperator.h. Referenced by ResetVtxCache(), and VtxIsInsideNewPolyg(). |
|
|
Definition at line 64 of file BFLVorOperator.h. Referenced by DistanceFrom(), EdgeHasNewVtx(), EdgeIsInsideNewPolygon(), FindCurrentPolygon(), FindNewVtx(), GeneratorsDist(), MoveToNextPolygon(), RetrieveEdgesIncidentToVtx(), RetrieveEdgesSurrPolygon(), RetrievePolygonsIncidentToVtx(), RetrieveVtxSurrPolygon(), and VtxIsInsideNewPolyg(). |
1.3.9.1