00001
00002
00003
00004
00006
00007 #include <fstream>
00008
00009
00010 #include "TRandom.h"
00011 #include "TMatrix.h"
00012
00013
00014
00015 #include "BField/TIntList.h"
00016 #include "BField/BFLNode.h"
00017 #include "BField/BFLVtx.h"
00018 #include "BField/BFLEdge.h"
00019 #include "BField/BFLPolyg.h"
00020 #include "BField/BFLWingedEdge.h"
00021 #include "BField/BFLVorOperator.h"
00022 #include "BField/BFLVoronoiMaker.h"
00023
00024 ClassImp(BFLVoronoiMaker)
00025 ClassImp(BFLVtx)
00026 ClassImp(BFLEdge)
00027 ClassImp(BFLPolyg)
00028
00030
00031
00033
00034 BFLVoronoiMaker::BFLVoronoiMaker(BFLWingedEdge * voronoi)
00035 {
00036
00037
00038 fVor = (BFLWingedEdge *) voronoi;
00039
00040 fGenerators = (TObjArray *) fVor->GetGenerators();
00041 fOp = new BFLVorOperator(voronoi);
00042
00043 fN = 0;
00044 fRandomToSorted = new TIntList();
00045 fSortedToRandom = new TIntList();
00046 fEdgesToDelete = new TIntList();
00047 fVerticesToDelete = new TIntList();
00048 fNewEdgesTopology = new TIntList();
00049 fNewVertices = new TIntList();
00050 }
00052
00053 BFLVoronoiMaker::~BFLVoronoiMaker()
00054 {
00055 delete fRandomToSorted;
00056 delete fSortedToRandom;
00057 delete fNewEdgesTopology;
00058 delete fNewVertices;
00059 }
00061
00062 void BFLVoronoiMaker::IncreaseEntropy(void)
00063 {
00064
00065
00066
00067
00068
00069
00070 BFLNode * CurrentGen;
00071 TRandom *rand = new TRandom();
00072 Int_t i = 0, irandom;
00073 Int_t NumberOfGenerators = fGenerators->GetEntries();
00074
00075 cout << "number of generators = " << NumberOfGenerators << endl;
00076 fGenerators->Sort();
00077
00078 fN = NumberOfGenerators - 1;
00079
00080 TIter next(fGenerators);
00081 while( (CurrentGen = (BFLNode *)next()) ) {
00082 irandom = (Int_t) ( NumberOfGenerators * rand->Rndm() );
00083 fGenerators->AddAt((BFLNode *)fGenerators->At(irandom),i);
00084 fGenerators->AddAt(CurrentGen,irandom);
00085
00086 fSortedToRandom->AddAt(irandom,i);
00087 fRandomToSorted->AddAt(i,irandom);
00088 i++;
00089 }
00090
00091
00092
00093 for (i=0; i<3; i++) fGenerators->Add((BFLNode *)fGenerators->At(i));
00094
00095
00096
00097 delete CurrentGen;
00098 delete rand;
00099 }
00101
00102 void BFLVoronoiMaker::AddDistantGenerators(void)
00103 {
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114 Float_t x, y;
00115
00116
00117
00118
00119 x = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);
00120 y = kAugmentedGrRadius * TMath::Sin(TMath::Pi()/6.);
00121
00122
00123
00124 fVor->AddVtx(1);
00125 fVor->SetX(1,0.);
00126 fVor->SetY(1,0.);
00127 fVor->SetWeight(1,kTRUE);
00128 fVor->SetEdgeAroundVtx(1,1);
00129
00130 fVor->AddVtx(2);
00131 fVor->SetVtx(2);
00132 fVor->SetX(2,x);
00133 fVor->SetY(2,y);
00134 fVor->SetWeight(2,kFALSE);
00135 fVor->SetEdgeAroundVtx(2,4);
00136
00137 fVor->AddVtx(3);
00138 fVor->SetX(3,0);
00139 fVor->SetY(3,-kAugmentedGrRadius);
00140 fVor->SetWeight(3,kFALSE);
00141 fVor->SetEdgeAroundVtx(3,5);
00142
00143 fVor->AddVtx(4);
00144 fVor->SetX(4,-x);
00145 fVor->SetY(4,y);
00146 fVor->SetWeight(4,kFALSE);
00147 fVor->SetEdgeAroundVtx(4,6);
00148
00149
00150
00151
00152 fVor->AddPolyg(0);
00153 fVor->SetEdgeAroundPolyg(0,4);
00154 fVor->AddPolyg(1);
00155 fVor->SetEdgeAroundPolyg(1,1);
00156 fVor->AddPolyg(2);
00157 fVor->SetEdgeAroundPolyg(2,2);
00158 fVor->AddPolyg(3);
00159 fVor->SetEdgeAroundPolyg(3,3);
00160
00161
00162
00163
00164
00165
00166
00167
00168 fVor->AddEdge(1); fVor->AddEdge(2);
00169 fVor->SetLeftPolyg(1,1); fVor->SetLeftPolyg(2,2);
00170 fVor->SetRightPolyg(1,2); fVor->SetRightPolyg(2,3);
00171 fVor->SetStartVtx(1,1); fVor->SetStartVtx(2,1);
00172 fVor->SetEndVtx(1,2); fVor->SetEndVtx(2,3);
00173 fVor->SetCwSuccessor(1,4); fVor->SetCwSuccessor(2,5);
00174 fVor->SetCcwSuccessor(1,5); fVor->SetCcwSuccessor(2,6);
00175 fVor->SetCwPredecessor(1,2); fVor->SetCwPredecessor(2,3);
00176 fVor->SetCcwPredecessor(1,3); fVor->SetCcwPredecessor(2,1);
00177
00178
00179 fVor->AddEdge(3); fVor->AddEdge(4);
00180 fVor->SetLeftPolyg(3,3); fVor->SetLeftPolyg(4,0);
00181 fVor->SetRightPolyg(3,1); fVor->SetRightPolyg(4,1);
00182 fVor->SetStartVtx(3,1); fVor->SetStartVtx(4,4);
00183 fVor->SetEndVtx(3,4); fVor->SetEndVtx(4,2);
00184 fVor->SetCwSuccessor(3,6); fVor->SetCwSuccessor(4,5);
00185 fVor->SetCcwSuccessor(3,4); fVor->SetCcwSuccessor(4,1);
00186 fVor->SetCwPredecessor(3,1); fVor->SetCwPredecessor(4,3);
00187 fVor->SetCcwPredecessor(3,2); fVor->SetCcwPredecessor(4,6);
00188
00189
00190 fVor->AddEdge(5); fVor->AddEdge(6);
00191 fVor->SetLeftPolyg(5,0); fVor->SetLeftPolyg(6,0);
00192 fVor->SetRightPolyg(5,2); fVor->SetRightPolyg(6,3);
00193 fVor->SetStartVtx(5,2); fVor->SetStartVtx(6,3);
00194 fVor->SetEndVtx(5,3); fVor->SetEndVtx(6,4);
00195 fVor->SetCwSuccessor(5,6); fVor->SetCwSuccessor(6,4);
00196 fVor->SetCcwSuccessor(5,2); fVor->SetCcwSuccessor(6,3);
00197 fVor->SetCwPredecessor(5,1); fVor->SetCwPredecessor(6,2);
00198 fVor->SetCcwPredecessor(5,4); fVor->SetCcwPredecessor(6,5);
00199
00200
00201
00202 fVor->AddAvailableEdgeID(7);
00203 fVor->AddAvailableVtxID(5);
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216 fGenerators->AddAt(new BFLNode(0,kGensRadius),0);
00217
00218 x = kGensRadius * TMath::Sin(4.*TMath::Pi()/6.);
00219 y = kGensRadius * TMath::Cos(4.*TMath::Pi()/6.);
00220 fGenerators->AddAt(new BFLNode(x,y),1);
00221
00222 x = kGensRadius * TMath::Sin(8.*TMath::Pi()/6.);
00223 y = kGensRadius * TMath::Cos(8.*TMath::Pi()/6.);
00224 fGenerators->AddAt(new BFLNode(x,y),2);
00225 }
00227
00228 void BFLVoronoiMaker::Make(void)
00229 {
00230
00231
00232
00233 Int_t EdgeID = 0, iedge = 0, LastEdgeID = 0, AddedEdgeID = 0;
00234 Int_t VtxID = 0, LastVtxID = 0, StartVtxID = 0, StartEdgeID = 0;
00235 Bool_t IsFirstVtx;
00236 BFLNode * CurrentGen;
00237
00238 fGenID = 0;
00239
00240
00241
00242 IncreaseEntropy();
00243
00244
00245 AddDistantGenerators();
00246
00247
00248 TIter next(fGenerators);
00249 while( (CurrentGen = (BFLNode *)next())) {
00250 fGenID++;
00251
00252 fOp->SetCurrentGen(CurrentGen);
00253 if(fGenID >= BaseGeneratorID) {
00254
00255
00256 fVorPatch = new BFLWingedEdge(fN + 3);
00257
00258 cout << "generator " << fGenID << endl;
00259
00260
00261 SubstructureInit();
00262
00263 NewStructureInit();
00264
00265
00266 fCurrentPolygID = fOp->FindCurrentPolygon();
00267 fOp->SetCurrentPolygID(fCurrentPolygID);
00268
00269
00270 EdgeID = fOp->GetFirstIntersectEdge();
00271 StartEdgeID = EdgeID;
00272 LastEdgeID = 0;
00273 fNewEdgesTopology->Add(EdgeID);
00274 IsFirstVtx = kTRUE;
00275
00276 do {
00277
00278
00279 MarkEdgesToDelete();
00280
00281
00282 BFLNode NewVtx = fOp->FindNewVtx(EdgeID);
00283
00284
00285 LastVtxID = VtxID;
00286 VtxID = AddNewVtx(EdgeID,NewVtx.GetX(),NewVtx.GetY());
00287 fNewVertices->Add(VtxID);
00288
00289 if(IsFirstVtx) {
00290 StartVtxID = VtxID;
00291 IsFirstVtx = kFALSE;
00292 }
00293
00294
00295 iedge = fOp->GetNextIntersectEdge(EdgeID);
00296 if (iedge == LastEdgeID ) {
00297
00298
00299
00300 AddedEdgeID = AddNewEdge(LastVtxID,VtxID,
00301 LastEdgeID,EdgeID);
00302 fNewEdgesTopology->Add(AddedEdgeID);
00303 fNewEdgesTopology->Add(EdgeID);
00304
00305
00306 fCurrentPolygID = fOp->MoveToNextPolygon(fCurrentPolygID,EdgeID);
00307 fOp->SetCurrentPolygID(fCurrentPolygID);
00308
00309 LastEdgeID = EdgeID;
00310 EdgeID = fOp->GetNextIntersectEdge(EdgeID);
00311
00312 } else {
00313 LastEdgeID = EdgeID;
00314 EdgeID = iedge;
00315 }
00316
00317 } while(EdgeID != StartEdgeID);
00318
00319
00320 LastVtxID = VtxID;
00321 VtxID = StartVtxID;
00322 AddedEdgeID = AddNewEdge(LastVtxID,VtxID,LastEdgeID,EdgeID);
00323 fNewEdgesTopology->Add(AddedEdgeID);
00324
00325
00326 AddNewPolyg(AddedEdgeID);
00327
00328
00329 MarkVerticesToDelete();
00330
00331
00332 WingedEdgePatch();
00333 MergeDataStructures();
00334
00335 delete fVorPatch;
00336
00337
00338 DeleteSubstructure();
00339
00340
00341
00342
00343 fOp->ResetVtxCache();
00344
00345 }
00346 }
00347
00348
00349
00350
00351 delete CurrentGen;
00352 }
00354
00355 Int_t BFLVoronoiMaker::GuessNearestNeighbour(void) const
00356 {
00357
00358
00359
00360
00361
00362
00363
00364 Int_t k, NeighbourGuess = 1;
00365 Int_t ncount = 1, icount = 0;
00366 Float_t sign;
00367
00368 if(fGenID > 1000) {
00369
00370 Int_t SlotAtSorted = RandomToSorted(fGenID - 1);
00371
00372 do {
00373 sign = TMath::Power(-1,(icount%2)+1);
00374 k = ncount * Int_t(sign);
00375
00376 if(SlotAtSorted + k >= 0 && SlotAtSorted + k < fN+3) {
00377 NeighbourGuess = SortedToRandom(SlotAtSorted + k);
00378 }
00379
00380 if(icount%2 == 1) ncount++;
00381
00382 icount++;
00383
00384 } while(NeighbourGuess > fGenID - 1);
00385
00386 } else NeighbourGuess = fGenID - 1;
00387
00388 return NeighbourGuess;
00389 }
00391
00392 void BFLVoronoiMaker::WingedEdgePatch(void)
00393 {
00394 Int_t ivtx = 0, i = 0, iedge = 0, EdgeID = 0, VtxID = 0;
00395
00396
00397
00398 for(i = 1; i < fNewEdgesTopology->NumberOfElements(); i+=2) {
00399 iedge = i+2;
00400 if(iedge > fNewEdgesTopology->NumberOfElements()) {
00401 iedge -= fNewEdgesTopology->NumberOfElements();
00402 }
00403 fVorPatch->SetCwSuccessor(fNewEdgesTopology->At(i),
00404 fNewEdgesTopology->At(iedge));
00405 }
00406
00407
00408
00409 for(i = fNewEdgesTopology->NumberOfElements() - 1; i>0; i-=2) {
00410 iedge = i-2;
00411 if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00412 fVorPatch->SetCcwPredecessor(fNewEdgesTopology->At(i),
00413 fNewEdgesTopology->At(iedge));
00414 }
00415
00416
00417
00418
00419
00420
00421 for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
00422 EdgeID = fNewEdgesTopology->At(i);
00423 BFLEdge * ResizedEdge = new BFLEdge(EdgeID);
00424 *ResizedEdge = *(fVor->GetEdgeObj(EdgeID));
00425 fVorPatch->SetEdgeObj(ResizedEdge,EdgeID);
00426 }
00427
00428 ivtx = 0;
00429 for(i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2) {
00430
00431 VtxID = fNewVertices->At(ivtx);
00432 EdgeID = fNewEdgesTopology->At(i);
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444 if(fOp->VtxIsInsideNewPolyg(fVor->GetStartVtx(EdgeID))) {
00445
00446 fVorPatch->SetStartVtx(EdgeID,VtxID);
00447
00448
00449 iedge = i-1;
00450 if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00451 fVorPatch->SetCwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
00452
00453 iedge = i+1;
00454 if(iedge > fNewEdgesTopology->NumberOfElements()) {
00455 iedge -= fNewEdgesTopology->NumberOfElements();
00456 }
00457 fVorPatch->SetCcwPredecessor(EdgeID,fNewEdgesTopology->At(iedge));
00458
00459 } else if(fOp->VtxIsInsideNewPolyg(fVor->GetEndVtx(EdgeID))) {
00460
00461 fVorPatch->SetEndVtx(EdgeID,VtxID);
00462
00463
00464 iedge = i-1;
00465 if(iedge < 0) iedge += fNewEdgesTopology->NumberOfElements();
00466 fVorPatch->SetCwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));
00467
00468 iedge = i+1;
00469 if(iedge > fNewEdgesTopology->NumberOfElements()) {
00470 iedge -= fNewEdgesTopology->NumberOfElements();
00471 }
00472 fVorPatch->SetCcwSuccessor(EdgeID,fNewEdgesTopology->At(iedge));
00473 }
00474 ivtx++;
00475 }
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486 RemoveRefsToDeletedEdges();
00487 }
00489
00490 Int_t BFLVoronoiMaker::GetAnotherEdgeAround(Int_t PolygID) const
00491 {
00492
00493
00494
00495
00496
00497 Int_t NewEdgeAround = 0;
00498
00499 TIntList * edges = fOp->RetrieveEdgesSurrPolygon(PolygID);
00500
00501 for(Int_t j=0; j < edges->NumberOfElements(); j++){
00502 NewEdgeAround = edges->At(j);
00503 if(!fEdgesToDelete->Exists(NewEdgeAround)) break;
00504 }
00505
00506 delete edges;
00507
00508 return NewEdgeAround;
00509 }
00510
00512
00513 void BFLVoronoiMaker::RemoveRefsToDeletedEdges(void)
00514 {
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526 for(Int_t i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
00527
00528 Int_t EdgeID = fEdgesToDelete->At(i);
00529
00530
00531
00532 Int_t LPolygID = fVor->GetLeftPolyg(EdgeID);
00533 if(EdgeID == fVor->GetEdgeAroundPolyg(LPolygID)) {
00534
00535 Int_t NewEdgeAround = GetAnotherEdgeAround(LPolygID);
00536 fVor->SetEdgeAroundPolyg(LPolygID,NewEdgeAround);
00537 }
00538
00539
00540
00541 Int_t RPolygID = fVor->GetRightPolyg(EdgeID);
00542 if(EdgeID == fVor->GetEdgeAroundPolyg(RPolygID)) {
00543
00544 Int_t NewEdgeAround = GetAnotherEdgeAround(RPolygID);
00545 fVor->SetEdgeAroundPolyg(RPolygID,NewEdgeAround);
00546 }
00547 }
00548 }
00550
00551 void BFLVoronoiMaker::MergeDataStructures(void)
00552 {
00553
00554
00555
00556
00557
00558
00559 TIter NextEdge(fVorPatch->GetEdges());
00560 BFLEdge * EdgeObj;
00561 while ((EdgeObj = (BFLEdge *)NextEdge())) {
00562 BFLEdge *NewEdge = new BFLEdge(EdgeObj->GetEdgeID());
00563 *NewEdge = *EdgeObj;
00564 fVor->SetEdgeObj(NewEdge, EdgeObj->GetEdgeID());
00565 }
00566 delete EdgeObj;
00567
00568
00569 TIter NextVtx(fVorPatch->GetVertices());
00570 BFLVtx * VtxObj;
00571 while ((VtxObj = (BFLVtx *)NextVtx())) {
00572 BFLVtx *NewVtx = new BFLVtx(VtxObj->GetVtxID());
00573 *NewVtx = *VtxObj;
00574 fVor->SetVtxObj(NewVtx, VtxObj->GetVtxID());
00575 }
00576 delete VtxObj;
00577
00578
00579 TIter NextPolyg(fVorPatch->GetPolygons());
00580 BFLPolyg * PolygObj;
00581 while ((PolygObj = (BFLPolyg *)NextPolyg())) {
00582 BFLPolyg *NewPolyg = new BFLPolyg(PolygObj->GetPolygID());
00583 *NewPolyg = *PolygObj;
00584 fVor->SetPolygObj(NewPolyg, PolygObj->GetPolygID());
00585 }
00586 delete PolygObj;
00587 }
00589
00590 Int_t BFLVoronoiMaker::AddNewVtx(Int_t EdgeID, Float_t x, Float_t y)
00591 {
00592
00593
00594
00595
00596 Int_t VtxID;
00597
00598 VtxID = fVor->FirstAvailableVtxID();
00599
00600 fVorPatch->AddVtx(VtxID);
00601 fVorPatch->SetVtxID(VtxID,VtxID);
00602 fVorPatch->SetEdgeAroundVtx(VtxID,EdgeID);
00603 fVorPatch->SetX(VtxID,x);
00604 fVorPatch->SetY(VtxID,y);
00605 fVorPatch->SetWeight(VtxID,kTRUE);
00606
00607 fVor->DeleteFirstAvailableVtxID();
00608
00609 return VtxID;
00610 }
00611
00613
00614 void BFLVoronoiMaker::AddNewPolyg(Int_t EdgeID)
00615 {
00616
00617
00618
00619
00620 Int_t NewPolygID;
00621
00622
00623 NewPolygID = fGenID;
00624
00625
00626 fVorPatch->AddPolyg(NewPolygID);
00627 fVorPatch->SetPolygID(NewPolygID,NewPolygID);
00628 fVorPatch->SetEdgeAroundPolyg(NewPolygID,EdgeID);
00629 }
00631
00632 Int_t BFLVoronoiMaker::AddNewEdge(Int_t SVtxID, Int_t EVtxID,
00633 Int_t EdgeOfSVtx, Int_t EdgeOfEVtx)
00634 {
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651 Int_t EdgeID, NewPolygID;
00652
00653 EdgeID = fVor->FirstAvailableEdgeID();
00654 fVor->DeleteFirstAvailableEdgeID();
00655
00656 fVorPatch->AddEdge(EdgeID);
00657 fVorPatch->SetEdgeID(EdgeID,EdgeID);
00658
00659
00660 fVorPatch->SetStartVtx(EdgeID,SVtxID);
00661 fVorPatch->SetEndVtx(EdgeID,EVtxID);
00662
00663
00664
00665
00666 NewPolygID = fGenID;
00667 fVorPatch->SetLeftPolyg(EdgeID,NewPolygID);
00668 fVorPatch->SetRightPolyg(EdgeID,fCurrentPolygID);
00669
00670
00671
00672 fVorPatch->SetCcwSuccessor(EdgeID,EdgeOfEVtx);
00673 fVorPatch->SetCwPredecessor(EdgeID,EdgeOfSVtx);
00674
00675 return EdgeID;
00676 }
00678
00679 void BFLVoronoiMaker::SubstructureInit(void)
00680 {
00681
00682
00683
00684 fEdgesToDelete->Delete();
00685 fVerticesToDelete->Delete();
00686 }
00688
00689 void BFLVoronoiMaker::NewStructureInit(void)
00690 {
00691 fNewEdgesTopology->Delete();
00692 fNewVertices->Delete();
00693 }
00695
00696 void BFLVoronoiMaker::MarkEdgesToDelete(void)
00697 {
00698 Int_t EdgeID;
00699 Bool_t IsInside, AlreadyExists;
00700 TIntList * EdgesAround = new TIntList();
00701
00702 EdgesAround = fOp->RetrieveEdgesSurrPolygon(fCurrentPolygID);
00703
00704 for(Int_t i = 0; i < EdgesAround->NumberOfElements(); i++){
00705 EdgeID = EdgesAround->At(i);
00706
00707 if(fOp->EdgeIsInsideNewPolygon(EdgeID)) IsInside = kTRUE;
00708 else IsInside = kFALSE;
00709
00710 if(fEdgesToDelete->Exists(EdgeID)) AlreadyExists = kTRUE;
00711 else AlreadyExists = kFALSE;
00712
00713 if(IsInside && !AlreadyExists) fEdgesToDelete->Add(EdgeID);
00714 }
00715
00716 delete EdgesAround;
00717 }
00719
00720 void BFLVoronoiMaker::MarkVerticesToDelete(void)
00721 {
00722
00723
00724
00725
00726
00727
00728
00729
00730 Int_t SvtxID, EvtxID, vtxID, EdgeID;
00731 Bool_t AlreadyExists;
00732
00733 for(Int_t i = 0; i< fNewEdgesTopology->NumberOfElements(); i+=2){
00734 EdgeID = fNewEdgesTopology->At(i);
00735
00736
00737 SvtxID = fVor->GetStartVtx(EdgeID);
00738 EvtxID = fVor->GetEndVtx(EdgeID);
00739
00740
00741 if(fOp->VtxIsInsideNewPolyg(EvtxID)) vtxID = EvtxID;
00742 else vtxID = SvtxID;
00743
00744
00745 if(fVerticesToDelete->Exists(vtxID)) AlreadyExists = kTRUE;
00746 else AlreadyExists = kFALSE;
00747
00748
00749 if(!AlreadyExists) fVerticesToDelete->Add(vtxID);
00750 }
00751 }
00753
00754 void BFLVoronoiMaker::DeleteSubstructure(void)
00755 {
00756
00757
00758
00759 Int_t i = 0, EvtxID, SvtxID, EdgeID, VtxID;
00760 Bool_t AlreadyDeleted;
00761 TIntList * DeletedVertices = new TIntList();
00762
00763
00764
00765 for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
00766 SvtxID = fVor->GetStartVtx(fEdgesToDelete->At(i));
00767 EvtxID = fVor->GetEndVtx(fEdgesToDelete->At(i));
00768
00769 if(! DeletedVertices->Exists(SvtxID)) {
00770 fVor->DeleteVtx(SvtxID);
00771 fVor->AddAvailableVtxID(SvtxID);
00772 DeletedVertices->Add(SvtxID);
00773 }
00774
00775 if(! DeletedVertices->Exists(EvtxID)) {
00776 fVor->DeleteVtx(EvtxID);
00777 fVor->AddAvailableVtxID(EvtxID);
00778 DeletedVertices->Add(EvtxID);
00779 }
00780 }
00781
00782
00783
00784 for(i = 0; i < fEdgesToDelete->NumberOfElements(); i++){
00785 EdgeID = fEdgesToDelete->At(i);
00786 fVor->DeleteEdge(EdgeID);
00787 fVor->AddAvailableEdgeID(EdgeID);
00788 }
00789
00790
00791
00792
00793 for(i = 0; i < fVerticesToDelete->NumberOfElements(); i++){
00794 VtxID = fVerticesToDelete->At(i);
00795 AlreadyDeleted = DeletedVertices->Exists(VtxID);
00796 if(!AlreadyDeleted) {
00797 fVor->DeleteVtx(VtxID);
00798 fVor->AddAvailableVtxID(VtxID);
00799 DeletedVertices->Add(VtxID);
00800 }
00801 }
00802
00803 delete DeletedVertices;
00804 }
00806
00807 void BFLVoronoiMaker::Defrag(void)
00808 {
00809
00810
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830
00831
00832
00833
00834
00835
00836
00837
00838
00839
00840
00841
00842
00843
00844
00845
00846
00847
00848
00849
00850
00851
00852
00853
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871
00872
00873
00874
00875
00876
00877
00878
00879
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907
00908
00909
00910
00911
00912
00913
00914
00915
00916
00917
00918
00919
00920
00921
00922
00923
00924
00925
00926
00927 }