1// Created on: 1992-10-12
2// Created by: Laurent BUCHARD
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#define TEST 0
18
19#include <Standard_ConstructionError.hxx>
20#include <Bnd_Box2d.hxx>
21#include <TColgp_Array1OfPnt2d.hxx>
22#include <gp_Lin2d.hxx>
23#include <gp_Vec2d.hxx>
24#include <gp_Dir2d.hxx>
25
26
27#define MAJORATION_DEFLECTION 1.5
28//======================================================================
29//== We take samples on the Domain of the Curve  NbPts Points
30//== with constant parameters.
31//==
32//== We estimate the maximum deflection taking the max distance between the
33//== right Curve.Value(X(i))-->Curve.Value(X(i+1))
34//== and the point Curve.Value(X(i+1/2))
35//======================================================================
36//  Modified by Sergey KHROMOV - Mon Mar 24 12:02:43 2003 Begin
37IntCurve_Polygon2dGen::IntCurve_Polygon2dGen(const TheCurve&        C,
38					     const Standard_Integer tNbPts,
39					     const IntRes2d_Domain& D,
40					     const Standard_Real    Tol):
41//  Modified by Sergey KHROMOV - Mon Mar 24 12:02:45 2003 End
42       ThePnts(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)),
43       TheParams(1,(tNbPts<3)? 6 : (tNbPts+tNbPts)),
44       TheIndex(1,(tNbPts<3)? 6 : (tNbPts+tNbPts))
45{
46
47  Standard_Integer NbPts = (tNbPts<3)? 3 : tNbPts;
48  TheMaxNbPoints = NbPts+NbPts;
49  NbPntIn = NbPts;
50  //-----------------------------------------------------
51  //--- Initialization of the breaking with d_Parametre constant
52  //---
53  Binf = D.FirstParameter();
54  Bsup = D.LastParameter();
55  //-----------------------------------------------------
56  //-- IntRes2d Raise if HasFirst returns False
57  //-- and accesses First Parameter
58  //--
59  Standard_Real u=Binf;
60  Standard_Real u1=Bsup;
61  Standard_Real du=(u1-u)/(Standard_Real)(NbPts-1);
62//  Standard_Integer ip1,i=1;
63  Standard_Integer i=1;
64
65  do {
66    gp_Pnt2d P=TheCurveTool::Value(C,u);
67    myBox.Add(P);
68    TheIndex.SetValue(i,i);
69    ThePnts.SetValue(i,P);
70    TheParams.SetValue(i,u);
71    u+=du;
72    i++;
73  }
74  while(i<=NbPts);
75
76
77  //-----------------------------------------------------
78  //--- Calculate a maximal deflection
79  //---
80//  Modified by Sergey KHROMOV - Mon Mar 24 12:03:05 2003 Begin
81//   TheDeflection = 0.000000001;
82  TheDeflection = Min(0.000000001, Tol/100.);
83//  Modified by Sergey KHROMOV - Mon Mar 24 12:03:05 2003 End
84  i=1;
85  u=D.FirstParameter();
86  u+=du * 0.5;
87
88  do {
89    gp_Pnt2d Pm = TheCurveTool::Value(C,u);
90    const gp_Pnt2d& P1 = ThePnts.Value(i);
91    const gp_Pnt2d& P2 = ThePnts.Value(i+1);
92
93    u+=du;
94    i++;
95
96
97    Standard_Real dx,dy,t=0;
98    dx=P1.X()-P2.X(); if(dx<0) dx=-dx;
99    dy=P1.Y()-P2.Y(); if(dy<0) dy=-dy;
100    if(dx+dy>1e-12) {
101      gp_Lin2d L(P1,gp_Dir2d(gp_Vec2d(P1,P2)));
102      t = L.Distance(Pm);
103      if(t>TheDeflection) {
104	TheDeflection = t;
105      }
106    }
107  }
108  while(i<NbPts);
109
110  myBox.Enlarge(TheDeflection*MAJORATION_DEFLECTION);
111  ClosedPolygon = Standard_False;
112}
113//======================================================================
114void IntCurve_Polygon2dGen::ComputeWithBox(const TheCurve&        C,
115					   const Bnd_Box2d& BoxOtherPolygon) {
116  if(myBox.IsOut(BoxOtherPolygon)) {
117    NbPntIn=2;
118    myBox.SetVoid();
119  }
120  else {
121     Standard_Real bx0,bx1,by0,by1;
122     BoxOtherPolygon.Get(bx0,by0,bx1,by1);
123
124    bx0-=TheDeflection;
125    by0-=TheDeflection;
126    bx1+=TheDeflection;
127    by1+=TheDeflection;
128    Standard_Integer MaxIndexUsed = 1;
129    Standard_Integer i,nbp;
130    Standard_Integer Rprec,Ri;
131    Standard_Real x,y;
132
133    nbp = 0;
134    x = ThePnts.Value(TheIndex.Value(1)).X();
135    y = ThePnts.Value(TheIndex.Value(1)).Y();
136
137    Rprec = CalculRegion(x,y,bx0,bx1,by0,by1);
138    for(i = 2; i<=NbPntIn; i++) {
139      const gp_Pnt2d& P2d = ThePnts.Value(TheIndex.Value(i));
140      Ri = CalculRegion(P2d.X(),P2d.Y(),bx0,bx1,by0,by1);
141      if((Ri & Rprec)==0) {
142        if(nbp) {
143          if(TheIndex.Value(nbp) != TheIndex.Value(i-1)) {
144            nbp++;
145            TheIndex.SetValue(nbp,TheIndex.Value(i-1));
146          }
147        }
148        else {
149          nbp++;
150          TheIndex.SetValue(nbp,TheIndex.Value(i-1));
151        }
152        nbp++;
153        TheIndex.SetValue(nbp,TheIndex.Value(i));
154        if(TheIndex.Value(i) > MaxIndexUsed) MaxIndexUsed = TheIndex.Value(i);
155
156        Rprec = Ri;
157      }//if((Ri & Rprec)==0) condition
158
159      Rprec = Ri;
160    }
161    if(nbp==1) {
162      NbPntIn=2;
163      myBox.SetVoid();
164    }
165    else {
166      myBox.SetVoid();
167      if(nbp) {
168	myBox.Add(ThePnts.Value(TheIndex.Value(1)));
169      }
170      Standard_Real    RatioDeflection;
171      Standard_Integer nbpassagedeflection = 0;
172//      Standard_Integer PointHasBeenAdded = 0;
173      do {
174	nbpassagedeflection++;
175//  Modified by Sergey KHROMOV - Mon Mar 24 12:05:28 2003 Begin
176// 	Standard_Real NewDeflection = 0.0000001;
177	Standard_Real NewDeflection = TheDeflection;
178//  Modified by Sergey KHROMOV - Mon Mar 24 12:05:29 2003 End
179	for(i=2; i<=nbp; i++) {
180	  Standard_Integer Ii  = TheIndex.Value(i);
181	  Standard_Integer Iim1= TheIndex.Value(i-1);
182	  const gp_Pnt2d& Pi   = ThePnts.Value(Ii);
183	  const gp_Pnt2d& Pim1 = ThePnts.Value(Iim1);
184	  myBox.Add(Pi);
185	  Standard_Integer Regi   = CalculRegion(Pi.X(),Pi.Y(),bx0,bx1,by0,by1);
186	  Standard_Integer Regim1 = CalculRegion(Pim1.X(),Pim1.Y(),bx0,bx1,by0,by1);
187	  if((Regi & Regim1) == 0) {
188	    Standard_Real u = 0.5*( TheParams.Value(Ii)
189				   +TheParams.Value(Iim1));
190	    gp_Pnt2d Pm = TheCurveTool::Value(C,u);
191	    Standard_Real dx,dy,t=0;
192	    dx=Pim1.X()-Pi.X(); if(dx<0) dx=-dx;
193	    dy=Pim1.Y()-Pi.Y(); if(dy<0) dy=-dy;
194	    if(dx+dy>1e-12)  {
195	      gp_Lin2d L(Pim1,gp_Dir2d(gp_Vec2d(Pim1,Pi)));
196	      t = L.Distance(Pm);
197	      if((MaxIndexUsed<(TheMaxNbPoints-1)) && (t>(TheDeflection * 0.5))) {
198		const gp_Pnt2d& P1=Pim1;
199		nbp++;
200		for(Standard_Integer j=nbp; j>=i+1; j--) {
201		  TheIndex.SetValue(j,TheIndex.Value(j-1));
202		}
203		MaxIndexUsed++;
204		TheIndex.SetValue(i,MaxIndexUsed);
205		ThePnts.SetValue(MaxIndexUsed,Pm);
206		TheParams.SetValue(MaxIndexUsed,u);
207
208		Standard_Real u1m = 0.5*(u+TheParams.Value(TheIndex.Value(i-1)));
209		gp_Pnt2d P1m = TheCurveTool::Value(C,u1m);
210        gp_Lin2d L1m(P1,gp_Dir2d(gp_Vec2d(P1,Pm)));
211        t = L1m.Distance(P1m);
212		i--;
213	      }
214	    }
215	    else {
216	      if(t>NewDeflection) {
217		NewDeflection = t;
218	      }
219	    }
220	  }
221	}
222	if(NewDeflection)
223	  RatioDeflection = TheDeflection / NewDeflection;
224	else RatioDeflection = 10.0;
225	TheDeflection = NewDeflection;
226	NbPntIn = nbp;
227      }
228      while((RatioDeflection<3.0)
229	    && (nbpassagedeflection < 3)
230	    && (MaxIndexUsed<(TheMaxNbPoints-2)));
231    }
232
233    TheDeflection*=MAJORATION_DEFLECTION;
234    myBox.Enlarge(TheDeflection);
235  }
236  ClosedPolygon = Standard_False;
237  Dump();
238}
239
240
241Standard_Boolean IntCurve_Polygon2dGen::AutoIntersectionIsPossible() const {
242
243  gp_Vec2d VRef(ThePnts.Value(TheIndex.Value(1)),
244		ThePnts.Value(TheIndex.Value(2)));
245  for(Standard_Integer i=3; i<=NbPntIn; i++) {
246    gp_Vec2d V(ThePnts.Value(TheIndex.Value(i-1)),
247		ThePnts.Value(TheIndex.Value(i)));
248    if(V.Dot(VRef)<0.0) {
249      return(Standard_True);
250    }
251  }
252  return(Standard_False);
253}
254
255//======================================================================
256Standard_Real IntCurve_Polygon2dGen::ApproxParamOnCurve( const Standard_Integer Aindex
257							,const Standard_Real TheParamOnLine)
258     const
259{
260  Standard_Integer Indexp1,Index = Aindex;
261  Standard_Real    ParamOnLine = TheParamOnLine;
262  if (Index > NbPntIn) {
263    std::cout << "OutOfRange Polygon2d::ApproxParamOnCurve " <<std::endl;
264  }
265  if((Index == NbPntIn) && (ParamOnLine == 0.0)) {
266    Index--; ParamOnLine=1.0;
267  }
268  if(Index==0) {
269    Index=1;
270    ParamOnLine = 0.0;
271  }
272  Indexp1 = TheIndex.Value(Index+1);
273  Index   = TheIndex.Value(Index);
274
275  Standard_Real du = TheParams.Value(Indexp1)-TheParams.Value(Index);
276  Standard_Real u  = TheParams.Value(Index) + ParamOnLine * du;
277  return(u);
278}
279
280
281//======================================================================
282#if TEST
283
284extern Standard_Boolean DebugPolygon2d;
285extern void DrawSegmentBlanc(const gp_Pnt2d& _P1,const gp_Pnt2d& _P2);
286extern void DrawSegment(const gp_Pnt2d& _P1,const gp_Pnt2d& _P2);
287
288void IntCurve_Polygon2dGen::Dump(void) const {
289  if(!DebugPolygon2d) return;
290  Standard_Real bx0,bx1,by0,by1;
291  if(myBox.IsVoid()) return;
292  myBox.Get(bx0,by0,bx1,by1);
293  DrawSegment(gp_Pnt2d(bx0,by0),gp_Pnt2d(bx1,by0));
294  DrawSegment(gp_Pnt2d(bx1,by0),gp_Pnt2d(bx1,by1));
295  DrawSegment(gp_Pnt2d(bx1,by1),gp_Pnt2d(bx0,by1));
296  DrawSegment(gp_Pnt2d(bx0,by1),gp_Pnt2d(bx0,by0));
297  Standard_Integer i;
298  if(NbPntIn<=1) return;
299  for(i=2;i<=NbPntIn; i++) {
300    DrawSegmentBlanc(ThePnts.Value(TheIndex.Value(i-1)),ThePnts.Value(TheIndex.Value(i)));
301  }
302}
303#else
304void IntCurve_Polygon2dGen::Dump(void) const {
305  static int debug = 0;
306  if(debug) {
307    Standard_Real bx0,bx1,by0,by1;
308
309    std::cout<<"\n ----- Dump of IntCurve_Polygon2dGen -----"<<std::endl;
310    if(myBox.IsVoid()) {
311      std::cout<<"  Polygone Vide "<<std::endl;
312      return;
313    }
314    myBox.Get(bx0,by0,bx1,by1);
315    std::cout<<"  bx0:"<<bx0  <<std::endl;
316    std::cout<<"  by0:"<<by0<<std::endl;
317    std::cout<<"  bx1:"<<bx1<<std::endl;
318    std::cout<<"  by1:"<<by1<<std::endl;
319
320    Standard_Integer i;
321    for(i=1;i<=NbPntIn; i++) {
322      const gp_Pnt2d& P = ThePnts(TheIndex(i));
323      std::cout<<"  ("<<i<<") u:"<<TheParams.Value(TheIndex(i))<<" X:"<<P.X()<<"  Y:"<<P.Y()<<std::endl;
324    }
325  }
326}
327#endif
328//======================================================================
329void IntCurve_Polygon2dGen::Segment(const Standard_Integer theIndex,
330                                    gp_Pnt2d &theBegin, gp_Pnt2d &theEnd) const
331{
332  Standard_Integer ind = theIndex;
333  theBegin = ThePnts(TheIndex(theIndex));
334  if (theIndex >= NbPntIn) {
335    if (!ClosedPolygon)
336      throw Standard_OutOfRange("IntCurve_Polygon2dGen::Segment!");
337    ind = 0;
338  }
339  theEnd = ThePnts(TheIndex(ind+1));
340}
341//======================================================================
342