src/lineconn2d/LineConn2d_Path.cxx

   1 // File:      LineConn2d_Path.cpp
   2 // Created:   11.08.05 15:16:13
   3 // Author:    Alexander GRIGORIEV
   4 // Copyright: Open Cascade 2005
   5
   6
   7 #include <LineConn2dAfx.h>
   8
   9 #include <LineConn2d_Path.h>
  10 #include <LineConn2d_Model.h>
  11 #include <LineConn2d_SegmentIterator.h>
  12
  13 //=======================================================================
  14 //function : LineConn2d_Path
  15 //purpose  : Empty constructor
  16 //=======================================================================
  17
  18 LineConn2d_Path::LineConn2d_Path ()
  19    : myModel            (0L),
  20      myParent           (0L),
  21      myPriceLen         (0),
  22      myPriceDist        (0),
  23      myLimitation       (0),
  24      myOrient           (LineConn2d::Indefinite),
  25      myIsComplete       (Standard_False) {}
  26
  27 //=======================================================================
  28 //function : LineConn2d_Path()
  29 //purpose  : Constructor
  30 //=======================================================================
  31
  32 LineConn2d_Path::LineConn2d_Path (const gp_XY&             theStart,
  33                                   const gp_XY&             theEnd,
  34                                   const LineConn2d_Model&  theModel,
  35                                   const LineConn2d::Orient theOri)
  36   : LineConn2d_Segment  (theStart, theEnd),
  37     myModel             (&theModel),
  38     myParent            (0L),
  39     myBranches          (theModel.TempAlloc()),
  40     myPriceLen          (0),
  41     myPriceDist         (0),
  42     myLimitation        (0),
  43     myOrient            (theOri),
  44     myIsComplete        (Standard_False)
  45 {
  46   if (theOri == LineConn2d::Indefinite)
  47     myOrient = LineConn2d::Orientation (Delta());
  48 }
  49
  50 //=======================================================================
  51 //function : Width
  52 //purpose  :
  53 //=======================================================================
  54
  55 Standard_Real LineConn2d_Path::Width () const
  56 {
  57   return (myModel ? myModel -> Tolerance() : 0.);
  58 }
  59
  60 //=======================================================================
  61 //function : AddBranch
  62 //purpose  :
  63 //=======================================================================
  64
  65 void LineConn2d_Path::AddBranch (LineConn2d_Path& theBranch,
  66                                  const gp_XY&     theTgt)
  67 {
  68   theBranch.myParent = this;
  69   theBranch.Evaluate (theTgt);
  70   myBranches.Append (theBranch);
  71 }
  72
  73 //=======================================================================
  74 //function : Evaluate
  75 //purpose  :
  76 //=======================================================================
  77
  78 Standard_Integer LineConn2d_Path::Evaluate (const gp_XY& theTarget)
  79 {
  80   const Standard_Real aHalfPerimeterNorm  (myModel->HalfPerimeter() / 1000.);
  81   const Standard_Real aHalfPerimeterNorm1 (aHalfPerimeterNorm * 10.);
  82
  83   // Calculate the price due to the distance
  84   const gp_XY aDistVector (theTarget - Extremity());
  85   // ... distance from the extremity to the target
  86   const Standard_Real aDist =
  87     LineConn2d_FABS(aDistVector.X()) + LineConn2d_FABS(aDistVector.Y());
  88   // ... deflection from the shortest way
  89   gp_XY aV = theTarget - Origin();
  90   Standard_Real aDist1 = (Delta() ^ aV);
  91   aDist1 = ::sqrt((aDist1 * aDist1) / (aV * aV));
  92
  93   if (aDist < Precision::Confusion())
  94     myIsComplete = Standard_True;
  95
  96   myPriceDist = Standard_Integer ((aDist + 0.2 * aDist1) / aHalfPerimeterNorm);
  97
  98   // Calculate the price due to length.
  99   myPriceLen = Standard_Integer (Delta().Modulus() / aHalfPerimeterNorm1);
 100
 101   // Take into account the additive from the parent
 102   if (myParent != 0L) {
 103     if (myParent -> Orientation() != myOrient)
 104       myPriceLen += PriceOfBreak();
 105     myPriceLen += (myParent -> myPriceLen -
 106                    (Origin() - myParent->Extremity()).Modulus()
 107                       / aHalfPerimeterNorm1);
 108   }
 109   return myPriceLen + myPriceDist;
 110 }
 111
 112 //=======================================================================
 113 //function : createPath
 114 //purpose  :
 115 //=======================================================================
 116
 117 Standard_Boolean LineConn2d_Path::createPath
 118                                         (LineConn2d_Path&          thePath,
 119                                          const LineConn2d_Model&   theModel,
 120                                          const gp_XY&              theStart,
 121                                          const LineConn2d::Orient  theOrient,
 122                                          const Standard_Boolean    isRoot)
 123 {
 124   Standard_Boolean aResult (Standard_False);
 125   const Standard_Real aTol = theModel.Tolerance();
 126   // Create a long box extending in the direction theOrient (till the boundary)
 127   LineConn2d_Box        aPathBox;
 128   const LineConn2d_Box& aModelBox = theModel.Box();
 129   Standard_Real         aPathBoxLen (0.);
 130   gp_XY                 aPathDir (0., 0.);
 131   // Four segments forming the PathBox:
 132   // 0 - the transversal segment containing theStart
 133   // 1 - left side
 134   // 2 - the front
 135   // 3 - the right side
 136   LineConn2d_Segment aSeg[4];
 137   switch (theOrient) {
 138   case LineConn2d::E:
 139     aPathBoxLen = aModelBox.Center().X() + aModelBox.HSize().X() - theStart.X();
 140     aPathBox = LineConn2d_Box (theStart + gp_XY (0.5 * aPathBoxLen, 0.),
 141                                gp_XY (0.5 * aPathBoxLen, aTol));
 142     aPathDir.SetX (1.);
 143     aSeg[0] = LineConn2d_Segment (theStart + gp_XY (0., -aTol),
 144                                   theStart + gp_XY (0., aTol));
 145     aSeg[1] = LineConn2d_Segment (theStart + gp_XY (0., aTol),
 146                                   theStart + gp_XY (aPathBoxLen, aTol));
 147     aSeg[2] = LineConn2d_Segment (theStart + gp_XY (aPathBoxLen, aTol),
 148                                   theStart + gp_XY (aPathBoxLen, -aTol));
 149     aSeg[3] = LineConn2d_Segment (theStart + gp_XY (0., -aTol),
 150                                   theStart + gp_XY (aPathBoxLen, -aTol));
 151     break;
 152   case LineConn2d::N:
 153     aPathBoxLen = aModelBox.Center().Y() + aModelBox.HSize().Y() - theStart.Y();
 154     aPathBox = LineConn2d_Box (theStart + gp_XY (0., 0.5 * aPathBoxLen),
 155                                gp_XY (aTol, 0.5 * aPathBoxLen));
 156     aPathDir.SetY (1.);
 157     aSeg[0] = LineConn2d_Segment (theStart + gp_XY (aTol, 0.),
 158                                   theStart + gp_XY (-aTol, 0.));
 159     aSeg[1] = LineConn2d_Segment (theStart + gp_XY (-aTol, 0),
 160                                   theStart + gp_XY (-aTol, aPathBoxLen));
 161     aSeg[2] = LineConn2d_Segment (theStart + gp_XY (-aTol, aPathBoxLen),
 162                                   theStart + gp_XY (aTol, aPathBoxLen));
 163     aSeg[3] = LineConn2d_Segment (theStart + gp_XY (aTol, 0.),
 164                                   theStart + gp_XY (aTol, aPathBoxLen));
 165     break;
 166   case LineConn2d::W:
 167     aPathBoxLen= -aModelBox.Center().X() + aModelBox.HSize().X() + theStart.X();
 168     aPathBox = LineConn2d_Box (theStart - gp_XY (0.5 * aPathBoxLen, 0.),
 169                                gp_XY (0.5 * aPathBoxLen, aTol));
 170     aPathDir.SetX (-1.);
 171     aSeg[0] = LineConn2d_Segment (theStart - gp_XY (0., -aTol),
 172                                   theStart - gp_XY (0., aTol));
 173     aSeg[1] = LineConn2d_Segment (theStart - gp_XY (0., aTol),
 174                                   theStart - gp_XY (aPathBoxLen, aTol));
 175     aSeg[2] = LineConn2d_Segment (theStart - gp_XY (aPathBoxLen, aTol),
 176                                   theStart - gp_XY (aPathBoxLen, -aTol));
 177     aSeg[3] = LineConn2d_Segment (theStart - gp_XY (0., -aTol),
 178                                   theStart - gp_XY (aPathBoxLen, -aTol));
 179     break;
 180   case LineConn2d::S:
 181     aPathBoxLen= -aModelBox.Center().Y() + aModelBox.HSize().Y() + theStart.Y();
 182     aPathBox = LineConn2d_Box (theStart - gp_XY (0., 0.5 * aPathBoxLen),
 183                                gp_XY (aTol, 0.5 * aPathBoxLen));
 184     aPathDir.SetY (-1.);
 185     aSeg[0] = LineConn2d_Segment (theStart - gp_XY (aTol, 0.),
 186                                   theStart - gp_XY (-aTol, 0.));
 187     aSeg[1] = LineConn2d_Segment (theStart - gp_XY (-aTol, 0),
 188                                   theStart - gp_XY (-aTol, aPathBoxLen));
 189     aSeg[2] = LineConn2d_Segment (theStart - gp_XY (-aTol, aPathBoxLen),
 190                                   theStart - gp_XY (aTol, aPathBoxLen));
 191     aSeg[3] = LineConn2d_Segment (theStart - gp_XY (aTol, 0.),
 192                                   theStart - gp_XY (aTol, aPathBoxLen));
 193     break;
 194   }
 195
 196   // Find intersections between aPathBox and the model Objects
 197   Standard_Real aMinInterDistance (aPathBoxLen);
 198   Standard_Integer anInterSide (0);
 199
 200   aPathBox.Enlarge (4 * Precision::Confusion());
 201   LineConn2d_BoxTreeSelector aSelBox (aPathBox);
 202   theModel.GetTree().Select (aSelBox);
 203   NCollection_List<const LineConn2d_Object *>::Iterator
 204     aSelBoxIter (aSelBox.GetObjects());
 205   for (; aSelBoxIter.More(); aSelBoxIter.Next()) {
 206     LineConn2d_SegmentIterator anIter (* aSelBoxIter.Value());
 207     Standard_Real aMinDistance (aMinInterDistance);
 208     // Loop on the segments of the Object
 209     for (; anIter.More(); anIter.Next()) {
 210       const LineConn2d_Segment& aSegment = anIter.Value();
 211       Standard_Real anAlpha[2];
 212       // intersection box - segment
 213       if (aPathBox.IsOut (aSegment) == Standard_False) {
 214         if (aSeg[0].IsIntersect (aSegment, anAlpha)) // intersect with the rear
 215         {
 216           // cancel intersection test, the rear intersection means the
 217           // intersection with the own object
 218           aMinDistance = (isRoot ? ::RealLast() : 0.);
 219           break;
 220         }
 221         if (aSeg[1].IsIntersect (aSegment, anAlpha)) // intersect with the Left
 222         {
 223           const Standard_Real aDist = anAlpha[0] * aPathBoxLen;
 224           if (aDist < aMinDistance) {
 225             aMinDistance = aDist;
 226             anInterSide = -1;
 227           }
 228         }
 229         if (aSeg[3].IsIntersect (aSegment, anAlpha)) // intersect with the Right
 230         {
 231           const Standard_Real aDist = anAlpha[0] * aPathBoxLen;
 232           if (aDist < aMinDistance) {
 233             aMinDistance = aDist;
 234             anInterSide = 1;
 235           }
 236         }
 237         if (aPathBox.IsOut (aSegment.Origin()) == Standard_False) {
 238           const Standard_Real aDist = (aSegment.Origin() - theStart) * aPathDir;
 239           if (aDist < aMinDistance) {
 240             aMinDistance = aDist;
 241             anInterSide = 0;
 242           }
 243         }
 244       }
 245     }
 246     if (aMinDistance < aMinInterDistance)
 247       aMinInterDistance = aMinDistance;
 248   }
 249
 250   // The PathLine segment is the medial segment of the PathBox prolongated
 251   // by the Tolerance (i.e., by the half-width of the PathBox). Find the
 252   // intersection with this PathLine. This intersection also delimits the Path.
 253   if (aMinInterDistance > aTol) {
 254     Standard_Real aPathLineDist = aTol + aMinInterDistance + 2 * Precision::Confusion();
 255     if (aPathLineDist > aPathBoxLen)
 256       aPathLineDist = aPathBoxLen;
 257     const LineConn2d_Segment aPathLine
 258       (theStart, theStart + aPathDir * aPathLineDist);
 259
 260     LineConn2d_BoxTreeSelector aSelSeg (aPathLine);
 261     theModel.GetTree().Select (aSelSeg);
 262     NCollection_List<const LineConn2d_Object *>::Iterator
 263       aSelSegIter (aSelSeg.GetObjects());
 264     for (; aSelSegIter.More(); aSelSegIter.Next()) {
 265       LineConn2d_SegmentIterator anIter (* aSelSegIter.Value());
 266       for (; anIter.More(); anIter.Next()) {
 267         const LineConn2d_Segment& aSegment = anIter.Value();
 268         Standard_Real anAlpha[2];
 269         // intersection pathline - segment
 270         if (aPathLine.IsIntersect (aSegment, anAlpha)) {
 271           const Standard_Real aDist = anAlpha[0] * aPathLineDist - aTol;
 272           if (aDist < aMinInterDistance && aDist > 0)
 273             aMinInterDistance = aDist;
 274         }
 275       }
 276     }
 277   }
 278
 279   if (aMinInterDistance > aTol) {
 280     thePath = LineConn2d_Path (theStart, theStart + aMinInterDistance*aPathDir,
 281                                theModel, theOrient);
 282     thePath.myLimitation = anInterSide;
 283     aResult = Standard_True;
 284   }
 285   return aResult;
 286 }
 287
 288 //=======================================================================
 289 //function : Orientation
 290 //purpose  :
 291 //=======================================================================
 292
 293 LineConn2d::Orient LineConn2d_Path::Orientation
 294                                         (const Standard_Integer theSide) const
 295 {
 296   LineConn2d::Orient aResult (myOrient);
 297   switch (theSide) {
 298   case 1:
 299     ((Standard_Integer&)aResult) --;
 300     if (aResult == LineConn2d::Indefinite)
 301       aResult = LineConn2d::S;
 302     break;
 303   case -1:
 304     ((Standard_Integer&)aResult) ++;
 305     if (aResult == LineConn2d::Indefinite1)
 306       aResult = LineConn2d::E;
 307     break;
 308   }
 309   return aResult;
 310 }
 311
 312
 313 //=======================================================================
 314 //function : Direction
 315 //purpose  :
 316 //=======================================================================
 317
 318 gp_XY LineConn2d_Path::Direction (const Standard_Integer theSide) const
 319 {
 320   gp_XY aResult (0., 0.);
 321   switch (theSide) {
 322   case -1:
 323     switch (myOrient) {
 324     case LineConn2d::E : aResult.SetY (1.); break;
 325     case LineConn2d::N : aResult.SetX (-1.); break;
 326     case LineConn2d::W : aResult.SetY (-1.); break;
 327     case LineConn2d::S : aResult.SetX (1.); break;
 328     }
 329     break;
 330   case 0:
 331     switch (myOrient) {
 332     case LineConn2d::E : aResult.SetX (1.); break;
 333     case LineConn2d::N : aResult.SetY (1.); break;
 334     case LineConn2d::W : aResult.SetX (-1.); break;
 335     case LineConn2d::S : aResult.SetY (-1.); break;
 336     }
 337     break;
 338   case 1:
 339     switch (myOrient) {
 340     case LineConn2d::E : aResult.SetY (-1.); break;
 341     case LineConn2d::N : aResult.SetX (1.); break;
 342     case LineConn2d::W : aResult.SetY (1.); break;
 343     case LineConn2d::S : aResult.SetX (-1.); break;
 344     }
 345     break;
 346   }
 347   return aResult;
 348 }
 349
 350 //=======================================================================
 351 //function : ProjectPoint
 352 //purpose  :
 353 //=======================================================================
 354
 355 Standard_Boolean LineConn2d_Path::ProjectPoint (gp_XY&         theProj,
 356                                                 const gp_XY&   thePoint) const
 357 {
 358   Standard_Boolean aResult (Standard_False);
 359   switch (myOrient) {
 360   case LineConn2d::E :
 361     if (LineConn2d::IsInside (thePoint.X(),
 362                               Origin().X(),
 363                               Extremity().X()))
 364     {
 365       aResult = Standard_True;
 366       theProj.SetCoord (thePoint.X(), Origin().Y());
 367     }
 368     break;
 369   case LineConn2d::W :
 370     if (LineConn2d::IsInside (thePoint.X(),
 371                               Extremity().X(),
 372                               Origin().X()))
 373     {
 374       aResult = Standard_True;
 375       theProj.SetCoord (thePoint.X(), Origin().Y());
 376     }
 377     break;
 378   case LineConn2d::N :
 379     if (LineConn2d::IsInside (thePoint.Y(),
 380                               Origin().Y(),
 381                               Extremity().Y()))
 382     {
 383       aResult = Standard_True;
 384       theProj.SetCoord (Origin().X(), thePoint.Y());
 385     }
 386     break;
 387   case LineConn2d::S :
 388     if (LineConn2d::IsInside (thePoint.Y(),
 389                               Extremity().Y(),
 390                               Origin().Y()))
 391     {
 392       aResult = Standard_True;
 393       theProj.SetCoord (Origin().X(), thePoint.Y());
 394     }
 395     break;
 396   }
 397   return aResult;
 398 }