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