// Copyright (c) 1995-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.

//-- IntWalk_IWalking_2.gxx

#include <Bnd_Range.hxx>
#include <TColStd_MapOfInteger.hxx>

#ifndef OCCT_DEBUG
#define No_Standard_RangeError
#define No_Standard_OutOfRange
#endif


// _______________________________________________
//
// Location of point (u, v) in the natural domain of a surface AND update  
// of couple (u, v) for the calculation of the next point.
//
Standard_Boolean IntWalk_IWalking::Cadrage 
  (math_Vector& BornInf,
   math_Vector& BornSup,
   math_Vector& UVap,
   Standard_Real& Step,
//   Standard_Real& StepV,
   const Standard_Integer StepSign) const 

// there are always :
// BorInf(1) <= UVap(1) <= BornSup(1) et BorInf(2) <= UVap(2) <= BornSup(2)
// 1) check if the process point is out of the natural domain of the surface.
// 2) if yes the approximated point is located on border taking the best direction
// the step and a limit blocating one of the parameters during the recent call of 
// FunctionSetRoot are modified;
// 3) couple (u, v) is recomputed by approximation for the calculation of the next point.
// 4) return Standard_True if location, Standard_False if no location.
{
  Standard_Real Duvx = previousd2d.X();
  Standard_Real Duvy = previousd2d.Y();

  if (!reversed) {
    previousPoint.ParametersOnS2(UVap(1),UVap(2));
  }
  else {
    previousPoint.ParametersOnS1(UVap(1),UVap(2));
  }

  Standard_Real U1 = UVap(1) + Step * Duvx * StepSign;
  Standard_Real V1 = UVap(2) + Step * Duvy * StepSign;


  Standard_Boolean infu = (U1 <= BornInf(1)+Precision::PConfusion());
  Standard_Boolean supu = (U1 >= BornSup(1)-Precision::PConfusion());
  Standard_Boolean infv = (V1 <= BornInf(2)+Precision::PConfusion());
  Standard_Boolean supv = (V1 >= BornSup(2)-Precision::PConfusion());

  Standard_Real theStepU,theStepV;

  if (!infu && !supu && !infv && !supv) {
    UVap(1) = U1;
    UVap(2) = V1;
    return Standard_False;
  }

  if ((infu || supu) && (infv || supv)) {
    if (infu) { // jag 940616
      if(Duvx) { 
	theStepU = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
      }
      else { 
	theStepU = Step; 
      }
    }
    else {
      if(Duvx) { 
	theStepU = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
      }
      else { 
	theStepU = Step;
      }
    }
    if (infv) { // jag 940616
      if(Duvy) { 
	theStepV = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2)
      }
      else { 
	theStepV = Step;
      }
    }
    else {
      if(Duvy) { 
	theStepV = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
      }
      else { 
	theStepV = Step; 
      }
    }


    if (theStepU <= theStepV) {
      Step = theStepU;
      if (infu) {
	UVap(1) = BornInf(1);
	BornSup(1) = BornInf(1);
      }
      else {
	UVap(1) = BornSup(1);
	BornInf(1) = BornSup(1);
      }
      UVap(2) += Step*Duvy*StepSign;
    }
    else {
      Step = theStepV;
      if (infv) {
	UVap(2) = BornInf(2);
	BornSup(2) = BornInf(2); 
      }
      else {
	UVap(2) = BornSup(2);
	BornInf(2) = BornSup(2); 
      }
      UVap(1) += Step*Duvx*StepSign;
    }
    return Standard_True;
  }

  else if (infu) { // jag 940616
    if(Duvx) { 
      Standard_Real aStep = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
      if(aStep<Step) Step=aStep;
    }
    BornSup(1) = BornInf(1);                     // limit the parameter
    UVap(1) = BornInf(1);
    UVap(2) += Step*Duvy*StepSign;
    return Standard_True;
  }
  else if (supu) { // jag 940616
    if(Duvx) { 
      Standard_Real aStep = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
      if(aStep<Step) Step=aStep;
    }
    BornInf(1) = BornSup(1);                    // limit the parameter
    UVap(1) = BornSup(1);
    UVap(2) += Step*Duvy*StepSign;
    return Standard_True;
  }
  else if (infv) { // jag 940616
    if(Duvy) { 
      Standard_Real aStep = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2) 
      if(aStep<Step) Step=aStep;
    }
    BornSup(2) = BornInf(2);
    UVap(1) += Step*Duvx*StepSign;
    UVap(2) = BornInf(2);
    return Standard_True;
  }
  else if (supv) { // jag 940616
    if(Duvy) { 
      Standard_Real aStep = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
      if(aStep<Step) Step=aStep;
    }
    BornInf(2) = BornSup(2);
    UVap(1) += Step*Duvx*StepSign;
    UVap(2) = BornSup(2);
    return Standard_True;
  }
  return Standard_True;
}


Standard_Boolean IntWalk_IWalking::TestArretPassage
  (const TColStd_SequenceOfReal& Umult,
   const TColStd_SequenceOfReal& Vmult,
   TheIWFunction& sp,
   math_Vector& UV,
   Standard_Integer& Irang)

// Umult et Vmult : table of stop (or crossing) points on border, 
//         here only the crossing points are taken into account.
// UV     : the current point.
// Irang  : at exit : give index of the stop point in uvstart1 or 0.
//          consider that there is no risk of crossing only if there is one crossing point.


// test of stop for an OPEN intersection line
// 1) crossing test on all interior points
// 2) stop test on all start points
// if a stop is detected, the index of the stop point (Irang) is returned  
// in the iterator of start points and the associated parameters in UV space.
{
  Standard_Real Up, Vp, Du, Dv, Dup, Dvp, Utest,Vtest; 
  Standard_Integer j, N, ind;
  Standard_Real tolu = tolerance(1);
  Standard_Real tolv = tolerance(2);
  Standard_Real tolu2 = 10.*tolerance(1);
  Standard_Real tolv2 = 10.*tolerance(2);
  
  Standard_Boolean Arrive = Standard_False;
  
  // crossing test  on point that can start a loop; mark 
  // as processed if passes through an open line 
  
  if (!reversed) {
    previousPoint.ParametersOnS2(Up,Vp);
  }
  else {
    previousPoint.ParametersOnS1(Up,Vp);
  }

  for (size_t i = 1; i < wd2.size(); i++) { 
    if (wd2[i].etat > 0) { 
      // debug jag 05.04.94

//      if ((Up-wd2[i].ustart)*(UV(1)-wd2[i].ustart) +
//	  (Vp-wd2[i].vstart)*(UV(2)-wd2[i].vstart) <= 0)
      Utest = wd2[i].ustart;
      Vtest = wd2[i].vstart;

      Du  = UV(1)-Utest;
      Dv  = UV(2)-Vtest;
      Dup = Up - Utest;
      Dvp = Vp - Vtest;
      
//-- lbr le 30 oct 97 

      //IFV for OCC20285

      if ((Abs(Du) < tolu2 && Abs(Dv) < tolv2) ||
	  (Abs(Dup) < tolu2 && Abs(Dvp) < tolv2)) { 
	    
	wd2[i].etat = -wd2[i].etat;
      }
      else {
	Standard_Real DDu = (UV(1)-Up);
	Standard_Real DDv = (UV(2)-Vp);
	Standard_Real DDD = DDu*DDu+DDv*DDv;
	Standard_Real DD1 = Du*Du+Dv*Dv;
	if(DD1<=DDD) { 
	  Standard_Real DD2 = Dup*Dup+Dvp*Dvp;
	  if(DD2<=DDD && ((Du*Dup) + (Dv*Dvp*tolu/tolv) <= 0.)) { 	
	    wd2[i].etat = -wd2[i].etat;
	  }
	}
      }
    }
  }

  // stop test on point given at input and not yet processed

//  Modified by Sergey KHROMOV - Tue Nov 20 10:55:01 2001 Begin
// Check of all path points in the following order:
//   * First check all not treated points;
//   * After that check of already treated ones.
  Standard_Integer l;

  //// Modified by jgv, 28.07.2010 for OCC21914 ////
  // There are several path points between (Up,Vp) and UV
  // So several path points satisfy the condition
  // Dup*UV1mUtest + Dvp*UV2mVtest) < 0
  // We choose from them the path point with
  // minimum distance to (Up,Vp)
  TColStd_SequenceOfInteger i_candidates;
  TColStd_SequenceOfReal    SqDist_candidates;

  for (l = 1; l <= 2 && !Arrive; l++) {
    Standard_Boolean isToCheck;

    for (size_t i = 1; i < wd1.size(); i++) {
      if (l == 1)
	isToCheck = (wd1[i].etat > 0);
      else
	isToCheck = (wd1[i].etat < 0);
	
      if (isToCheck) {
//  Modified by Sergey KHROMOV - Tue Nov 20 11:03:16 2001 End

	// debug jag voir avec isg

	Utest = wd1[i].ustart;
	Vtest = wd1[i].vstart;
	Dup = Up - Utest;
	Dvp = Vp - Vtest;
	if (Abs(Dup) >= tolu || Abs(Dvp) >= tolv) {
	  Standard_Real UV1mUtest = UV(1)-Utest;
	  Standard_Real UV2mVtest = UV(2)-Vtest;
	  if(( (Dup*UV1mUtest + Dvp*UV2mVtest) < 0) ||
	     (   Abs(UV1mUtest) < tolu 
	      && Abs(UV2mVtest) < tolv)) {
	    i_candidates.Append((Standard_Integer)i);
	    SqDist_candidates.Append(Dup*Dup + Dvp*Dvp);
	    /*
	    Irang=i;
	    Arrive = Standard_True;
	    UV(1) = Utest;
	    UV(2) = Vtest;
	    */
	  }
	  else if (nbMultiplicities[i] > 0 && i_candidates.IsEmpty()) {
	    N=0;
	    for (size_t k = 1; k < i; k++) { 
	      N+=nbMultiplicities[k];
	    }
	    for (j = N + 1; j <= N + nbMultiplicities[i]; j++) {
	      if (((Up-Umult(j))*(UV(1)-Umult(j)) +
		   (Vp-Vmult(j))*(UV(2)-Vmult(j)) < 0) ||
		  (Abs(UV(1)-Umult(j)) < tolu &&
		   Abs(UV(2)-Vmult(j)) < tolv)) {
		Irang=(Standard_Integer)i;
		Arrive = Standard_True;
		UV(1) = Utest;
		UV(2) = Vtest;
		break;
	      }
	    }
	  }
	  if (Arrive) {
	    Standard_Real abidF[1], abidD[1][2];
	    math_Vector bidF(abidF,1,1);
	    math_Matrix bidD(abidD,1,1,1,2);
        sp.Values(UV,bidF,bidD);
	    break;
	  }
	}
      }
    } //end of for (i = 1; i < wd1.size(); i++)
    if (!i_candidates.IsEmpty())
      {
	Standard_Real MinSqDist = RealLast();
	for (ind = 1; ind <= i_candidates.Length(); ind++)
	  if (SqDist_candidates(ind) < MinSqDist)
	    {
	      MinSqDist = SqDist_candidates(ind);
	      Irang = i_candidates(ind);
	    }
	Arrive = Standard_True;
	UV(1) = wd1[Irang].ustart;
	UV(2) = wd1[Irang].vstart;
      }
  } //end of for (l = 1; l <= 2 && !Arrive; l++)
  return  Arrive;
}

Standard_Boolean IntWalk_IWalking::TestArretPassage
  (const TColStd_SequenceOfReal& Umult,
   const TColStd_SequenceOfReal& Vmult,
   const math_Vector& UV, 
   const Standard_Integer Index, 
   Standard_Integer& Irang)
{
// Umult, Vmult : table of stop (or crossing) points on border, here
//          only crossing points are taken into account.
// UV     : the current point.
// Index  : index of the start point in uvstart2 of the current line
//          (this is an interior point).
// Irang  : at output : gives the index of the point passing in uvstart1 or 0.
//          consider that there is risk to cross only one crossing point.

// test of stop for a CLOSED intersection line.
// 1) test of crossing on all interior points.
// 2) test of crossing on all crossing points.

  Standard_Real Up, Vp, Scal;
  Standard_Boolean Arrive = Standard_False;
  Standard_Integer N, k, i;
  Standard_Real Utest,Vtest;
  Standard_Real tolu = tolerance(1);
  Standard_Real tolv = tolerance(2);

  
  // tests of stop and of crossing on all interior points.

  if (!reversed) {
    previousPoint.ParametersOnS2(Up,Vp);
  }
  else {
    previousPoint.ParametersOnS1(Up,Vp);
  }

  Standard_Real UV1=UV(1);
  Standard_Real UV2=UV(2);


  //Normalizing factor. If it is less than 1.0 then the range will be expanded. 
  //This is no good for computation. Therefore, it is limited.
  const Standard_Real deltau = mySRangeU.IsVoid() ? UM - Um : Max(mySRangeU.Delta(), 1.0);
  const Standard_Real deltav = mySRangeV.IsVoid() ? VM - Vm : Max(mySRangeV.Delta(), 1.0);

  Up/=deltau; UV1/=deltau; 
  Vp/=deltav; UV2/=deltav;

  tolu/=deltau;
  tolv/=deltav;

  Standard_Real tolu2=tolu+tolu;
  Standard_Real tolv2=tolv+tolv;

  
  Standard_Real dPreviousCurrent = (Up-UV1)*(Up-UV1)+(Vp-UV2)*(Vp-UV2);
  for (k = 1; k < (int)wd2.size(); k++) { 
    if (wd2[k].etat > 0) {
      Utest = wd2[k].ustart;
      Vtest = wd2[k].vstart;
      
      Utest/=deltau;
      Vtest/=deltav;
      
      Standard_Real UV1mUtest=UV1-Utest;
      Standard_Real UV2mVtest=UV2-Vtest;
      if(   (UV1mUtest<tolu2 && UV1mUtest>-tolu2)
	 && (UV2mVtest<tolv2 && UV2mVtest>-tolv2)) { 
	if(Index!=k) { 
	  //-- cout<<"* etat2 : ("<<k<<")"<<endl;
	  wd2[k].etat=-wd2[k].etat; //-- mark the point as a crossing point 
	}
	else {  //-- Index == k
	  //-- cout<<"* Arrive"<<endl;
	  Arrive=Standard_True;
	}
      }
      else { 
	Standard_Real UpmUtest = (Up-Utest);
	Standard_Real VpmVtest = (Vp-Vtest);
	Standard_Real dPreviousStart = (UpmUtest)*(UpmUtest)+(VpmVtest)*(VpmVtest);
	Standard_Real dCurrentStart  = UV1mUtest * UV1mUtest + UV2mVtest * UV2mVtest;

	Scal=(UpmUtest)*(UV1mUtest)+(VpmVtest)*(UV2mVtest);
	if( (Abs(UpmUtest)<tolu && Abs(VpmVtest)<tolv)) { 
	  if(Index != k ) { 
	    //-- cout<<"** etat2 : ("<<k<<")"<<endl;
	    wd2[k].etat = -wd2[k].etat;
	  }
	}
	else if(Scal<0 && (dPreviousStart+dCurrentStart < dPreviousCurrent)) { 
	  if (Index == k ) { // on a boucle.
	    Arrive = Standard_True;
	    //-- cout<<"** Arrive  : k="<<k<<endl;
	  }
	  else {
	    //-- cout<<"*** etat2 : ("<<k<<")"<<endl;
	    wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point 
	  }
	}
	else if(k!=Index) {
	  if(dPreviousStart < dPreviousCurrent*0.25) { 
	    wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point 
	    //-- cout<<"**** etat2 : ("<<k<<")"<<endl;
	  }
	  else { 
	    if(dCurrentStart < dPreviousCurrent*0.25) {
	      //-- cout<<"***** etat2 : ("<<k<<")"<<endl;
	      wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point 
	    }
	    else { 
	      Standard_Real UMidUtest = 0.5*(UV1+Up)-Utest;
	      Standard_Real VMidVtest = 0.5*(UV2+Vp)-Vtest;	    
	      Standard_Real dMiddleStart =  UMidUtest* UMidUtest+VMidVtest*VMidVtest;

	      if(dMiddleStart < dPreviousCurrent*0.5) { 
		//-- cout<<"*********** etat2 : ("<<k<<")"<<endl;
		wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point 
	      }
	    }
	  }
	}
      }
    }
  }

  // crossing test on crossing points.
  
  Irang =0;
  for (i = 1; i < (int)wd1.size(); i++) {
    if (wd1[i].etat > 0 && wd1[i].etat < 11) { //test of crossing points 
      Utest = wd1[i].ustart;
      Vtest = wd1[i].vstart;
      Utest/=deltau;
      Vtest/=deltav;
      
      if (((Up-Utest) * (UV1-Utest) + (Vp-Vtest) * (UV2-Vtest) < 0) ||
	  (Abs(UV1-Utest) < tolu &&  Abs(UV2-Vtest) < tolv)) 
	Irang = i;
      else if (nbMultiplicities[i] > 0) {
	N=0;
	for (k = 1; k < i; k++) N = N + nbMultiplicities[k];
	for (Standard_Integer j = N + 1; j <= N + nbMultiplicities[i]; j++) {
	  Standard_Real Umultj = Umult(j)/deltau;
	  Standard_Real Vmultj = Vmult(j)/deltav;	  
          if (((Up-Umultj)*(UV1-Umultj) +
	       (Vp-Vmultj)*(UV2-Vmultj) < 0) ||
	      (Abs(UV1-Umultj) < tolu &&
	       Abs(UV2-Vmultj) < tolv)) {
	    Irang=i;
	    break;
          }
	}
      }
    }    
  }
  return Arrive;
}


Standard_Boolean IntWalk_IWalking::TestArretAjout
  (TheIWFunction& sp,
   math_Vector& UV, 
   Standard_Integer& Irang,
   IntSurf_PntOn2S& Psol) 

// test of stop on added points 
// these are the points on the natural biorder that were not given at input
// return : Psol,  the added point.
//          Irang, index in the iterator of added points.
//          UV,    parameter of the added point.
//
{
  Standard_Boolean Arrive = Standard_False;
  Standard_Real U1,V1;
  Standard_Real Up,Vp; 

  if (!reversed) {
    previousPoint.ParametersOnS2(Up,Vp);
  }
  else {
    previousPoint.ParametersOnS1(Up,Vp);
  }

  Standard_Integer nbAjout = seqAjout.Length();
  for (Standard_Integer i = 1; i <= nbAjout; i++) {
    Irang = seqAjout.Value(i);

// add test Abs(Irang) <= lines.Length() for the case when 
// a closed line is opened by adding a  1 point on this same
// line. Anyway there is a huge problem as 2 points will be 
// added on this line...

    if (Abs(Irang) <= lines.Length()) {

      const Handle(IntWalk_TheIWLine)& Line = lines.Value(Abs(Irang));
      if (Irang>0) 
	Psol = Line->Value(Line->NbPoints()); 
      else 
	Psol = Line->Value(1);
      if (!reversed) {
	Psol.ParametersOnS2(U1, V1);
      }
      else {
	Psol.ParametersOnS1(U1, V1);
      }
      if (((Up-U1) * (UV(1)-U1) + 
	   (Vp-V1) * (UV(2)-V1)) < 0 ||
	  (Abs(UV(1)-U1) < tolerance(1) &&  
	   Abs(UV(2)-V1) < tolerance(2))) {
//jag 940615	Irang= -Abs(Irang); 
	Arrive = Standard_True; 
	UV(1) = U1;
	UV(2) = V1;
	Standard_Real abidF[1], abidD[1][2];
	math_Vector bidF(abidF,1,1);
	math_Matrix bidD(abidD,1,1,1,2);
    sp.Values(UV,bidF,bidD);
	break;
      }
    }
  }
  return Arrive;
}

void IntWalk_IWalking::FillPntsInHoles(TheIWFunction& sp,
                                       TColStd_SequenceOfInteger& CopySeqAlone,
                                       IntSurf_SequenceOfInteriorPoint& PntsInHoles)
{
  math_Vector BornInf(1,2), BornSup(1,2);
  BornInf(1) = Um;
  BornSup(1) = UM;
  BornInf(2) = Vm;
  BornSup(2) = VM;
  PointLineLine.Clear();
  TColStd_SequenceOfInteger SeqToRemove;
  TColStd_MapOfInteger BadSolutions;
  
  for (Standard_Integer i = 1; i < CopySeqAlone.Length(); i++)
  {
    Standard_Integer Irang1 = CopySeqAlone(i);
    if (Irang1 == 0)
      continue;
    Standard_Boolean ToRemove = Standard_False;
    IntSurf_PntOn2S PointAlone1, PointAlone2;
    const Handle(IntWalk_TheIWLine)& Line1 = lines.Value(Abs(Irang1));
    if (Irang1 > 0) 
      PointAlone1 = Line1->Value(Line1->NbPoints()); 
    else 
      PointAlone1 = Line1->Value(1);
    gp_Pnt2d P2d1 = PointAlone1.ValueOnSurface(reversed), P2d2;
    Standard_Real MinSqDist = RealLast();
    Standard_Integer MinRang = 0, MinIndex = 0;
    for (Standard_Integer j = i+1; j <= CopySeqAlone.Length(); j++)
    {
      Standard_Integer Irang2 = CopySeqAlone(j);
      if (Irang2 == 0 ||
          BadSolutions.Contains(Irang2))
        continue;
      const Handle(IntWalk_TheIWLine)& Line2 = lines.Value(Abs(Irang2));
      if (Irang2 > 0)
        PointAlone2 = Line2->Value(Line2->NbPoints());
      else
        PointAlone2 = Line2->Value(1);
      P2d2 = PointAlone2.ValueOnSurface(reversed);
      Standard_Real aSqDist = P2d1.SquareDistance(P2d2);
      if (aSqDist < MinSqDist)
      {
        MinSqDist = aSqDist;
        MinRang = Irang2;
        MinIndex = j;
      }
    }
    //processing points from Irang1 and MinRang
    if (MinRang == 0)
    {
      SeqToRemove.Append(Irang1);
      BadSolutions.Clear();
      continue;
    }
    //Ends of same line
    if (Abs(Irang1) == Abs(MinRang) &&
        lines.Value(Abs(Irang1))->NbPoints() == 2)
    {
      SeqToRemove.Append(Irang1);
      SeqToRemove.Append(MinRang);
      CopySeqAlone(i) = 0;
      CopySeqAlone(MinIndex) = 0;
      BadSolutions.Clear();
      continue;
    }
    ///////////////////
    const Handle(IntWalk_TheIWLine)& Line2 = lines.Value(Abs(MinRang));
    if (MinRang > 0)
      PointAlone2 = Line2->Value(Line2->NbPoints());
    else
      PointAlone2 = Line2->Value(1);
    gp_Pnt Pnt1 = PointAlone1.Value();
    gp_Pnt Pnt2 = PointAlone2.Value();
    P2d2 = PointAlone2.ValueOnSurface(reversed);
    Standard_Real MinSqDist3d = Pnt1.SquareDistance(Pnt2);
    if (MinSqDist3d <= epsilon ||
        (Abs(P2d1.X() - P2d2.X()) <= tolerance(1) &&
         Abs(P2d1.Y() - P2d2.Y()) <= tolerance(2))) //close points
      ToRemove = Standard_True;
    else //real curve
    {
      math_Vector UVap(1,2), UV(1,2);
      UVap(1) = (P2d1.X() + P2d2.X())/2;
      UVap(2) = (P2d1.Y() + P2d2.Y())/2;
      math_FunctionSetRoot Rsnld(sp, tolerance);
      Rsnld.Perform(sp, UVap, BornInf, BornSup);
      if (Rsnld.IsDone() &&
          Abs(sp.Root()) <= sp.Tolerance() &&
          !sp.IsTangent())
      {
        Rsnld.Root(UV);
        gp_Pnt2d Pmid(UV(1),UV(2));
        gp_Vec2d P1P2(P2d1, P2d2);
        gp_Vec2d P1Pmid(P2d1, Pmid);
        gp_Vec2d P2Pmid(P2d2, Pmid);
        Standard_Real ScalProd1 = P1P2 * P1Pmid;
        Standard_Real ScalProd2 = P1P2 * P2Pmid;
        Standard_Boolean IsPmidValid = (ScalProd1 > 0. && ScalProd2 < 0); //Pmid is in the middle
        if (IsPmidValid)
        {
          for (Standard_Integer iline = 1; iline <= lines.Length(); iline++)
            if (IsPointOnLine(Pmid,iline))
            {
              IsPmidValid = Standard_False;
              break;
            }
        }
        if (IsPmidValid)
        {
          IntSurf_InteriorPoint aPoint(sp.Point(), UV(1), UV(2),
                                       sp.Direction3d(),
                                       sp.Direction2d());
          PntsInHoles.Append(aPoint);
          TColStd_ListOfInteger LineLine;
          LineLine.Append(Irang1);
          LineLine.Append(MinRang);
          PointLineLine.Bind(PntsInHoles.Length(), LineLine);
        }
        else
        {
          BadSolutions.Add(MinRang);
          i--;
          continue;
        }
      }
      else
      {
        BadSolutions.Add(MinRang);
        i--;
        continue;
      }
    }
    CopySeqAlone(i) = 0;
    CopySeqAlone(MinIndex) = 0;
    if (ToRemove)
    {
      SeqToRemove.Append(Irang1);
      SeqToRemove.Append(MinRang);
    }
    BadSolutions.Clear();
  }

  for (Standard_Integer i = 1; i <= SeqToRemove.Length(); i++)
    for (Standard_Integer j = 1; j <= seqAlone.Length(); j++)
      if (seqAlone(j) == SeqToRemove(i))
      {
        seqAlone.Remove(j);
        break;
      }
}

void IntWalk_IWalking::TestArretCadre
  (const TColStd_SequenceOfReal& Umult,
   const TColStd_SequenceOfReal& Vmult,
   const Handle(IntWalk_TheIWLine)& Line,
   TheIWFunction& sp,
   math_Vector& UV,
   Standard_Integer& Irang)

// test of stop when located on border.
// tried all tests of stop and arrived.
// test of stop on all given departure points already marked and on the entire current line.
// This line can be shortened if the stop point is found.
// Abs(Irang) = index in the iterator of departure points or 0
//  if Irang <0 , it is necessary to add this point on the line (no Line->Cut)
// UV = parameter of the departure point
{
  Standard_Real Scal, Up, Vp, Uc, Vc;
  Standard_Integer N;
  Standard_Boolean Found = Standard_False;


  Irang =0;
  for (Standard_Integer i = 1; i < (int)wd1.size(); i++) {
    if (wd1[i].etat < 0) {
      N=0; // range in UVMult.
      if (nbMultiplicities[i] > 0) {
	for (Standard_Integer k = 1; k < i; k++) 
	  N+=nbMultiplicities[k];
      }
      if (!reversed) {
	Line->Value(1).ParametersOnS2(Up,Vp);
      }
      else {
	Line->Value(1).ParametersOnS1(Up,Vp);
      }
      Standard_Integer nbp= Line->NbPoints();
      for (Standard_Integer j = 2; j <= nbp; j++) {
	if (!reversed) {
	  Line->Value(j).ParametersOnS2(Uc,Vc);
	}
	else {
	  Line->Value(j).ParametersOnS1(Uc,Vc);
	}

	Scal = (Up-wd1[i].ustart) * (Uc-wd1[i].ustart) +
	       (Vp-wd1[i].vstart) * (Vc-wd1[i].vstart);
        // if a stop point is found: stop the line on this point.
	if (Scal < 0) { 
          Line->Cut(j);  nbp= Line->NbPoints();
          Irang = i;
	  UV(1) = wd1[Irang].ustart;
	  UV(2) = wd1[Irang].vstart;
          Found = Standard_True;
	}
	else if (Abs(Uc-wd1[i].ustart) < tolerance(1) &&
		 Abs(Vc-wd1[i].vstart) < tolerance(2) ) {
          Line->Cut(j);  nbp= Line->NbPoints();
          Irang=i; 
	  UV(1) = wd1[Irang].ustart;
	  UV(2) = wd1[Irang].vstart;
          Found = Standard_True;
	}
	else if (nbMultiplicities[i] > 0) {
          for (Standard_Integer k = N+1; k <= N + nbMultiplicities[i]; k++) {
	    Scal = (Up-Umult(k)) * (Uc-Umult(k)) +
	           (Vp-Vmult(k)) * (Vc-Vmult(k));
	    if (Scal < 0) { 
	      Line->Cut(j);  nbp= Line->NbPoints();
	      Irang=i;
	      UV(1) = wd1[Irang].ustart;
	      UV(2) = wd1[Irang].vstart;
	      Found = Standard_True;
	      break;
	    }
	    else if (Abs(Uc-Umult(k)) < tolerance(1) &&
		     Abs(Vc-Vmult(k)) < tolerance(2)) {
	      Line->Cut(j);  nbp= Line->NbPoints();
	      Irang=i; 
	      UV(1) = wd1[Irang].ustart;
	      UV(2) = wd1[Irang].vstart;
	      Found = Standard_True;
	      break;
	    }
          }
	}
	if (Found) {
	  Standard_Real abidF[1], abidD[1][2];
	  math_Vector bidF(abidF,1,1);
	  math_Matrix bidD(abidD,1,1,1,2);
      sp.Values(UV,bidF,bidD);
	  Standard_Integer NBP =  Line->NbPoints();
	  Standard_Integer Indextg;	  
	  Line->TangentVector(Indextg);
	  if(Indextg > NBP) { 
	    if(j>3 && j<=NBP+1) { 
	      gp_Vec Dir3d = sp.Direction3d();
	      gp_Vec Dir3d1 = gp_Vec(Line->Value(j-2).Value(),Line->Value(j-1).Value());
	      Standard_Real dot = Dir3d.Dot(Dir3d1);
	      if(dot<0.0) { // Normally this Function should not be used often !!! 
		Dir3d.Reverse();
		//-- cout<<" IntWalk_IWalking_2.gxx REVERSE "<<endl;
	      }
	      Line->SetTangentVector(previousd3d,j-1);
	    }
#ifdef OCCT_DEBUG
	    else { 
	      std::cout<<" IntWalk_IWalking_2.gxx : bizarrerie 30 10 97 "<<std::endl;
	    }
#endif
	  }

	  return;
	}
	Up = Uc;
	Vp = Vc;
      }

      // now the last point of the line and the last calculated point are compated.
      // there will be no need to "Cut"

      Scal = (Up-wd1[i].ustart) * (UV(1)-wd1[i].ustart) +
	// 	(Vp-wd1[i].vstart) * (UV(2)-wd1[i].vstart);
      // modified by NIZHNY-MKK  Fri Oct 27 12:29:41 2000
	(Vp-wd1[i].vstart) * (UV(2)-wd1[i].vstart);

      if (Scal < 0) { 
        Irang = i;
	UV(1) = wd1[Irang].ustart;
	UV(2) = wd1[Irang].vstart;
	Found = Standard_True;
      }
      else if (Abs(UV(1)-wd1[i].ustart) < tolerance(1) &&
	       Abs(UV(2)-wd1[i].vstart) < tolerance(2)) {
        Irang=i; 
	UV(1) = wd1[Irang].ustart;
	UV(2) = wd1[Irang].vstart;
	Found = Standard_True;
      }
      else if (nbMultiplicities[i] > 0) {
        for (Standard_Integer j = N+1; j <= N+nbMultiplicities[i]; j++) {
	  Scal = (Up-Umult(j)) * (UV(1)-Umult(j)) +
                 (Vp-Vmult(j)) * (UV(2)-Vmult(j));
	  if (Scal < 0) { 
	    Irang=i;
	    UV(1) = wd1[Irang].ustart;
	    UV(2) = wd1[Irang].vstart;
	    Found = Standard_True;
	    break;
	  }
	  else if (Abs(UV(1)-Umult(j)) < tolerance(1) &&
		   Abs(UV(2)-Vmult(j)) < tolerance(2)) {
	    Irang=i; 
	    UV(1) = wd1[Irang].ustart;
	    UV(2) = wd1[Irang].vstart;
	    Found = Standard_True;
	    break;
	  }
        }
      }
      if (Found) {
	Irang = -Irang; // jag 941017
	Standard_Real abidF[1], abidD[1][2];
	math_Vector bidF(abidF,1,1);
	math_Matrix bidD(abidD,1,1,1,2);
    sp.Values(UV,bidF,bidD);
	return;
      }
    }
  } 
}