5be3c418bedec1f589ce7cedd3bba19113ba5001
[occt.git] / src / IntCurve / IntCurve_Polygon2dGen.gxx
1 // File:        IntCurve_Polygon2dGen.gxx
2 // Created:     Mon Oct 12 17:17:30 1992
3 // Author:      Laurent BUCHARD
4 //              <lbr@sdsun2>
5
6 #define TEST 0
7
8
9 #include <Standard_ConstructionError.hxx>
10 #include <Bnd_Box2d.hxx>
11 #include <TColgp_Array1OfPnt2d.hxx>
12 #include <gp_Lin2d.hxx>
13 #include <gp_Vec2d.hxx>
14 #include <gp_Dir2d.hxx>
15
16
17
18
19 #define MAJORATION_DEFLECTION 1.5
20 //======================================================================
21 //== On echantillonne sur le Domain de la Curve  NbPts Points 
22 //== a parametres constants.
23 //== 
24 //== On estime la fleche maximum en prenant la distance maxi entre la 
25 //== droite Curve.Value(X(i))-->Curve.Value(X(i+1)) 
26 //== et le point Curve.Value(X(i+1/2))
27 //======================================================================
28 //  Modified by Sergey KHROMOV - Mon Mar 24 12:02:43 2003 Begin
29 IntCurve_Polygon2dGen::IntCurve_Polygon2dGen(const TheCurve&        C,
30                                              const Standard_Integer tNbPts,
31                                              const IntRes2d_Domain& D,
32                                              const Standard_Real    Tol):
33 //                                           const Standard_Real    ):
34 //  Modified by Sergey KHROMOV - Mon Mar 24 12:02:45 2003 End
35        ThePnts(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)),
36        TheParams(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)),
37        TheIndex(1,(tNbPts<3)? 6 : (tNbPts+tNbPts))
38
39          
40   Standard_Integer NbPts = (tNbPts<3)? 3 : tNbPts;
41   TheMaxNbPoints = NbPts+NbPts;
42   NbPntIn = NbPts;
43   //----------------------------------------------------- 
44   //--- Initialisation du Brise a d_Parametre constant
45   //---
46   Binf = D.FirstParameter();
47   Bsup = D.LastParameter();
48   //-----------------------------------------------------
49   //-- IntRes2d Raise si HasFirst retourne False
50   //-- et Acces a First Parameter
51   //-- 
52   Standard_Real u=Binf; 
53   Standard_Real u1=Bsup;
54   Standard_Real du=(u1-u)/(Standard_Real)(NbPts-1);
55 //  Standard_Integer ip1,i=1;
56   Standard_Integer i=1;
57   
58   do {
59     gp_Pnt2d P=TheCurveTool::Value(C,u);
60     TheBnd.Add(P);
61     TheIndex.SetValue(i,i);
62     ThePnts.SetValue(i,P); 
63     TheParams.SetValue(i,u);
64     u+=du;
65     i++;
66   }
67   while(i<=NbPts);
68
69
70   //-----------------------------------------------------
71   //--- Calcul d un majorant de fleche approche
72   //---
73 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:05 2003 Begin
74 //   TheDeflection = 0.000000001;
75   TheDeflection = Min(0.000000001, Tol/100.);
76 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:05 2003 End
77   i=1;
78   u=D.FirstParameter();
79   u+=du * 0.5;
80   
81   do {
82     gp_Pnt2d Pm = TheCurveTool::Value(C,u);
83     const gp_Pnt2d& P1 = ThePnts.Value(i);
84     const gp_Pnt2d& P2 = ThePnts.Value(i+1);
85
86     u+=du;
87     i++;
88
89
90     Standard_Real dx,dy,t=0;    
91     dx=P1.X()-P2.X(); if(dx<0) dx=-dx;
92     dy=P1.Y()-P2.Y(); if(dy<0) dy=-dy;
93     if(dx+dy>1e-12) { 
94       gp_Lin2d L(P1,gp_Dir2d(gp_Vec2d(P1,P2)));
95       t = L.Distance(Pm);
96       if(t>TheDeflection) {
97         TheDeflection = t;
98       }
99     }
100   }
101   while(i<NbPts);
102
103   TheBnd.Enlarge(TheDeflection*MAJORATION_DEFLECTION);
104   ClosedPolygon = Standard_False;
105 }
106 //======================================================================
107 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:26 2003 Begin
108 IntCurve_Polygon2dGen::IntCurve_Polygon2dGen(const TheCurve&        C,
109                                              const Standard_Integer tNbPts,
110                                              const IntRes2d_Domain& D,
111                                              const Standard_Real Tol,
112                                              const Bnd_Box2d& BoxOtherPolygon):
113 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:28 2003 End
114        ThePnts(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)), 
115        TheParams(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)), 
116        TheIndex(1,(tNbPts<3)? 6 : (tNbPts+tNbPts))
117 {
118   Standard_Integer NbPts = (tNbPts<3)? 3 : tNbPts;
119   TheMaxNbPoints = NbPts+NbPts;
120   NbPntIn = NbPts; 
121   //----------------------------------------------------- 
122   //--- Initialisation du Brise a d_Parametre constant
123   //---
124   Binf = D.FirstParameter();
125   Bsup = D.LastParameter();
126   //-----------------------------------------------------
127   Standard_Real u=Binf; 
128   Standard_Real u1=Bsup;
129   Standard_Real du=(u1-u)/(Standard_Real)(NbPts-1);
130   Standard_Integer i=1;
131   do {
132     gp_Pnt2d P=TheCurveTool::Value(C,u);
133     TheBnd.Add(P);
134     ThePnts.SetValue(i,P); 
135     TheParams.SetValue(i,u);
136     TheIndex.SetValue(i,i);
137     u+=du;
138     i++;
139   }
140   while(i<=NbPts);
141
142
143   //-----------------------------------------------------
144   //--- Calcul d un majorant de fleche approche
145   //---
146 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:55 2003 Begin
147 //   TheDeflection = 0.0000001;
148   TheDeflection = Min(0.0000001, Tol/100.);
149 //  Modified by Sergey KHROMOV - Mon Mar 24 12:03:56 2003 End
150   i=1;
151   u=D.FirstParameter();
152   u+=du * 0.5;
153   
154   do {
155     gp_Pnt2d Pm = TheCurveTool::Value(C,u);
156     const gp_Pnt2d& P1 = ThePnts.Value(i);
157     const gp_Pnt2d& P2 = ThePnts.Value(i+1);
158
159     Standard_Real dx,dy;    
160     dx=P1.X()-P2.X(); if(dx<0) dx=-dx;
161     dy=P1.Y()-P2.Y(); if(dy<0) dy=-dy;
162     if(dx+dy>1e-12) {      
163       gp_Lin2d L(P1,gp_Dir2d(gp_Vec2d(P1,P2)));
164       Standard_Real t = L.Distance(Pm);      
165       if(t>TheDeflection) {
166         TheDeflection = t;
167       }
168     }
169     u+=du;
170     i++;
171   }
172   while(i<NbPts);
173   
174   TheBnd.Enlarge(TheDeflection*MAJORATION_DEFLECTION);
175   ClosedPolygon = Standard_False;
176   //-------------------------------------------------------
177   //-- On supprime les points alignes 
178   //-- (Permet de diminuer le nombre total de points) 
179   //-- (Dans le cas ou la courbe est "droite"       )
180   Standard_Real DeflectionMaj = TheDeflection;
181   for(i=2;i<NbPntIn && NbPntIn>3;i++) { 
182     Standard_Integer indexim1 = TheIndex.Value(i-1);
183     Standard_Integer indexi   = TheIndex.Value(i);
184     Standard_Integer indexip1 = TheIndex.Value(i+1);
185     const gp_Pnt2d& Pim1 = ThePnts.Value(indexim1);
186     const gp_Pnt2d& Pi   = ThePnts.Value(indexi);
187     const gp_Pnt2d& Pip1 = ThePnts.Value(indexip1);
188
189     Standard_Real dx,dy;    
190     dx=Pim1.X()-Pip1.X(); if(dx<0) dx=-dx;
191     dy=Pim1.Y()-Pip1.Y(); if(dy<0) dy=-dy;
192     Standard_Real t=0;
193     if(dx+dy>1e-12) {    
194       gp_Lin2d L(Pim1,gp_Dir2d(gp_Vec2d(Pim1,Pip1)));
195       t = L.Distance(Pi);
196     }
197     if(t<=DeflectionMaj) { 
198       //-- On supprime le point i
199       for(Standard_Integer j = i; j<NbPntIn; j++) { 
200         TheIndex.SetValue(j,TheIndex.Value(j+1));
201       }
202       NbPntIn--;
203       i--;
204     }
205   }
206
207   ComputeWithBox(C,BoxOtherPolygon);
208 }
209 //======================================================================
210 void IntCurve_Polygon2dGen::ComputeWithBox(const TheCurve&        C,
211                                            const Bnd_Box2d& BoxOtherPolygon) {
212   if(TheBnd.IsOut(BoxOtherPolygon)) { 
213     NbPntIn=2;
214     TheBnd.SetVoid();
215   }
216   else { 
217      Standard_Real bx0,bx1,by0,by1;
218      BoxOtherPolygon.Get(bx0,by0,bx1,by1);
219
220     bx0-=TheDeflection; 
221     by0-=TheDeflection; 
222     bx1+=TheDeflection; 
223     by1+=TheDeflection;
224     Standard_Integer MaxIndexUsed = 1;
225     Standard_Integer i,nbp;
226     Standard_Integer Rprec,Ri;
227     Standard_Real x,y;
228     
229     nbp = 0;
230     x = ThePnts.Value(TheIndex.Value(1)).X();
231     y = ThePnts.Value(TheIndex.Value(1)).Y();
232     
233     Rprec = CalculRegion(x,y,bx0,bx1,by0,by1);
234     for(i = 2; i<=NbPntIn; i++) { 
235       const gp_Pnt2d& P2d = ThePnts.Value(TheIndex.Value(i));
236       Ri = CalculRegion(P2d.X(),P2d.Y(),bx0,bx1,by0,by1);
237       if((Ri & Rprec)==0) { 
238         if(nbp) { 
239           if(TheIndex.Value(nbp) != TheIndex.Value(i-1)) { 
240             nbp++;
241             TheIndex.SetValue(nbp,TheIndex.Value(i-1));
242           }
243         }
244         else {
245           nbp++;
246           TheIndex.SetValue(nbp,TheIndex.Value(i-1)); 
247         }
248         nbp++;
249         TheIndex.SetValue(nbp,TheIndex.Value(i));
250         if(TheIndex.Value(i) > MaxIndexUsed) MaxIndexUsed = TheIndex.Value(i);
251
252         Rprec = Ri;
253       }
254       else { 
255         if((Ri & Rprec)==0) { 
256           nbp++;
257           TheIndex.SetValue(nbp,TheIndex.Value(i));
258           if(TheIndex.Value(i) > MaxIndexUsed) MaxIndexUsed = TheIndex.Value(i);
259
260           Rprec = Ri; 
261         }
262       }
263       Rprec = Ri;
264     }
265     if(nbp==1) { 
266       NbPntIn=2;
267       TheBnd.SetVoid();
268     }
269     else {
270       TheBnd.SetVoid();
271       if(nbp) { 
272         TheBnd.Add(ThePnts.Value(TheIndex.Value(1)));
273       }
274       Standard_Real    RatioDeflection;
275       Standard_Integer nbpassagedeflection = 0;
276 //      Standard_Integer PointHasBeenAdded = 0;
277       do { 
278         nbpassagedeflection++;
279 //  Modified by Sergey KHROMOV - Mon Mar 24 12:05:28 2003 Begin
280 //      Standard_Real NewDeflection = 0.0000001;
281         Standard_Real NewDeflection = TheDeflection;
282 //  Modified by Sergey KHROMOV - Mon Mar 24 12:05:29 2003 End
283         for(i=2; i<=nbp; i++) { 
284           Standard_Integer Ii  = TheIndex.Value(i);
285           Standard_Integer Iim1= TheIndex.Value(i-1);
286           const gp_Pnt2d& Pi   = ThePnts.Value(Ii);
287           const gp_Pnt2d& Pim1 = ThePnts.Value(Iim1);
288           TheBnd.Add(Pi);
289           Standard_Integer Regi   = CalculRegion(Pi.X(),Pi.Y(),bx0,bx1,by0,by1);
290           Standard_Integer Regim1 = CalculRegion(Pim1.X(),Pim1.Y(),bx0,bx1,by0,by1); 
291           if((Regi & Regim1) == 0) {  
292             Standard_Real u = 0.5*( TheParams.Value(Ii)
293                                    +TheParams.Value(Iim1));
294             gp_Pnt2d Pm = TheCurveTool::Value(C,u);
295             Standard_Real dx,dy,t=0;    
296             dx=Pim1.X()-Pi.X(); if(dx<0) dx=-dx;
297             dy=Pim1.Y()-Pi.Y(); if(dy<0) dy=-dy;
298             if(dx+dy>1e-12)  {
299               gp_Lin2d L(Pim1,gp_Dir2d(gp_Vec2d(Pim1,Pi)));
300               t = L.Distance(Pm);
301               if((MaxIndexUsed<(TheMaxNbPoints-1)) && (t>(TheDeflection * 0.5))) {
302                 const gp_Pnt2d& P1=Pim1;
303                 nbp++;
304                 for(Standard_Integer j=nbp; j>=i+1; j--) { 
305                   TheIndex.SetValue(j,TheIndex.Value(j-1));
306                 }
307                 MaxIndexUsed++;
308                 TheIndex.SetValue(i,MaxIndexUsed);
309                 ThePnts.SetValue(MaxIndexUsed,Pm);
310                 TheParams.SetValue(MaxIndexUsed,u);
311                 
312                 Standard_Real u1m = 0.5*(u+TheParams.Value(TheIndex.Value(i-1)));
313                 Standard_Real um2 = 0.5*(u+TheParams.Value(TheIndex.Value(i+1)));
314                 gp_Pnt2d P1m = TheCurveTool::Value(C,u1m);
315 #ifdef DEB
316                 gp_Pnt2d Pm2 = TheCurveTool::Value(C,um2);
317 #else
318                 TheCurveTool::Value(C,um2);
319 #endif
320                 gp_Lin2d L1m(P1,gp_Dir2d(gp_Vec2d(P1,Pm)));
321 #ifdef DEB
322                 gp_Lin2d Lm2(Pm,gp_Dir2d(gp_Vec2d(Pm,ThePnts.Value(TheIndex.Value(i+1)))));
323 #else
324                 ThePnts.Value(TheIndex.Value(i+1));
325 #endif
326                 t = L1m.Distance(P1m);
327                 i--; 
328               }
329             }
330             else { 
331               if(t>NewDeflection) { 
332                 NewDeflection = t; 
333               }
334             }
335           }
336         }
337         if(NewDeflection) 
338           RatioDeflection = TheDeflection / NewDeflection; 
339         else RatioDeflection = 10.0;
340         TheDeflection = NewDeflection;
341         NbPntIn = nbp;
342       }
343       while((RatioDeflection<3.0)
344             && (nbpassagedeflection < 3) 
345             && (MaxIndexUsed<(TheMaxNbPoints-2)));
346     }
347
348     TheDeflection*=MAJORATION_DEFLECTION;
349     TheBnd.Enlarge(TheDeflection);
350   }
351   ClosedPolygon = Standard_False;
352   Dump();
353 }
354
355
356 Standard_Boolean IntCurve_Polygon2dGen::AutoIntersectionIsPossible() const { 
357
358   gp_Vec2d VRef(ThePnts.Value(TheIndex.Value(1)),
359                 ThePnts.Value(TheIndex.Value(2)));
360   for(Standard_Integer i=3; i<=NbPntIn; i++) { 
361     gp_Vec2d V(ThePnts.Value(TheIndex.Value(i-1)),
362                 ThePnts.Value(TheIndex.Value(i)));
363     if(V.Dot(VRef)<0.0) {
364       return(Standard_True);
365     }
366   }
367   return(Standard_False); 
368 }
369
370 //======================================================================
371 Standard_Real IntCurve_Polygon2dGen::ApproxParamOnCurve( const Standard_Integer Aindex
372                                                         ,const Standard_Real TheParamOnLine) 
373      const 
374 {
375   Standard_Integer Indexp1,Index = Aindex;
376   Standard_Real    ParamOnLine = TheParamOnLine;
377   if (Index > NbPntIn) {
378     cout << "OutOfRange Polygon2d::ApproxParamOnCurve " <<endl;
379   }
380   if((Index == NbPntIn) && (ParamOnLine == 0.0)) { 
381     Index--; ParamOnLine=1.0;
382   }
383   if(Index==0) { 
384     Index=1; 
385     ParamOnLine = 0.0;
386   }
387   Indexp1 = TheIndex.Value(Index+1);
388   Index   = TheIndex.Value(Index);
389
390   Standard_Real du = TheParams.Value(Indexp1)-TheParams.Value(Index);
391   Standard_Real u  = TheParams.Value(Index) + ParamOnLine * du;
392   return(u);
393 }
394
395
396 //======================================================================
397 #if TEST
398
399 extern Standard_Boolean DebugPolygon2d;
400 extern void DrawSegmentBlanc(const gp_Pnt2d& _P1,const gp_Pnt2d& _P2);
401 extern void DrawSegment(const gp_Pnt2d& _P1,const gp_Pnt2d& _P2);
402
403 void IntCurve_Polygon2dGen::Dump(void) const {
404   if(!DebugPolygon2d) return;
405   Standard_Real bx0,bx1,by0,by1;
406   if(TheBnd.IsVoid()) return;
407   TheBnd.Get(bx0,by0,bx1,by1);
408   DrawSegment(gp_Pnt2d(bx0,by0),gp_Pnt2d(bx1,by0));
409   DrawSegment(gp_Pnt2d(bx1,by0),gp_Pnt2d(bx1,by1));
410   DrawSegment(gp_Pnt2d(bx1,by1),gp_Pnt2d(bx0,by1));
411   DrawSegment(gp_Pnt2d(bx0,by1),gp_Pnt2d(bx0,by0));    
412   Standard_Integer i;
413   if(NbPntIn<=1) return;
414   for(i=2;i<=NbPntIn; i++) { 
415     DrawSegmentBlanc(ThePnts.Value(TheIndex.Value(i-1)),ThePnts.Value(TheIndex.Value(i)));
416   }
417 }
418 #else
419 void IntCurve_Polygon2dGen::Dump(void) const { 
420   static int debug = 0;
421   if(debug) { 
422     Standard_Real bx0,bx1,by0,by1;
423     
424     cout<<"\n ----- Dump de IntCurve_Polygon2dGen -----"<<endl;
425     if(TheBnd.IsVoid()) { 
426       cout<<"  Polygone Vide "<<endl;
427       return;
428     }
429     TheBnd.Get(bx0,by0,bx1,by1);
430     cout<<"  bx0:"<<bx0  <<endl;
431     cout<<"  by0:"<<by0<<endl;
432     cout<<"  bx1:"<<bx1<<endl;
433     cout<<"  by1:"<<by1<<endl;
434     
435     Standard_Integer i;
436     for(i=1;i<=NbPntIn; i++) { 
437       const gp_Pnt2d& P = ThePnts(TheIndex(i));
438       cout<<"  ("<<i<<") u:"<<TheParams.Value(TheIndex(i))<<" X:"<<P.X()<<"  Y:"<<P.Y()<<endl;
439     }
440   }
441
442 #endif
443 //======================================================================
444 //======================================================================
445