src/IntRes2d/IntRes2d_Intersection.cxx

   1 // Created on: 1992-04-28
   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
  18 #include <IntRes2d_Intersection.hxx>
  19 #include <IntRes2d_IntersectionPoint.hxx>
  20 #include <IntRes2d_IntersectionSegment.hxx>
  21 #include <IntRes2d_Position.hxx>
  22 #include <IntRes2d_SequenceOfIntersectionPoint.hxx>
  23 #include <IntRes2d_SequenceOfIntersectionSegment.hxx>
  24 #include <Standard_OutOfRange.hxx>
  25 #include <StdFail_NotDone.hxx>
  26
  27 #define PARAMEQUAL(a,b) (Abs((a)-(b))< (1e-8))
  28
  29
  30 static void InternalVerifyPosition(IntRes2d_Transition& T1,
  31                                    IntRes2d_Transition& T2,
  32                                    const Standard_Real PParamOnFirst,
  33                                    const Standard_Real PParamOnSecond,
  34                                    const Standard_Real FirstParam1,
  35                                    const Standard_Real LastParam1,
  36                                    const Standard_Real FirstParam2,
  37                                    const Standard_Real LastParam2);
  38
  39
  40
  41 //----------------------------------------------------------------------
  42 static Standard_Boolean TransitionEqual( const IntRes2d_Transition& T1
  43                                         ,const IntRes2d_Transition& T2);
  44
  45
  46 Standard_Boolean TransitionEqual( const IntRes2d_Transition& T1
  47                                  ,const IntRes2d_Transition& T2) {
  48
  49   if(T1.PositionOnCurve() == T2.PositionOnCurve())  {
  50     if(T1.TransitionType() == T2.TransitionType()) {
  51       if(T1.TransitionType() == IntRes2d_Touch) {
  52         if(T1.IsTangent()==T2.IsTangent()) {
  53           if(T1.Situation() == T2.Situation()) {
  54             if(T1.IsOpposite() == T2.IsOpposite()) {
  55               return(Standard_True);
  56             }
  57           }
  58         }
  59       }
  60       else {
  61         return(Standard_True);
  62       }
  63     }
  64   }
  65   return(Standard_False);
  66 }
  67
  68
  69
  70 void IntRes2d_Intersection::Insert(const IntRes2d_IntersectionPoint& Pnt) {
  71   Standard_Integer n = lpnt.Length();
  72   if(n==0) {
  73     lpnt.Append(Pnt);
  74   }
  75   else {
  76     Standard_Real u = Pnt.ParamOnFirst();
  77     Standard_Integer i = 1;
  78     Standard_Integer b = n+1;
  79     while(i<=n) {
  80       const IntRes2d_IntersectionPoint& Pnti=lpnt(i);
  81       Standard_Real ui = Pnti.ParamOnFirst();
  82       if(ui >= u) { b=i; i=n; }
  83       if(PARAMEQUAL(ui,u)) {
  84         if(PARAMEQUAL((Pnt.ParamOnSecond()),(Pnti.ParamOnSecond()))) {
  85           if(   (TransitionEqual(Pnt.TransitionOfFirst(),Pnti.TransitionOfFirst()))
  86              && (TransitionEqual(Pnt.TransitionOfSecond(),Pnti.TransitionOfSecond()))) {
  87             b=0;
  88             i=n;
  89           }
  90         }
  91       }
  92       //----------------------------------------------------------------
  93
  94       i++;
  95     }
  96     if(b>n)          { lpnt.Append(Pnt); }
  97     else if(b>0)     { lpnt.InsertBefore(b,Pnt); }
  98   }
  99 }
 100
 101 void IntRes2d_Intersection::SetValues(const IntRes2d_Intersection& Other) {
 102   Standard_Integer i ;
 103   if(Other.done) {
 104     lseg.Clear();
 105     lpnt.Clear();
 106     Standard_Integer N = Other.lpnt.Length();
 107     for( i=1; i<= N ; i++) {
 108       lpnt.Append(Other.lpnt(i));
 109     }
 110     N = Other.lseg.Length();
 111     for(i=1; i<= N ; i++) {
 112       lseg.Append(Other.lseg(i));
 113     }
 114     //-----------------------
 115     //lpnt=Other.lpnt;  Pose des problemes
 116     //lseg=Other.lseg;  pour des objets composites
 117     //-----------------------
 118     done=Standard_True;
 119   }
 120   else {
 121     done=Standard_False;
 122   }
 123 }
 124
 125 //----------------------------------------------------------------------
 126 //-- Function used to Merge the results of two Intersections .
 127 //-- for Composite Curves only. FirstParam and LastParam are the
 128 //--  parameter of the bounds of the composite Curve
 129 //-- Merge of two Intersection Segments S1 and S2 when :
 130 //--
 131 //--     S1 : U1First,PosU1Fisrt   -->  U1Last,PosU1Last
 132 //--          V1First,PosV1Fisrt   -->  V1Last,PosV1Last
 133 //--     S2 : U2First,PosU2Fisrt   -->  U2Last,PosU2Last
 134 //--          V2First,PosV2Fisrt   -->  V2Last,PosV2Last
 135 //--
 136 //--   1       U :      X------1-------E H-----2-------X   U -->
 137 //--           V :      X------1-------X X-----2-------X  <- V -> ?
 138 //--
 139 //--      PosU1Last == End    &&  PosU2First == Head
 140 //--      && U1Last == U2First
 141 //--      && V1Last == V2First
 142 //--
 143 //--   OR
 144 //--
 145 //--   2       U :      X------1-------H E-----2-------X   U <--
 146 //--           V :      X------1-------X X-----2-------X  <- V -> ?
 147 //--
 148 //--      PosU1Last == Head   &&  PosU2First == End
 149 //--      && U1Last == U2First
 150 //--      && V1Last == V2First
 151 //--
 152 //--  merge the two Segment in :
 153 //--
 154 //--           U :      X------1----------2-------X     U
 155 //--           V :      X------1----------2-------X  <- V -> ?
 156 //--
 157 //--
 158 //--
 159 //--  The Position of Intersection Point is set to Middle
 160 //--  when the Parameters U et V are between FirstParam1, EndParam1
 161 //--  and FirstParam2, EndParam2
 162 //--
 163 void IntRes2d_Intersection::Append( const IntRes2d_Intersection& Other
 164                                    ,const Standard_Real FirstParam1
 165                                    ,const Standard_Real LastParam1
 166                                    ,const Standard_Real FirstParam2
 167                                    ,const Standard_Real LastParam2) {
 168
 169
 170   if(Other.done) {
 171     //-- Verification of the Position of the IntersectionPoints
 172     Standard_Integer n=Other.lpnt.Length();
 173     Standard_Integer i ;
 174     for( i=1; i<=n ; i++) {
 175
 176       const IntRes2d_IntersectionPoint& P=Other.lpnt(i);
 177       Standard_Real PParamOnFirst=P.ParamOnFirst();
 178       Standard_Real PParamOnSecond=P.ParamOnSecond();
 179       IntRes2d_Transition T1=P.TransitionOfFirst();
 180       IntRes2d_Transition T2=P.TransitionOfSecond();
 181       gp_Pnt2d Pt=P.Value();
 182
 183
 184       InternalVerifyPosition(T1,T2
 185                              ,PParamOnFirst,PParamOnSecond
 186                              ,FirstParam1,LastParam1
 187                              ,FirstParam2,LastParam2);
 188
 189       this->Insert(IntRes2d_IntersectionPoint(Pt,
 190                                               PParamOnFirst,
 191                                               PParamOnSecond,
 192                                               T1,T2,
 193                                               Standard_False));
 194     }
 195
 196     //--------------------------------------------------
 197     //-- IntersectionSegment
 198     //-- (we assume that a composite curve is always bounded)
 199     //-- (a segment has always a FirstPoint and a LastPoint)
 200     //--------------------------------------------------
 201     n=Other.lseg.Length();
 202     Standard_Real SegModif_P1First=0,SegModif_P1Second=0;
 203     Standard_Real SegModif_P2First=0,SegModif_P2Second=0;
 204
 205     for(i=1; i<=n ; i++) {
 206
 207       const IntRes2d_IntersectionPoint& P1=Other.lseg(i).FirstPoint();
 208
 209       Standard_Real P1PParamOnFirst=P1.ParamOnFirst();
 210       Standard_Real P1PParamOnSecond=P1.ParamOnSecond();
 211       IntRes2d_Transition P1T1=P1.TransitionOfFirst();
 212       IntRes2d_Transition P1T2=P1.TransitionOfSecond();
 213       const gp_Pnt2d& P1Pt=P1.Value();
 214
 215       InternalVerifyPosition(P1T1,P1T2
 216                              ,P1PParamOnFirst,P1PParamOnSecond
 217                              ,FirstParam1,LastParam1
 218                              ,FirstParam2,LastParam2);
 219
 220       const IntRes2d_IntersectionPoint& P2=Other.lseg(i).LastPoint();
 221
 222       Standard_Real P2PParamOnFirst=P2.ParamOnFirst();
 223       Standard_Real P2PParamOnSecond=P2.ParamOnSecond();
 224       IntRes2d_Transition P2T1=P2.TransitionOfFirst();
 225       IntRes2d_Transition P2T2=P2.TransitionOfSecond();
 226       const gp_Pnt2d& P2Pt=P2.Value();
 227
 228       Standard_Boolean Opposite=Other.lseg(i).IsOpposite();
 229
 230       InternalVerifyPosition(P2T1,P2T2
 231                              ,P2PParamOnFirst,P2PParamOnSecond
 232                              ,FirstParam1,LastParam1
 233                              ,FirstParam2,LastParam2);
 234
 235
 236
 237       //-- Loop on the previous segments
 238       //--
 239       Standard_Integer an=lseg.Length();
 240       Standard_Boolean NotYetModified=Standard_True;
 241
 242       for(Standard_Integer j=1;(j<=an)&&(NotYetModified);j++) {
 243
 244         const IntRes2d_IntersectionPoint& AnP1=lseg(j).FirstPoint();
 245         Standard_Real AnP1PParamOnFirst=AnP1.ParamOnFirst();
 246         Standard_Real AnP1PParamOnSecond=AnP1.ParamOnSecond();
 247
 248         const IntRes2d_IntersectionPoint& AnP2=lseg(j).LastPoint();
 249         Standard_Real AnP2PParamOnFirst=AnP2.ParamOnFirst();
 250         Standard_Real AnP2PParamOnSecond=AnP2.ParamOnSecond();
 251
 252         if(Opposite == lseg(j).IsOpposite()) {
 253           //---------------------------------------------------------------
 254           //--    AnP1---------AnP2
 255           //--                  P1-------------P2
 256           //--
 257           if(  PARAMEQUAL(P1PParamOnFirst,AnP2PParamOnFirst)
 258              &&PARAMEQUAL(P1PParamOnSecond,AnP2PParamOnSecond)) {
 259             NotYetModified=Standard_False;
 260             lseg(j)=IntRes2d_IntersectionSegment(AnP1,P2,
 261                                                  Opposite,Standard_False);
 262             SegModif_P1First   = AnP1PParamOnFirst;
 263             SegModif_P1Second  = AnP1PParamOnSecond;
 264             SegModif_P2First   = P2PParamOnFirst;
 265             SegModif_P2Second  = P2PParamOnSecond;
 266           }
 267           //---------------------------------------------------------------
 268           //--                                AnP1---------AnP2
 269           //--                  P1-------------P2
 270           //--
 271           else if(  PARAMEQUAL(P2PParamOnFirst,AnP1PParamOnFirst)
 272                   &&PARAMEQUAL(P2PParamOnSecond,AnP1PParamOnSecond)) {
 273             NotYetModified=Standard_False;
 274             lseg(j)=IntRes2d_IntersectionSegment(P1,AnP2,
 275                                                  Opposite,Standard_False);
 276             SegModif_P1First   = P1PParamOnFirst;
 277             SegModif_P1Second  = P1PParamOnSecond;
 278             SegModif_P2First   = AnP2PParamOnFirst;
 279             SegModif_P2Second  = AnP2PParamOnSecond;
 280           }
 281           //---------------------------------------------------------------
 282           //--    AnP2---------AnP1
 283           //--                  P1-------------P2
 284           //--
 285           if(  PARAMEQUAL(P1PParamOnFirst,AnP1PParamOnFirst)
 286              &&PARAMEQUAL(P1PParamOnSecond,AnP1PParamOnSecond)) {
 287             NotYetModified=Standard_False;
 288             lseg(j)=IntRes2d_IntersectionSegment(AnP2,P2,
 289                                                  Opposite,Standard_False);
 290             SegModif_P1First   = P2PParamOnFirst;
 291             SegModif_P1Second  = P2PParamOnSecond;
 292             SegModif_P2First   = AnP2PParamOnFirst;
 293             SegModif_P2Second  = AnP2PParamOnSecond;
 294           }
 295           //---------------------------------------------------------------
 296           //--                                AnP2---------AnP1
 297           //--                  P1-------------P2
 298           //--
 299           else if(  PARAMEQUAL(P2PParamOnFirst,AnP2PParamOnFirst)
 300                   &&PARAMEQUAL(P2PParamOnSecond,AnP2PParamOnSecond)) {
 301             NotYetModified=Standard_False;
 302             lseg(j)=IntRes2d_IntersectionSegment(P1,AnP1,
 303                                                  Opposite,Standard_False);
 304             SegModif_P1First   = P1PParamOnFirst;
 305             SegModif_P1Second  = P1PParamOnSecond;
 306             SegModif_P2First   = AnP1PParamOnFirst;
 307             SegModif_P2Second  = AnP1PParamOnSecond;
 308           }
 309         }
 310       }
 311       if(NotYetModified) {
 312         this->Append(IntRes2d_IntersectionSegment(
 313                             IntRes2d_IntersectionPoint(P1Pt,
 314                                                        P1PParamOnFirst,
 315                                                        P1PParamOnSecond,
 316                                                        P1T1,P1T2,
 317                                                        Standard_False),
 318                             IntRes2d_IntersectionPoint(P2Pt,
 319                                                        P2PParamOnFirst,
 320                                                        P2PParamOnSecond,
 321                                                        P2T1,P2T2,
 322                                                        Standard_False),
 323                                                   Opposite,Standard_False));
 324
 325       }    //-- if(NotYetModified)
 326       else {
 327         //--------------------------------------------------------------
 328         //-- Are some Existing Points in this segment ?
 329         //--------------------------------------------------------------
 330         Standard_Integer rnbpts=lpnt.Length();
 331         for(Standard_Integer rp=1; (rp<=rnbpts)&&(rp>=1); rp++) {
 332           Standard_Real PonFirst=lpnt(rp).ParamOnFirst();
 333           Standard_Real PonSecond=lpnt(rp).ParamOnSecond();
 334
 335           if(  ((PonFirst  >=   SegModif_P1First    &&    PonFirst  <=  SegModif_P2First)
 336               ||(PonFirst  <=   SegModif_P1First    &&    PonFirst  >=  SegModif_P2First))
 337             && ((PonSecond >=   SegModif_P1Second   &&    PonSecond <=  SegModif_P2Second)
 338               ||(PonSecond<=    SegModif_P1Second   &&    PonSecond >=  SegModif_P2Second))) {
 339             lpnt.Remove(rp);
 340             rp--;
 341             rnbpts--;
 342           }
 343         }  //-- for(Standard_Integer rp=1; (rp<=rnbpts)&&(rp>=1); rp++)
 344       }
 345     }
 346     //--------------------------------------------------
 347     //-- Remove some Points ?
 348     //-- Example : Points which lie in a segment.
 349     //--------------------------------------------------
 350
 351     done=Standard_True;
 352   }
 353   else {
 354     done=Standard_False;
 355   }
 356 }
 357
 358
 359 //----------------------------------------------------------------------
 360 //--
 361 #define DEBUGPOSITION 0
 362
 363 #if DEBUGPOSITION
 364 void AffPosition(IntRes2d_Transition& T,const Standard_Real u,const char *Texte);
 365 void AffPosition(IntRes2d_Transition& T,const Standard_Real u,const char *Texte) {
 366   if(T.PositionOnCurve() == IntRes2d_End) { std::cout <<Texte<<" Param :"<<u<<" End "<<std::endl; }
 367   if(T.PositionOnCurve() == IntRes2d_Middle) { std::cout <<Texte<<" Param :"<<u<<" Middle "<<std::endl; }
 368   if(T.PositionOnCurve() == IntRes2d_Head) { std::cout <<Texte<<" Param :"<<u<<" Head "<<std::endl; }
 369 }
 370 #endif
 371
 372 void InternalVerifyPosition(IntRes2d_Transition& T1,
 373                             IntRes2d_Transition& T2,
 374                             const Standard_Real PParamOnFirst,
 375                             const Standard_Real PParamOnSecond,
 376                             const Standard_Real FirstParam1,
 377                             const Standard_Real LastParam1,
 378                             const Standard_Real FirstParam2,
 379                             const Standard_Real LastParam2) {
 380 #if DEBUGPOSITION
 381 AffPosition(T1,PParamOnFirst," Point 1 ");
 382 AffPosition(T2,PParamOnSecond," Point 2 ");
 383 #endif
 384   if(T1.PositionOnCurve() != IntRes2d_Middle) {
 385     if(!(   PARAMEQUAL(PParamOnFirst,FirstParam1)
 386          || PARAMEQUAL(PParamOnFirst,LastParam1)))  {
 387       //-- Middle on the Curve 1
 388
 389       // modified by NIZHNY-MKK  Tue Nov 26 14:23:24 2002.BEGIN
 390       if((PParamOnFirst > FirstParam1) && (PParamOnFirst < LastParam1))
 391       // modified by NIZHNY-MKK  Tue Nov 26 14:23:27 2002.END
 392         T1.SetPosition(IntRes2d_Middle);
 393     }
 394   }
 395   if(T2.PositionOnCurve() != IntRes2d_Middle) {
 396     if(!(   PARAMEQUAL(PParamOnSecond,FirstParam2)
 397          || PARAMEQUAL(PParamOnSecond,LastParam2))) {
 398
 399       // modified by NIZHNY-MKK  Tue Nov 26 14:24:15 2002.BEGIN
 400       if((PParamOnSecond > FirstParam2) && (PParamOnSecond < LastParam2))
 401       // modified by NIZHNY-MKK  Tue Nov 26 14:24:19 2002.END
 402         T2.SetPosition(IntRes2d_Middle);
 403     }
 404   }
 405 }
 406 //----------------------------------------------------------------------
 407
 408
 409
 410
 411
 412
 413
 414 #if 0
 415 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 416 #define Debug(q) std::cout<<"IntRes2d_Intersectionq ="<<q<<std::endl;
 417
 418 char *DebugPos(const IntRes2d_Position P);
 419
 420 Debug(FirstParam1);
 421 Debug(LastParam1);
 422 Debug(FirstParam2);
 423 Debug(LastParam2);
 424 Debug(PParamOnFirst);
 425 Debug(PParamOnSecond);
 426 std::cout<<" ##### T1  <> Middle ###### "<<DebugPos(T1.PositionOnCurve())<<std::endl;
 427 char *DebugPos(const IntRes2d_Position P) {
 428   if(P==IntRes2d_Middle) return(" Middle ");
 429   if(P==IntRes2d_Head) return(" Head ");
 430   if(P==IntRes2d_End) return(" End ");
 431 }
 432 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 433 #endif
 434