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