1 // Created on: 1992-10-13
2 // Created by: Laurent BUCHARD
3 // Copyright (c) 1992-1999 Matra Datavision
4 // Copyright (c) 1999-2012 OPEN CASCADE SAS
6 // The content of this file is subject to the Open CASCADE Technology Public
7 // License Version 6.5 (the "License"). You may not use the content of this file
8 // except in compliance with the License. Please obtain a copy of the License
9 // at http://www.opencascade.org and read it completely before using this file.
11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
14 // The Original Code and all software distributed under the License is
15 // distributed on an "AS IS" basis, without warranty of any kind, and the
16 // Initial Developer hereby disclaims all such warranties, including without
17 // limitation, any warranties of merchantability, fitness for a particular
18 // purpose or non-infringement. Please see the License for the specific terms
19 // and conditions governing the rights and limitations under the License.
22 // Modified by skv - Tue Mar 1 14:22:09 2005 OCC8169
26 #define No_Standard_RangeError
27 #define No_Standard_OutOfRange
31 #include <Standard_ConstructionError.hxx>
33 #include <IntRes2d_Domain.hxx>
34 #include <IntRes2d_Position.hxx>
35 #include <IntRes2d_Transition.hxx>
36 #include <IntRes2d_IntersectionPoint.hxx>
37 #include <IntRes2d_IntersectionSegment.hxx>
40 #include <IntImpParGen.hxx>
42 #include <Intf_SectionPoint.hxx>
43 #include <Intf_SectionLine.hxx>
44 #include <Intf_TangentZone.hxx>
45 #include <Intf_InterferencePolygon2d.hxx>
47 #include <gp_Vec2d.hxx>
49 #include <math_Vector.hxx>
50 #include <math_FunctionSetRoot.hxx>
51 #include <math_NewtonFunctionSetRoot.hxx>
53 //======================================================================
55 // Modified by skv - Tue Mar 1 14:22:09 2005 OCC8169 Begin
56 // #define NBITER_MAX_POLYGON 3
57 #define NBITER_MAX_POLYGON 10
58 // Modified by skv - Tue Mar 1 14:22:09 2005 OCC8169 End
59 #define TOL_CONF_MINI 0.0000000001
60 #define TOL_MINI 0.0000000001
62 //----------------------------------------------------------------------
68 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
70 ,const Standard_Real u
71 ,const IntRes2d_Domain& D2
73 ,const Standard_Real v
74 ,const Standard_Real TolConf
75 ,IntRes2d_IntersectionPoint& IntPt
76 ,Standard_Boolean& HeadOn1
77 ,Standard_Boolean& HeadOn2
78 ,Standard_Boolean& EndOn1
79 ,Standard_Boolean& EndOn2
80 ,Standard_Integer PosSegment);
83 //======================================================================
84 IntCurve_IntPolyPolyGen::IntCurve_IntPolyPolyGen(void) {
85 done = Standard_False;
87 //======================================================================
88 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
89 ,const IntRes2d_Domain& D1
91 ,const IntRes2d_Domain& D2
92 ,const Standard_Real TheTolConf
93 ,const Standard_Real TheTol)
96 Standard_Boolean AnErrorOccurred = Standard_False;
101 Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
102 Standard_Real DV = D2.LastParameter()-D2.FirstParameter();
103 Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
104 Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
105 Perform(C1,D1,C2,D2,TlConf,Tl,0,DU,DV);
106 //----------------------------------------------------------------------
107 //-- Traitement des points en bouts
108 //----------------------------------------------------------------------
109 Standard_Boolean HeadOn1 = Standard_False;
110 Standard_Boolean HeadOn2 = Standard_False;
111 Standard_Boolean EndOn1 = Standard_False;
112 Standard_Boolean EndOn2 = Standard_False;
114 Standard_Integer n=this->NbPoints();
117 //--------------------------------------------------------------------
118 //-- On ne rejette les points Head Head ... End End
119 //-- si ils figurent deja dans un bout de segment
120 //-- ( On ne peut pas tester les egalites sur les parametres)
121 //-- ( ces points n etant pas trouves a EpsX pres )
122 //-- PosSegment = 1 si Head Head
126 //--------------------------------------------------------------------
127 Standard_Integer PosSegment = 0;
132 IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
133 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
134 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
136 IntRes2d_Position Pos2 = this->Point(i).TransitionOfSecond().PositionOnCurve();
137 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
138 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
140 if(Pos1 == IntRes2d_Head) {
141 if(Pos2 == IntRes2d_Head) PosSegment|=1;
142 else if(Pos2 == IntRes2d_End) PosSegment|=2;
144 else if(Pos1 == IntRes2d_End) {
145 if(Pos2 == IntRes2d_Head) PosSegment|=4;
146 else if(Pos2 == IntRes2d_End) PosSegment|=8;
150 n=this->NbSegments();
152 IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
153 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
154 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
156 IntRes2d_Position Pos2 = this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
157 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
158 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
160 if(Pos1 == IntRes2d_Head) {
161 if(Pos2 == IntRes2d_Head) PosSegment|=1;
162 else if(Pos2 == IntRes2d_End) PosSegment|=2;
164 else if(Pos1 == IntRes2d_End) {
165 if(Pos2 == IntRes2d_Head) PosSegment|=4;
166 else if(Pos2 == IntRes2d_End) PosSegment|=8;
169 Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
170 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
171 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
173 Pos2 = this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
174 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
175 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
177 if(Pos1 == IntRes2d_Head) {
178 if(Pos2 == IntRes2d_Head) PosSegment|=1;
179 else if(Pos2 == IntRes2d_End) PosSegment|=2;
181 else if(Pos1 == IntRes2d_End) {
182 if(Pos2 == IntRes2d_Head) PosSegment|=4;
183 else if(Pos2 == IntRes2d_End) PosSegment|=8;
189 Standard_Real U0 = D1.FirstParameter();
190 Standard_Real U1 = D1.LastParameter();
191 Standard_Real V0 = D2.FirstParameter();
192 Standard_Real V1 = D2.LastParameter();
194 Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
195 Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
196 IntRes2d_IntersectionPoint IntPt;
198 if(D1.FirstTolerance() || D2.FirstTolerance()) {
199 if(HeadOrEndPoint(D1,C1,U0,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
202 if(D1.FirstTolerance() || D2.LastTolerance()) {
203 if(HeadOrEndPoint(D1,C1,U0,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
206 if(D1.LastTolerance() || D2.FirstTolerance()) {
207 if(HeadOrEndPoint(D1,C1,U1,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
210 if(D1.LastTolerance() || D2.LastTolerance()) {
211 if(HeadOrEndPoint(D1,C1,U1,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
214 if(AnErrorOccurred) {
215 //----------------------------------------------------------------------------------
216 //-- On a donne un point approche a la recherche du point exact, et cette recherche
218 //-- Soit le point n'existe pas, soit c'est un point en bout dont un des parameteres
219 //-- est en dehors du domaine de la courbe.
221 //-- Dans le cas contraire, on suppose que les points en bouts ont ete trouves par
222 //-- les interferences des polygones
226 v = TheProjPCur::FindParameter( C2,D1.FirstPoint(),V0,V1,EpsX2);
227 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
233 v = TheProjPCur::FindParameter( C2,D1.LastPoint(),V0,V1,EpsX2);
234 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
239 u = TheProjPCur::FindParameter( C1,D2.FirstPoint(),U0,U1,EpsX1);
241 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
246 u = TheProjPCur::FindParameter( C1,D2.LastPoint(),U0,U1,EpsX1);
248 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
258 //======================================================================
259 //== A u t o I n t e r s e c t i o n
260 //======================================================================
261 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
262 ,const IntRes2d_Domain& D1
263 ,const Standard_Real TheTolConf
264 ,const Standard_Real TheTol)
270 Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
271 Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
272 Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
273 Perform(C1,D1,TlConf,Tl,0,DU,DU);
274 //----------------------------------------------------------------------
275 //-- Traitement des points en bouts
276 //----------------------------------------------------------------------
277 Standard_Boolean HeadOn1 = Standard_False;
278 Standard_Boolean HeadOn2 = Standard_False;
279 Standard_Boolean EndOn1 = Standard_False;
280 Standard_Boolean EndOn2 = Standard_False;
282 Standard_Integer n=this->NbPoints();
285 //--------------------------------------------------------------------
286 //-- On ne rejette les points Head Head ... End End
287 //-- si ils figurent deja dans un bout de segment
288 //-- ( On ne peut pas tester les egalites sur les parametres)
289 //-- ( ces points n etant pas trouves a EpsX pres )
290 //-- PosSegment = 1 si Head Head
294 //--------------------------------------------------------------------
295 Standard_Integer PosSegment = 0;
300 IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
301 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
302 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
304 IntRes2d_Position Pos2 = this->Point(i).TransitionOfSecond().PositionOnCurve();
305 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
306 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
308 if(Pos1 == IntRes2d_Head) {
309 if(Pos2 == IntRes2d_Head) PosSegment|=1;
310 else if(Pos2 == IntRes2d_End) PosSegment|=2;
312 else if(Pos1 == IntRes2d_End) {
313 if(Pos2 == IntRes2d_Head) PosSegment|=4;
314 else if(Pos2 == IntRes2d_End) PosSegment|=8;
318 n=this->NbSegments();
320 IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
321 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
322 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
324 IntRes2d_Position Pos2 = this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
325 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
326 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
328 if(Pos1 == IntRes2d_Head) {
329 if(Pos2 == IntRes2d_Head) PosSegment|=1;
330 else if(Pos2 == IntRes2d_End) PosSegment|=2;
332 else if(Pos1 == IntRes2d_End) {
333 if(Pos2 == IntRes2d_Head) PosSegment|=4;
334 else if(Pos2 == IntRes2d_End) PosSegment|=8;
337 Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
338 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
339 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
341 Pos2 = this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
342 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
343 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
345 if(Pos1 == IntRes2d_Head) {
346 if(Pos2 == IntRes2d_Head) PosSegment|=1;
347 else if(Pos2 == IntRes2d_End) PosSegment|=2;
349 else if(Pos1 == IntRes2d_End) {
350 if(Pos2 == IntRes2d_Head) PosSegment|=4;
351 else if(Pos2 == IntRes2d_End) PosSegment|=8;
355 //======================================================================
359 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
360 ,const IntRes2d_Domain& D1
361 ,const Standard_Real TolConf
362 ,const Standard_Real Tol
363 ,const Standard_Integer NbIter
364 ,const Standard_Real DeltaU
365 ,const Standard_Real) {
367 gp_Vec2d Tan1,Tan2,Norm1,Norm2;
369 Standard_Integer nbsamples;
370 done = Standard_False;
371 Standard_Boolean AnErrorOccurred = Standard_False;
374 nbsamples = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
376 if(NbIter>3 || (NbIter>2 && nbsamples>100)) return;
378 nbsamples*=2; //--- On prend systematiquement 2 fois plus de points que
379 //-- sur une courbe normale.
380 //-- Les courbes auto-intersectantes donne souvent des
381 //-- polygones assez loin de la courbe a parametre ct.
384 nbsamples=(3*(nbsamples*NbIter))/2;
386 IntCurve_ThePolygon2d Poly1(C1,nbsamples,D1,Tol);
387 if(!Poly1.AutoIntersectionIsPossible()) {
388 done = Standard_True;
392 //----------------------------------------------------------------------
393 //-- Si la deflection est inferieure a la Tolerance de Confusion
394 //-- Alors la deflection du polygone est fixee a TolConf
395 //-- (Detection des Zones de Tangence)
396 //----------------------------------------------------------------------
397 if(Poly1.DeflectionOverEstimation() < TolConf) {
398 Poly1.SetDeflectionOverEstimation(TolConf);
401 Intf_InterferencePolygon2d InterPP(Poly1);
402 IntCurve_ExactIntersectionPoint EIP(C1,C1,TolConf);
405 //----------------------------------------------------------------------
406 //-- Traitement des SectionPoint
407 //----------------------------------------------------------------------
408 Standard_Integer Nbsp = InterPP.NbSectionPoints();
411 //-- ---------------------------------------------------------------------
412 //-- tri tri tri tri tri tri tri tri tri tri tri tri tri tri
414 Standard_Integer* TriIndex = new Standard_Integer [Nbsp+1];
415 Standard_Integer* PtrSegIndex1 = new Standard_Integer [Nbsp+1];
416 Standard_Integer* PtrSegIndex2 = new Standard_Integer [Nbsp+1];
417 Standard_Boolean Triok;
418 Standard_Integer SegIndex1,SegIndex2,SegIndex_1,SegIndex_2;
419 // Standard_Real ParamOn1,ParamOn2,ParamOn_1,ParamOn_2;
420 Standard_Real ParamOn1,ParamOn2;
423 for( i=1;i<=Nbsp;i++) {
425 const Intf_SectionPoint& SPnt1 = InterPP.PntValue(i);
426 SPnt1.InfoFirst(Type,PtrSegIndex1[i],ParamOn1);
427 SPnt1.InfoSecond(Type,PtrSegIndex2[i],ParamOn2);
434 for(Standard_Integer tr=1;tr<Nbsp;tr++) {
435 SegIndex1=PtrSegIndex1[TriIndex[tr]];
436 SegIndex_1=PtrSegIndex1[TriIndex[tr+1]];
438 SegIndex2=PtrSegIndex2[TriIndex[tr]];
439 SegIndex_2=PtrSegIndex2[TriIndex[tr+1]];
441 if(SegIndex1 > SegIndex_1) {
442 Standard_Integer q=TriIndex[tr];
443 TriIndex[tr]=TriIndex[tr+1];
445 Triok=Standard_False;
447 else if(SegIndex1 == SegIndex_1) {
448 if(SegIndex2 > SegIndex_2) {
449 Standard_Integer q=TriIndex[tr];
450 TriIndex[tr]=TriIndex[tr+1];
452 Triok=Standard_False;
457 while(Triok==Standard_False);
459 //-- supression des doublons Si Si !
460 for(i=1; i<Nbsp;i++) {
461 if( (PtrSegIndex1[TriIndex[i]] == PtrSegIndex1[TriIndex[i+1]])
462 && (PtrSegIndex2[TriIndex[i]] == PtrSegIndex2[TriIndex[i+1]])) {
468 Standard_Integer Nelarg=(Poly1.NbSegments()/20);
469 if(Nelarg<2) Nelarg=2;
471 for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
473 const Intf_SectionPoint& SPnt = InterPP.PntValue(TriIndex[sp]);
475 SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
476 SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
478 if(Abs(SegIndex1-SegIndex2)>1) {
480 EIP.Perform(Poly1,Poly1,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
481 AnErrorOccurred = EIP.AnErrorOccurred();
482 if(EIP.NbRoots()==0) {
483 //-- On supprime tous les segments voisins
484 for(Standard_Integer k=sp+1;k<=Nbsp;k++) {
485 Standard_Integer kk=TriIndex[k];
486 // modified by OFV OCC2502 Tue Apr 29 15:07:45 2003 .Begin
487 // --- avoid negative indicies as well as in outer done
489 if( Abs(SegIndex1-PtrSegIndex1[kk])< Nelarg
490 && Abs(SegIndex2-PtrSegIndex2[kk])< Nelarg) {
494 // modified by OFV OCC2502 Tue Apr 29 15:11:34 2003 .End
497 else if(EIP.NbRoots()>=1) {
498 //--------------------------------------------------------------------
499 //-- On verifie que le point trouve est bien une racine
500 //--------------------------------------------------------------------
503 TheCurveTool::D1(C1,U,P1,Tan1);
504 TheCurveTool::D1(C1,V,P2,Tan2);
505 Standard_Real Dist = P1.Distance(P2);
506 Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
508 if(Abs(U-V)<=EpsX1) {
509 //-----------------------------------------
510 //-- Solution non valide
511 //-- Les maths ont du converger vers une
512 //-- solution triviale ( point U = V )
513 //-----------------------------------------
517 //-----------------------------------------------------------------
518 //-- On verifie que le point (u,v) n existe pas deja
520 done = Standard_True;
521 Standard_Integer nbp=NbPoints();
523 for(Standard_Integer p=1; p<=nbp; p++) {
524 const IntRes2d_IntersectionPoint& P=Point(p);
525 if(Abs(U-P.ParamOnFirst()) <= EpsX1) {
526 if(Abs(V-P.ParamOnSecond()) <= EpsX1) {
527 Dist = TolConf+1.0; p+=nbp;
532 if(Dist <= TolConf) { //-- Ou le point est deja present
533 IntRes2d_Position Pos1 = IntRes2d_Middle;
534 IntRes2d_Position Pos2 = IntRes2d_Middle;
535 IntRes2d_Transition Trans1,Trans2;
536 //-----------------------------------------------------------------
537 //-- Calcul des Positions des Points sur la courbe
539 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())
540 Pos1 = IntRes2d_Head;
541 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance())
544 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())
545 Pos2 = IntRes2d_Head;
546 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance())
548 //-----------------------------------------------------------------
549 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
551 ,TolConf) == Standard_False) {
552 TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
553 TheCurveTool::D2(C1,V,P2,Tan2,Norm2);
554 IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
555 ,Pos2,Tan2,Norm2,Trans2
558 IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
566 delete [] PtrSegIndex1;
567 delete [] PtrSegIndex2;
571 //----------------------------------------------------------------------
572 //-- Traitement des TangentZone
573 //----------------------------------------------------------------------
574 Standard_Integer Nbtz = InterPP.NbTangentZones();
577 Standard_Real ParamInf=D1.FirstParameter();
578 Standard_Real ParamSup=D1.LastParameter();
579 ParamSup=-RealLast();
581 for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
582 Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
583 //====================================================================
584 //== Recherche du premier et du dernier point dans la zone de tg.
585 //== ATTENTION LA LISTE N EST PAS TRIEE
586 //====================================================================
587 for(Standard_Integer tzz=1; tzz<=NbPnts; tzz++) {
588 const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(tzz);
590 // Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2;
591 Standard_Integer SegIndex1onP1;
593 Standard_Real ParamOnLine;
595 SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
596 if(SegIndex1onP1 >= Poly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
597 if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
598 Standard_Real Par = Poly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
599 if(ParamSup<Par) ParamSup=Par;
600 if(ParamInf>Par) ParamInf=Par;
603 if(ParamSup > ParamInf) {
604 //-- printf("\n %g -> %g %g -> %g ",D1.FirstParameter(),ParamInf,D1.LastParameter(),ParamSup);
605 IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInf)
607 ,TheCurveTool::Value(C1,ParamSup)
609 Perform(C1,RecursD1,TolConf,Tol,NbIter+1,ParamSup-ParamInf,0.0);
612 //----------------------------------------------------------------------
613 done = Standard_True;
617 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
619 ,const Standard_Real tu
620 ,const IntRes2d_Domain& D2
622 ,const Standard_Real tv
623 ,const Standard_Real TolConf
624 ,IntRes2d_IntersectionPoint& IntPt
625 ,Standard_Boolean& HeadOn1
626 ,Standard_Boolean& HeadOn2
627 ,Standard_Boolean& EndOn1
628 ,Standard_Boolean& EndOn2
629 ,Standard_Integer PosSegment) {
631 gp_Pnt2d P1,P2,SP1,SP2;
632 gp_Vec2d T1,T2,N1,N2;
635 Standard_Real svu = u;
636 Standard_Real svv = v;
638 TheCurveTool::D1(C1,u,P1,T1);
639 TheCurveTool::D1(C2,v,P2,T2);
641 IntRes2d_Position Pos1 = IntRes2d_Middle;
642 IntRes2d_Position Pos2 = IntRes2d_Middle;
643 IntRes2d_Transition Trans1,Trans2;
645 //----------------------------------------------------------------------
646 //-- Head On 1 : Head1 <-> P2
647 if(P2.Distance(D1.FirstPoint())<=D1.FirstTolerance()) {
648 Pos1 = IntRes2d_Head;
649 HeadOn1 = Standard_True;
650 SP1 = D1.FirstPoint();
651 u = D1.FirstParameter();
653 //----------------------------------------------------------------------
654 //-- End On 1 : End1 <-> P2
655 else if(P2.Distance(D1.LastPoint())<=D1.LastTolerance()) {
657 EndOn1 = Standard_True;
658 SP1 = D1.LastPoint();
659 u = D1.LastParameter();
663 //----------------------------------------------------------------------
664 //-- Head On 2 : Head2 <-> P1
665 else if(P1.Distance(D2.FirstPoint())<=D2.FirstTolerance()) {
666 Pos2 = IntRes2d_Head;
667 HeadOn2 = Standard_True;
668 SP2 = D2.FirstPoint();
669 v = D2.FirstParameter();
671 //----------------------------------------------------------------------
672 //-- End On 2 : End2 <-> P1
673 else if(P1.Distance(D2.LastPoint())<=D2.LastTolerance()) {
675 EndOn2 = Standard_True;
676 SP2 = D2.LastPoint();
677 v = D2.LastParameter();
680 Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
681 Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
684 if((Pos1 != IntRes2d_Middle)||(Pos2 != IntRes2d_Middle)) {
685 if(Pos1 == IntRes2d_Middle) {
686 if(Abs(u-D1.FirstParameter()) <= EpsX1) {
687 Pos1 = IntRes2d_Head;
688 P1 = D1.FirstPoint();
689 HeadOn1 = Standard_True;
691 else if(Abs(u-D1.LastParameter()) <= EpsX1) {
694 EndOn1 = Standard_True;
702 if(Pos2 == IntRes2d_Middle) {
703 if(Abs(v-D2.FirstParameter()) <= EpsX2) {
704 Pos2 = IntRes2d_Head;
705 HeadOn2 = Standard_True;
706 P2 = D2.FirstPoint();
707 if(Pos1 != IntRes2d_Middle) {
708 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
714 else if(Abs(v-D2.LastParameter()) <= EpsX2) {
716 EndOn2 = Standard_True;
718 if(Pos1 != IntRes2d_Middle) {
719 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
728 //--------------------------------------------------------------------
729 //-- On Teste si un point de bout de segment a deja ces trnasitions
730 //-- Si Oui, on ne cree pas de nouveau point
732 //-- PosSegment = 1 si Head Head
736 //--------------------------------------------------------------------
737 if(Pos1 == IntRes2d_Head) {
738 if((Pos2 == IntRes2d_Head)&&(PosSegment & 1)) return(Standard_False);
739 if((Pos2 == IntRes2d_End )&&(PosSegment & 2)) return(Standard_False);
741 else if(Pos1 == IntRes2d_End) {
742 if((Pos2 == IntRes2d_Head)&&(PosSegment & 4)) return(Standard_False);
743 if((Pos2 == IntRes2d_End )&&(PosSegment & 8)) return(Standard_False);
747 if(IntImpParGen::DetermineTransition( Pos1,T1,Trans1,Pos2,T2,Trans2,TolConf)
749 TheCurveTool::D2(C1,svu,P1,T1,N1);
750 TheCurveTool::D2(C2,svv,P2,T2,N2);
751 IntImpParGen::DetermineTransition(Pos1,T1,N1,Trans1,
752 Pos2,T2,N2,Trans2,TolConf);
754 IntPt.SetValues(P1,u,v,Trans1,Trans2,Standard_False);
755 return(Standard_True);
758 return(Standard_False);
767 //======================================================================
768 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
769 ,const IntRes2d_Domain& D1
771 ,const IntRes2d_Domain& D2
772 ,const Standard_Real TolConf
773 ,const Standard_Real Tol
774 ,const Standard_Integer NbIter
775 ,const Standard_Real DeltaU
776 ,const Standard_Real DeltaV) {
778 gp_Vec2d Tan1,Tan2,Norm1,Norm2;
780 Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
781 done = Standard_False;
782 Standard_Boolean AnErrorOccurred = Standard_False;
784 if(NbIter>NBITER_MAX_POLYGON) return;
786 nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
788 //// modified by jgv, 5.12.02 for OCC935 ////
789 if (NbIter == 0) // first time
791 if (nbsamplesOnC1 < 20)
796 nbsamplesOnC1=(5*(nbsamplesOnC1*NbIter))/4;
798 /////////////////////////////////////////////
800 nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
802 //// modified by jgv, 5.12.02 for OCC935 ////
803 if (NbIter == 0) // first time
805 if (nbsamplesOnC2 < 20)
810 nbsamplesOnC2=(5*(nbsamplesOnC2*NbIter))/4;
812 /////////////////////////////////////////////
814 IntCurve_ThePolygon2d *PtrPoly1,*PtrPoly2;
815 if(nbsamplesOnC2 > nbsamplesOnC1) {
816 PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
817 if(PtrPoly1->DeflectionOverEstimation() < TolConf) {
818 PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
821 PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol,PtrPoly1->Bounding());
822 PtrPoly1->SetDeflectionOverEstimation( PtrPoly2->DeflectionOverEstimation()
823 +PtrPoly1->DeflectionOverEstimation());
824 PtrPoly1->ComputeWithBox(C1,PtrPoly2->Bounding());
828 PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
829 if(PtrPoly2->DeflectionOverEstimation() < TolConf) {
830 PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
833 PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol,PtrPoly2->Bounding());
834 PtrPoly2->SetDeflectionOverEstimation( PtrPoly2->DeflectionOverEstimation()
835 +PtrPoly1->DeflectionOverEstimation());
836 PtrPoly2->ComputeWithBox(C2,PtrPoly1->Bounding());
839 //----------------------------------------------------------------------
840 //-- Si la deflection est inferieure a la Tolerance de Confusion
841 //-- Alors la deflection du polygone est fixee a TolConf
842 //-- (Detection des Zones de Tangence)
843 //----------------------------------------------------------------------
845 if(PtrPoly1->DeflectionOverEstimation() < TolConf) {
846 PtrPoly1->SetDeflectionOverEstimation(TolConf);
848 if(PtrPoly2->DeflectionOverEstimation() < TolConf) {
849 PtrPoly2->SetDeflectionOverEstimation(TolConf);
851 Intf_InterferencePolygon2d InterPP(*PtrPoly1,*PtrPoly2);
852 IntCurve_ExactIntersectionPoint EIP(C1,C2,TolConf);
855 //----------------------------------------------------------------------
856 //-- Traitement des SectionPoint
857 //----------------------------------------------------------------------
858 Standard_Integer Nbsp = InterPP.NbSectionPoints();
861 for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
862 const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
863 Standard_Integer SegIndex1,SegIndex2;
864 Standard_Real ParamOn1,ParamOn2;
867 SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
868 SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
869 EIP.Perform(*PtrPoly1,*PtrPoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
870 AnErrorOccurred = EIP.AnErrorOccurred();
871 if(EIP.NbRoots()>=1) {
872 //--------------------------------------------------------------------
873 //-- On verifie que le point trouve est bien une racine
874 //--------------------------------------------------------------------
876 TheCurveTool::D1(C1,U,P1,Tan1);
877 TheCurveTool::D1(C2,V,P2,Tan2);
878 Standard_Real Dist = P1.Distance(P2);
879 //-----------------------------------------------------------------
880 //-- On verifie que le point (u,v) n existe pas deja
882 done = Standard_True;
883 Standard_Integer nbp=NbPoints();
884 Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
885 Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
887 for(Standard_Integer p=1; p<=nbp; p++) {
888 const IntRes2d_IntersectionPoint& P=Point(p);
889 if(Abs(U-P.ParamOnFirst()) <= EpsX1) {
890 if(Abs(V-P.ParamOnSecond()) <= EpsX2) {
891 Dist = TolConf+1.0; p+=nbp;
896 if(Dist <= TolConf) { //-- Ou le point est deja present
897 IntRes2d_Position Pos1 = IntRes2d_Middle;
898 IntRes2d_Position Pos2 = IntRes2d_Middle;
899 IntRes2d_Transition Trans1,Trans2;
900 //-----------------------------------------------------------------
901 //-- Calcul des Positions des Points sur la courbe
903 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())
904 Pos1 = IntRes2d_Head;
905 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance())
908 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())
909 Pos2 = IntRes2d_Head;
910 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance())
912 //-----------------------------------------------------------------
913 //-- Calcul des Transitions (Voir IntImpParGen.cxx)
915 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
917 ,TolConf)==Standard_False) {
919 TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
920 TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
921 IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
922 ,Pos2,Tan2,Norm2,Trans2
925 IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
928 } //-- if(EIP.NbRoots()>=1)
933 //----------------------------------------------------------------------
934 //-- Traitement des TangentZone
935 //----------------------------------------------------------------------
936 Standard_Integer Nbtz = InterPP.NbTangentZones();
937 for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
938 Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
939 //====================================================================
940 //== Recherche du premier et du dernier point dans la zone de tg.
941 //====================================================================
942 Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
943 Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
944 // Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
945 Standard_Integer SegIndex1onP1,SegIndex1onP2;
947 Standard_Real ParamOnLine;
948 Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
949 ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
950 ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
951 for(Standard_Integer qq=1;qq<=NbPnts;qq++) {
952 const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
953 //====================================================================
954 //== On discretise sur les zones de tangence
957 //== Deflection < Tolerance
958 //== OU Echantillon < EpsX (normalement la premiere condition est
960 //====================================================================
961 // Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
962 Standard_Real _PolyUInf,_PolyVInf;
964 SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
965 if(SegIndex1onP1 >= PtrPoly1->NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
966 if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
967 _PolyUInf = PtrPoly1->ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
969 SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
970 if(SegIndex1onP2 >= PtrPoly2->NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
971 if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
972 _PolyVInf = PtrPoly2->ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
974 //----------------------------------------------------------------------
976 if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
977 if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
979 if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
980 if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
984 PolyUInf= ParamInfOnCurve1;
985 PolyUSup= ParamSupOnCurve1;
986 PolyVInf= ParamInfOnCurve2;
987 PolyVSup= ParamSupOnCurve2;
989 TheCurveTool::D0(C1,PolyUInf,P1);
990 TheCurveTool::D0(C2,PolyVInf,P2);
991 Standard_Real distmemesens = P1.SquareDistance(P2);
992 TheCurveTool::D0(C2,PolyVSup,P2);
993 Standard_Real distdiffsens = P1.SquareDistance(P2);
994 if(distmemesens > distdiffsens) {
995 Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
1000 if( ( (PtrPoly1->DeflectionOverEstimation() > TolConf)
1001 ||(PtrPoly2->DeflectionOverEstimation() > TolConf))
1002 &&(NbIter<NBITER_MAX_POLYGON)) {
1004 IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
1005 ,ParamInfOnCurve1,TolConf
1006 ,TheCurveTool::Value(C1,ParamSupOnCurve1)
1007 ,ParamSupOnCurve1,TolConf);
1008 IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
1009 ,ParamInfOnCurve2,TolConf
1010 ,TheCurveTool::Value(C2,ParamSupOnCurve2)
1011 ,ParamSupOnCurve2,TolConf);
1012 //-- On ne delete pas PtrPoly1(2) ,
1013 //-- ils sont detruits enfin de fct.
1014 //-- !! Pas de return intempestif !!
1015 Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
1018 //-----------------------------------------------------------------
1019 //-- Calcul des Positions des Points sur la courbe et des
1020 //-- Transitions sur chaque borne du segment
1022 IntRes2d_Position Pos1 = IntRes2d_Middle;
1023 IntRes2d_Position Pos2 = IntRes2d_Middle;
1024 IntRes2d_Transition Trans1,Trans2;
1026 TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
1027 TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
1029 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance()) {
1030 Pos1 = IntRes2d_Head;
1032 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1033 Pos1 = IntRes2d_End;
1035 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance()) {
1036 Pos2 = IntRes2d_Head;
1038 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1039 Pos2 = IntRes2d_End;
1042 if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1043 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1045 else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1046 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1048 else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1049 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1052 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1057 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1058 == Standard_False) {
1059 TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
1060 TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
1061 IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1062 Pos2,Tan2,Norm2,Trans2,TolConf);
1064 IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
1065 ,Trans1,Trans2,Standard_False);
1066 //----------------------------------------------------------------------
1068 if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1))
1069 || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2))) {
1073 TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
1074 TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
1075 Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1077 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance()) {
1078 Pos1 = IntRes2d_Head;
1080 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1081 Pos1 = IntRes2d_End;
1083 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance()) {
1084 Pos2 = IntRes2d_Head;
1086 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1087 Pos2 = IntRes2d_End;
1091 if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1092 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1094 else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1095 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1097 else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1098 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1101 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1104 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1106 TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1107 TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1108 IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1109 Pos2,Tan2,Norm2,Trans2,TolConf);
1111 IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1112 ,Trans1,Trans2,Standard_False);
1116 Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1117 if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1118 IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1122 IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1128 //----------------------------------------------------------------------
1131 done = Standard_True;