src/MAT2d/MAT2d_Mat2d.cxx

   1 // Created on: 1992-09-22
   2 // Created by: Gilles DEBARBOUILLE
   3 // Copyright (c) 1992-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 <MAT2d_Mat2d.ixx>
  18
  19 #include <MAT_Edge.hxx>
  20 #include <MAT_ListOfEdge.hxx>
  21 #include <MAT_Bisector.hxx>
  22 #include <MAT_ListOfBisector.hxx>
  23 #include <TColStd_DataMapOfIntegerInteger.hxx>
  24 #include <TColStd_Array1OfInteger.hxx>
  25 #include <MAT_DataMapOfIntegerBisector.hxx>
  26 #include <Precision.hxx>
  27 #include <MAT2d_Tool2d.hxx>
  28
  29 //========================================================================
  30 //  function : MAT2d_Mat2d
  31 //  purpose  :
  32 //========================================================================
  33
  34 MAT2d_Mat2d::MAT2d_Mat2d(const Standard_Boolean IsOpenResult)
  35 {
  36   myIsOpenResult = IsOpenResult;
  37   thenumberofbisectors = 0;
  38   thenumberofedges     = 0;
  39 }
  40
  41
  42 //========================================================================
  43 //  function : CreateMat
  44 //  purpose  : Calcul des lieux Bisecteurs.
  45 //
  46 //  Structure de la carte.
  47 //  ======================
  48 //  La carte des lieux bisecteurs se presente sous la forme d un ou plusieurs
  49 //  arbres de bisectrices.
  50 //  ( un arbre, si calcul a l interieur du contour, plusieurs sinon).
  51 //
  52 //  Les branches de plus bas niveau de l arbre separent deux elements voisins
  53 //  du contour.
  54 //
  55 //  Principe de l algorithme.
  56 //  -------------------------
  57 //  l arbre est construit des branches les plus basses vers les plus hautes.
  58 //
  59 //  0 . Calcul des bisectrices entre elements voisins du contour.
  60 //  1 . Elimination de certains element du contour => nouveau contour
  61 //  2 . Retour en 0.
  62 //
  63 //  Principales etapes de l algorithme.
  64 //  ===================================
  65 //
  66 //  etape 1: Initialisation de l algorithme .
  67 //  -----------------------------------------
  68 //   Recuperation via le tool du nombre d'elements sur le contour
  69 //   Initialisation de <theedgelist>, un edge correspond a chaque
  70 //   element du contour.
  71 //
  72 //  etape 2 : Boucle principale.
  73 //  ----------------------------
  74 //    0 - Tant que Nombre d'edge > 1
  75 //
  76 //      1. Pour chaque edge: construction de la bissectrice entre l edge
  77 //         et l edge suivante.
  78 //         La bissectrice est semi_infinie, elle est soit trimmee par le
  79 //         point commun des deux edges, soit par l intersection de deux
  80 //         bissectrices antecedentes.
  81 //
  82 //      2. Intersection des Bisectrices issue du meme edge
  83 //         => une bisectrice est intersectee avec sa voisine a gauche
  84 //            et sa voisine a droite.
  85 //
  86 //      3. Analyse des intersections.
  87 //         Si pas d'intersection entre deux bisectrices B1 et B2
  88 //         - Recherche de l intersection la plus basse de B1 avec les
  89 //           Bisectrices antecedentes a B2 du cote de B1. Soit Bi la
  90 //           bissectrice intersectee. Toutes les bissectrices constituant la
  91 //           branche qui relie B2 a Bi sont marquees a effacer
  92 //         - idem pour B2.
  93 //
  94 //      4. Suppresion des bisectrices a effacer.
  95 //         une bisectrise est a effacer :
  96 //          - Anulation de l intersection dont la bissectrice est issue
  97 //            => Prolongement des deux bisectrices posterieures.
  98 //          - Reinsertion des edge correspondant dans <theedgelist>.
  99 //
 100 //      5. Pour chaque edge, analyse des distances entre les points d inter
 101 //         section et l edge.
 102 //         B1 B2 les bisectrices liee a l edge
 103 //         Soit P0 le point d intersection des bissectrices .
 104 //         Soit P1 le point d intersection de B1 avec son autre voisine .
 105 //         Soit P2 le point d intersection de B2 avec son autre voisine .
 106 //
 107 //         si sur B1 le parametre de P0 < parametre de P1 et
 108 //         si sur B2 le parametre de P0 < parametre de P2
 109 //         alors suppression de l edge de la liste des edges <theedgelist>.
 110 //
 111 //         rq: le parametre sur une bissectirce est croissant par rapport
 112 //         a la distance du point courant aux edges.
 113
 114 //      6. Si aucune edge est elimine alors sortie de la boucle principale.
 115 //
 116 //      7. Retour en 0.
 117 //
 118 //  etape 3 : Creation des racines des arbres de bisectrices.
 119 //  ---------------------------------------------------------
 120 //            Recuperation des bissectrices calculees lors du dernier passage
 121 //            dans la boucle.
 122 //
 123 //========================================================================
 124 void MAT2d_Mat2d::CreateMatOpen(MAT2d_Tool2d& atool)
 125 {
 126
 127 #ifdef ICONTINUE
 128   Standard_Boolean Icontinue;
 129 #endif
 130
 131   Standard_Boolean interrupt = Standard_False;
 132
 133   Handle(MAT_Edge) edgetoremove;
 134   Handle(MAT_Edge) previousedge,currentedge;
 135
 136   Standard_Integer      noofbisectorstoremove;
 137   Handle(MAT_Bisector)  firstbisector,secondbisector;
 138   Handle(MAT_Edge)      edge;
 139   Standard_Integer      intersectionpoint;
 140   Standard_Integer      beginbisector;
 141   Standard_Integer      noofbisectors;
 142
 143   Standard_Integer      NbIterBis = 0;
 144   Standard_Integer      EvenNbIterBis = 10;
 145   TColStd_Array1OfInteger EdgeNumbers(1, EvenNbIterBis+1);
 146   EdgeNumbers.Init(-1);
 147   Standard_Boolean      ToNullifyNoofbisectorstoremove = Standard_False;
 148
 149   Handle(MAT_ListOfBisector) currentbisectorlist;
 150
 151   Handle(MAT_Bisector) bisectortoremove,lastbisector,currentbisector;
 152   Handle(MAT_Bisector) previousbisector;
 153
 154   Standard_Integer     i,j,k,narea,shift,compact,all;
 155   Standard_Integer     noofedges;
 156   Standard_Integer     NumberMaxOfIte;
 157   Standard_Real        toleranceofconfusion;
 158
 159   noofedges            = atool.NumberOfItems();
 160   toleranceofconfusion = atool.ToleranceOfConfusion();
 161   NumberMaxOfIte       = noofedges*noofedges;
 162
 163   TColStd_Array1OfInteger firstarea(0, noofedges);
 164   TColStd_Array1OfInteger lastarea(0, noofedges);
 165   TColStd_Array1OfInteger noofarea(0, noofedges);
 166
 167   Standard_Integer  parama[2];
 168   Standard_Integer  paramb[2];
 169
 170 // -----------------------------------------
 171 // Initialisation et remise a zero des maps.
 172 // -----------------------------------------
 173   bisectoronetoremove.Clear();
 174   bisectortwotoremove.Clear();
 175   typeofbisectortoremove.Clear();
 176   bisectormap.Clear();
 177
 178   isDone        = Standard_True;
 179   noofbisectors = noofedges-1;
 180   beginbisector = 0;
 181
 182 // --------------------------------------------------------------------
 183 // Construction de <theedgelist> un edge correspond a un element simple
 184 // du contour.
 185 // --------------------------------------------------------------------
 186   theedgelist = new MAT_ListOfEdge();
 187
 188   for(i=0; i<noofedges; i++) {
 189     edge = new MAT_Edge();
 190     edge->EdgeNumber(i+1);
 191     edge->Distance(-1);
 192     theedgelist->BackAdd(edge);
 193   }
 194
 195   theedgelist->Loop();
 196
 197 //---------------------------------------------------
 198 // Initialisation des bissectrices issues du contour.
 199 //---------------------------------------------------
 200   Standard_Real Dist;
 201   theedgelist->First();
 202
 203   for(i=0; i<theedgelist->Number()-1; i++) {
 204     bisectormap.Bind(i,new MAT_Bisector());
 205     bisectormap(i)->IndexNumber(i);
 206     bisectormap(i)->FirstEdge(theedgelist->Current());
 207     bisectormap(i)->FirstVector
 208       (atool.TangentBefore(theedgelist->Current()->EdgeNumber(), myIsOpenResult));
 209     theedgelist->Next();
 210     bisectormap(i)->SecondEdge(theedgelist->Current());
 211     bisectormap(i)->IssuePoint
 212       (atool.FirstPoint(theedgelist->Current()->EdgeNumber(),Dist));
 213     bisectormap(i)->DistIssuePoint(Dist);
 214     bisectormap(i)->SecondVector
 215       (atool.TangentAfter(theedgelist->Current()->EdgeNumber(), myIsOpenResult));
 216   }
 217
 218 //----------------------------------------------------
 219 // Affectation a chaque edge de ses deux bissectrices.
 220 //----------------------------------------------------
 221   theedgelist->First();
 222   theedgelist->Current()->FirstBisector(bisectormap(0));
 223   theedgelist->Current()->SecondBisector(bisectormap(0));
 224   theedgelist->Next();
 225
 226   for(i=1; i<theedgelist->Number()-1; i++) {
 227     theedgelist->Current()->FirstBisector
 228       (bisectormap(i-1));
 229     theedgelist->Current()->SecondBisector
 230       (bisectormap(i));
 231     theedgelist->Next();
 232   }
 233
 234   theedgelist->Current()->FirstBisector(bisectormap(theedgelist->Number()-2));
 235   theedgelist->Current()->SecondBisector(bisectormap(theedgelist->Number()-2));
 236
 237 //===========================================================================
 238 //                         Boucle Principale   (etape 2)
 239 //===========================================================================
 240   Standard_Integer NumberOfIte = 0;
 241
 242   while(theedgelist->Number()>1) {
 243
 244
 245     // ------------------------------------------------------------------
 246     //  Creation des geometries des bissectrices via le tool. (etape 2.1)
 247     // -------------------------------------------------------------------
 248
 249     for(i=beginbisector; i<noofbisectors; i++) {
 250
 251       atool.CreateBisector(bisectormap(i));
 252       thenumberofbisectors++;
 253
 254 #ifdef DEBUG_Mat
 255       atool.Dump(bisectormap(i)->BisectorNumber(),1);
 256 #ifdef ICONTINUE
 257       cin>>Icontinue;
 258 #endif
 259 #endif
 260     }
 261
 262     // ---------------------------------------------
 263     //  Condition de sortie de la boucle principale.
 264     // ---------------------------------------------
 265
 266 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:28 2000 Begin
 267     if (theedgelist->Number() < 3)
 268       break;
 269 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:37 2000 End
 270
 271     //---------------------------------------------------
 272     // boucle 2 Tant qu il y a des bisectrices a effacer.
 273     //---------------------------------------------------
 274     for(;;) {
 275       NbIterBis++;
 276
 277       noofbisectorstoremove = 0;
 278       theedgelist->First();
 279       theedgelist->Next();
 280
 281       //--------------------------------------------------------------
 282       // Calcul des intersections des bisectrices voisines.(etape 2.2)
 283       //--------------------------------------------------------------
 284
 285       if (NbIterBis <= EvenNbIterBis+1)
 286         EdgeNumbers(NbIterBis) = theedgelist->Number();
 287       else
 288         {
 289           for (k = 1; k <= EvenNbIterBis; k++)
 290             EdgeNumbers(k) = EdgeNumbers(k+1);
 291           EdgeNumbers(EvenNbIterBis+1) = theedgelist->Number();
 292         }
 293       if (EdgeNumbers(EvenNbIterBis+1) == EdgeNumbers(1))
 294         ToNullifyNoofbisectorstoremove = Standard_True;
 295
 296       for(i=1; i<theedgelist->Number()-1; i++) {
 297         edge = theedgelist->Current();
 298         if(edge->Distance() == -1.) {
 299           firstbisector = edge->FirstBisector();
 300           secondbisector = edge->SecondBisector();
 301           edge->Distance(atool.IntersectBisector
 302                          (firstbisector,secondbisector,intersectionpoint));
 303           edge->IntersectionPoint(intersectionpoint);
 304
 305           if(edge->Distance() == Precision::Infinite()) {
 306             if(firstbisector->IndexNumber() >= beginbisector ||
 307                secondbisector->IndexNumber() >= beginbisector)
 308               Intersect(atool,0,noofbisectorstoremove,
 309                         firstbisector,secondbisector );
 310           }
 311           else {
 312             if(firstbisector->IndexNumber() >= beginbisector) {
 313               Intersect(atool,1,noofbisectorstoremove,
 314                         firstbisector,secondbisector );
 315             }
 316             if(secondbisector->IndexNumber() >= beginbisector) {
 317               Intersect(atool,2,noofbisectorstoremove,
 318                         firstbisector,secondbisector );
 319             }
 320           }
 321         }
 322         theedgelist->Next();
 323       }
 324
 325       //-------------------------------
 326       // Test de sortie de la boucle 2.
 327       //-------------------------------
 328
 329       if (ToNullifyNoofbisectorstoremove)
 330         noofbisectorstoremove = 0;
 331       if(noofbisectorstoremove == 0) break;
 332
 333       //---------------------------------------------------
 334       // Annulation des bissectrices a effacer. (etape 2.4)
 335       //---------------------------------------------------
 336
 337       for(i=0; i<noofbisectorstoremove; i++) {
 338
 339         bisectortoremove = bisectoronetoremove(i);
 340
 341         //---------------------------------------------------------------
 342         // Destruction des bisectrices descendantes de <bisectortoremove>
 343         // On descend dans l arbre jusqu a ce qu on atteigne
 344         // <bisectortwotoremove(i).
 345         //---------------------------------------------------------------
 346
 347         for(;;){
 348
 349 #ifdef DEBUG_Mat
 350           atool.Dump(bisectortoremove->BisectorNumber(),0);
 351 #endif
 352           // ----------------------------------
 353           // Annulation de <bisectortoremove>.
 354           // ----------------------------------
 355           thenumberofbisectors--;
 356           currentbisectorlist = bisectortoremove->List();
 357           currentbisectorlist->First();
 358           currentbisector = currentbisectorlist->FirstItem();
 359           previousedge = currentbisector->FirstEdge();
 360           theedgelist->Init(previousedge);
 361           previousedge->Distance(-1.);
 362           previousedge->FirstBisector()->SecondParameter(Precision::Infinite());
 363           previousedge->SecondBisector()->FirstParameter(Precision::Infinite());
 364
 365           //------------------------------------------
 366           // Annulation des fils de <currentbisector>.
 367           //------------------------------------------
 368
 369           while(currentbisectorlist->More()) {
 370             currentbisector = currentbisectorlist->Current();
 371             currentedge  = currentbisector->SecondEdge();
 372
 373             //---------------------------------------
 374             // Reinsertion de l edge dans le contour.
 375             //---------------------------------------
 376             theedgelist->LinkAfter(currentedge);
 377             theedgelist->Next();
 378
 379             currentedge->FirstBisector(currentbisector);
 380             previousedge->SecondBisector(currentbisector);
 381 #ifdef DEBUG_Mat
 382             atool.Dump(currentbisector->BisectorNumber(),0);
 383 #endif
 384
 385             //------------------------------------------------------
 386             // Annulation de l intersection ie les fils qui
 387             // ont generes l intersection sont prolonges a l infini.
 388             //------------------------------------------------------
 389
 390             currentbisector->FirstParameter (Precision::Infinite());
 391             currentbisector->SecondParameter(Precision::Infinite());
 392
 393             atool.TrimBisector(currentbisector);
 394
 395 #ifdef DEBUG_Mat
 396             atool.Dump(currentbisector->BisectorNumber(),1);
 397 #endif
 398             currentedge->Distance(-1.);
 399             currentedge->FirstBisector()->SecondParameter(Precision::Infinite());
 400             currentedge->SecondBisector()->FirstParameter(Precision::Infinite());
 401
 402             previousedge = currentedge;
 403             currentbisectorlist->Next();
 404           }
 405
 406           theedgelist->Unlink();
 407
 408           //-----------------------------------------------------------
 409           // Test de sortie de la boucle d annulation des bissectrices.
 410           //-----------------------------------------------------------
 411
 412           if(bisectortoremove->BisectorNumber() ==
 413              bisectortwotoremove(i)->BisectorNumber()) break;
 414
 415           //-----------------------
 416           // Descente dans l arbre.
 417           //-----------------------
 418
 419           if(typeofbisectortoremove(i) == 1)
 420             bisectortoremove = bisectortoremove->FirstBisector();
 421           else
 422             bisectortoremove = bisectortoremove->LastBisector();
 423
 424         }  //----------------------------------------------------
 425            // Fin boucle d annulation des bissectrices issue de
 426            // <bisectoronetoremove(i)>.
 427            //----------------------------------------------------
 428
 429       } //------------------------------------------
 430         // Fin boucle d annulation des bissectrices.
 431         //-------------------------------------------
 432
 433 #ifdef ICONTINUE
 434       cin>>Icontinue;
 435 #endif
 436     } //--------------
 437       // Fin Boucle 2.
 438       //--------------
 439
 440     // ----------------------------------------------------------------------
 441     // Analyse des parametres des intersections sur les bisectrices de chaque
 442     // edge et determination des portions de contour a supprimees. (etape 2.5)
 443     // ----------------------------------------------------------------------
 444
 445     theedgelist->First();
 446     theedgelist->Next();
 447
 448     currentbisector = theedgelist->Current()->FirstBisector();
 449     if (currentbisector->FirstParameter()  == Precision::Infinite() &&
 450         currentbisector->SecondParameter() == Precision::Infinite()) {
 451       parama[0] = -1;
 452       paramb[0] = -1;
 453     }
 454     else if(currentbisector->FirstParameter() == Precision::Infinite()) {
 455       parama[0] = -1;
 456       paramb[0] =  1;
 457     }
 458     else if(currentbisector->SecondParameter() == Precision::Infinite()) {
 459       paramb[0] = -1;
 460       parama[0] =  1;
 461     }
 462     else if (atool.Distance(currentbisector,
 463                             currentbisector->FirstParameter(),
 464                             currentbisector->SecondParameter())
 465              > toleranceofconfusion) {
 466       if((currentbisector->FirstParameter() -
 467           currentbisector->SecondParameter())
 468          *currentbisector->Sense() > 0.) {
 469         parama[0] = -1;
 470         paramb[0] =  1;
 471       }
 472       else {
 473         paramb[0] = -1;
 474         parama[0] =  1;
 475       }
 476     }
 477     else {
 478       parama[0] = 1;
 479       paramb[0] = 1;
 480     }
 481
 482     narea = -1;
 483
 484     for(i=1; i<theedgelist->Number()-1; i++) {
 485       currentbisector = theedgelist->Current()->SecondBisector();
 486       if (currentbisector->FirstParameter()  == Precision::Infinite() &&
 487           currentbisector->SecondParameter() == Precision::Infinite()) {
 488         parama[1] = -1;
 489         paramb[1] = -1;
 490       }
 491       else if(currentbisector->FirstParameter() == Precision::Infinite()) {
 492         parama[1] = -1;
 493         paramb[1] =  1;
 494       }
 495       else if(currentbisector->SecondParameter() == Precision::Infinite()) {
 496         paramb[1] = -1;
 497         parama[1] =  1;
 498       }
 499       else if (atool.Distance(currentbisector,
 500                               currentbisector->FirstParameter(),
 501                               currentbisector->SecondParameter())
 502                > toleranceofconfusion) {
 503         if((currentbisector->FirstParameter() -
 504             currentbisector->SecondParameter())
 505            *currentbisector->Sense() > 0.) {
 506           parama[1] = -1;
 507           paramb[1] =  1;
 508         }
 509         else {
 510           paramb[1] = -1;
 511           parama[1] =  1;
 512         }
 513       }
 514       else {
 515         parama[1] = 1;
 516         paramb[1] = 1;
 517       }
 518
 519       //-----------------------------------------------------------------
 520       // Test si l edge est a enlever du contour
 521       // Construction des portions de contour a eliminer.
 522       //
 523       //  narea : nombre de portions continues du contour a eliminer.
 524       //  firstarea[i] : indice premier edge de la portion i.
 525       //  lastarea[i]  : indice dernier edge de la portion i.
 526       //-----------------------------------------------------------------
 527
 528 #ifdef DEBUG_Mat
 529       cout <<" Test sur les parametres pour elimination"<<endl;
 530       cout << " Edge number :"<<theedgelist->Current()->EdgeNumber()<<endl;
 531 #endif
 532
 533       if(paramb[0] > 0 && parama[1] > 0) {
 534
 535 #ifdef DEBUG_Mat
 536       cout <<" A ELIMINER "<<endl;
 537 #endif
 538         if(narea < 0) {
 539           firstarea(++narea) = theedgelist->Index();
 540           lastarea(narea) = firstarea(narea);
 541           noofarea(narea) = 1;
 542         }
 543         else {
 544           if(theedgelist->Index() == lastarea(narea)+1) {
 545             lastarea(narea)++;
 546             noofarea(narea)++;
 547           }
 548           else {
 549             firstarea(++narea) = theedgelist->Index();
 550             lastarea(narea) = firstarea(narea);
 551             noofarea(narea) = 1;
 552           }
 553         }
 554       }
 555       parama[0] = parama[1];
 556       paramb[0] = paramb[1];
 557       theedgelist->Next();
 558
 559     }
 560
 561     compact = 0;
 562     if(narea > 0) {
 563       if(lastarea(narea) == theedgelist->Number() && firstarea(0) == 1) {
 564         firstarea(0) = firstarea(narea);
 565         noofarea(0) = noofarea(0)+noofarea(narea);
 566         compact = noofarea(narea);
 567         narea--;
 568       }
 569     }
 570
 571     narea++;
 572
 573     //------------------------------------------------------------------
 574     // Sortie de la boucle principale si il n y a pas d edge a eliminer.
 575     // (etape 2.6)
 576     //------------------------------------------------------------------
 577     if(narea == 0) {
 578       interrupt = Standard_True;
 579       break;
 580     }
 581
 582
 583     //----------------------------------------------------------------
 584     // Elimination des edges a enlever du contour
 585     // => Mise a jour du nouveau contour.
 586     // => Creation des bissectrices entre les nouvelles edges voisines.
 587     //----------------------------------------------------------------
 588
 589     beginbisector = noofbisectors;
 590     shift = 0;
 591     all = 0;
 592     if(narea == 1 && noofarea(0) == theedgelist->Number()) all = 1;
 593
 594     for(i=0; i<narea; i++) {
 595       if(i == 1)shift = shift-compact;
 596       theedgelist->First();
 597       theedgelist->Next();
 598       edgetoremove = theedgelist->Brackets(firstarea(i)-shift);
 599
 600       edgetoremove->FirstBisector()->EndPoint(edgetoremove
 601                                               ->IntersectionPoint());
 602
 603 #ifdef DEBUG_Mat
 604       atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),0);
 605 #endif
 606
 607       edgetoremove->FirstBisector()->FirstParameter
 608         (edgetoremove->FirstBisector()->SecondParameter());
 609
 610 #ifdef DEBUG_Mat
 611       if(atool.TrimBisector(edgetoremove->FirstBisector()))
 612         atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),1);
 613 #else
 614       atool.TrimBisector(edgetoremove->FirstBisector());
 615 #endif
 616
 617       bisectormap.Bind(noofbisectors,new MAT_Bisector());
 618       bisectormap(noofbisectors)->IndexNumber(noofbisectors);
 619       bisectormap(noofbisectors)->DistIssuePoint(edgetoremove->Distance());
 620       bisectormap(noofbisectors)->IssuePoint(edgetoremove
 621                                                 ->IntersectionPoint());
 622       bisectormap(noofbisectors)->FirstEdge(theedgelist->PreviousItem());
 623       bisectormap(noofbisectors)->AddBisector(edgetoremove
 624                                                  ->FirstBisector());
 625
 626       for(j=0; j<noofarea(i); j++) {
 627         theedgelist->Unlink();
 628         theedgelist->Next();
 629         shift++;
 630
 631 #ifdef DEBUG_Mat
 632         cout<<" Suppression de l'arete : "<<edgetoremove->EdgeNumber()<<endl;
 633 #endif
 634
 635         if(all == 0 || j+1 != noofarea(i)) {
 636           bisectormap(noofbisectors)->AddBisector(edgetoremove
 637                                                      ->SecondBisector());
 638         }
 639         edgetoremove->SecondBisector()->EndPoint(edgetoremove
 640                                                  ->IntersectionPoint());
 641
 642 #ifdef DEBUG_Mat
 643         atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),0);
 644 #endif
 645
 646         edgetoremove->SecondBisector()->SecondParameter
 647           (edgetoremove->SecondBisector()->FirstParameter());
 648 #ifdef DEBUG_Mat
 649         if(atool.TrimBisector(edgetoremove->SecondBisector()))
 650           atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),1);
 651 #else
 652         atool.TrimBisector(edgetoremove->SecondBisector());
 653 #endif
 654         edgetoremove = theedgelist->Current();
 655       }
 656       bisectormap(noofbisectors)->SecondEdge(theedgelist->Current());
 657
 658       theedgelist->PreviousItem()
 659         ->SecondBisector(bisectormap(noofbisectors));
 660       theedgelist->Current()->FirstBisector(bisectormap(noofbisectors));
 661
 662       bisectormap(noofbisectors)->FirstVector
 663         (atool.Tangent
 664          (bisectormap(noofbisectors)->FirstBisector()
 665           ->BisectorNumber()));
 666
 667       bisectormap(noofbisectors)->SecondVector
 668         (atool.Tangent
 669          (bisectormap(noofbisectors)->LastBisector()
 670           ->BisectorNumber()));
 671
 672       noofbisectors++;
 673
 674       theedgelist->PreviousItem()->Distance(-1);
 675       theedgelist->Current()->Distance(-1);
 676
 677       theedgelist->PreviousItem()->FirstBisector()
 678         ->SecondParameter(Precision::Infinite());
 679       theedgelist->Current()->SecondBisector()->FirstParameter(Precision::Infinite());
 680     }
 681
 682     //-----------------------------------------------------------------------
 683     // Test sur le nombre d iterations :
 684     // A chaque iteration est elimine un element du contour qui ne sera plus
 685     // reinsere par la suite => le nombre d iterartions doit etre < au nombre
 686     // d elements.
 687     // Le nombre d iteration maximum est fixe a numberofedges*numberofedges.
 688     //-----------------------------------------------------------------------
 689     if (NumberOfIte > NumberMaxOfIte) {
 690       isDone = Standard_False;             //Echec calcul de la carte.
 691       break;
 692     }
 693     NumberOfIte++;
 694
 695   }  //===============================================
 696      //            Fin Boucle Principale.
 697      //===============================================
 698
 699   //----------
 700   // etape 3.
 701   //----------
 702
 703
 704   //----------------------------------------------
 705   // interupt = True => bissectrices semi_infinies.
 706   //----------------------------------------------
 707
 708   if(interrupt)
 709     semiInfinite = Standard_True;
 710   else {
 711     semiInfinite = Standard_False;
 712
 713     //------------------------------------------------------------------
 714     // Si le nombre d edge > 1 => le nombre d edge = 2
 715     //              (cf test sortie boucle principale)
 716     // Les deux dernieres bisectrices separent les memes edges .
 717     // Soit elles sont confondues si calcul a l interieur, soit elles
 718     // sont semi-Infinies (exemple : contour compose seulement de deux
 719     // arcs de cercles).
 720     //------------------------------------------------------------------
 721
 722     if(theedgelist->Number() > 1) { //Now this branch is never reachable
 723                                     //because the case edgenumber = 2 is processed in the main loop
 724       theedgelist->First();
 725       edge = theedgelist->Current();
 726       if(edge->FirstBisector()->IndexNumber() == noofbisectors-1) {
 727 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
 728         if (atool.TrimBisector(edge->SecondBisector(),
 729                                edge->FirstBisector()->IssuePoint())) {
 730           if (edge->SecondBisector()->EndPoint() == 0)
 731             edge->SecondBisector()->EndPoint(edge->FirstBisector()->IssuePoint());
 732           bisectormap(noofbisectors-1)->AddBisector(edge->SecondBisector());
 733         } else
 734           semiInfinite = Standard_True;
 735 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
 736       }
 737       else {
 738 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
 739         if (atool.TrimBisector(edge->FirstBisector(),
 740                                edge->SecondBisector()->IssuePoint())) {
 741           if (edge->FirstBisector()->EndPoint() == 0)
 742             edge->FirstBisector()->EndPoint(edge->SecondBisector()->IssuePoint());
 743           bisectormap(noofbisectors-1)->AddBisector(edge->FirstBisector());
 744         } else
 745           semiInfinite = Standard_True;
 746 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
 747       }
 748       if (!semiInfinite) {
 749         thenumberofbisectors--;
 750         bisectormap(noofbisectors-1)->SecondEdge(edge);
 751         bisectormap(noofbisectors-1)->BisectorNumber(-1);
 752       }
 753     }
 754   }
 755
 756   if(semiInfinite) {
 757     beginbisector = noofbisectors;
 758     theedgelist->First();
 759     for(i=1; i<theedgelist->Number(); i++) {
 760       edge = theedgelist->Current();
 761       bisectormap.Bind(noofbisectors,edge->SecondBisector());
 762       noofbisectors++;
 763       theedgelist->Next();
 764     }
 765
 766   }
 767
 768   //---------------------------
 769   // Recuperations des racines.
 770   //---------------------------
 771
 772   roots = new MAT_ListOfBisector;
 773
 774   if (bisectormap(noofbisectors-1)->BisectorNumber() == -1) {
 775     roots = bisectormap(noofbisectors-1)->List();
 776     roots->First();
 777     roots->Current()->FirstEdge()
 778       ->Distance(bisectormap(noofbisectors-1)->DistIssuePoint());
 779   }
 780   else {
 781     for (i=beginbisector;i<noofbisectors;i++) {
 782       roots->BackAdd(bisectormap(i));
 783     }
 784   }
 785
 786 }
 787
 788 void MAT2d_Mat2d::CreateMat(MAT2d_Tool2d& atool)
 789 {
 790
 791 #ifdef ICONTINUE
 792   Standard_Boolean Icontinue;
 793 #endif
 794
 795   Standard_Boolean interrupt = Standard_False;
 796
 797   Handle(MAT_Edge) edgetoremove;
 798   Handle(MAT_Edge) previousedge,currentedge;
 799
 800   Standard_Integer      noofbisectorstoremove;
 801   Handle(MAT_Bisector)  firstbisector,secondbisector;
 802   Handle(MAT_Edge)      edge;
 803   Standard_Integer      intersectionpoint;
 804   Standard_Integer      beginbisector;
 805   Standard_Integer      noofbisectors;
 806
 807   Standard_Integer      NbIterBis = 0;
 808   Standard_Integer      EvenNbIterBis = 10;
 809   TColStd_Array1OfInteger EdgeNumbers(1, EvenNbIterBis+1);
 810   EdgeNumbers.Init(-1);
 811   Standard_Boolean      ToNullifyNoofbisectorstoremove = Standard_False;
 812
 813   Handle(MAT_ListOfBisector) currentbisectorlist;
 814
 815   Handle(MAT_Bisector) bisectortoremove,lastbisector,currentbisector;
 816   Handle(MAT_Bisector) previousbisector;
 817
 818   Standard_Integer     i,j,k,narea,shift,compact,all;
 819   Standard_Integer     noofedges;
 820   Standard_Integer     NumberMaxOfIte;
 821   Standard_Real        toleranceofconfusion;
 822
 823   noofedges            = atool.NumberOfItems();
 824   toleranceofconfusion = atool.ToleranceOfConfusion();
 825   NumberMaxOfIte       = noofedges*noofedges;
 826
 827   TColStd_Array1OfInteger firstarea(0, noofedges);
 828   TColStd_Array1OfInteger lastarea(0, noofedges);
 829   TColStd_Array1OfInteger noofarea(0, noofedges);
 830
 831   Standard_Integer  parama[2];
 832   Standard_Integer  paramb[2];
 833
 834 // -----------------------------------------
 835 // Initialisation et remise a zero des maps.
 836 // -----------------------------------------
 837   bisectoronetoremove.Clear();
 838   bisectortwotoremove.Clear();
 839   typeofbisectortoremove.Clear();
 840   bisectormap.Clear();
 841
 842   isDone        = Standard_True;
 843   noofbisectors = noofedges;
 844   beginbisector = 0;
 845
 846 // --------------------------------------------------------------------
 847 // Construction de <theedgelist> un edge correspond a un element simple
 848 // du contour.
 849 // --------------------------------------------------------------------
 850   theedgelist = new MAT_ListOfEdge();
 851
 852   for(i=0; i<noofedges; i++) {
 853     edge = new MAT_Edge();
 854     edge->EdgeNumber(i+1);
 855     edge->Distance(-1);
 856     theedgelist->BackAdd(edge);
 857   }
 858
 859   theedgelist->Loop();
 860
 861 //---------------------------------------------------
 862 // Initialisation des bissectrices issues du contour.
 863 //---------------------------------------------------
 864   Standard_Real Dist;
 865   theedgelist->First();
 866
 867   for(i=0; i<theedgelist->Number(); i++) {
 868     bisectormap.Bind(i,new MAT_Bisector());
 869     bisectormap(i)->IndexNumber(i);
 870     bisectormap(i)->FirstEdge(theedgelist->Current());
 871     bisectormap(i)->FirstVector
 872       (atool.TangentBefore(theedgelist->Current()->EdgeNumber(), myIsOpenResult));
 873     theedgelist->Next();
 874     bisectormap(i)->SecondEdge(theedgelist->Current());
 875     bisectormap(i)->IssuePoint
 876       (atool.FirstPoint(theedgelist->Current()->EdgeNumber(),Dist));
 877     bisectormap(i)->DistIssuePoint(Dist);
 878     bisectormap(i)->SecondVector
 879       (atool.TangentAfter(theedgelist->Current()->EdgeNumber(), myIsOpenResult));
 880   }
 881
 882 //----------------------------------------------------
 883 // Affectation a chaque edge de ses deux bissectrices.
 884 //----------------------------------------------------
 885   theedgelist->First();
 886
 887   for(i=0; i<theedgelist->Number(); i++) {
 888     theedgelist->Current()->FirstBisector
 889       (bisectormap((i-1+noofbisectors)%noofbisectors));
 890     theedgelist->Current()->SecondBisector
 891       (bisectormap(i));
 892     theedgelist->Next();
 893   }
 894
 895 //===========================================================================
 896 //                         Boucle Principale   (etape 2)
 897 //===========================================================================
 898   Standard_Integer NumberOfIte = 0;
 899
 900   while(theedgelist->Number()>1) {
 901
 902
 903     // ------------------------------------------------------------------
 904     //  Creation des geometries des bissectrices via le tool. (etape 2.1)
 905     // -------------------------------------------------------------------
 906
 907     for(i=beginbisector; i<noofbisectors; i++) {
 908
 909       atool.CreateBisector(bisectormap(i));
 910       thenumberofbisectors++;
 911
 912 #ifdef DEBUG_Mat
 913       atool.Dump(bisectormap(i)->BisectorNumber(),1);
 914 #ifdef ICONTINUE
 915       cin>>Icontinue;
 916 #endif
 917 #endif
 918     }
 919
 920     // ---------------------------------------------
 921     //  Condition de sortie de la boucle principale.
 922     // ---------------------------------------------
 923
 924 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:28 2000 Begin
 925     if (theedgelist->Number() < 3)
 926       break;
 927 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:37 2000 End
 928
 929     //---------------------------------------------------
 930     // boucle 2 Tant qu il y a des bisectrices a effacer.
 931     //---------------------------------------------------
 932     for(;;) {
 933       NbIterBis++;
 934
 935       noofbisectorstoremove = 0;
 936       theedgelist->First();
 937
 938       //--------------------------------------------------------------
 939       // Calcul des intersections des bisectrices voisines.(etape 2.2)
 940       //--------------------------------------------------------------
 941
 942       if (NbIterBis <= EvenNbIterBis+1)
 943         EdgeNumbers(NbIterBis) = theedgelist->Number();
 944       else
 945         {
 946           for (k = 1; k <= EvenNbIterBis; k++)
 947             EdgeNumbers(k) = EdgeNumbers(k+1);
 948           EdgeNumbers(EvenNbIterBis+1) = theedgelist->Number();
 949         }
 950       if (EdgeNumbers(EvenNbIterBis+1) == EdgeNumbers(1))
 951         ToNullifyNoofbisectorstoremove = Standard_True;
 952
 953       for(i=0; i<theedgelist->Number(); i++) {
 954         edge = theedgelist->Current();
 955         if(edge->Distance() == -1.) {
 956           firstbisector = edge->FirstBisector();
 957           secondbisector = edge->SecondBisector();
 958           edge->Distance(atool.IntersectBisector
 959                          (firstbisector,secondbisector,intersectionpoint));
 960           edge->IntersectionPoint(intersectionpoint);
 961
 962           if(edge->Distance() == Precision::Infinite()) {
 963             if(firstbisector->IndexNumber() >= beginbisector ||
 964                secondbisector->IndexNumber() >= beginbisector)
 965               Intersect(atool,0,noofbisectorstoremove,
 966                         firstbisector,secondbisector );
 967           }
 968           else {
 969             if(firstbisector->IndexNumber() >= beginbisector) {
 970               Intersect(atool,1,noofbisectorstoremove,
 971                         firstbisector,secondbisector );
 972             }
 973             if(secondbisector->IndexNumber() >= beginbisector) {
 974               Intersect(atool,2,noofbisectorstoremove,
 975                         firstbisector,secondbisector );
 976             }
 977           }
 978         }
 979         theedgelist->Next();
 980       }
 981
 982       //-------------------------------
 983       // Test de sortie de la boucle 2.
 984       //-------------------------------
 985
 986       if (ToNullifyNoofbisectorstoremove)
 987         noofbisectorstoremove = 0;
 988       if(noofbisectorstoremove == 0) break;
 989
 990       //---------------------------------------------------
 991       // Annulation des bissectrices a effacer. (etape 2.4)
 992       //---------------------------------------------------
 993
 994       for(i=0; i<noofbisectorstoremove; i++) {
 995
 996         bisectortoremove = bisectoronetoremove(i);
 997
 998         //---------------------------------------------------------------
 999         // Destruction des bisectrices descendantes de <bisectortoremove>
1000         // On descend dans l arbre jusqu a ce qu on atteigne
1001         // <bisectortwotoremove(i).
1002         //---------------------------------------------------------------
1003
1004         for(;;){
1005
1006 #ifdef DEBUG_Mat
1007           atool.Dump(bisectortoremove->BisectorNumber(),0);
1008 #endif
1009           // ----------------------------------
1010           // Annulation de <bisectortoremove>.
1011           // ----------------------------------
1012           thenumberofbisectors--;
1013           currentbisectorlist = bisectortoremove->List();
1014           currentbisectorlist->First();
1015           currentbisector = currentbisectorlist->FirstItem();
1016           previousedge = currentbisector->FirstEdge();
1017           theedgelist->Init(previousedge);
1018           previousedge->Distance(-1.);
1019           previousedge->FirstBisector()->SecondParameter(Precision::Infinite());
1020           previousedge->SecondBisector()->FirstParameter(Precision::Infinite());
1021
1022           //------------------------------------------
1023           // Annulation des fils de <currentbisector>.
1024           //------------------------------------------
1025
1026           while(currentbisectorlist->More()) {
1027             currentbisector = currentbisectorlist->Current();
1028             currentedge  = currentbisector->SecondEdge();
1029
1030             //---------------------------------------
1031             // Reinsertion de l edge dans le contour.
1032             //---------------------------------------
1033             theedgelist->LinkAfter(currentedge);
1034             theedgelist->Next();
1035
1036             currentedge->FirstBisector(currentbisector);
1037             previousedge->SecondBisector(currentbisector);
1038 #ifdef DEBUG_Mat
1039             atool.Dump(currentbisector->BisectorNumber(),0);
1040 #endif
1041
1042             //------------------------------------------------------
1043             // Annulation de l intersection ie les fils qui
1044             // ont generes l intersection sont prolonges a l infini.
1045             //------------------------------------------------------
1046
1047             currentbisector->FirstParameter (Precision::Infinite());
1048             currentbisector->SecondParameter(Precision::Infinite());
1049
1050             atool.TrimBisector(currentbisector);
1051
1052 #ifdef DEBUG_Mat
1053             atool.Dump(currentbisector->BisectorNumber(),1);
1054 #endif
1055             currentedge->Distance(-1.);
1056             currentedge->FirstBisector()->SecondParameter(Precision::Infinite());
1057             currentedge->SecondBisector()->FirstParameter(Precision::Infinite());
1058
1059             previousedge = currentedge;
1060             currentbisectorlist->Next();
1061           }
1062
1063           theedgelist->Unlink();
1064
1065           //-----------------------------------------------------------
1066           // Test de sortie de la boucle d annulation des bissectrices.
1067           //-----------------------------------------------------------
1068
1069           if(bisectortoremove->BisectorNumber() ==
1070              bisectortwotoremove(i)->BisectorNumber()) break;
1071
1072           //-----------------------
1073           // Descente dans l arbre.
1074           //-----------------------
1075
1076           if(typeofbisectortoremove(i) == 1)
1077             bisectortoremove = bisectortoremove->FirstBisector();
1078           else
1079             bisectortoremove = bisectortoremove->LastBisector();
1080
1081         }  //----------------------------------------------------
1082            // Fin boucle d annulation des bissectrices issue de
1083            // <bisectoronetoremove(i)>.
1084            //----------------------------------------------------
1085
1086       } //------------------------------------------
1087         // Fin boucle d annulation des bissectrices.
1088         //-------------------------------------------
1089
1090 #ifdef ICONTINUE
1091       cin>>Icontinue;
1092 #endif
1093     } //--------------
1094       // Fin Boucle 2.
1095       //--------------
1096
1097     // ----------------------------------------------------------------------
1098     // Analyse des parametres des intersections sur les bisectrices de chaque
1099     // edge et determination des portions de contour a supprimees. (etape 2.5)
1100     // ----------------------------------------------------------------------
1101
1102     theedgelist->First();
1103
1104     currentbisector = theedgelist->Current()->FirstBisector();
1105     if (currentbisector->FirstParameter()  == Precision::Infinite() &&
1106         currentbisector->SecondParameter() == Precision::Infinite()) {
1107       parama[0] = -1;
1108       paramb[0] = -1;
1109     }
1110     else if(currentbisector->FirstParameter() == Precision::Infinite()) {
1111       parama[0] = -1;
1112       paramb[0] =  1;
1113     }
1114     else if(currentbisector->SecondParameter() == Precision::Infinite()) {
1115       paramb[0] = -1;
1116       parama[0] =  1;
1117     }
1118     else if (atool.Distance(currentbisector,
1119                             currentbisector->FirstParameter(),
1120                             currentbisector->SecondParameter())
1121              > toleranceofconfusion) {
1122       if((currentbisector->FirstParameter() -
1123           currentbisector->SecondParameter())
1124          *currentbisector->Sense() > 0.) {
1125         parama[0] = -1;
1126         paramb[0] =  1;
1127       }
1128       else {
1129         paramb[0] = -1;
1130         parama[0] =  1;
1131       }
1132     }
1133     else {
1134       parama[0] = 1;
1135       paramb[0] = 1;
1136     }
1137
1138     narea = -1;
1139
1140     for(i=0; i<theedgelist->Number(); i++) {
1141       currentbisector = theedgelist->Current()->SecondBisector();
1142       if (currentbisector->FirstParameter()  == Precision::Infinite() &&
1143           currentbisector->SecondParameter() == Precision::Infinite()) {
1144         parama[1] = -1;
1145         paramb[1] = -1;
1146       }
1147       else if(currentbisector->FirstParameter() == Precision::Infinite()) {
1148         parama[1] = -1;
1149         paramb[1] =  1;
1150       }
1151       else if(currentbisector->SecondParameter() == Precision::Infinite()) {
1152         paramb[1] = -1;
1153         parama[1] =  1;
1154       }
1155       else if (atool.Distance(currentbisector,
1156                               currentbisector->FirstParameter(),
1157                               currentbisector->SecondParameter())
1158                > toleranceofconfusion) {
1159         if((currentbisector->FirstParameter() -
1160             currentbisector->SecondParameter())
1161            *currentbisector->Sense() > 0.) {
1162           parama[1] = -1;
1163           paramb[1] =  1;
1164         }
1165         else {
1166           paramb[1] = -1;
1167           parama[1] =  1;
1168         }
1169       }
1170       else {
1171         parama[1] = 1;
1172         paramb[1] = 1;
1173       }
1174
1175       //-----------------------------------------------------------------
1176       // Test si l edge est a enlever du contour
1177       // Construction des portions de contour a eliminer.
1178       //
1179       //  narea : nombre de portions continues du contour a eliminer.
1180       //  firstarea[i] : indice premier edge de la portion i.
1181       //  lastarea[i]  : indice dernier edge de la portion i.
1182       //-----------------------------------------------------------------
1183
1184 #ifdef DEBUG_Mat
1185       cout <<" Test sur les parametres pour elimination"<<endl;
1186       cout << " Edge number :"<<theedgelist->Current()->EdgeNumber()<<endl;
1187 #endif
1188
1189       if(paramb[0] > 0 && parama[1] > 0) {
1190
1191 #ifdef DEBUG_Mat
1192       cout <<" A ELIMINER "<<endl;
1193 #endif
1194         if(narea < 0) {
1195           firstarea(++narea) = theedgelist->Index();
1196           lastarea(narea) = firstarea(narea);
1197           noofarea(narea) = 1;
1198         }
1199         else {
1200           if(theedgelist->Index() == lastarea(narea)+1) {
1201             lastarea(narea)++;
1202             noofarea(narea)++;
1203           }
1204           else {
1205             firstarea(++narea) = theedgelist->Index();
1206             lastarea(narea) = firstarea(narea);
1207             noofarea(narea) = 1;
1208           }
1209         }
1210       }
1211       parama[0] = parama[1];
1212       paramb[0] = paramb[1];
1213       theedgelist->Next();
1214
1215     }
1216
1217     compact = 0;
1218     if(narea > 0) {
1219       if(lastarea(narea) == theedgelist->Number() && firstarea(0) == 1) {
1220         firstarea(0) = firstarea(narea);
1221         noofarea(0) = noofarea(0)+noofarea(narea);
1222         compact = noofarea(narea);
1223         narea--;
1224       }
1225     }
1226
1227     narea++;
1228
1229     //------------------------------------------------------------------
1230     // Sortie de la boucle principale si il n y a pas d edge a eliminer.
1231     // (etape 2.6)
1232     //------------------------------------------------------------------
1233     if(narea == 0) {
1234       interrupt = Standard_True;
1235       break;
1236     }
1237
1238
1239     //----------------------------------------------------------------
1240     // Elimination des edges a enlever du contour
1241     // => Mise a jour du nouveau contour.
1242     // => Creation des bissectrices entre les nouvelles edges voisines.
1243     //----------------------------------------------------------------
1244
1245     beginbisector = noofbisectors;
1246     shift = 0;
1247     all = 0;
1248     if(narea == 1 && noofarea(0) == theedgelist->Number()) all = 1;
1249
1250     for(i=0; i<narea; i++) {
1251       if(i == 1)shift = shift-compact;
1252       theedgelist->First();
1253       edgetoremove = theedgelist->Brackets(firstarea(i)-shift);
1254
1255       edgetoremove->FirstBisector()->EndPoint(edgetoremove
1256                                               ->IntersectionPoint());
1257
1258 #ifdef DEBUG_Mat
1259       atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),0);
1260 #endif
1261
1262       edgetoremove->FirstBisector()->FirstParameter
1263         (edgetoremove->FirstBisector()->SecondParameter());
1264
1265 #ifdef DEBUG_Mat
1266       if(atool.TrimBisector(edgetoremove->FirstBisector()))
1267         atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),1);
1268 #else
1269       atool.TrimBisector(edgetoremove->FirstBisector());
1270 #endif
1271
1272       bisectormap.Bind(noofbisectors,new MAT_Bisector());
1273       bisectormap(noofbisectors)->IndexNumber(noofbisectors);
1274       bisectormap(noofbisectors)->DistIssuePoint(edgetoremove->Distance());
1275       bisectormap(noofbisectors)->IssuePoint(edgetoremove
1276                                                 ->IntersectionPoint());
1277       bisectormap(noofbisectors)->FirstEdge(theedgelist->PreviousItem());
1278       bisectormap(noofbisectors)->AddBisector(edgetoremove
1279                                                  ->FirstBisector());
1280
1281       for(j=0; j<noofarea(i); j++) {
1282         theedgelist->Unlink();
1283         theedgelist->Next();
1284         shift++;
1285
1286 #ifdef DEBUG_Mat
1287         cout<<" Suppression de l'arete : "<<edgetoremove->EdgeNumber()<<endl;
1288 #endif
1289
1290         if(all == 0 || j+1 != noofarea(i)) {
1291           bisectormap(noofbisectors)->AddBisector(edgetoremove
1292                                                      ->SecondBisector());
1293         }
1294         edgetoremove->SecondBisector()->EndPoint(edgetoremove
1295                                                  ->IntersectionPoint());
1296
1297 #ifdef DEBUG_Mat
1298         atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),0);
1299 #endif
1300
1301         edgetoremove->SecondBisector()->SecondParameter
1302           (edgetoremove->SecondBisector()->FirstParameter());
1303 #ifdef DEBUG_Mat
1304         if(atool.TrimBisector(edgetoremove->SecondBisector()))
1305           atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),1);
1306 #else
1307         atool.TrimBisector(edgetoremove->SecondBisector());
1308 #endif
1309         edgetoremove = theedgelist->Current();
1310       }
1311       bisectormap(noofbisectors)->SecondEdge(theedgelist->Current());
1312
1313       theedgelist->PreviousItem()
1314         ->SecondBisector(bisectormap(noofbisectors));
1315       theedgelist->Current()->FirstBisector(bisectormap(noofbisectors));
1316
1317       bisectormap(noofbisectors)->FirstVector
1318         (atool.Tangent
1319          (bisectormap(noofbisectors)->FirstBisector()
1320           ->BisectorNumber()));
1321
1322       bisectormap(noofbisectors)->SecondVector
1323         (atool.Tangent
1324          (bisectormap(noofbisectors)->LastBisector()
1325           ->BisectorNumber()));
1326
1327       noofbisectors++;
1328
1329       theedgelist->PreviousItem()->Distance(-1);
1330       theedgelist->Current()->Distance(-1);
1331
1332       theedgelist->PreviousItem()->FirstBisector()
1333         ->SecondParameter(Precision::Infinite());
1334       theedgelist->Current()->SecondBisector()->FirstParameter(Precision::Infinite());
1335     }
1336
1337     //-----------------------------------------------------------------------
1338     // Test sur le nombre d iterations :
1339     // A chaque iteration est elimine un element du contour qui ne sera plus
1340     // reinsere par la suite => le nombre d iterartions doit etre < au nombre
1341     // d elements.
1342     // Le nombre d iteration maximum est fixe a numberofedges*numberofedges.
1343     //-----------------------------------------------------------------------
1344     if (NumberOfIte > NumberMaxOfIte) {
1345       isDone = Standard_False;             //Echec calcul de la carte.
1346       break;
1347     }
1348     NumberOfIte++;
1349
1350   }  //===============================================
1351      //            Fin Boucle Principale.
1352      //===============================================
1353
1354   //----------
1355   // etape 3.
1356   //----------
1357
1358
1359   //----------------------------------------------
1360   // interupt = True => bissectrices semi_infinies.
1361   //----------------------------------------------
1362
1363   if(interrupt)
1364     semiInfinite = Standard_True;
1365   else {
1366     semiInfinite = Standard_False;
1367
1368     //------------------------------------------------------------------
1369     // Si le nombre d edge > 1 => le nombre d edge = 2
1370     //              (cf test sortie boucle principale)
1371     // Les deux dernieres bisectrices separent les memes edges .
1372     // Soit elles sont confondues si calcul a l interieur, soit elles
1373     // sont semi-Infinies (exemple : contour compose seulement de deux
1374     // arcs de cercles).
1375     //------------------------------------------------------------------
1376
1377     if(theedgelist->Number() > 1) { //Now this branch is never reachable
1378                                     //because the case edgenumber = 2 is processed in the main loop
1379       theedgelist->First();
1380       edge = theedgelist->Current();
1381       if(edge->FirstBisector()->IndexNumber() == noofbisectors-1) {
1382 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
1383         if (atool.TrimBisector(edge->SecondBisector(),
1384                                edge->FirstBisector()->IssuePoint())) {
1385           if (edge->SecondBisector()->EndPoint() == 0)
1386             edge->SecondBisector()->EndPoint(edge->FirstBisector()->IssuePoint());
1387           bisectormap(noofbisectors-1)->AddBisector(edge->SecondBisector());
1388         } else
1389           semiInfinite = Standard_True;
1390 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
1391       }
1392       else {
1393 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
1394         if (atool.TrimBisector(edge->FirstBisector(),
1395                                edge->SecondBisector()->IssuePoint())) {
1396           if (edge->FirstBisector()->EndPoint() == 0)
1397             edge->FirstBisector()->EndPoint(edge->SecondBisector()->IssuePoint());
1398           bisectormap(noofbisectors-1)->AddBisector(edge->FirstBisector());
1399         } else
1400           semiInfinite = Standard_True;
1401 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
1402       }
1403       if (!semiInfinite) {
1404         thenumberofbisectors--;
1405         bisectormap(noofbisectors-1)->SecondEdge(edge);
1406         bisectormap(noofbisectors-1)->BisectorNumber(-1);
1407       }
1408     }
1409   }
1410   if(semiInfinite) {
1411     beginbisector = noofbisectors;
1412     theedgelist->First();
1413     for(i=0; i<theedgelist->Number(); i++) {
1414       edge = theedgelist->Current();
1415       bisectormap.Bind(noofbisectors,edge->SecondBisector());
1416       noofbisectors++;
1417       theedgelist->Next();
1418     }
1419
1420   }
1421
1422   //---------------------------
1423   // Recuperations des racines.
1424   //---------------------------
1425
1426   roots = new MAT_ListOfBisector;
1427
1428   if (bisectormap(noofbisectors-1)->BisectorNumber() == -1) {
1429     roots = bisectormap(noofbisectors-1)->List();
1430     roots->First();
1431     roots->Current()->FirstEdge()
1432       ->Distance(bisectormap(noofbisectors-1)->DistIssuePoint());
1433   }
1434   else {
1435     for (i=beginbisector;i<noofbisectors;i++) {
1436       roots->BackAdd(bisectormap(i));
1437     }
1438   }
1439
1440 }
1441
1442 //========================================================================
1443 //  function : LoadBisectorsToRemove
1444 //  purpose  : Chargement des bisectrices a effacer.
1445 //========================================================================
1446 void MAT2d_Mat2d::LoadBisectorsToRemove
1447   (      Standard_Integer&     noofbisectorstoremove,
1448    const Standard_Real         distance1,
1449    const Standard_Real         distance2,
1450    const Handle(MAT_Bisector)& firstbisectortoremove1,
1451    const Handle(MAT_Bisector)& firstbisectortoremove2,
1452    const Handle(MAT_Bisector)& lastbisectortoremove1,
1453    const Handle(MAT_Bisector)& lastbisectortoremove2  )
1454 {
1455
1456   Standard_Integer found,index;
1457   Handle(MAT_Bisector) firstbisectortoremove[2];
1458   Handle(MAT_Bisector) lastbisectortoremove[2];
1459
1460   firstbisectortoremove[0] = firstbisectortoremove1;
1461   firstbisectortoremove[1] = firstbisectortoremove2;
1462   lastbisectortoremove[0]  = lastbisectortoremove1;
1463   lastbisectortoremove[1]  = lastbisectortoremove2;
1464
1465   if     (distance1  < Precision::Infinite() &&
1466           distance2 == Precision::Infinite()    )   index =  0;
1467   else if(distance2  < Precision::Infinite() &&
1468           distance1 == Precision::Infinite()    )   index =  1;
1469   else                                              index = -1;
1470
1471   if(index != -1) {
1472     found = noofbisectorstoremove;
1473     for(int j=0; j<noofbisectorstoremove; j++) {
1474       if(bisectoronetoremove(j)->BisectorNumber() ==
1475          firstbisectortoremove[index]->BisectorNumber()) {
1476         found = j;
1477         if(bisectortwotoremove(j)->BisectorNumber() <
1478            lastbisectortoremove[index]->BisectorNumber())found = -1;
1479         break;
1480       }
1481     }
1482
1483     if(found != -1) {
1484 #ifdef DEBUG_Mat
1485       cout<<" first last bisector to remove :"<<
1486         firstbisectortoremove[index]->BisectorNumber()<<" "<<
1487           lastbisectortoremove[index]->BisectorNumber()<<endl;
1488 #endif
1489       bisectoronetoremove.Bind(found,firstbisectortoremove[index]);
1490       bisectortwotoremove.Bind(found,lastbisectortoremove[index]);
1491       typeofbisectortoremove.Bind(found,index+1);
1492
1493       if(found == noofbisectorstoremove)noofbisectorstoremove++;
1494     }
1495   }
1496 }
1497
1498 //========================================================================
1499 //  function : Intersect
1500 //  purpose  : Si <aside=0> Intersection de <firstbisector> avec les
1501 //                 descendants de <secondbisector> les plus a gauche
1502 //                (ie secondbisector->FirstBisector()->FirstBisector...)
1503 //                          Intersection de <secondbisector> avec les
1504 //                 descendants de <firstbisector> les plus a droite
1505 //                (ie firstbisector->LastBisector()->LastBisector...)
1506 //
1507 //             Si <aside=1> Intersection de <firstbisector> avec ses
1508 //                descendants les plus a gauche et les plus a droite.
1509 //
1510 //             Si <aside=2> Intersection de <secondbisector> avec ses
1511 //                descendants les plus a gauche et les plus a droite.
1512 //========================================================================v
1513 void MAT2d_Mat2d::Intersect(      MAT2d_Tool2d&                 atool,
1514                         const Standard_Integer      aside,
1515                               Standard_Integer&     noofbisectortoremove,
1516                         const Handle(MAT_Bisector)& firstbisector,
1517                         const Handle(MAT_Bisector)& secondbisector)
1518 {
1519   Standard_Integer      bisectornumber;
1520   Standard_Real         distant,saveparameter;
1521   Standard_Real         distance[2];
1522   Standard_Integer      intersectionpoint;
1523   Handle(MAT_Bisector)  lastbisector,previousbisector;
1524   Handle(MAT_Bisector)  firstbisectortoremove[2];
1525   Handle(MAT_Bisector)  lastbisectortoremove[2];
1526
1527   distance[0] = Precision::Infinite();
1528   distance[1] = Precision::Infinite();
1529
1530   for(bisectornumber = 0; bisectornumber<2; bisectornumber++) {
1531     if(aside == 0) {
1532       if(bisectornumber == 0)
1533         firstbisectortoremove[bisectornumber] = secondbisector;
1534       else
1535         firstbisectortoremove[bisectornumber] = firstbisector;
1536     }
1537     else if(aside == 1) {
1538       firstbisectortoremove[bisectornumber] = firstbisector;
1539     }
1540     else {
1541       firstbisectortoremove[bisectornumber] = secondbisector;
1542     }
1543
1544     lastbisector = firstbisectortoremove[bisectornumber];
1545
1546     if(aside == 0) {
1547       previousbisector = firstbisectortoremove[bisectornumber];
1548     }
1549     else {
1550       if(firstbisectortoremove[bisectornumber]->List()->IsEmpty())continue;
1551
1552       if(bisectornumber == 0)
1553         previousbisector = firstbisectortoremove[bisectornumber]
1554                               ->FirstBisector();
1555       else
1556         previousbisector = firstbisectortoremove[bisectornumber]
1557                               ->LastBisector();
1558     }
1559
1560     distant = distance[bisectornumber];
1561     while(!previousbisector->List()->IsEmpty()) {
1562
1563       if(bisectornumber == 0)
1564         previousbisector = previousbisector->FirstBisector();
1565       else
1566         previousbisector = previousbisector->LastBisector();
1567
1568       if(aside == 1 || (aside == 0 && bisectornumber == 0)) {
1569         saveparameter = previousbisector->FirstParameter();
1570         distant = atool.IntersectBisector
1571           (firstbisector,previousbisector,intersectionpoint);
1572         previousbisector->FirstParameter(saveparameter);
1573       }
1574       else {
1575         saveparameter = previousbisector->SecondParameter();
1576         distant = atool.IntersectBisector
1577           (previousbisector,secondbisector,intersectionpoint);
1578         previousbisector->SecondParameter(saveparameter);
1579       }
1580
1581       if(distant < Precision::Infinite()) {
1582         distance[bisectornumber] = distant;
1583         lastbisectortoremove[bisectornumber] = lastbisector;
1584       }
1585
1586       lastbisector = previousbisector;
1587     }
1588   }
1589
1590   //---------------------------------------
1591   // Chargement des bissectrices a effacer.
1592   //---------------------------------------
1593
1594   LoadBisectorsToRemove(noofbisectortoremove,
1595                         distance[0],distance[1],
1596                         firstbisectortoremove[0],firstbisectortoremove[1],
1597                         lastbisectortoremove[0] ,lastbisectortoremove[1]);
1598 }
1599
1600 //========================================================================
1601 //  function : Init
1602 //  purpose  :
1603 //========================================================================
1604 void MAT2d_Mat2d::Init()
1605 {
1606   roots->First();
1607 }
1608
1609 //========================================================================
1610 //  function : More
1611 //  purpose  :
1612 //========================================================================
1613 Standard_Boolean MAT2d_Mat2d::More() const
1614 {
1615   return roots->More();
1616 }
1617
1618 //========================================================================
1619 //  function : Next
1620 //  purpose  :
1621 //========================================================================
1622 void MAT2d_Mat2d::Next()
1623 {
1624   roots->Next();
1625 }
1626
1627 //========================================================================
1628 //  function : Bisector
1629 //  purpose  :
1630 //========================================================================
1631 Handle(MAT_Bisector) MAT2d_Mat2d::Bisector() const
1632 {
1633   return roots->Current();
1634 }
1635
1636 //========================================================================
1637 //  function : NumberOfBisectors
1638 //  purpose  :
1639 //========================================================================
1640 Standard_Integer MAT2d_Mat2d::NumberOfBisectors() const
1641 {
1642   return thenumberofbisectors;
1643 }
1644
1645 //========================================================================
1646 //  function : SemiInfinite
1647 //  purpose  :
1648 //========================================================================
1649 Standard_Boolean MAT2d_Mat2d::SemiInfinite() const
1650 {
1651   return semiInfinite;
1652 }
1653
1654 //========================================================================
1655 //  function : IsDone
1656 //  purpose  :
1657 //========================================================================
1658 Standard_Boolean MAT2d_Mat2d::IsDone() const
1659 {
1660   return isDone;
1661 }
1662