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