[occt.git] / src / BRepTools / BRepTools_WireExplorer.cxx

// Created on: 1993-01-21
// Created by: Remi LEQUETTE
// Copyright (c) 1993-1999 Matra Datavision
// Copyright (c) 1999-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.


#include <BRep_Tool.hxx>
#include <BRepTools.hxx>
#include <BRepTools_WireExplorer.hxx>
#include <Geom2d_Curve.hxx>
#include <Geom_Surface.hxx>
#include <GeomAdaptor_Surface.hxx>
#include <gp_Pnt2d.hxx>
#include <Precision.hxx>
#include <Standard_DomainError.hxx>
#include <Standard_NoMoreObject.hxx>
#include <Standard_NoSuchObject.hxx>
#include <TopExp.hxx>
#include <TopExp_Explorer.hxx>
#include <TopoDS.hxx>
#include <TopoDS_Edge.hxx>
#include <TopoDS_Face.hxx>
#include <TopoDS_Iterator.hxx>
#include <TopoDS_Vertex.hxx>
#include <TopoDS_Wire.hxx>
#include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
#include <TopTools_ListIteratorOfListOfShape.hxx>
#include <TopTools_ListOfShape.hxx>
#include <TopTools_MapIteratorOfMapOfShape.hxx>
#include <TopTools_MapOfShape.hxx>

//=======================================================================
// forward declarations of aux functions
//=======================================================================
static Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
				     TopTools_ListOfShape& L,
				     TopoDS_Edge&          E);

static Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
					  TopoDS_Edge&          E);

static Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
				      const gp_Pnt2d& aPRef,
				      const Standard_Real& fP,
				      const Standard_Real& lP,
				      const Standard_Real& tolU,
				      const Standard_Real& tolV,
				      const Standard_Boolean& reverse);

//=======================================================================
//function : BRepTools_WireExplorer
//purpose  : 
//=======================================================================
BRepTools_WireExplorer::BRepTools_WireExplorer() 
{
}

//=======================================================================
//function : BRepTools_WireExplorer
//purpose  : 
//=======================================================================
BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W)
{
  TopoDS_Face F = TopoDS_Face();
  Init(W,F);
}

//=======================================================================
//function : BRepTools_WireExplorer
//purpose  : 
//=======================================================================
BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W,
					       const TopoDS_Face& F)
{
  Init(W,F);
}

//=======================================================================
//function : Init
//purpose  : 
//=======================================================================
void  BRepTools_WireExplorer::Init(const TopoDS_Wire& W)
{  
  TopoDS_Face F = TopoDS_Face();
  Init(W,F);
}

//=======================================================================
//function : Init
//purpose  : 
//=======================================================================
void  BRepTools_WireExplorer::Init(const TopoDS_Wire& W,
				   const TopoDS_Face& F)
{
  myEdge = TopoDS_Edge();
  myVertex = TopoDS_Vertex();
  myMap.Clear();
  myDoubles.Clear();

  if( W.IsNull() )
    return;

  myFace = F;
  Standard_Real dfVertToler = 0.;
  myReverse = Standard_False;

  if (!myFace.IsNull())
    {
      BRepTools::Update(myFace);
      TopLoc_Location aL;  
      const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(myFace, aL);
      GeomAdaptor_Surface aGAS(aSurf);
      TopExp_Explorer anExp(W, TopAbs_VERTEX);
      for(; anExp.More(); anExp.Next())
	{
	  const TopoDS_Vertex& aV = TopoDS::Vertex(anExp.Current());
	  dfVertToler = Max(BRep_Tool::Tolerance(aV), dfVertToler);
	}
      myTolU = 2. * aGAS.UResolution(dfVertToler);
      myTolV = 2. * aGAS.VResolution(dfVertToler);
      
      // uresolution for cone with infinite vmin vmax is too small.
      if(aGAS.GetType() == GeomAbs_Cone)
	{
	  Standard_Real u1, u2, v1, v2;
	  BRepTools::UVBounds(myFace, u1, u2, v1, v2);
	  gp_Pnt aP;
	  gp_Vec aD1U, aD1V;
	  aGAS.D1(u1, v1, aP, aD1U, aD1V);
	  Standard_Real tol1, tol2, maxtol = .0005*(u2-u1);
	  Standard_Real a = aD1U.Magnitude();

	  if(a <= Precision::Confusion())
	    tol1 = maxtol;
	  else
	    tol1 = Min(maxtol, dfVertToler/a);

	  aGAS.D1(u1, v2, aP, aD1U, aD1V);
	  a = aD1U.Magnitude();
	  if(a <= Precision::Confusion())
	    tol2 = maxtol;
	  else
	    tol2 = Min(maxtol, dfVertToler/a);

	  myTolU = 2. * Max(tol1, tol2);
	}

      if( aGAS.GetType() == GeomAbs_BSplineSurface || 
	  aGAS.GetType() == GeomAbs_BezierSurface )
	{
	  Standard_Real maxTol = Max(myTolU,myTolV);
	  myTolU = maxTol;
	  myTolV = maxTol;
	}

      myReverse = (myFace.Orientation() == TopAbs_REVERSED);
    }
      
  // map of vertices to know if the wire is open
  TopTools_MapOfShape vmap;
  //  Modified by Sergey KHROMOV - Mon May 13 11:50:48 2002 Begin
  //  map of infinite edges
  TopTools_MapOfShape anInfEmap;
  //  Modified by Sergey KHROMOV - Mon May 13 11:50:49 2002 End

  // list the vertices
  TopoDS_Vertex V1,V2;
  TopTools_ListOfShape empty;

  TopoDS_Iterator it(W);
  while (it.More())
    {
      const TopoDS_Edge& E = TopoDS::Edge(it.Value());
      TopAbs_Orientation Eori = E.Orientation();
      if (Eori == TopAbs_INTERNAL || Eori == TopAbs_EXTERNAL)
	{
	  it.Next();
	  continue;
	}
      TopExp::Vertices(E,V1,V2,Standard_True);

      if( !V1.IsNull() )
	{
	  if( !myMap.IsBound(V1) )
	    myMap.Bind(V1,empty);
	  myMap(V1).Append(E);

	  // add or remove in the vertex map
	  V1.Orientation(TopAbs_FORWARD);
	  if( !vmap.Add(V1) )
	    vmap.Remove(V1);
	}

      if( !V2.IsNull() )
	{
	  V2.Orientation(TopAbs_REVERSED);
	  if(!vmap.Add(V2))
	    vmap.Remove(V2);
	}

      //  Modified by Sergey KHROMOV - Mon May 13 11:52:20 2002 Begin
      if (V1.IsNull() || V2.IsNull())
	{
	  Standard_Real aF = 0., aL = 0.;
	  BRep_Tool::Range(E, aF, aL);
	  
	  if(Eori == TopAbs_FORWARD)
	    {
	      if (aF == -Precision::Infinite())
		anInfEmap.Add(E);
	    }
	  else
	    { // Eori == TopAbs_REVERSED
	      if (aL == Precision::Infinite())
		anInfEmap.Add(E);
	    }
	}
      //  Modified by Sergey KHROMOV - Mon May 13 11:52:20 2002 End
      it.Next();
    }

  //Construction of the set of double edges.
  TopoDS_Iterator it2(W);  
  TopTools_MapOfShape emap;
  while (it2.More()) {
    if (!emap.Add(it2.Value())) 
      myDoubles.Add(it2.Value());
    it2.Next();
  }

  // if vmap is not empty the wire is open, let us find the first vertex
  if (!vmap.IsEmpty()) {
    TopTools_MapIteratorOfMapOfShape itt(vmap); // skl : I change "it" to "itt"
    while (itt.Key().Orientation() != TopAbs_FORWARD) {
      itt.Next();
      if (!itt.More()) break;
    }
    if (itt.More()) V1 = TopoDS::Vertex(itt.Key());
  }
  else {
//  Modified by Sergey KHROMOV - Mon May 13 12:05:30 2002 Begin
//   The wire is infinite Try to find the first vertex. It may be NULL.
    if (!anInfEmap.IsEmpty()) {
      TopTools_MapIteratorOfMapOfShape itt(anInfEmap);

      for (; itt.More(); itt.Next()) {
	TopoDS_Edge        anEdge = TopoDS::Edge(itt.Key());
	TopAbs_Orientation anOri  = anEdge.Orientation();
	Standard_Real      aF;
	Standard_Real      aL;

	BRep_Tool::Range(anEdge, aF, aL);
	if ((anOri == TopAbs_FORWARD  && aF == -Precision::Infinite()) ||
	    (anOri == TopAbs_REVERSED && aL ==  Precision::Infinite())) {
	  myEdge   = anEdge;
	  myVertex = TopoDS_Vertex();

	  return;
	}
      }
    }
//  Modified by Sergey KHROMOV - Mon May 13 12:05:31 2002 End


    // use the first vertex in iterator
    it.Initialize(W);
    while (it.More()) {
      const TopoDS_Edge& E = TopoDS::Edge(it.Value());
      TopAbs_Orientation Eori = E.Orientation();
      if (Eori == TopAbs_INTERNAL || Eori == TopAbs_EXTERNAL) {
	// JYL 10-03-97 : waiting for correct processing 
	// of INTERNAL/EXTERNAL edges
	it.Next();
	continue;
      }
      TopExp::Vertices(E,V1,V2,Standard_True);
      break;
    }
  }

  if (V1.IsNull() ) return;
  if (!myMap.IsBound(V1)) return;
  
  TopTools_ListOfShape& l = myMap(V1);
  myEdge = TopoDS::Edge(l.First());
  l.RemoveFirst();
  myVertex = TopExp::FirstVertex (myEdge, Standard_True);

}

//=======================================================================
//function : More
//purpose  : 
//=======================================================================
Standard_Boolean  BRepTools_WireExplorer::More()const 
{
  return !myEdge.IsNull();
}

//=======================================================================
//function : Next
//purpose  : 
//=======================================================================
void  BRepTools_WireExplorer::Next()
{
  myVertex = TopExp::LastVertex (myEdge, Standard_True);

  if (myVertex.IsNull()) {
     myEdge = TopoDS_Edge();
     return;
  }
  if (!myMap.IsBound(myVertex)) {
     myEdge = TopoDS_Edge();
     return;
  }

  TopTools_ListOfShape& l = myMap(myVertex);

  if (l.IsEmpty()) {
    myEdge = TopoDS_Edge();
  }
  else if (l.Extent() == 1) {
//  Modified by Sergey KHROMOV - Fri Jun 21 10:28:01 2002 OCC325 Begin
    TopoDS_Vertex aV1;
    TopoDS_Vertex aV2;
    TopoDS_Edge   aNextEdge = TopoDS::Edge(l.First());

    TopExp::Vertices(aNextEdge, aV1, aV2, Standard_True);

    if (!aV1.IsSame(myVertex)) {
      myEdge = TopoDS_Edge();
      return;
    }
    if (!myFace.IsNull() && aV1.IsSame(aV2)) {
      Handle(Geom2d_Curve) aPrevPC;
      Handle(Geom2d_Curve) aNextPC;
      Standard_Real        aPar11, aPar12;
      Standard_Real        aPar21, aPar22;
      Standard_Real        aPrevPar;
      Standard_Real        aNextFPar;
      Standard_Real        aNextLPar;

      aPrevPC = BRep_Tool::CurveOnSurface(myEdge, myFace, aPar11, aPar12);
      aNextPC = BRep_Tool::CurveOnSurface(aNextEdge, myFace, aPar21, aPar22);

      if (aPrevPC.IsNull() || aNextPC.IsNull()) {
	      myEdge = TopoDS_Edge();
	      return;
      }

      if (myEdge.Orientation() == TopAbs_FORWARD)
	      aPrevPar = aPar12;
      else
	      aPrevPar = aPar11;

      if (aNextEdge.Orientation() == TopAbs_FORWARD) {
	      aNextFPar = aPar21;
	      aNextLPar = aPar22;
      } else {
	      aNextFPar = aPar22;
	      aNextLPar = aPar21;
      }

      gp_Pnt2d aPPrev  = aPrevPC->Value(aPrevPar);
      gp_Pnt2d aPNextF = aNextPC->Value(aNextFPar);
      gp_Pnt2d aPNextL = aNextPC->Value(aNextLPar);

      if (aPPrev.SquareDistance(aPNextF) > aPPrev.SquareDistance(aPNextL)) {
	      myEdge = TopoDS_Edge();
	      return;
      }
    }
//  Modified by Sergey KHROMOV - Fri Jun 21 11:08:16 2002 End
    myEdge = TopoDS::Edge(l.First());
    l.Clear();
  }
  else {
    if (myFace.IsNull()) {
      // Without Face - try to return edges
      // as logically as possible
      // At first degenerated edges.
      TopoDS_Edge E = myEdge;
      if (SelectDegenerated(l,E)) {
	      myEdge = E;
	      return;
      }
      // At second double edges.
      E = myEdge;
      if (SelectDouble(myDoubles,l,E)) {
	      myEdge = E;
	      return;
      }

      TopTools_ListIteratorOfListOfShape it(l); 
      Standard_Boolean notfound = Standard_True;
      while (it.More()) {
	      if (!it.Value().IsSame(myEdge)) {
	        myEdge = TopoDS::Edge(it.Value());
	        l.Remove(it);
	        notfound = Standard_False;
	        break;
	      }
	      it.Next();
      }
      
      if(notfound) {
	      myEdge = TopoDS_Edge();
	      return;
      }

    }
    else
    {
      // If we have more than one edge attached to the list
      // probably wire that we explore contains a loop or loops.
      Standard_Real dfFPar = 0., dfLPar = 0.;
      Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface (myEdge, myFace, dfFPar, dfLPar);
      if(aPCurve.IsNull())
      {
        myEdge = TopoDS_Edge();
        return;
      }
      // Note: current < myVertex > which is last on < myEdge >
      //       equals in 2D to following 2D points:
      //       edge is FORWARD  - point with MAX parameter on PCurve;
      //       edge is REVERSED - point with MIN parameter on PCurve.

      // Get 2D point equals to < myVertex > in 2D for current edge.
      gp_Pnt2d PRef;
      if( myEdge.Orientation() == TopAbs_REVERSED )
        aPCurve->D0(dfFPar, PRef);
      else 
        aPCurve->D0(dfLPar, PRef);

      // Get next 2D point from current edge's PCurve with parameter
      // F + dP (REV) or L - dP (FOR)
      Standard_Boolean isrevese = ( myEdge.Orientation() == TopAbs_REVERSED );
      Standard_Real dfMPar = GetNextParamOnPC(aPCurve,PRef,dfFPar,dfLPar,myTolU,myTolV,isrevese);

      gp_Pnt2d PRefm;
      aPCurve->D0(dfMPar, PRefm);
      // Get vector from PRef to PRefm
      gp_Vec2d anERefDir(PRef,PRefm);
      // Search the list of edges looking for the edge having hearest
      // 2D point of connected vertex to current one and smallest angle.
      // First process all degenerated edges, then - all others.

      TopTools_ListIteratorOfListOfShape it;
      Standard_Integer k = 1, kMin = 0, iDone = 0;
      Standard_Boolean isDegenerated = Standard_True;
      Standard_Real dmin = RealLast();
      Standard_Real dfMinAngle = 3.0*M_PI, dfCurAngle = 3.0*M_PI;

      for(iDone = 0; iDone < 2; iDone++)
      {
        it.Initialize(l);
        while( it.More() )
        {
	        const TopoDS_Edge& E = TopoDS::Edge(it.Value());
	        if( E.IsSame(myEdge) )
	        {
	          it.Next();
	          k++;
	          continue;
	        }
  		
	        TopoDS_Vertex aVert1, aVert2;
	        TopExp::Vertices (E, aVert1, aVert2, Standard_True);
	        if( aVert1.IsNull() || aVert2.IsNull() )
          {
            it.Next();
            k++;
            continue;
          }
  		
	        aPCurve = BRep_Tool::CurveOnSurface (E, myFace, dfFPar, dfLPar);
	        if( aPCurve.IsNull() )
          {
            it.Next();
            k++;
            continue;
          }
    		
	        gp_Pnt2d aPEb, aPEe;
	        if( aVert1.IsSame(aVert2) == isDegenerated )
	        {
	          if( E.Orientation() == TopAbs_REVERSED )
	            aPCurve->D0(dfLPar, aPEb);
	          else	
	            aPCurve->D0(dfFPar, aPEb);

	          if( Abs(dfLPar-dfFPar) > Precision::PConfusion() )
	          {
		          isrevese = ( E.Orientation() == TopAbs_REVERSED );
		          isrevese = !isrevese;
		          Standard_Real aEPm = GetNextParamOnPC(aPCurve,aPEb,dfFPar,dfLPar,myTolU,myTolV,isrevese);
        			
		          aPCurve->D0 (aEPm, aPEe);
              if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
              {
                //seems to be very short curve
                gp_Vec2d aD;
                aPCurve->D1(aEPm, aPEe, aD);
	              if( E.Orientation() == TopAbs_REVERSED )
                  aPEe.SetXY(aPEb.XY()-aD.XY());
	              else	
                  aPEe.SetXY(aPEb.XY()+aD.XY());

                if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
                {
                  it.Next();
                  k++;
                  continue;
                }
              }
		          gp_Vec2d anEDir(aPEb, aPEe);
		          dfCurAngle = Abs( anEDir.Angle(anERefDir) );
	          }

	          if( dfCurAngle <= dfMinAngle )
	          {
		          Standard_Real d = PRef.SquareDistance(aPEb);
		          if( d <= Precision::PConfusion() )
		            d = 0.;
		          if( Abs(aPEb.X()-PRef.X()) < myTolU  &&  Abs(aPEb.Y()-PRef.Y()) < myTolV )
		          {
		            if( d <= dmin )
		            {
			            dfMinAngle = dfCurAngle;
			            kMin = k;
			            dmin = d;
		            }
		          }
	          }
	        }
	        it.Next();
	        k++;
        }// while it

        if( kMin == 0 )
        {
	        isDegenerated = Standard_False;
	        k = 1;
	        dmin = RealLast();
        }
        else
          break;
      }// for iDone

      if(kMin == 0)
      {
        // probably unclosed in 2d space wire
        myEdge = TopoDS_Edge();
        return;
      }

      // Selection the edge.
      it.Initialize(l);
      k = 1;
      while( it.More() )
      {
        if( k == kMin )
        {
          myEdge = TopoDS::Edge(it.Value());
          l.Remove(it);
          break;
        }
        it.Next();
        k++;
      }
    }//else face != NULL && l > 1
  }//else l > 1
}

//=======================================================================
//function : Current
//purpose  : 
//=======================================================================
const TopoDS_Edge&  BRepTools_WireExplorer::Current()const 
{
  return myEdge;
}

//=======================================================================
//function : Orientation
//purpose  : 
//=======================================================================
TopAbs_Orientation BRepTools_WireExplorer::Orientation() const
{
  TopoDS_Iterator it(myEdge,Standard_False);
  while (it.More()) {
    if (myVertex.IsSame(it.Value()))
      return it.Value().Orientation();
    it.Next();
  }
  Standard_NoSuchObject::Raise("BRepTools_WireExplorer::Orientation");
  return TopAbs_FORWARD;
}

//=======================================================================
//function : CurrentVertex
//purpose  : 
//=======================================================================
const TopoDS_Vertex& BRepTools_WireExplorer::CurrentVertex() const
{
  return myVertex;
}

//=======================================================================
//function : Clear
//purpose  : 
//=======================================================================

void BRepTools_WireExplorer::Clear()
{
  myMap.Clear();
  myDoubles.Clear();
  myEdge = TopoDS_Edge();
  myFace = TopoDS_Face();
  myVertex = TopoDS_Vertex();
}


//=======================================================================
//function : SelectDouble
//purpose  : 
//=======================================================================

Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
			      TopTools_ListOfShape& L,
			      TopoDS_Edge&          E)
{
  TopTools_ListIteratorOfListOfShape it(L);
  
  for (; it.More(); it.Next()) {
    const TopoDS_Shape& CE = it.Value();
    if (Doubles.Contains(CE) && (!E.IsSame(CE))) {
      E = TopoDS::Edge(CE);
      L.Remove(it);
      return 1;
    }
  }
  return 0;
}

//=======================================================================
//function : SelectDegenerated
//purpose  : 
//=======================================================================

Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
				   TopoDS_Edge&          E)
{
  TopTools_ListIteratorOfListOfShape it(L);
  while (it.More()) {
    if (!it.Value().IsSame(E)) {
      E = TopoDS::Edge(it.Value());
      if (BRep_Tool::Degenerated(E)) {
	L.Remove(it);
	return 1;
      }
    }
    it.Next();
  } 
  return 0;
}

//=======================================================================
//function : GetNextParamOnPC
//purpose  : 
//=======================================================================
Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
			       const gp_Pnt2d& aPRef,
			       const Standard_Real& fP,
			       const Standard_Real& lP,
			       const Standard_Real& tolU,
			       const Standard_Real& tolV,
			       const Standard_Boolean& reverse)
{
  Standard_Real result = ( reverse ) ? fP : lP;
  Standard_Real dP = Abs( lP - fP ) / 1000.; // was / 16.;
  if( reverse )
    {
      Standard_Real startPar = fP;
      Standard_Boolean nextPntOnEdge = Standard_False;
      while( !nextPntOnEdge && startPar < lP )
	{
	  gp_Pnt2d pnt;
	  startPar += dP;
	  aPC->D0(startPar, pnt);
	  if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
	    continue;
	  else
	    {
	      result = startPar;
	      nextPntOnEdge = Standard_True;
	      break;
	    }
	}
      
      if( !nextPntOnEdge )
	result = lP;

      if( result > lP )
	result = lP;
    }
  else
    {
      Standard_Real startPar = lP;
      Standard_Boolean nextPntOnEdge = Standard_False;
      while( !nextPntOnEdge && startPar > fP )
	{
	  gp_Pnt2d pnt;
	  startPar -= dP;
	  aPC->D0(startPar, pnt);
	  if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
	    continue;
	  else
	    {
	      result = startPar;
	      nextPntOnEdge = Standard_True;
	      break;
	    }
	}
      
      if( !nextPntOnEdge )
	result = fP;

      if( result < fP )
	result = fP;
    }

  return result;
}
Commit	Line	Data
b311480e	1	// Created on: 1993-01-21
	2	// Created by: Remi LEQUETTE
	3	// Copyright (c) 1993-1999 Matra Datavision
973c2be1	4	// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e	5	//
973c2be1	6	// This file is part of Open CASCADE Technology software library.
b311480e	7	//
d5f74e42	8	// This library is free software; you can redistribute it and/or modify it under
d5f74e42	9	// the terms of the GNU Lesser General Public License version 2.1 as published
973c2be1	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.
b311480e	13	//
973c2be1	14	// Alternatively, this file may be used under the terms of Open CASCADE
973c2be1	15	// commercial license or contractual agreement.
7fd59977	16
42cf5bc1	17
7fd59977	18	#include <BRep_Tool.hxx>
7fd59977	19	#include <BRepTools.hxx>
42cf5bc1	20	#include <BRepTools_WireExplorer.hxx>
7fd59977	21	#include <Geom2d_Curve.hxx>
42cf5bc1	22	#include <Geom_Surface.hxx>
7fd59977	23	#include <GeomAdaptor_Surface.hxx>
42cf5bc1	24	#include <gp_Pnt2d.hxx>
	25	#include <Precision.hxx>
	26	#include <Standard_DomainError.hxx>
	27	#include <Standard_NoMoreObject.hxx>
	28	#include <Standard_NoSuchObject.hxx>
	29	#include <TopExp.hxx>
7fd59977	30	#include <TopExp_Explorer.hxx>
42cf5bc1	31	#include <TopoDS.hxx>
	32	#include <TopoDS_Edge.hxx>
	33	#include <TopoDS_Face.hxx>
	34	#include <TopoDS_Iterator.hxx>
	35	#include <TopoDS_Vertex.hxx>
	36	#include <TopoDS_Wire.hxx>
	37	#include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
	38	#include <TopTools_ListIteratorOfListOfShape.hxx>
	39	#include <TopTools_ListOfShape.hxx>
	40	#include <TopTools_MapIteratorOfMapOfShape.hxx>
	41	#include <TopTools_MapOfShape.hxx>
7fd59977	42
	43	//=======================================================================
	44	// forward declarations of aux functions
	45	//=======================================================================
	46	static Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
	47	TopTools_ListOfShape& L,
	48	TopoDS_Edge& E);
	49
	50	static Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
	51	TopoDS_Edge& E);
	52
	53	static Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
	54	const gp_Pnt2d& aPRef,
	55	const Standard_Real& fP,
	56	const Standard_Real& lP,
	57	const Standard_Real& tolU,
	58	const Standard_Real& tolV,
	59	const Standard_Boolean& reverse);
	60
	61	//=======================================================================
	62	//function : BRepTools_WireExplorer
	63	//purpose :
	64	//=======================================================================
	65	BRepTools_WireExplorer::BRepTools_WireExplorer()
	66	{
	67	}
	68
	69	//=======================================================================
	70	//function : BRepTools_WireExplorer
	71	//purpose :
	72	//=======================================================================
	73	BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W)
	74	{
	75	TopoDS_Face F = TopoDS_Face();
	76	Init(W,F);
	77	}
	78
	79	//=======================================================================
	80	//function : BRepTools_WireExplorer
	81	//purpose :
	82	//=======================================================================
	83	BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W,
	84	const TopoDS_Face& F)
	85	{
	86	Init(W,F);
	87	}
	88
	89	//=======================================================================
	90	//function : Init
	91	//purpose :
	92	//=======================================================================
	93	void BRepTools_WireExplorer::Init(const TopoDS_Wire& W)
	94	{
	95	TopoDS_Face F = TopoDS_Face();
	96	Init(W,F);
	97	}
	98
	99	//=======================================================================
	100	//function : Init
	101	//purpose :
	102	//=======================================================================
	103	void BRepTools_WireExplorer::Init(const TopoDS_Wire& W,
	104	const TopoDS_Face& F)
	105	{
106	myEdge = TopoDS_Edge();
107	myVertex = TopoDS_Vertex();
108	myMap.Clear();
109	myDoubles.Clear();
110
111	if( W.IsNull() )
112	return;
113
114	myFace = F;
115	Standard_Real dfVertToler = 0.;
116	myReverse = Standard_False;
117
118	if (!myFace.IsNull())
119	{
120	BRepTools::Update(myFace);
121	TopLoc_Location aL;
122	const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(myFace, aL);
123	GeomAdaptor_Surface aGAS(aSurf);
124	TopExp_Explorer anExp(W, TopAbs_VERTEX);
125	for(; anExp.More(); anExp.Next())
126	{
127	const TopoDS_Vertex& aV = TopoDS::Vertex(anExp.Current());
128	dfVertToler = Max(BRep_Tool::Tolerance(aV), dfVertToler);
129	}
130	myTolU = 2. * aGAS.UResolution(dfVertToler);
131	myTolV = 2. * aGAS.VResolution(dfVertToler);
132
133	// uresolution for cone with infinite vmin vmax is too small.
134	if(aGAS.GetType() == GeomAbs_Cone)
135	{
136	Standard_Real u1, u2, v1, v2;
137	BRepTools::UVBounds(myFace, u1, u2, v1, v2);
138	gp_Pnt aP;
139	gp_Vec aD1U, aD1V;
140	aGAS.D1(u1, v1, aP, aD1U, aD1V);
141	Standard_Real tol1, tol2, maxtol = .0005*(u2-u1);
142	Standard_Real a = aD1U.Magnitude();
143
144	if(a <= Precision::Confusion())
145	tol1 = maxtol;
146	else
147	tol1 = Min(maxtol, dfVertToler/a);
148
149	aGAS.D1(u1, v2, aP, aD1U, aD1V);
150	a = aD1U.Magnitude();
151	if(a <= Precision::Confusion())
152	tol2 = maxtol;
153	else
154	tol2 = Min(maxtol, dfVertToler/a);
155
156	myTolU = 2. * Max(tol1, tol2);
157	}
158
159	if( aGAS.GetType() == GeomAbs_BSplineSurface \|\|
160	aGAS.GetType() == GeomAbs_BezierSurface )
161	{
162	Standard_Real maxTol = Max(myTolU,myTolV);
163	myTolU = maxTol;
164	myTolV = maxTol;
165	}
166
167	myReverse = (myFace.Orientation() == TopAbs_REVERSED);
168	}
169
170	// map of vertices to know if the wire is open
171	TopTools_MapOfShape vmap;
172	// Modified by Sergey KHROMOV - Mon May 13 11:50:48 2002 Begin
173	// map of infinite edges
174	TopTools_MapOfShape anInfEmap;
175	// Modified by Sergey KHROMOV - Mon May 13 11:50:49 2002 End
176
177	// list the vertices
178	TopoDS_Vertex V1,V2;
179	TopTools_ListOfShape empty;
180
181	TopoDS_Iterator it(W);
182	while (it.More())
183	{
184	const TopoDS_Edge& E = TopoDS::Edge(it.Value());
185	TopAbs_Orientation Eori = E.Orientation();
186	if (Eori == TopAbs_INTERNAL \|\| Eori == TopAbs_EXTERNAL)
187	{
188	it.Next();
189	continue;
190	}
191	TopExp::Vertices(E,V1,V2,Standard_True);
192
193	if( !V1.IsNull() )
194	{
195	if( !myMap.IsBound(V1) )
196	myMap.Bind(V1,empty);
197	myMap(V1).Append(E);
198
199	// add or remove in the vertex map
200	V1.Orientation(TopAbs_FORWARD);
201	if( !vmap.Add(V1) )
202	vmap.Remove(V1);
203	}
204
205	if( !V2.IsNull() )
206	{
207	V2.Orientation(TopAbs_REVERSED);
208	if(!vmap.Add(V2))
209	vmap.Remove(V2);
210	}
211
212	// Modified by Sergey KHROMOV - Mon May 13 11:52:20 2002 Begin
213	if (V1.IsNull() \|\| V2.IsNull())
214	{
215	Standard_Real aF = 0., aL = 0.;
216	BRep_Tool::Range(E, aF, aL);
217
218	if(Eori == TopAbs_FORWARD)
219	{
220	if (aF == -Precision::Infinite())
221	anInfEmap.Add(E);
222	}
223	else
224	{ // Eori == TopAbs_REVERSED
225	if (aL == Precision::Infinite())
226	anInfEmap.Add(E);
227	}
228	}
229	// Modified by Sergey KHROMOV - Mon May 13 11:52:20 2002 End
230	it.Next();
231	}
232
0d969553	233	//Construction of the set of double edges.
7fd59977	234	TopoDS_Iterator it2(W);
	235	TopTools_MapOfShape emap;
	236	while (it2.More()) {
	237	if (!emap.Add(it2.Value()))
	238	myDoubles.Add(it2.Value());
	239	it2.Next();
	240	}
	241
	242	// if vmap is not empty the wire is open, let us find the first vertex
	243	if (!vmap.IsEmpty()) {
	244	TopTools_MapIteratorOfMapOfShape itt(vmap); // skl : I change "it" to "itt"
	245	while (itt.Key().Orientation() != TopAbs_FORWARD) {
	246	itt.Next();
	247	if (!itt.More()) break;
	248	}
	249	if (itt.More()) V1 = TopoDS::Vertex(itt.Key());
	250	}
	251	else {
	252	// Modified by Sergey KHROMOV - Mon May 13 12:05:30 2002 Begin
	253	// The wire is infinite Try to find the first vertex. It may be NULL.
	254	if (!anInfEmap.IsEmpty()) {
	255	TopTools_MapIteratorOfMapOfShape itt(anInfEmap);
	256
	257	for (; itt.More(); itt.Next()) {
	258	TopoDS_Edge anEdge = TopoDS::Edge(itt.Key());
	259	TopAbs_Orientation anOri = anEdge.Orientation();
	260	Standard_Real aF;
	261	Standard_Real aL;
	262
	263	BRep_Tool::Range(anEdge, aF, aL);
	264	if ((anOri == TopAbs_FORWARD && aF == -Precision::Infinite()) \|\|
	265	(anOri == TopAbs_REVERSED && aL == Precision::Infinite())) {
	266	myEdge = anEdge;
	267	myVertex = TopoDS_Vertex();
	268
	269	return;
	270	}
	271	}
	272	}
	273	// Modified by Sergey KHROMOV - Mon May 13 12:05:31 2002 End
	274
	275
	276	// use the first vertex in iterator
	277	it.Initialize(W);
	278	while (it.More()) {
	279	const TopoDS_Edge& E = TopoDS::Edge(it.Value());
	280	TopAbs_Orientation Eori = E.Orientation();
	281	if (Eori == TopAbs_INTERNAL \|\| Eori == TopAbs_EXTERNAL) {
0d969553 Y	282	// JYL 10-03-97 : waiting for correct processing
0d969553 Y	283	// of INTERNAL/EXTERNAL edges
7fd59977	284	it.Next();
	285	continue;
	286	}
	287	TopExp::Vertices(E,V1,V2,Standard_True);
	288	break;
	289	}
	290	}
	291
	292	if (V1.IsNull() ) return;
	293	if (!myMap.IsBound(V1)) return;
	294
	295	TopTools_ListOfShape& l = myMap(V1);
	296	myEdge = TopoDS::Edge(l.First());
	297	l.RemoveFirst();
	298	myVertex = TopExp::FirstVertex (myEdge, Standard_True);
	299
	300	}
	301
	302	//=======================================================================
	303	//function : More
	304	//purpose :
	305	//=======================================================================
	306	Standard_Boolean BRepTools_WireExplorer::More()const
	307	{
	308	return !myEdge.IsNull();
	309	}
	310
	311	//=======================================================================
	312	//function : Next
	313	//purpose :
	314	//=======================================================================
	315	void BRepTools_WireExplorer::Next()
	316	{
	317	myVertex = TopExp::LastVertex (myEdge, Standard_True);
	318
	319	if (myVertex.IsNull()) {
	320	myEdge = TopoDS_Edge();
	321	return;
	322	}
	323	if (!myMap.IsBound(myVertex)) {
	324	myEdge = TopoDS_Edge();
	325	return;
	326	}
	327
	328	TopTools_ListOfShape& l = myMap(myVertex);
	329
	330	if (l.IsEmpty()) {
	331	myEdge = TopoDS_Edge();
	332	}
	333	else if (l.Extent() == 1) {
	334	// Modified by Sergey KHROMOV - Fri Jun 21 10:28:01 2002 OCC325 Begin
	335	TopoDS_Vertex aV1;
	336	TopoDS_Vertex aV2;
	337	TopoDS_Edge aNextEdge = TopoDS::Edge(l.First());
	338
	339	TopExp::Vertices(aNextEdge, aV1, aV2, Standard_True);
	340
	341	if (!aV1.IsSame(myVertex)) {
	342	myEdge = TopoDS_Edge();
	343	return;
	344	}
	345	if (!myFace.IsNull() && aV1.IsSame(aV2)) {
	346	Handle(Geom2d_Curve) aPrevPC;
	347	Handle(Geom2d_Curve) aNextPC;
348	Standard_Real aPar11, aPar12;
349	Standard_Real aPar21, aPar22;
350	Standard_Real aPrevPar;
351	Standard_Real aNextFPar;
352	Standard_Real aNextLPar;
353
354	aPrevPC = BRep_Tool::CurveOnSurface(myEdge, myFace, aPar11, aPar12);
355	aNextPC = BRep_Tool::CurveOnSurface(aNextEdge, myFace, aPar21, aPar22);
356
357	if (aPrevPC.IsNull() \|\| aNextPC.IsNull()) {
a0f8845f	358	myEdge = TopoDS_Edge();
a0f8845f	359	return;
7fd59977	360	}
	361
	362	if (myEdge.Orientation() == TopAbs_FORWARD)
a0f8845f	363	aPrevPar = aPar12;
7fd59977	364	else
a0f8845f	365	aPrevPar = aPar11;
7fd59977	366
7fd59977	367	if (aNextEdge.Orientation() == TopAbs_FORWARD) {
a0f8845f	368	aNextFPar = aPar21;
a0f8845f	369	aNextLPar = aPar22;
7fd59977	370	} else {
a0f8845f	371	aNextFPar = aPar22;
a0f8845f	372	aNextLPar = aPar21;
7fd59977	373	}
	374
	375	gp_Pnt2d aPPrev = aPrevPC->Value(aPrevPar);
	376	gp_Pnt2d aPNextF = aNextPC->Value(aNextFPar);
	377	gp_Pnt2d aPNextL = aNextPC->Value(aNextLPar);
	378
	379	if (aPPrev.SquareDistance(aPNextF) > aPPrev.SquareDistance(aPNextL)) {
a0f8845f	380	myEdge = TopoDS_Edge();
a0f8845f	381	return;
7fd59977	382	}
	383	}
	384	// Modified by Sergey KHROMOV - Fri Jun 21 11:08:16 2002 End
	385	myEdge = TopoDS::Edge(l.First());
	386	l.Clear();
	387	}
	388	else {
	389	if (myFace.IsNull()) {
0d969553 Y	390	// Without Face - try to return edges
	391	// as logically as possible
	392	// At first degenerated edges.
7fd59977	393	TopoDS_Edge E = myEdge;
7fd59977	394	if (SelectDegenerated(l,E)) {
a0f8845f	395	myEdge = E;
a0f8845f	396	return;
7fd59977	397	}
0d969553	398	// At second double edges.
7fd59977	399	E = myEdge;
7fd59977	400	if (SelectDouble(myDoubles,l,E)) {
a0f8845f	401	myEdge = E;
a0f8845f	402	return;
7fd59977	403	}
	404
	405	TopTools_ListIteratorOfListOfShape it(l);
	406	Standard_Boolean notfound = Standard_True;
	407	while (it.More()) {
a0f8845f	408	if (!it.Value().IsSame(myEdge)) {
	409	myEdge = TopoDS::Edge(it.Value());
	410	l.Remove(it);
	411	notfound = Standard_False;
	412	break;
	413	}
	414	it.Next();
7fd59977	415	}
	416
	417	if(notfound) {
a0f8845f	418	myEdge = TopoDS_Edge();
a0f8845f	419	return;
7fd59977	420	}
	421
	422	}
	423	else
a0f8845f	424	{
	425	// If we have more than one edge attached to the list
	426	// probably wire that we explore contains a loop or loops.
	427	Standard_Real dfFPar = 0., dfLPar = 0.;
	428	Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface (myEdge, myFace, dfFPar, dfLPar);
	429	if(aPCurve.IsNull())
7fd59977	430	{
a0f8845f	431	myEdge = TopoDS_Edge();
	432	return;
	433	}
	434	// Note: current < myVertex > which is last on < myEdge >
	435	// equals in 2D to following 2D points:
	436	// edge is FORWARD - point with MAX parameter on PCurve;
	437	// edge is REVERSED - point with MIN parameter on PCurve.
	438
	439	// Get 2D point equals to < myVertex > in 2D for current edge.
	440	gp_Pnt2d PRef;
	441	if( myEdge.Orientation() == TopAbs_REVERSED )
	442	aPCurve->D0(dfFPar, PRef);
	443	else
	444	aPCurve->D0(dfLPar, PRef);
	445
	446	// Get next 2D point from current edge's PCurve with parameter
	447	// F + dP (REV) or L - dP (FOR)
	448	Standard_Boolean isrevese = ( myEdge.Orientation() == TopAbs_REVERSED );
	449	Standard_Real dfMPar = GetNextParamOnPC(aPCurve,PRef,dfFPar,dfLPar,myTolU,myTolV,isrevese);
	450
	451	gp_Pnt2d PRefm;
	452	aPCurve->D0(dfMPar, PRefm);
	453	// Get vector from PRef to PRefm
	454	gp_Vec2d anERefDir(PRef,PRefm);
	455	// Search the list of edges looking for the edge having hearest
	456	// 2D point of connected vertex to current one and smallest angle.
	457	// First process all degenerated edges, then - all others.
	458
	459	TopTools_ListIteratorOfListOfShape it;
	460	Standard_Integer k = 1, kMin = 0, iDone = 0;
	461	Standard_Boolean isDegenerated = Standard_True;
	462	Standard_Real dmin = RealLast();
	463	Standard_Real dfMinAngle = 3.0M_PI, dfCurAngle = 3.0M_PI;
	464
	465	for(iDone = 0; iDone < 2; iDone++)
	466	{
	467	it.Initialize(l);
	468	while( it.More() )
	469	{
	470	const TopoDS_Edge& E = TopoDS::Edge(it.Value());
	471	if( E.IsSame(myEdge) )
	472	{
	473	it.Next();
	474	k++;
	475	continue;
	476	}
	477
	478	TopoDS_Vertex aVert1, aVert2;
	479	TopExp::Vertices (E, aVert1, aVert2, Standard_True);
	480	if( aVert1.IsNull() \|\| aVert2.IsNull() )
	481	{
	482	it.Next();
	483	k++;
	484	continue;
	485	}
	486
	487	aPCurve = BRep_Tool::CurveOnSurface (E, myFace, dfFPar, dfLPar);
	488	if( aPCurve.IsNull() )
	489	{
	490	it.Next();
	491	k++;
	492	continue;
	493	}
	494
495	gp_Pnt2d aPEb, aPEe;
496	if( aVert1.IsSame(aVert2) == isDegenerated )
497	{
498	if( E.Orientation() == TopAbs_REVERSED )
499	aPCurve->D0(dfLPar, aPEb);
500	else
501	aPCurve->D0(dfFPar, aPEb);
502
503	if( Abs(dfLPar-dfFPar) > Precision::PConfusion() )
504	{
505	isrevese = ( E.Orientation() == TopAbs_REVERSED );
506	isrevese = !isrevese;
507	Standard_Real aEPm = GetNextParamOnPC(aPCurve,aPEb,dfFPar,dfLPar,myTolU,myTolV,isrevese);
508
509	aPCurve->D0 (aEPm, aPEe);
510	if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
511	{
512	//seems to be very short curve
513	gp_Vec2d aD;
514	aPCurve->D1(aEPm, aPEe, aD);
515	if( E.Orientation() == TopAbs_REVERSED )
516	aPEe.SetXY(aPEb.XY()-aD.XY());
517	else
518	aPEe.SetXY(aPEb.XY()+aD.XY());
519
520	if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
521	{
522	it.Next();
523	k++;
524	continue;
525	}
526	}
527	gp_Vec2d anEDir(aPEb, aPEe);
528	dfCurAngle = Abs( anEDir.Angle(anERefDir) );
529	}
530
531	if( dfCurAngle <= dfMinAngle )
532	{
533	Standard_Real d = PRef.SquareDistance(aPEb);
534	if( d <= Precision::PConfusion() )
535	d = 0.;
536	if( Abs(aPEb.X()-PRef.X()) < myTolU && Abs(aPEb.Y()-PRef.Y()) < myTolV )
537	{
538	if( d <= dmin )
539	{
540	dfMinAngle = dfCurAngle;
541	kMin = k;
542	dmin = d;
543	}
544	}
545	}
546	}
547	it.Next();
548	k++;
549	}// while it
550
551	if( kMin == 0 )
552	{
553	isDegenerated = Standard_False;
554	k = 1;
555	dmin = RealLast();
556	}
557	else
558	break;
559	}// for iDone
560
561	if(kMin == 0)
562	{
563	// probably unclosed in 2d space wire
564	myEdge = TopoDS_Edge();
565	return;
566	}
567
568	// Selection the edge.
569	it.Initialize(l);
570	k = 1;
571	while( it.More() )
572	{
573	if( k == kMin )
574	{
575	myEdge = TopoDS::Edge(it.Value());
576	l.Remove(it);
577	break;
578	}
579	it.Next();
580	k++;
581	}
582	}//else face != NULL && l > 1
7fd59977	583	}//else l > 1
	584	}
	585
	586	//=======================================================================
	587	//function : Current
	588	//purpose :
	589	//=======================================================================
	590	const TopoDS_Edge& BRepTools_WireExplorer::Current()const
	591	{
	592	return myEdge;
	593	}
	594
	595	//=======================================================================
	596	//function : Orientation
	597	//purpose :
	598	//=======================================================================
	599	TopAbs_Orientation BRepTools_WireExplorer::Orientation() const
	600	{
	601	TopoDS_Iterator it(myEdge,Standard_False);
	602	while (it.More()) {
	603	if (myVertex.IsSame(it.Value()))
	604	return it.Value().Orientation();
	605	it.Next();
	606	}
	607	Standard_NoSuchObject::Raise("BRepTools_WireExplorer::Orientation");
	608	return TopAbs_FORWARD;
	609	}
	610
	611	//=======================================================================
	612	//function : CurrentVertex
	613	//purpose :
	614	//=======================================================================
	615	const TopoDS_Vertex& BRepTools_WireExplorer::CurrentVertex() const
	616	{
	617	return myVertex;
	618	}
	619
	620	//=======================================================================
	621	//function : Clear
	622	//purpose :
	623	//=======================================================================
	624
	625	void BRepTools_WireExplorer::Clear()
	626	{
	627	myMap.Clear();
	628	myDoubles.Clear();
	629	myEdge = TopoDS_Edge();
	630	myFace = TopoDS_Face();
	631	myVertex = TopoDS_Vertex();
	632	}
	633
	634
	635	//=======================================================================
	636	//function : SelectDouble
	637	//purpose :
	638	//=======================================================================
	639
	640	Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
	641	TopTools_ListOfShape& L,
	642	TopoDS_Edge& E)
	643	{
	644	TopTools_ListIteratorOfListOfShape it(L);
	645
	646	for (; it.More(); it.Next()) {
647	const TopoDS_Shape& CE = it.Value();
648	if (Doubles.Contains(CE) && (!E.IsSame(CE))) {
649	E = TopoDS::Edge(CE);
650	L.Remove(it);
651	return 1;
652	}
653	}
654	return 0;
655	}
656
657	//=======================================================================
658	//function : SelectDegenerated
659	//purpose :
660	//=======================================================================
661
662	Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
663	TopoDS_Edge& E)
664	{
665	TopTools_ListIteratorOfListOfShape it(L);
666	while (it.More()) {
667	if (!it.Value().IsSame(E)) {
668	E = TopoDS::Edge(it.Value());
669	if (BRep_Tool::Degenerated(E)) {
670	L.Remove(it);
671	return 1;
672	}
673	}
674	it.Next();
675	}
676	return 0;
677	}
678
679	//=======================================================================
680	//function : GetNextParamOnPC
681	//purpose :
682	//=======================================================================
683	Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
684	const gp_Pnt2d& aPRef,
685	const Standard_Real& fP,
686	const Standard_Real& lP,
687	const Standard_Real& tolU,
688	const Standard_Real& tolV,
689	const Standard_Boolean& reverse)
690	{
691	Standard_Real result = ( reverse ) ? fP : lP;
692	Standard_Real dP = Abs( lP - fP ) / 1000.; // was / 16.;
693	if( reverse )
694	{
695	Standard_Real startPar = fP;
696	Standard_Boolean nextPntOnEdge = Standard_False;
697	while( !nextPntOnEdge && startPar < lP )
698	{
699	gp_Pnt2d pnt;
700	startPar += dP;
701	aPC->D0(startPar, pnt);
702	if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
703	continue;
704	else
705	{
706	result = startPar;
707	nextPntOnEdge = Standard_True;
708	break;
709	}
710	}
711
712	if( !nextPntOnEdge )
713	result = lP;
714
715	if( result > lP )
716	result = lP;
717	}
718	else
719	{
720	Standard_Real startPar = lP;
721	Standard_Boolean nextPntOnEdge = Standard_False;
722	while( !nextPntOnEdge && startPar > fP )
723	{
724	gp_Pnt2d pnt;
725	startPar -= dP;
726	aPC->D0(startPar, pnt);
727	if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
728	continue;
729	else
730	{
731	result = startPar;
732	nextPntOnEdge = Standard_True;
733	break;
734	}
735	}
736
737	if( !nextPntOnEdge )
738	result = fP;
739
740	if( result < fP )
741	result = fP;
742	}
743
744	return result;
745	}