src/IntCurve/IntCurve_Polygon2dGen.gxx

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