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