cd2db7b60f6a31191a11c8846f0683eaf0b13dcd
[occt.git] / 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()
35 {
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::CreateMat(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;
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(); 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()));
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()));
215   }
216
217 //----------------------------------------------------
218 // Affectation a chaque edge de ses deux bissectrices.
219 //----------------------------------------------------
220   theedgelist->First();
221
222   for(i=0; i<theedgelist->Number(); i++) {
223     theedgelist->Current()->FirstBisector
224       (bisectormap((i-1+noofbisectors)%noofbisectors));
225     theedgelist->Current()->SecondBisector
226       (bisectormap(i));
227     theedgelist->Next();
228   }
229
230 //===========================================================================
231 //                         Boucle Principale   (etape 2)
232 //===========================================================================
233   Standard_Integer NumberOfIte = 0;
234
235   while(theedgelist->Number()>1) {
236
237
238     // ------------------------------------------------------------------
239     //  Creation des geometries des bissectrices via le tool. (etape 2.1)
240     // -------------------------------------------------------------------
241
242     for(i=beginbisector; i<noofbisectors; i++) {
243
244       atool.CreateBisector(bisectormap(i));
245       thenumberofbisectors++;
246       
247 #ifdef DEBUG_Mat
248       atool.Dump(bisectormap(i)->BisectorNumber(),1);
249 #ifdef ICONTINUE
250       cin>>Icontinue;
251 #endif
252 #endif
253     }
254
255     // ---------------------------------------------
256     //  Condition de sortie de la boucle principale.
257     // ---------------------------------------------
258
259 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:28 2000 Begin
260     if (theedgelist->Number() < 3)
261       break;
262 //  Modified by Sergey KHROMOV - Fri Nov 17 10:28:37 2000 End
263     
264     //---------------------------------------------------
265     // boucle 2 Tant qu il y a des bisectrices a effacer.
266     //---------------------------------------------------
267     for(;;) {
268       NbIterBis++;
269
270       noofbisectorstoremove = 0;
271       theedgelist->First();
272
273       //--------------------------------------------------------------
274       // Calcul des intersections des bisectrices voisines.(etape 2.2)
275       //--------------------------------------------------------------
276
277       if (NbIterBis <= EvenNbIterBis+1)
278         EdgeNumbers(NbIterBis) = theedgelist->Number();
279       else
280         {
281           for (k = 1; k <= EvenNbIterBis; k++)
282             EdgeNumbers(k) = EdgeNumbers(k+1);
283           EdgeNumbers(EvenNbIterBis+1) = theedgelist->Number();
284         }
285       if (EdgeNumbers(EvenNbIterBis+1) == EdgeNumbers(1))
286         ToNullifyNoofbisectorstoremove = Standard_True;
287
288       for(i=0; i<theedgelist->Number(); i++) {
289         edge = theedgelist->Current();
290         if(edge->Distance() == -1.) {
291           firstbisector = edge->FirstBisector();
292           secondbisector = edge->SecondBisector();
293           edge->Distance(atool.IntersectBisector
294                          (firstbisector,secondbisector,intersectionpoint));
295           edge->IntersectionPoint(intersectionpoint);
296
297           if(edge->Distance() == Precision::Infinite()) {
298             if(firstbisector->IndexNumber() >= beginbisector ||
299                secondbisector->IndexNumber() >= beginbisector) 
300               Intersect(atool,0,noofbisectorstoremove,
301                         firstbisector,secondbisector );
302           }
303           else {
304             if(firstbisector->IndexNumber() >= beginbisector) {
305               Intersect(atool,1,noofbisectorstoremove,
306                         firstbisector,secondbisector );
307             }
308             if(secondbisector->IndexNumber() >= beginbisector) {
309               Intersect(atool,2,noofbisectorstoremove,
310                         firstbisector,secondbisector );
311             }
312           }
313         }
314         theedgelist->Next();
315       }
316       
317       //-------------------------------
318       // Test de sortie de la boucle 2.
319       //-------------------------------
320
321       if (ToNullifyNoofbisectorstoremove)
322         noofbisectorstoremove = 0;
323       if(noofbisectorstoremove == 0) break;
324
325       //---------------------------------------------------
326       // Annulation des bissectrices a effacer. (etape 2.4)
327       //---------------------------------------------------
328
329       for(i=0; i<noofbisectorstoremove; i++) {
330
331         bisectortoremove = bisectoronetoremove(i);
332
333         //---------------------------------------------------------------
334         // Destruction des bisectrices descendantes de <bisectortoremove>
335         // On descend dans l arbre jusqu a ce qu on atteigne
336         // <bisectortwotoremove(i).
337         //---------------------------------------------------------------
338
339         for(;;){
340
341 #ifdef DEBUG_Mat
342           atool.Dump(bisectortoremove->BisectorNumber(),0);
343 #endif
344           // ----------------------------------
345           // Annulation de <bisectortoremove>.
346           // ----------------------------------
347           thenumberofbisectors--;
348           currentbisectorlist = bisectortoremove->List();
349           currentbisectorlist->First();
350           currentbisector = currentbisectorlist->FirstItem();
351           previousedge = currentbisector->FirstEdge();
352           theedgelist->Init(previousedge);
353           previousedge->Distance(-1.);
354           previousedge->FirstBisector()->SecondParameter(Precision::Infinite());
355           previousedge->SecondBisector()->FirstParameter(Precision::Infinite());
356
357           //------------------------------------------
358           // Annulation des fils de <currentbisector>.
359           //------------------------------------------
360
361           while(currentbisectorlist->More()) {
362             currentbisector = currentbisectorlist->Current();
363             currentedge  = currentbisector->SecondEdge();
364
365             //---------------------------------------
366             // Reinsertion de l edge dans le contour.
367             //---------------------------------------
368             theedgelist->LinkAfter(currentedge);
369             theedgelist->Next();
370             
371             currentedge->FirstBisector(currentbisector);
372             previousedge->SecondBisector(currentbisector);
373 #ifdef DEBUG_Mat                      
374             atool.Dump(currentbisector->BisectorNumber(),0);
375 #endif
376
377             //------------------------------------------------------
378             // Annulation de l intersection ie les fils qui
379             // ont generes l intersection sont prolonges a l infini.
380             //------------------------------------------------------
381
382             currentbisector->FirstParameter (Precision::Infinite());
383             currentbisector->SecondParameter(Precision::Infinite());
384                       
385             atool.TrimBisector(currentbisector);
386             
387 #ifdef DEBUG_Mat
388             atool.Dump(currentbisector->BisectorNumber(),1);
389 #endif
390             currentedge->Distance(-1.);
391             currentedge->FirstBisector()->SecondParameter(Precision::Infinite());
392             currentedge->SecondBisector()->FirstParameter(Precision::Infinite());
393             
394             previousedge = currentedge;
395             currentbisectorlist->Next();
396           }
397           
398           theedgelist->Unlink();
399
400           //-----------------------------------------------------------
401           // Test de sortie de la boucle d annulation des bissectrices.
402           //-----------------------------------------------------------
403
404           if(bisectortoremove->BisectorNumber() ==
405              bisectortwotoremove(i)->BisectorNumber()) break;
406
407           //-----------------------
408           // Descente dans l arbre.
409           //-----------------------
410
411           if(typeofbisectortoremove(i) == 1)
412             bisectortoremove = bisectortoremove->FirstBisector();
413           else
414             bisectortoremove = bisectortoremove->LastBisector();
415         
416         }  //----------------------------------------------------
417            // Fin boucle d annulation des bissectrices issue de 
418            // <bisectoronetoremove(i)>.
419            //----------------------------------------------------
420
421       } //------------------------------------------
422         // Fin boucle d annulation des bissectrices.
423         //-------------------------------------------
424
425 #ifdef ICONTINUE
426       cin>>Icontinue;
427 #endif
428     } //--------------
429       // Fin Boucle 2.
430       //--------------
431     
432     // ----------------------------------------------------------------------
433     // Analyse des parametres des intersections sur les bisectrices de chaque
434     // edge et determination des portions de contour a supprimees. (etape 2.5)
435     // ----------------------------------------------------------------------
436
437     theedgelist->First();
438       
439     currentbisector = theedgelist->Current()->FirstBisector();
440     if (currentbisector->FirstParameter()  == Precision::Infinite() &&
441         currentbisector->SecondParameter() == Precision::Infinite()) {
442       parama[0] = -1;
443       paramb[0] = -1;
444     }
445     else if(currentbisector->FirstParameter() == Precision::Infinite()) {
446       parama[0] = -1;
447       paramb[0] =  1;
448     }
449     else if(currentbisector->SecondParameter() == Precision::Infinite()) {
450       paramb[0] = -1;
451       parama[0] =  1;
452     }
453     else if (atool.Distance(currentbisector,
454                             currentbisector->FirstParameter(),
455                             currentbisector->SecondParameter()) 
456              > toleranceofconfusion) {
457       if((currentbisector->FirstParameter() - 
458           currentbisector->SecondParameter())
459          *currentbisector->Sense() > 0.) {      
460         parama[0] = -1;
461         paramb[0] =  1;
462       }
463       else {
464         paramb[0] = -1;
465         parama[0] =  1;
466       }
467     }
468     else {
469       parama[0] = 1;
470       paramb[0] = 1;
471     }
472     
473     narea = -1;
474     
475     for(i=0; i<theedgelist->Number(); i++) {
476       currentbisector = theedgelist->Current()->SecondBisector();
477       if (currentbisector->FirstParameter()  == Precision::Infinite() &&
478           currentbisector->SecondParameter() == Precision::Infinite()) {
479         parama[1] = -1;
480         paramb[1] = -1;
481       }
482       else if(currentbisector->FirstParameter() == Precision::Infinite()) {
483         parama[1] = -1;
484         paramb[1] =  1;
485       }
486       else if(currentbisector->SecondParameter() == Precision::Infinite()) {
487         paramb[1] = -1;
488         parama[1] =  1;
489       }
490       else if (atool.Distance(currentbisector,
491                               currentbisector->FirstParameter(),
492                               currentbisector->SecondParameter()) 
493                > toleranceofconfusion) {
494         if((currentbisector->FirstParameter() - 
495             currentbisector->SecondParameter()) 
496            *currentbisector->Sense() > 0.) {      
497           parama[1] = -1;
498           paramb[1] =  1;
499         }
500         else {
501           paramb[1] = -1;
502           parama[1] =  1;
503         }
504       }
505       else {
506         parama[1] = 1;
507         paramb[1] = 1;
508       }
509
510       //-----------------------------------------------------------------
511       // Test si l edge est a enlever du contour
512       // Construction des portions de contour a eliminer.
513       //
514       //  narea : nombre de portions continues du contour a eliminer.
515       //  firstarea[i] : indice premier edge de la portion i.
516       //  lastarea[i]  : indice dernier edge de la portion i.
517       //-----------------------------------------------------------------
518
519 #ifdef DEBUG_Mat
520       cout <<" Test sur les parametres pour elimination"<<endl;
521       cout << " Edge number :"<<theedgelist->Current()->EdgeNumber()<<endl;
522 #endif
523
524       if(paramb[0] > 0 && parama[1] > 0) {
525
526 #ifdef DEBUG_Mat
527       cout <<" A ELIMINER "<<endl;
528 #endif  
529         if(narea < 0) {
530           firstarea(++narea) = theedgelist->Index();
531           lastarea(narea) = firstarea(narea);
532           noofarea(narea) = 1;
533         }
534         else {
535           if(theedgelist->Index() == lastarea(narea)+1) {
536             lastarea(narea)++;
537             noofarea(narea)++;
538           }
539           else {
540             firstarea(++narea) = theedgelist->Index();
541             lastarea(narea) = firstarea(narea);
542             noofarea(narea) = 1;
543           }
544         }
545       }
546       parama[0] = parama[1];
547       paramb[0] = paramb[1];
548       theedgelist->Next();
549     
550     } 
551     
552     compact = 0;
553     if(narea > 0) {
554       if(lastarea(narea) == theedgelist->Number() && firstarea(0) == 1) {
555         firstarea(0) = firstarea(narea);
556         noofarea(0) = noofarea(0)+noofarea(narea);
557         compact = noofarea(narea);
558         narea--;
559       }
560     }
561     
562     narea++;
563
564     //------------------------------------------------------------------
565     // Sortie de la boucle principale si il n y a pas d edge a eliminer.
566     // (etape 2.6)
567     //------------------------------------------------------------------
568     if(narea == 0) {
569       interrupt = Standard_True;
570       break;
571     }
572     
573
574     //----------------------------------------------------------------
575     // Elimination des edges a enlever du contour
576     // => Mise a jour du nouveau contour.
577     // => Creation des bissectrices entre les nouvelles edges voisines.
578     //----------------------------------------------------------------
579
580     beginbisector = noofbisectors;
581     shift = 0;
582     all = 0;
583     if(narea == 1 && noofarea(0) == theedgelist->Number()) all = 1;
584
585     for(i=0; i<narea; i++) {
586       if(i == 1)shift = shift-compact;
587       theedgelist->First();
588       edgetoremove = theedgelist->Brackets(firstarea(i)-shift);
589       
590       edgetoremove->FirstBisector()->EndPoint(edgetoremove
591                                               ->IntersectionPoint());
592       
593 #ifdef DEBUG_Mat
594       atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),0);
595 #endif
596
597       edgetoremove->FirstBisector()->FirstParameter
598         (edgetoremove->FirstBisector()->SecondParameter());
599           
600 #ifdef DEBUG_Mat
601       if(atool.TrimBisector(edgetoremove->FirstBisector()))
602         atool.Dump(edgetoremove->FirstBisector()->BisectorNumber(),1);
603 #else
604       atool.TrimBisector(edgetoremove->FirstBisector());
605 #endif
606
607       bisectormap.Bind(noofbisectors,new MAT_Bisector());
608       bisectormap(noofbisectors)->IndexNumber(noofbisectors);
609       bisectormap(noofbisectors)->DistIssuePoint(edgetoremove->Distance());
610       bisectormap(noofbisectors)->IssuePoint(edgetoremove
611                                                 ->IntersectionPoint());
612       bisectormap(noofbisectors)->FirstEdge(theedgelist->PreviousItem());
613       bisectormap(noofbisectors)->AddBisector(edgetoremove
614                                                  ->FirstBisector());
615
616       for(j=0; j<noofarea(i); j++) {
617         theedgelist->Unlink();
618         theedgelist->Next();
619         shift++;
620
621 #ifdef DEBUG_Mat
622         cout<<" Suppression de l'arete : "<<edgetoremove->EdgeNumber()<<endl;
623 #endif
624
625         if(all == 0 || j+1 != noofarea(i)) {
626           bisectormap(noofbisectors)->AddBisector(edgetoremove
627                                                      ->SecondBisector());
628         }
629         edgetoremove->SecondBisector()->EndPoint(edgetoremove
630                                                  ->IntersectionPoint());
631
632 #ifdef DEBUG_Mat
633         atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),0);
634 #endif
635
636         edgetoremove->SecondBisector()->SecondParameter
637           (edgetoremove->SecondBisector()->FirstParameter());
638 #ifdef DEBUG_Mat
639         if(atool.TrimBisector(edgetoremove->SecondBisector()))
640           atool.Dump(edgetoremove->SecondBisector()->BisectorNumber(),1);
641 #else
642         atool.TrimBisector(edgetoremove->SecondBisector());
643 #endif
644         edgetoremove = theedgelist->Current();
645       }
646       bisectormap(noofbisectors)->SecondEdge(theedgelist->Current());
647           
648       theedgelist->PreviousItem()
649         ->SecondBisector(bisectormap(noofbisectors));
650       theedgelist->Current()->FirstBisector(bisectormap(noofbisectors));
651           
652       bisectormap(noofbisectors)->FirstVector
653         (atool.Tangent
654          (bisectormap(noofbisectors)->FirstBisector()
655           ->BisectorNumber()));
656       
657       bisectormap(noofbisectors)->SecondVector
658         (atool.Tangent
659          (bisectormap(noofbisectors)->LastBisector()
660           ->BisectorNumber()));
661       
662       noofbisectors++;
663       
664       theedgelist->PreviousItem()->Distance(-1);
665       theedgelist->Current()->Distance(-1);
666       
667       theedgelist->PreviousItem()->FirstBisector()
668         ->SecondParameter(Precision::Infinite());
669       theedgelist->Current()->SecondBisector()->FirstParameter(Precision::Infinite());
670     }
671
672     //-----------------------------------------------------------------------
673     // Test sur le nombre d iterations :
674     // A chaque iteration est elimine un element du contour qui ne sera plus
675     // reinsere par la suite => le nombre d iterartions doit etre < au nombre
676     // d elements.
677     // Le nombre d iteration maximum est fixe a numberofedges*numberofedges.
678     //-----------------------------------------------------------------------
679     if (NumberOfIte > NumberMaxOfIte) {
680       isDone = Standard_False;             //Echec calcul de la carte.
681       break;
682     }
683     NumberOfIte++;
684
685   }  //===============================================
686      //            Fin Boucle Principale.
687      //===============================================
688      
689   //----------
690   // etape 3.
691   //----------
692
693
694   //----------------------------------------------
695   // interupt = True => bissectrices semi_infinies.
696   //----------------------------------------------
697   
698   if(interrupt)
699     semiInfinite = Standard_True;
700   else {
701     semiInfinite = Standard_False;
702
703     //------------------------------------------------------------------
704     // Si le nombre d edge > 1 => le nombre d edge = 2 
705     //              (cf test sortie boucle principale)
706     // Les deux dernieres bisectrices separent les memes edges .
707     // Soit elles sont confondues si calcul a l interieur, soit elles
708     // sont semi-Infinies (exemple : contour compose seulement de deux
709     // arcs de cercles).                           
710     //------------------------------------------------------------------
711
712     if(theedgelist->Number() > 1) { //Now this branch is never reachable
713                                     //because the case edgenumber = 2 is processed in the main loop
714       theedgelist->First();
715       edge = theedgelist->Current();
716       if(edge->FirstBisector()->IndexNumber() == noofbisectors-1) {
717 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
718         if (atool.TrimBisector(edge->SecondBisector(),
719                                edge->FirstBisector()->IssuePoint())) {
720           if (edge->SecondBisector()->EndPoint() == 0)
721             edge->SecondBisector()->EndPoint(edge->FirstBisector()->IssuePoint());
722           bisectormap(noofbisectors-1)->AddBisector(edge->SecondBisector());
723         } else
724           semiInfinite = Standard_True;
725 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
726       }
727       else {
728 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM Begin
729         if (atool.TrimBisector(edge->FirstBisector(),
730                                edge->SecondBisector()->IssuePoint())) {
731           if (edge->FirstBisector()->EndPoint() == 0)
732             edge->FirstBisector()->EndPoint(edge->SecondBisector()->IssuePoint());
733           bisectormap(noofbisectors-1)->AddBisector(edge->FirstBisector());
734         } else 
735           semiInfinite = Standard_True;
736 //  Modified by skv - Tue Sep 13 12:13:28 2005 IDEM End
737       }
738       if (!semiInfinite) {     
739         thenumberofbisectors--;
740         bisectormap(noofbisectors-1)->SecondEdge(edge);
741         bisectormap(noofbisectors-1)->BisectorNumber(-1);
742       }
743     }
744   }
745   if(semiInfinite) {
746     beginbisector = noofbisectors;
747     theedgelist->First();
748     for(i=0; i<theedgelist->Number(); i++) {
749       edge = theedgelist->Current();
750       bisectormap.Bind(noofbisectors,edge->SecondBisector());
751       noofbisectors++;
752       theedgelist->Next();
753     }
754
755   } 
756
757   //---------------------------
758   // Recuperations des racines.
759   //---------------------------
760
761   roots = new MAT_ListOfBisector;
762   
763   if (bisectormap(noofbisectors-1)->BisectorNumber() == -1) {
764     roots = bisectormap(noofbisectors-1)->List();
765     roots->First();
766     roots->Current()->FirstEdge()
767       ->Distance(bisectormap(noofbisectors-1)->DistIssuePoint());
768   }
769   else {
770     for (i=beginbisector;i<noofbisectors;i++) {
771       roots->BackAdd(bisectormap(i));
772     }
773   }
774   
775 }
776
777 //========================================================================
778 //  function : LoadBisectorsToRemove
779 //  purpose  : Chargement des bisectrices a effacer.
780 //========================================================================
781 void MAT2d_Mat2d::LoadBisectorsToRemove
782   (      Standard_Integer&     noofbisectorstoremove,
783    const Standard_Real         distance1,
784    const Standard_Real         distance2,
785    const Handle(MAT_Bisector)& firstbisectortoremove1,
786    const Handle(MAT_Bisector)& firstbisectortoremove2,
787    const Handle(MAT_Bisector)& lastbisectortoremove1,
788    const Handle(MAT_Bisector)& lastbisectortoremove2  )
789 {
790
791   Standard_Integer found,index;
792   Handle(MAT_Bisector) firstbisectortoremove[2];
793   Handle(MAT_Bisector) lastbisectortoremove[2];
794
795   firstbisectortoremove[0] = firstbisectortoremove1;
796   firstbisectortoremove[1] = firstbisectortoremove2;
797   lastbisectortoremove[0]  = lastbisectortoremove1;
798   lastbisectortoremove[1]  = lastbisectortoremove2;
799   
800   if     (distance1  < Precision::Infinite() && 
801           distance2 == Precision::Infinite()    )   index =  0;
802   else if(distance2  < Precision::Infinite() && 
803           distance1 == Precision::Infinite()    )   index =  1;
804   else                                              index = -1;
805   
806   if(index != -1) {
807     found = noofbisectorstoremove;
808     for(int j=0; j<noofbisectorstoremove; j++) {
809       if(bisectoronetoremove(j)->BisectorNumber() ==
810          firstbisectortoremove[index]->BisectorNumber()) {
811         found = j;
812         if(bisectortwotoremove(j)->BisectorNumber() <
813            lastbisectortoremove[index]->BisectorNumber())found = -1;
814         break;
815       }
816     }
817     
818     if(found != -1) {
819 #ifdef DEBUG_Mat
820       cout<<" first last bisector to remove :"<<
821         firstbisectortoremove[index]->BisectorNumber()<<" "<<
822           lastbisectortoremove[index]->BisectorNumber()<<endl;
823 #endif
824       bisectoronetoremove.Bind(found,firstbisectortoremove[index]);
825       bisectortwotoremove.Bind(found,lastbisectortoremove[index]);
826       typeofbisectortoremove.Bind(found,index+1);
827       
828       if(found == noofbisectorstoremove)noofbisectorstoremove++;
829     }
830   }
831 }
832
833 //========================================================================
834 //  function : Intersect
835 //  purpose  : Si <aside=0> Intersection de <firstbisector> avec les
836 //                 descendants de <secondbisector> les plus a gauche 
837 //                (ie secondbisector->FirstBisector()->FirstBisector...)
838 //                          Intersection de <secondbisector> avec les
839 //                 descendants de <firstbisector> les plus a droite 
840 //                (ie firstbisector->LastBisector()->LastBisector...)
841 //                
842 //             Si <aside=1> Intersection de <firstbisector> avec ses 
843 //                descendants les plus a gauche et les plus a droite.
844 //
845 //             Si <aside=2> Intersection de <secondbisector> avec ses 
846 //                descendants les plus a gauche et les plus a droite.
847 //========================================================================v
848 void MAT2d_Mat2d::Intersect(      MAT2d_Tool2d&                 atool,
849                         const Standard_Integer      aside,
850                               Standard_Integer&     noofbisectortoremove,
851                         const Handle(MAT_Bisector)& firstbisector,
852                         const Handle(MAT_Bisector)& secondbisector)
853 {
854   Standard_Integer      bisectornumber;
855   Standard_Real         distant,saveparameter;
856   Standard_Real         distance[2];
857   Standard_Integer      intersectionpoint;
858   Handle(MAT_Bisector)  lastbisector,previousbisector;
859   Handle(MAT_Bisector)  firstbisectortoremove[2];
860   Handle(MAT_Bisector)  lastbisectortoremove[2];
861
862   distance[0] = Precision::Infinite();
863   distance[1] = Precision::Infinite();
864
865   for(bisectornumber = 0; bisectornumber<2; bisectornumber++) {
866     if(aside == 0) {
867       if(bisectornumber == 0) 
868         firstbisectortoremove[bisectornumber] = secondbisector;
869       else                    
870         firstbisectortoremove[bisectornumber] = firstbisector;
871     }
872     else if(aside == 1) {
873       firstbisectortoremove[bisectornumber] = firstbisector;
874     }
875     else {
876       firstbisectortoremove[bisectornumber] = secondbisector;
877     }
878     
879     lastbisector = firstbisectortoremove[bisectornumber];
880     
881     if(aside == 0) {
882       previousbisector = firstbisectortoremove[bisectornumber];
883     }
884     else {
885       if(firstbisectortoremove[bisectornumber]->List()->IsEmpty())continue;
886
887       if(bisectornumber == 0)
888         previousbisector = firstbisectortoremove[bisectornumber]
889                               ->FirstBisector();
890       else
891         previousbisector = firstbisectortoremove[bisectornumber]
892                               ->LastBisector();
893     }
894     
895     distant = distance[bisectornumber];
896     while(!previousbisector->List()->IsEmpty()) {
897
898       if(bisectornumber == 0)
899         previousbisector = previousbisector->FirstBisector();
900       else
901         previousbisector = previousbisector->LastBisector();
902       
903       if(aside == 1 || (aside == 0 && bisectornumber == 0)) {
904         saveparameter = previousbisector->FirstParameter();
905         distant = atool.IntersectBisector
906           (firstbisector,previousbisector,intersectionpoint);
907         previousbisector->FirstParameter(saveparameter);
908       }
909       else {
910         saveparameter = previousbisector->SecondParameter();
911         distant = atool.IntersectBisector
912           (previousbisector,secondbisector,intersectionpoint);
913         previousbisector->SecondParameter(saveparameter);
914       }
915       
916       if(distant < Precision::Infinite()) {
917         distance[bisectornumber] = distant;
918         lastbisectortoremove[bisectornumber] = lastbisector;
919       }
920           
921       lastbisector = previousbisector;
922     }
923   }
924
925   //---------------------------------------
926   // Chargement des bissectrices a effacer.
927   //---------------------------------------
928
929   LoadBisectorsToRemove(noofbisectortoremove,
930                         distance[0],distance[1],
931                         firstbisectortoremove[0],firstbisectortoremove[1],
932                         lastbisectortoremove[0] ,lastbisectortoremove[1]);
933 }
934
935 //========================================================================
936 //  function : Init
937 //  purpose  :
938 //========================================================================
939 void MAT2d_Mat2d::Init()
940 {
941   roots->First();
942 }
943
944 //========================================================================
945 //  function : More
946 //  purpose  :
947 //========================================================================
948 Standard_Boolean MAT2d_Mat2d::More() const
949 {
950   return roots->More();
951 }
952
953 //========================================================================
954 //  function : Next
955 //  purpose  :
956 //========================================================================
957 void MAT2d_Mat2d::Next()
958 {
959   roots->Next();
960 }
961
962 //========================================================================
963 //  function : Bisector 
964 //  purpose  :
965 //========================================================================
966 Handle(MAT_Bisector) MAT2d_Mat2d::Bisector() const
967 {
968   return roots->Current();
969 }
970
971 //========================================================================
972 //  function : NumberOfBisectors
973 //  purpose  :
974 //========================================================================
975 Standard_Integer MAT2d_Mat2d::NumberOfBisectors() const
976 {
977   return thenumberofbisectors;
978 }
979
980 //========================================================================
981 //  function : SemiInfinite
982 //  purpose  :
983 //========================================================================
984 Standard_Boolean MAT2d_Mat2d::SemiInfinite() const
985 {
986   return semiInfinite;
987 }
988
989 //========================================================================
990 //  function : IsDone
991 //  purpose  :
992 //========================================================================
993 Standard_Boolean MAT2d_Mat2d::IsDone() const
994 {
995   return isDone;
996 }
997