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