src/MAT/MAT_Graph.cxx

   1 // Created on: 1993-05-06
   2 // Created by: Yves FRICAUD
   3 // Copyright (c) 1993-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17
  18 #include <MAT_Arc.hxx>
  19 #include <MAT_Bisector.hxx>
  20 #include <MAT_DataMapIteratorOfDataMapOfIntegerBasicElt.hxx>
  21 #include <MAT_DataMapOfIntegerBasicElt.hxx>
  22 #include <MAT_Edge.hxx>
  23 #include <MAT_Graph.hxx>
  24 #include <MAT_ListOfBisector.hxx>
  25 #include <MAT_Node.hxx>
  26 #include <MAT_Zone.hxx>
  27 #include <Precision.hxx>
  28 #include <Standard_Type.hxx>
  29
  30 IMPLEMENT_STANDARD_RTTIEXT(MAT_Graph,Standard_Transient)
  31
  32 //------------------
  33 // functions static.
  34 //-------------------
  35   static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)&     aBisector,
  36                                  MAT_DataMapOfIntegerBasicElt&   TheBasicElts,
  37                                  MAT_DataMapOfIntegerArc&        TheArcs,
  38                                  Standard_Integer&               IndTabArcs);
  39
  40 // =====================================================================
  41 // Constructeur vide.
  42 // =====================================================================
  43 MAT_Graph::MAT_Graph()
  44 : numberOfArcs(0),
  45   numberOfNodes(0),
  46   numberOfBasicElts(0),
  47   numberOfInfiniteNodes(0)
  48 {
  49 }
  50
  51 // =====================================================================
  52 // function : Perform
  53 // purpose  : Creation du graphe contenant le resultat.
  54 // =====================================================================
  55 void MAT_Graph::Perform(const Standard_Boolean             SemiInfinite,
  56                         const Handle(MAT_ListOfBisector)&  TheRoots,
  57                         const Standard_Integer             NbBasicElts,
  58                         const Standard_Integer             NbArcs)
  59 {
  60   Standard_Integer        NbRoots;
  61   Handle(MAT_Arc)         FirstArc;
  62   Handle(MAT_Arc)         CurrentArc;
  63   Handle(MAT_Node)        Extremite;
  64   Standard_Integer        IndTabArcs = 1;
  65   Standard_Integer        IndTabNodes;
  66   Standard_Integer        i;
  67   Standard_Real           DistExt;
  68   Standard_Integer        IndExt;
  69   Handle(MAT_Arc)         PreviousArc = CurrentArc;
  70
  71   //------------------------
  72   // Construction du graphe.
  73   //------------------------
  74
  75   if (SemiInfinite) {
  76     NbRoots               = TheRoots->Number();
  77     numberOfInfiniteNodes = NbRoots;
  78   }
  79   else {
  80     NbRoots               = 1;
  81     numberOfInfiniteNodes = 0;
  82   }
  83
  84   numberOfArcs         = NbArcs;
  85   numberOfBasicElts    = NbBasicElts;
  86   numberOfNodes        = NbRoots + NbArcs;
  87   IndTabNodes          = numberOfNodes;
  88
  89   //---------------------------
  90   //... Creation des BasicElts.
  91   //---------------------------
  92   for (i = 1; i <= NbBasicElts; i++) {
  93     theBasicElts.Bind(i,new MAT_BasicElt(i));
  94     theBasicElts(i)->SetGeomIndex(i);
  95   }
  96
  97   //--------------------------------------------------------------------
  98   // ... Creation des ARCS et des NODES.
  99   //     Construction des arbres d arcs a partir des <Bisector> racines.
 100   //--------------------------------------------------------------------
 101
 102   if (SemiInfinite) {
 103
 104     // Plusieurs points d entree a l infini.
 105     //--------------------------------------
 106     TheRoots->First();
 107
 108     while (TheRoots->More()) {
 109       CurrentArc = MakeArc(TheRoots->Current(),
 110                            theBasicElts,
 111                            theArcs,
 112                            IndTabArcs);
 113       Extremite = new MAT_Node (0,CurrentArc,Precision::Infinite());
 114       Extremite ->SetIndex     (IndTabNodes);
 115       CurrentArc->SetSecondNode(Extremite);
 116       theNodes.Bind(IndTabNodes,Extremite);
 117       TheRoots->Next();
 118       IndTabNodes--;
 119     }
 120   }
 121   else {
 122     // -----------------------------------------------
 123     // Un seul point d entree .
 124     // Creation d un premier ARC et du NODE racine.
 125     // -----------------------------------------------
 126     NbRoots = 1;
 127     TheRoots->First();
 128     CurrentArc = MakeArc(TheRoots->Current(),
 129                          theBasicElts,
 130                          theArcs,
 131                          IndTabArcs);
 132     DistExt   = TheRoots->Current()->FirstEdge()->Distance();
 133     IndExt    = TheRoots->Current()->EndPoint();
 134
 135     Extremite = new MAT_Node(IndExt,CurrentArc,DistExt);
 136     Extremite ->SetIndex     (IndTabNodes);
 137     CurrentArc->SetSecondNode(Extremite);
 138     theNodes.Bind(IndTabNodes,Extremite);
 139     IndTabNodes--;
 140
 141     // -----------------------------------------------------------
 142     // ...Creation des ARCs issues de la racine.
 143     //    Codage des voisinages sur ces arcs et mise a jour de la
 144     //    sequence des arcs issue du Node racine.
 145     // -----------------------------------------------------------
 146     FirstArc     = CurrentArc;
 147     PreviousArc  = FirstArc;
 148     TheRoots->Next();
 149
 150     while (TheRoots->More()) {
 151       CurrentArc = MakeArc(TheRoots->Current(),
 152                            theBasicElts,
 153                            theArcs,
 154                            IndTabArcs);
 155       CurrentArc ->SetSecondNode(Extremite);
 156       CurrentArc ->SetNeighbour (MAT_Left,Extremite ,PreviousArc);
 157       PreviousArc->SetNeighbour (MAT_Right,Extremite,CurrentArc);
 158
 159       PreviousArc = CurrentArc;
 160       TheRoots->Next();
 161     }
 162     FirstArc  ->SetNeighbour (MAT_Left ,Extremite,CurrentArc);
 163     CurrentArc->SetNeighbour (MAT_Right,Extremite,FirstArc);
 164   }
 165
 166   // ----------------------------------------------------
 167   // Les sequence des Arcs des Nodes racines sont a jour.
 168   // Mise a jour des sequences des autres Nodes.
 169   // ----------------------------------------------------
 170   UpDateNodes(IndTabNodes);
 171 }
 172
 173 //=============================================================================
 174 //function : Arc
 175 //Purpose  :
 176 //=============================================================================
 177 Handle(MAT_Arc)  MAT_Graph::Arc(const Standard_Integer Index) const
 178 {
 179   return theArcs(Index);
 180 }
 181
 182 //=============================================================================
 183 //function : BasicElt
 184 //Purpose  :
 185 //=============================================================================
 186 Handle(MAT_BasicElt)  MAT_Graph::BasicElt(const Standard_Integer Index) const
 187 {
 188   return theBasicElts(Index);
 189 }
 190
 191 //=============================================================================
 192 //function : Node
 193 //Purpose  :
 194 //=============================================================================
 195 Handle(MAT_Node)  MAT_Graph::Node(const Standard_Integer Index) const
 196 {
 197   return theNodes(Index);
 198 }
 199
 200 //=============================================================================
 201 //function : NumberOfArcs
 202 //Purpose  :
 203 //=============================================================================
 204 Standard_Integer  MAT_Graph::NumberOfArcs() const
 205 {
 206   return numberOfArcs;
 207 }
 208
 209 //=============================================================================
 210 //function : NumberOfNodes
 211 //Purpose  :
 212 //=============================================================================
 213 Standard_Integer  MAT_Graph::NumberOfNodes() const
 214 {
 215   return numberOfNodes;
 216 }
 217
 218 //=============================================================================
 219 //function : NumberOfInfiniteNodes
 220 //Purpose  :
 221 //=============================================================================
 222 Standard_Integer  MAT_Graph::NumberOfInfiniteNodes() const
 223 {
 224   return numberOfInfiniteNodes;
 225 }
 226
 227 //=============================================================================
 228 //function : NumberOfBasicElts
 229 //Purpose  :
 230 //=============================================================================
 231 Standard_Integer  MAT_Graph::NumberOfBasicElts() const
 232 {
 233   return numberOfBasicElts;
 234 }
 235
 236 //=============================================================================
 237 //function : FusionOfBasicElts
 238 //Purpose  :
 239 //=============================================================================
 240 void MAT_Graph::FusionOfBasicElts(const Standard_Integer  IndexElt1,
 241                                   const Standard_Integer  IndexElt2,
 242                                         Standard_Boolean& MergeArc1,
 243                                         Standard_Integer& IGeomArc1,
 244                                         Standard_Integer& IGeomArc2,
 245                                         Standard_Boolean& MergeArc2,
 246                                         Standard_Integer& IGeomArc3,
 247                                         Standard_Integer& IGeomArc4)
 248 {
 249   Handle(MAT_BasicElt) Elt1 = theBasicElts(IndexElt1);
 250   Handle(MAT_BasicElt) Elt2 = theBasicElts(IndexElt2);
 251
 252   if (Elt1 == Elt2) return;
 253
 254   Standard_Integer i;
 255   Handle(MAT_Zone) Zone2   = new MAT_Zone(Elt2);
 256
 257   //--------------------------------------------------------------------
 258   // Les arcs de la zone de Elt2 ne separent plus Elt2 et qq chose mais
 259   // Elt1 et qq chose.
 260   //--------------------------------------------------------------------
 261   for (i = 1; i <= Zone2->NumberOfArcs(); i++) {
 262      if (Zone2->ArcOnFrontier(i)->FirstElement() == Elt2) {
 263        theArcs(Zone2->ArcOnFrontier(i)->Index())->SetFirstElement(Elt1);
 264      }
 265      else {
 266        theArcs(Zone2->ArcOnFrontier(i)->Index())->SetSecondElement(Elt1);
 267      }
 268    }
 269
 270   //-------------------------------------------------------------------
 271   // le EndArc de Elt1 et le StartArc de Elt2 peuvent separes les memes
 272   // elements de base => Fusion des deux arcs et mise a jour des noeuds.
 273   //-------------------------------------------------------------------
 274   Handle(MAT_Arc) EA1 = Elt1->EndArc();
 275   Handle(MAT_Arc) SA2 = Elt2->StartArc();
 276
 277   Handle(MAT_BasicElt) E1 = EA1->FirstElement();
 278   Handle(MAT_BasicElt) E2 = EA1->SecondElement();
 279   Handle(MAT_BasicElt) E3 = SA2->FirstElement();
 280   Handle(MAT_BasicElt) E4 = SA2->SecondElement();
 281   MergeArc1 = Standard_False;
 282
 283   if ( (E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4)) {
 284     FusionOfArcs(theArcs(EA1->Index()),theArcs(SA2->Index()));
 285     MergeArc1 = Standard_True;
 286     IGeomArc1 = EA1->GeomIndex();
 287     IGeomArc2 = SA2->GeomIndex();
 288   }
 289
 290   //-------------------------------------------------
 291   // La fin de Elt1 devient la fin de Elt2.
 292   //-------------------------------------------------
 293   Elt1->SetEndArc(Elt2->EndArc());
 294
 295   //-------------------------------------------------------------------
 296   // le EndArc de Elt1 et le StartArc de Elt1 peuvent separer les memes
 297   // elements de base.
 298   // si les noeuds des arcs ne sont pas sur le contour
 299   //    => fusion des arcs.(contour ferme compose d un seul BasicElt)
 300   // sinon rien            (contour ferme compose de deux BasicElts)
 301   //-------------------------------------------------------------------
 302   Handle(MAT_Arc) SA1 = Elt1->StartArc();
 303   EA1 = Elt1->EndArc();
 304
 305   if ( EA1 != SA1 ) {
 306     E1 = EA1->FirstElement ();
 307     E2 = EA1->SecondElement();
 308     E3 = SA1->FirstElement ();
 309     E4 = SA1->SecondElement();
 310
 311     Standard_Boolean OnFig = (EA1->FirstNode() ->OnBasicElt() ||
 312                               EA1->SecondNode()->OnBasicElt() ||
 313                               SA1->FirstNode() ->OnBasicElt() ||
 314                               SA1->SecondNode()->OnBasicElt() );
 315
 316     MergeArc2 = Standard_False;
 317
 318     if ((E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4) && !OnFig) {
 319       FusionOfArcs(theArcs(EA1->Index()),theArcs(SA1->Index()));
 320       MergeArc2 = Standard_True;
 321       IGeomArc3 = EA1->GeomIndex();
 322       IGeomArc4 = SA1->GeomIndex();
 323     }
 324   }
 325
 326   //----------------------------------------------------
 327   // un element de base a ete elimine.
 328   //----------------------------------------------------
 329   theBasicElts.UnBind(Elt2->Index());
 330   numberOfBasicElts--;
 331 }
 332
 333 //=============================================================================
 334 // function : FusionOfArcs
 335 // purpose  : Fusion de deux arcs separant les memes elements.
 336 //            l <Arc1> ira du Second noeud de <Arc2> au second Noeud de <Arc1>.
 337 //=============================================================================
 338 void MAT_Graph::FusionOfArcs(const Handle(MAT_Arc)& Arc1,
 339                              const Handle(MAT_Arc)& Arc2)
 340 {
 341
 342   Handle(MAT_Node) OldNode1 = Arc1->FirstNode();
 343   Handle(MAT_Node) OldNode2 = Arc2->FirstNode();
 344
 345   Arc1->SetFirstNode(Arc2->SecondNode());
 346
 347   //--------------------------------------------------------------------
 348   // Mise a jour des voisinages autour du nouveau premier noeud de Arc1.
 349   //--------------------------------------------------------------------
 350   if (!Arc2->SecondNode()->Infinite()) {
 351     Handle(MAT_Arc) LNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Left);
 352     Handle(MAT_Arc) RNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Right);
 353
 354     Arc1->SetFirstArc(MAT_Left,LNeighbour);
 355     Arc1->SetFirstArc(MAT_Right,RNeighbour);
 356     theArcs(LNeighbour->Index())->SetNeighbour(MAT_Right,
 357                                                Arc2->SecondNode(),
 358                                                Arc1);
 359     theArcs(RNeighbour->Index())->SetNeighbour(MAT_Left,
 360                                                Arc2->SecondNode(),
 361                                                Arc1);
 362   }
 363   else {
 364     Handle(MAT_Arc) EmptyArc;
 365     Arc1->SetFirstArc(MAT_Left ,EmptyArc);
 366     Arc1->SetFirstArc(MAT_Right,EmptyArc);
 367   }
 368
 369   //-------------------------------------------------------------------
 370   // Mise a jour du premier noeud Arc1.
 371   //-----------------------------------------------------------------
 372   Arc1->FirstNode()->SetLinkedArc(Arc1);
 373
 374   //------------------------------------
 375   // Elimination de Arc2 et des OldNode
 376   //------------------------------------
 377   if (theNodes.IsBound(OldNode1->Index())) {
 378     theNodes.UnBind(OldNode1->Index());
 379     numberOfNodes--;
 380   }
 381   if (theNodes.IsBound(OldNode2->Index())) {
 382     theNodes.UnBind(OldNode2->Index());
 383     numberOfNodes--;
 384   }
 385
 386   // Note: the Arc2 is actually a reference to a handle contained in theArcs map;
 387   // it is necessary to create copy of that handle and use only it to access
 388   // that object, since the handle contained in the map is destroyed by UnBind()
 389   Handle(MAT_Arc) anArc2 = Arc2;
 390   theArcs .UnBind(Arc2->Index());
 391   numberOfArcs--;
 392
 393   for (Standard_Integer i = 1; i <= 2; i++){
 394     Handle(MAT_BasicElt) BE;
 395     if (i == 1)
 396       BE  = theBasicElts(anArc2->FirstElement ()->Index());
 397     else
 398       BE  = theBasicElts(anArc2->SecondElement ()->Index());
 399
 400     if (BE->StartArc()  == anArc2) { BE->SetStartArc(Arc1);}
 401     if (BE->EndArc  ()  == anArc2) { BE->SetEndArc  (Arc1);}
 402   }
 403 }
 404
 405 //=============================================================================
 406 // function : CompactArcs
 407 // purpose  : Decalage des Arcs pour boucher les trous.
 408 //=============================================================================
 409 void MAT_Graph::CompactArcs()
 410 {
 411   Standard_Integer IFind      = 0;
 412   Standard_Integer i          = 1;
 413   Standard_Boolean YaDecalage = Standard_False;
 414
 415   while (IFind < numberOfArcs) {
 416     if (!theArcs.IsBound(i)) {
 417       YaDecalage = Standard_True;
 418     }
 419     else {
 420       IFind++;
 421       if (YaDecalage) {
 422         theArcs(i)->SetIndex(IFind);
 423         theArcs.Bind(IFind,theArcs(i));
 424         theArcs.UnBind(i);
 425       }
 426     }
 427     i++;
 428   }
 429 }
 430
 431 //=============================================================================
 432 // function : CompactNodes
 433 // purpose  : Decalage des Nodes pour boucher les trous.
 434 //=============================================================================
 435 void MAT_Graph::CompactNodes()
 436 {
 437   Standard_Integer IFind      = 0;
 438   Standard_Integer i          = 1;
 439   Standard_Boolean YaDecalage = Standard_False;
 440
 441   while (IFind < numberOfNodes) {
 442     if (!theNodes.IsBound(i)) {
 443       YaDecalage = Standard_True;
 444     }
 445     else {
 446       IFind++;
 447       if (YaDecalage) {
 448         theNodes(i)->SetIndex(IFind);
 449         theNodes.Bind(IFind,theNodes(i));
 450         theNodes.UnBind(i);
 451       }
 452     }
 453     i++;
 454   }
 455 }
 456
 457 //=============================================================================
 458 // function : ChangeBasicElts
 459 // purpose  :
 460 //=============================================================================
 461 void MAT_Graph::ChangeBasicElts(const MAT_DataMapOfIntegerBasicElt& NewMap)
 462 {
 463   theBasicElts = NewMap;
 464   MAT_DataMapIteratorOfDataMapOfIntegerBasicElt Ite;
 465   for (Ite.Initialize(theBasicElts); Ite.More(); Ite.Next()) {
 466     Ite.Value()->SetIndex(Ite.Key());
 467   }
 468 }
 469
 470 //=============================================================================
 471 //function : ChangeBasicElt
 472 //Purpose  :
 473 //=============================================================================
 474 Handle(MAT_BasicElt)  MAT_Graph::ChangeBasicElt(const Standard_Integer Index)
 475 {
 476   return theBasicElts(Index);
 477 }
 478
 479 //=============================================================================
 480 // function : UpDateNodes
 481 // purpose  : Mise a jour des sequence d'ARC de chaque FirstNode de chaque arc.
 482 //            et stockage de chaque noeud dans la table des noeuds.
 483 //            Les noeuds racines sont traites dans PERFORM.
 484 //=============================================================================
 485 void MAT_Graph::UpDateNodes (Standard_Integer&  IndTabNodes)
 486 {
 487   Standard_Integer    i;
 488   Handle(MAT_Node)    Bout;
 489   Handle(MAT_Arc)     CurrentArc;
 490
 491   for (i = 1; i <= numberOfArcs; i++) {
 492     Bout = theArcs(i)->FirstNode();
 493     theNodes.Bind(IndTabNodes,Bout);
 494     Bout->SetIndex(IndTabNodes);
 495     IndTabNodes--;
 496     Bout->SetLinkedArc(theArcs(i));
 497   }
 498 }
 499
 500
 501 //=============================================================================
 502 // function : MakeArc
 503 // purpose  : Creation des <ARCS> en parcourant l'arbre issue de <aBisector>.
 504 //=============================================================================
 505 static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)&     aBisector,
 506                                MAT_DataMapOfIntegerBasicElt&   TheBasicElts,
 507                                MAT_DataMapOfIntegerArc&        TheArcs,
 508                                Standard_Integer&               IndTabArcs)
 509 {
 510   Handle(MAT_Arc)              CurrentArc;
 511   Handle(MAT_Arc)              PrevArc;
 512   Handle(MAT_Arc)              NextArc;
 513   Handle(MAT_Node)             Extremite;
 514   Handle(MAT_ListOfBisector)   BisectorList;
 515   Standard_Real                DistExt;
 516
 517 #ifdef OCCT_DEBUG_Graph
 518   std::cout<<"Construction Arc : Index"<<aBisector->IndexNumber()<<std::endl;
 519   std::cout<<"Construction Arc : Bisector"<<aBisector->BisectorNumber()<<std::endl;
 520 #endif
 521
 522   CurrentArc = new MAT_Arc(IndTabArcs,
 523                            aBisector->BisectorNumber(),
 524                            TheBasicElts(aBisector->FirstEdge()->EdgeNumber()),
 525                            TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
 526                            );
 527   DistExt   = aBisector->DistIssuePoint();
 528   if (DistExt == Precision::Infinite()) {
 529     DistExt = 1.0;
 530 #ifdef OCCT_DEBUG_Graph
 531     std::cout<<"PB:RECUPERATION DISTANCE SUR ISSUEPOINT."<<std::endl;
 532 #endif
 533   }
 534
 535   Extremite = new MAT_Node(aBisector->IssuePoint(),CurrentArc,DistExt);
 536
 537   CurrentArc->SetFirstNode(Extremite);
 538   BisectorList = aBisector->List();
 539   BisectorList->First();
 540
 541   if (!BisectorList->More()) {
 542     // -------------------
 543     // Arc sur le contour.
 544     // -------------------
 545     TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
 546       ->SetStartArc(CurrentArc);
 547     TheBasicElts(aBisector->FirstEdge()->EdgeNumber())
 548       ->SetEndArc(CurrentArc);
 549   }
 550   else {
 551     PrevArc = CurrentArc;
 552
 553     while (BisectorList->More()) {
 554       NextArc = MakeArc(BisectorList->Current(),
 555                         TheBasicElts,
 556                         TheArcs,
 557                         IndTabArcs);
 558       NextArc->SetSecondNode(Extremite);
 559       NextArc->SetNeighbour (MAT_Left ,Extremite,PrevArc);
 560       PrevArc->SetNeighbour (MAT_Right,Extremite,NextArc);
 561       PrevArc  = NextArc;
 562       BisectorList->Next();
 563     }
 564     CurrentArc->SetNeighbour(MAT_Left ,Extremite,NextArc);
 565     NextArc   ->SetNeighbour(MAT_Right,Extremite,CurrentArc);
 566   }
 567
 568 #ifdef OCCT_DEBUG_Graph
 569   std::cout<<"IndTabArcs = "<<IndTabArcs<<std::endl;
 570   std::cout<<"ArcIndex   = "<<CurrentArc->ArcIndex()<<std::endl;
 571 #endif
 572   CurrentArc->SetIndex(IndTabArcs);
 573   TheArcs.Bind(IndTabArcs,CurrentArc);
 574   IndTabArcs          = IndTabArcs + 1;
 575
 576   return CurrentArc;
 577 }
 578
 579
 580
 581
 582