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>
52 #include <NCollection_Handle.hxx>
54 //======================================================================
56 // Modified by skv - Tue Mar 1 14:22:09 2005 OCC8169 Begin
57 // #define NBITER_MAX_POLYGON 3
58 #define NBITER_MAX_POLYGON 10
59 // Modified by skv - Tue Mar 1 14:22:09 2005 OCC8169 End
60 #define TOL_CONF_MINI 0.0000000001
61 #define TOL_MINI 0.0000000001
63 //----------------------------------------------------------------------
69 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
71 ,const Standard_Real u
72 ,const IntRes2d_Domain& D2
74 ,const Standard_Real v
75 ,const Standard_Real TolConf
76 ,IntRes2d_IntersectionPoint& IntPt
77 ,Standard_Boolean& HeadOn1
78 ,Standard_Boolean& HeadOn2
79 ,Standard_Boolean& EndOn1
80 ,Standard_Boolean& EndOn2
81 ,Standard_Integer PosSegment);
84 //======================================================================
85 IntCurve_IntPolyPolyGen::IntCurve_IntPolyPolyGen(void) {
86 done = Standard_False;
88 //======================================================================
89 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
90 ,const IntRes2d_Domain& D1
92 ,const IntRes2d_Domain& D2
93 ,const Standard_Real TheTolConf
94 ,const Standard_Real TheTol)
97 Standard_Boolean AnErrorOccurred = Standard_False;
102 Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
103 Standard_Real DV = D2.LastParameter()-D2.FirstParameter();
104 Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
105 Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
106 Perform(C1,D1,C2,D2,TlConf,Tl,0,DU,DV);
107 //----------------------------------------------------------------------
108 //-- Traitement des points en bouts
109 //----------------------------------------------------------------------
110 Standard_Boolean HeadOn1 = Standard_False;
111 Standard_Boolean HeadOn2 = Standard_False;
112 Standard_Boolean EndOn1 = Standard_False;
113 Standard_Boolean EndOn2 = Standard_False;
115 Standard_Integer n=this->NbPoints();
118 //--------------------------------------------------------------------
119 //-- On ne rejette les points Head Head ... End End
120 //-- si ils figurent deja dans un bout de segment
121 //-- ( On ne peut pas tester les egalites sur les parametres)
122 //-- ( ces points n etant pas trouves a EpsX pres )
123 //-- PosSegment = 1 si Head Head
127 //--------------------------------------------------------------------
128 Standard_Integer PosSegment = 0;
133 IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
134 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
135 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
137 IntRes2d_Position Pos2 = this->Point(i).TransitionOfSecond().PositionOnCurve();
138 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
139 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
141 if(Pos1 == IntRes2d_Head) {
142 if(Pos2 == IntRes2d_Head) PosSegment|=1;
143 else if(Pos2 == IntRes2d_End) PosSegment|=2;
145 else if(Pos1 == IntRes2d_End) {
146 if(Pos2 == IntRes2d_Head) PosSegment|=4;
147 else if(Pos2 == IntRes2d_End) PosSegment|=8;
151 n=this->NbSegments();
153 IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
154 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
155 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
157 IntRes2d_Position Pos2 = this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
158 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
159 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
161 if(Pos1 == IntRes2d_Head) {
162 if(Pos2 == IntRes2d_Head) PosSegment|=1;
163 else if(Pos2 == IntRes2d_End) PosSegment|=2;
165 else if(Pos1 == IntRes2d_End) {
166 if(Pos2 == IntRes2d_Head) PosSegment|=4;
167 else if(Pos2 == IntRes2d_End) PosSegment|=8;
170 Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
171 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
172 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
174 Pos2 = this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
175 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
176 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
178 if(Pos1 == IntRes2d_Head) {
179 if(Pos2 == IntRes2d_Head) PosSegment|=1;
180 else if(Pos2 == IntRes2d_End) PosSegment|=2;
182 else if(Pos1 == IntRes2d_End) {
183 if(Pos2 == IntRes2d_Head) PosSegment|=4;
184 else if(Pos2 == IntRes2d_End) PosSegment|=8;
190 Standard_Real U0 = D1.FirstParameter();
191 Standard_Real U1 = D1.LastParameter();
192 Standard_Real V0 = D2.FirstParameter();
193 Standard_Real V1 = D2.LastParameter();
195 Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
196 Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
197 IntRes2d_IntersectionPoint IntPt;
199 if(D1.FirstTolerance() || D2.FirstTolerance()) {
200 if(HeadOrEndPoint(D1,C1,U0,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
203 if(D1.FirstTolerance() || D2.LastTolerance()) {
204 if(HeadOrEndPoint(D1,C1,U0,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
207 if(D1.LastTolerance() || D2.FirstTolerance()) {
208 if(HeadOrEndPoint(D1,C1,U1,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
211 if(D1.LastTolerance() || D2.LastTolerance()) {
212 if(HeadOrEndPoint(D1,C1,U1,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
215 if(AnErrorOccurred) {
216 //----------------------------------------------------------------------------------
217 //-- On a donne un point approche a la recherche du point exact, et cette recherche
219 //-- Soit le point n'existe pas, soit c'est un point en bout dont un des parameteres
220 //-- est en dehors du domaine de la courbe.
222 //-- Dans le cas contraire, on suppose que les points en bouts ont ete trouves par
223 //-- les interferences des polygones
227 v = TheProjPCur::FindParameter( C2,D1.FirstPoint(),V0,V1,EpsX2);
228 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
234 v = TheProjPCur::FindParameter( C2,D1.LastPoint(),V0,V1,EpsX2);
235 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
240 u = TheProjPCur::FindParameter( C1,D2.FirstPoint(),U0,U1,EpsX1);
242 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
247 u = TheProjPCur::FindParameter( C1,D2.LastPoint(),U0,U1,EpsX1);
249 if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
259 //======================================================================
260 //== A u t o I n t e r s e c t i o n
261 //======================================================================
262 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
263 ,const IntRes2d_Domain& D1
264 ,const Standard_Real TheTolConf
265 ,const Standard_Real TheTol)
271 Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
272 Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
273 Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
274 Perform(C1,D1,TlConf,Tl,0,DU,DU);
275 //----------------------------------------------------------------------
276 //-- Traitement des points en bouts
277 //----------------------------------------------------------------------
278 Standard_Boolean HeadOn1 = Standard_False;
279 Standard_Boolean HeadOn2 = Standard_False;
280 Standard_Boolean EndOn1 = Standard_False;
281 Standard_Boolean EndOn2 = Standard_False;
283 Standard_Integer n=this->NbPoints();
286 //--------------------------------------------------------------------
287 //-- On ne rejette les points Head Head ... End End
288 //-- si ils figurent deja dans un bout de segment
289 //-- ( On ne peut pas tester les egalites sur les parametres)
290 //-- ( ces points n etant pas trouves a EpsX pres )
291 //-- PosSegment = 1 si Head Head
295 //--------------------------------------------------------------------
296 Standard_Integer PosSegment = 0;
301 IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
302 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
303 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
305 IntRes2d_Position Pos2 = this->Point(i).TransitionOfSecond().PositionOnCurve();
306 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
307 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
309 if(Pos1 == IntRes2d_Head) {
310 if(Pos2 == IntRes2d_Head) PosSegment|=1;
311 else if(Pos2 == IntRes2d_End) PosSegment|=2;
313 else if(Pos1 == IntRes2d_End) {
314 if(Pos2 == IntRes2d_Head) PosSegment|=4;
315 else if(Pos2 == IntRes2d_End) PosSegment|=8;
319 n=this->NbSegments();
321 IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
322 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
323 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
325 IntRes2d_Position Pos2 = this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
326 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
327 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
329 if(Pos1 == IntRes2d_Head) {
330 if(Pos2 == IntRes2d_Head) PosSegment|=1;
331 else if(Pos2 == IntRes2d_End) PosSegment|=2;
333 else if(Pos1 == IntRes2d_End) {
334 if(Pos2 == IntRes2d_Head) PosSegment|=4;
335 else if(Pos2 == IntRes2d_End) PosSegment|=8;
338 Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
339 if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
340 else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
342 Pos2 = this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
343 if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
344 else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
346 if(Pos1 == IntRes2d_Head) {
347 if(Pos2 == IntRes2d_Head) PosSegment|=1;
348 else if(Pos2 == IntRes2d_End) PosSegment|=2;
350 else if(Pos1 == IntRes2d_End) {
351 if(Pos2 == IntRes2d_Head) PosSegment|=4;
352 else if(Pos2 == IntRes2d_End) PosSegment|=8;
356 //======================================================================
360 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
361 ,const IntRes2d_Domain& D1
362 ,const Standard_Real TolConf
363 ,const Standard_Real Tol
364 ,const Standard_Integer NbIter
365 ,const Standard_Real /*DeltaU*/
366 ,const Standard_Real) {
368 gp_Vec2d Tan1,Tan2,Norm1,Norm2;
370 Standard_Integer nbsamples;
371 done = Standard_False;
372 Standard_Boolean AnErrorOccurred = Standard_False;
375 nbsamples = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
377 if(NbIter>3 || (NbIter>2 && nbsamples>100)) return;
379 nbsamples*=2; //--- On prend systematiquement 2 fois plus de points que
380 //-- sur une courbe normale.
381 //-- Les courbes auto-intersectantes donne souvent des
382 //-- polygones assez loin de la courbe a parametre ct.
385 nbsamples=(3*(nbsamples*NbIter))/2;
387 IntCurve_ThePolygon2d Poly1(C1,nbsamples,D1,Tol);
388 if(!Poly1.AutoIntersectionIsPossible()) {
389 done = Standard_True;
393 //----------------------------------------------------------------------
394 //-- Si la deflection est inferieure a la Tolerance de Confusion
395 //-- Alors la deflection du polygone est fixee a TolConf
396 //-- (Detection des Zones de Tangence)
397 //----------------------------------------------------------------------
398 if(Poly1.DeflectionOverEstimation() < TolConf) {
399 Poly1.SetDeflectionOverEstimation(TolConf);
402 Intf_InterferencePolygon2d InterPP(Poly1);
403 IntCurve_ExactIntersectionPoint EIP(C1,C1,TolConf);
406 //----------------------------------------------------------------------
407 //-- Traitement des SectionPoint
408 //----------------------------------------------------------------------
409 Standard_Integer Nbsp = InterPP.NbSectionPoints();
412 //-- ---------------------------------------------------------------------
413 //-- tri tri tri tri tri tri tri tri tri tri tri tri tri tri
415 Standard_Integer* TriIndex = new Standard_Integer [Nbsp+1];
416 Standard_Integer* PtrSegIndex1 = new Standard_Integer [Nbsp+1];
417 Standard_Integer* PtrSegIndex2 = new Standard_Integer [Nbsp+1];
418 Standard_Boolean Triok;
419 Standard_Integer SegIndex1,SegIndex2,SegIndex_1,SegIndex_2;
420 // Standard_Real ParamOn1,ParamOn2,ParamOn_1,ParamOn_2;
421 Standard_Real ParamOn1,ParamOn2;
424 for( i=1;i<=Nbsp;i++) {
426 const Intf_SectionPoint& SPnt1 = InterPP.PntValue(i);
427 SPnt1.InfoFirst(Type,PtrSegIndex1[i],ParamOn1);
428 SPnt1.InfoSecond(Type,PtrSegIndex2[i],ParamOn2);
435 for(Standard_Integer tr=1;tr<Nbsp;tr++) {
436 SegIndex1=PtrSegIndex1[TriIndex[tr]];
437 SegIndex_1=PtrSegIndex1[TriIndex[tr+1]];
439 SegIndex2=PtrSegIndex2[TriIndex[tr]];
440 SegIndex_2=PtrSegIndex2[TriIndex[tr+1]];
442 if(SegIndex1 > SegIndex_1) {
443 Standard_Integer q=TriIndex[tr];
444 TriIndex[tr]=TriIndex[tr+1];
446 Triok=Standard_False;
448 else if(SegIndex1 == SegIndex_1) {
449 if(SegIndex2 > SegIndex_2) {
450 Standard_Integer q=TriIndex[tr];
451 TriIndex[tr]=TriIndex[tr+1];
453 Triok=Standard_False;
458 while(Triok==Standard_False);
460 //-- supression des doublons Si Si !
461 for(i=1; i<Nbsp;i++) {
462 if( (PtrSegIndex1[TriIndex[i]] == PtrSegIndex1[TriIndex[i+1]])
463 && (PtrSegIndex2[TriIndex[i]] == PtrSegIndex2[TriIndex[i+1]])) {
469 Standard_Integer Nelarg=(Poly1.NbSegments()/20);
470 if(Nelarg<2) Nelarg=2;
472 for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
474 const Intf_SectionPoint& SPnt = InterPP.PntValue(TriIndex[sp]);
476 SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
477 SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
479 if(Abs(SegIndex1-SegIndex2)>1) {
481 EIP.Perform(Poly1,Poly1,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
482 AnErrorOccurred = EIP.AnErrorOccurred();
483 if(EIP.NbRoots()==0) {
484 //-- On supprime tous les segments voisins
485 for(Standard_Integer k=sp+1;k<=Nbsp;k++) {
486 Standard_Integer kk=TriIndex[k];
487 // modified by OFV OCC2502 Tue Apr 29 15:07:45 2003 .Begin
488 // --- avoid negative indicies as well as in outer done
490 if( Abs(SegIndex1-PtrSegIndex1[kk])< Nelarg
491 && Abs(SegIndex2-PtrSegIndex2[kk])< Nelarg) {
495 // modified by OFV OCC2502 Tue Apr 29 15:11:34 2003 .End
498 else if(EIP.NbRoots()>=1) {
499 //--------------------------------------------------------------------
500 //-- On verifie que le point trouve est bien une racine
501 //--------------------------------------------------------------------
504 TheCurveTool::D1(C1,U,P1,Tan1);
505 TheCurveTool::D1(C1,V,P2,Tan2);
506 Standard_Real Dist = P1.Distance(P2);
507 Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
509 if(Abs(U-V)<=EpsX1) {
510 //-----------------------------------------
511 //-- Solution non valide
512 //-- Les maths ont du converger vers une
513 //-- solution triviale ( point U = V )
514 //-----------------------------------------
518 //-----------------------------------------------------------------
519 //-- On verifie que le point (u,v) n existe pas deja
521 done = Standard_True;
522 Standard_Integer nbp=NbPoints();
524 for(Standard_Integer p=1; p<=nbp; p++) {
525 const IntRes2d_IntersectionPoint& P=Point(p);
526 if(Abs(U-P.ParamOnFirst()) <= EpsX1) {
527 if(Abs(V-P.ParamOnSecond()) <= EpsX1) {
528 Dist = TolConf+1.0; p+=nbp;
533 if(Dist <= TolConf) { //-- Ou le point est deja present
534 IntRes2d_Position Pos1 = IntRes2d_Middle;
535 IntRes2d_Position Pos2 = IntRes2d_Middle;
536 IntRes2d_Transition Trans1,Trans2;
537 //-----------------------------------------------------------------
538 //-- Calcul des Positions des Points sur la courbe
540 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())
541 Pos1 = IntRes2d_Head;
542 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance())
545 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())
546 Pos2 = IntRes2d_Head;
547 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance())
549 //-----------------------------------------------------------------
550 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
552 ,TolConf) == Standard_False) {
553 TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
554 TheCurveTool::D2(C1,V,P2,Tan2,Norm2);
555 IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
556 ,Pos2,Tan2,Norm2,Trans2
559 IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
567 delete [] PtrSegIndex1;
568 delete [] PtrSegIndex2;
570 done = Standard_True;
574 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
576 ,const Standard_Real tu
577 ,const IntRes2d_Domain& D2
579 ,const Standard_Real tv
580 ,const Standard_Real TolConf
581 ,IntRes2d_IntersectionPoint& IntPt
582 ,Standard_Boolean& HeadOn1
583 ,Standard_Boolean& HeadOn2
584 ,Standard_Boolean& EndOn1
585 ,Standard_Boolean& EndOn2
586 ,Standard_Integer PosSegment) {
588 gp_Pnt2d P1,P2,SP1,SP2;
589 gp_Vec2d T1,T2,N1,N2;
592 Standard_Real svu = u;
593 Standard_Real svv = v;
595 TheCurveTool::D1(C1,u,P1,T1);
596 TheCurveTool::D1(C2,v,P2,T2);
598 IntRes2d_Position Pos1 = IntRes2d_Middle;
599 IntRes2d_Position Pos2 = IntRes2d_Middle;
600 IntRes2d_Transition Trans1,Trans2;
602 //----------------------------------------------------------------------
603 //-- Head On 1 : Head1 <-> P2
604 if(P2.Distance(D1.FirstPoint())<=D1.FirstTolerance()) {
605 Pos1 = IntRes2d_Head;
606 HeadOn1 = Standard_True;
607 SP1 = D1.FirstPoint();
608 u = D1.FirstParameter();
610 //----------------------------------------------------------------------
611 //-- End On 1 : End1 <-> P2
612 else if(P2.Distance(D1.LastPoint())<=D1.LastTolerance()) {
614 EndOn1 = Standard_True;
615 SP1 = D1.LastPoint();
616 u = D1.LastParameter();
620 //----------------------------------------------------------------------
621 //-- Head On 2 : Head2 <-> P1
622 else if(P1.Distance(D2.FirstPoint())<=D2.FirstTolerance()) {
623 Pos2 = IntRes2d_Head;
624 HeadOn2 = Standard_True;
625 SP2 = D2.FirstPoint();
626 v = D2.FirstParameter();
628 //----------------------------------------------------------------------
629 //-- End On 2 : End2 <-> P1
630 else if(P1.Distance(D2.LastPoint())<=D2.LastTolerance()) {
632 EndOn2 = Standard_True;
633 SP2 = D2.LastPoint();
634 v = D2.LastParameter();
637 Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
638 Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
641 if((Pos1 != IntRes2d_Middle)||(Pos2 != IntRes2d_Middle)) {
642 if(Pos1 == IntRes2d_Middle) {
643 if(Abs(u-D1.FirstParameter()) <= EpsX1) {
644 Pos1 = IntRes2d_Head;
645 P1 = D1.FirstPoint();
646 HeadOn1 = Standard_True;
648 else if(Abs(u-D1.LastParameter()) <= EpsX1) {
651 EndOn1 = Standard_True;
659 if(Pos2 == IntRes2d_Middle) {
660 if(Abs(v-D2.FirstParameter()) <= EpsX2) {
661 Pos2 = IntRes2d_Head;
662 HeadOn2 = Standard_True;
663 P2 = D2.FirstPoint();
664 if(Pos1 != IntRes2d_Middle) {
665 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
671 else if(Abs(v-D2.LastParameter()) <= EpsX2) {
673 EndOn2 = Standard_True;
675 if(Pos1 != IntRes2d_Middle) {
676 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
685 //--------------------------------------------------------------------
686 //-- On Teste si un point de bout de segment a deja ces trnasitions
687 //-- Si Oui, on ne cree pas de nouveau point
689 //-- PosSegment = 1 si Head Head
693 //--------------------------------------------------------------------
694 if(Pos1 == IntRes2d_Head) {
695 if((Pos2 == IntRes2d_Head)&&(PosSegment & 1)) return(Standard_False);
696 if((Pos2 == IntRes2d_End )&&(PosSegment & 2)) return(Standard_False);
698 else if(Pos1 == IntRes2d_End) {
699 if((Pos2 == IntRes2d_Head)&&(PosSegment & 4)) return(Standard_False);
700 if((Pos2 == IntRes2d_End )&&(PosSegment & 8)) return(Standard_False);
704 if(IntImpParGen::DetermineTransition( Pos1,T1,Trans1,Pos2,T2,Trans2,TolConf)
706 TheCurveTool::D2(C1,svu,P1,T1,N1);
707 TheCurveTool::D2(C2,svv,P2,T2,N2);
708 IntImpParGen::DetermineTransition(Pos1,T1,N1,Trans1,
709 Pos2,T2,N2,Trans2,TolConf);
711 IntPt.SetValues(P1,u,v,Trans1,Trans2,Standard_False);
712 return(Standard_True);
715 return(Standard_False);
724 //======================================================================
725 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
726 ,const IntRes2d_Domain& D1
728 ,const IntRes2d_Domain& D2
729 ,const Standard_Real TolConf
730 ,const Standard_Real Tol
731 ,const Standard_Integer NbIter
732 ,const Standard_Real DeltaU
733 ,const Standard_Real DeltaV) {
735 Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
736 done = Standard_False;
738 if(NbIter>NBITER_MAX_POLYGON) return;
740 nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
742 //// modified by jgv, 5.12.02 for OCC935 ////
743 if (NbIter == 0) // first time
745 if (nbsamplesOnC1 < 20)
750 nbsamplesOnC1=(5*(nbsamplesOnC1*NbIter))/4;
752 /////////////////////////////////////////////
754 nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
756 //// modified by jgv, 5.12.02 for OCC935 ////
757 if (NbIter == 0) // first time
759 if (nbsamplesOnC2 < 20)
764 nbsamplesOnC2=(5*(nbsamplesOnC2*NbIter))/4;
766 /////////////////////////////////////////////
769 NCollection_Handle<IntCurve_ThePolygon2d> aPoly1 ,aPoly2;
770 if(nbsamplesOnC2 > nbsamplesOnC1) {
771 aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
772 if(aPoly1->DeflectionOverEstimation() < TolConf) {
773 aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
776 aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol,aPoly1->Bounding());
777 aPoly1->SetDeflectionOverEstimation( aPoly2->DeflectionOverEstimation()
778 + aPoly1->DeflectionOverEstimation());
779 aPoly1->ComputeWithBox(C1,aPoly2->Bounding());
783 aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
784 if(aPoly2->DeflectionOverEstimation() < TolConf) {
785 aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
788 aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol,aPoly2->Bounding());
789 aPoly2->SetDeflectionOverEstimation( aPoly2->DeflectionOverEstimation()
790 + aPoly1->DeflectionOverEstimation());
791 aPoly2->ComputeWithBox(C2,aPoly1->Bounding());
794 //----------------------------------------------------------------------
795 //-- Si la deflection est inferieure a la Tolerance de Confusion
796 //-- Alors la deflection du polygone est fixee a TolConf
797 //-- (Detection des Zones de Tangence)
798 //----------------------------------------------------------------------
800 if(aPoly1->DeflectionOverEstimation() < TolConf) {
801 aPoly1->SetDeflectionOverEstimation(TolConf);
803 if(aPoly2->DeflectionOverEstimation() < TolConf) {
804 aPoly2->SetDeflectionOverEstimation(TolConf);
806 //for case when a few polygon points were replaced by line
807 //if exact solution was not found
808 //then search of precise solution will be repeat
809 //for polygon conatins all initial points
810 //secondary search will be performed only for case when initial points
812 Standard_Boolean isFullRepresentation = ( aPoly1->NbSegments() == nbsamplesOnC1 &&
813 aPoly2->NbSegments() == nbsamplesOnC2 );
815 if( !findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
816 DeltaU, DeltaV, *aPoly1, *aPoly2, isFullRepresentation ) && !isFullRepresentation )
818 if(aPoly1->NbSegments() < nbsamplesOnC1)
820 aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
822 if(aPoly2->NbSegments() < nbsamplesOnC2)
824 aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
827 findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
828 DeltaU, DeltaV, *aPoly1, *aPoly2,
833 done = Standard_True;
836 //======================================================================
838 //======================================================================
840 Standard_Boolean IntCurve_IntPolyPolyGen::findIntersect(
842 const IntRes2d_Domain& D1,
844 const IntRes2d_Domain& D2,
845 const Standard_Real TolConf,
846 const Standard_Real Tol,
847 const Standard_Integer NbIter,
848 const Standard_Real DeltaU,
849 const Standard_Real DeltaV,
850 const IntCurve_ThePolygon2d& thePoly1,
851 const IntCurve_ThePolygon2d& thePoly2,
852 Standard_Boolean isFullPolygon )
855 gp_Vec2d Tan1,Tan2,Norm1,Norm2;
857 Intf_InterferencePolygon2d InterPP(thePoly1,thePoly2);
858 IntCurve_ExactIntersectionPoint EIP(C1,C2,TolConf);
861 //----------------------------------------------------------------------
862 //-- Traitement des SectionPoint
863 //----------------------------------------------------------------------
864 Standard_Integer Nbsp = InterPP.NbSectionPoints();
866 for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
867 const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
868 Standard_Integer SegIndex1,SegIndex2;
869 Standard_Real ParamOn1,ParamOn2;
872 SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
873 SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
874 EIP.Perform(thePoly1,thePoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
875 //AnErrorOccurred = EIP.AnErrorOccurred();
876 if( !EIP.NbRoots() && !isFullPolygon)
877 return Standard_False;
880 //--------------------------------------------------------------------
881 //-- On verifie que le point trouve est bien une racine
882 //--------------------------------------------------------------------
884 TheCurveTool::D1(C1,U,P1,Tan1);
885 TheCurveTool::D1(C2,V,P2,Tan2);
886 Standard_Real Dist = P1.Distance(P2);
887 //-----------------------------------------------------------------
888 //-- On verifie que le point (u,v) n existe pas deja
890 done = Standard_True;
891 Standard_Integer nbp=NbPoints();
892 Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
893 Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
895 for(Standard_Integer p=1; p<=nbp; p++) {
896 const IntRes2d_IntersectionPoint& P=Point(p);
897 if(Abs(U-P.ParamOnFirst()) <= EpsX1) {
898 if(Abs(V-P.ParamOnSecond()) <= EpsX2) {
899 Dist = TolConf+1.0; p+=nbp;
904 if(Dist <= TolConf) { //-- Ou le point est deja present
905 IntRes2d_Position Pos1 = IntRes2d_Middle;
906 IntRes2d_Position Pos2 = IntRes2d_Middle;
907 IntRes2d_Transition Trans1,Trans2;
908 //-----------------------------------------------------------------
909 //-- Calcul des Positions des Points sur la courbe
911 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())
912 Pos1 = IntRes2d_Head;
913 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance())
916 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())
917 Pos2 = IntRes2d_Head;
918 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance())
920 //-----------------------------------------------------------------
921 //-- Calcul des Transitions (Voir IntImpParGen.cxx)
923 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
925 ,TolConf)==Standard_False) {
927 TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
928 TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
929 IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
930 ,Pos2,Tan2,Norm2,Trans2
933 IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
938 //----------------------------------------------------------------------
939 //-- Traitement des TangentZone
940 //----------------------------------------------------------------------
941 Standard_Integer Nbtz = InterPP.NbTangentZones();
942 for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
943 Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
944 //====================================================================
945 //== Recherche du premier et du dernier point dans la zone de tg.
946 //====================================================================
947 Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
948 Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
949 // Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
950 Standard_Integer SegIndex1onP1,SegIndex1onP2;
952 Standard_Real ParamOnLine;
953 Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
954 ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
955 ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
956 for(Standard_Integer qq=1;qq<=NbPnts;qq++) {
957 const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
958 //====================================================================
959 //== On discretise sur les zones de tangence
962 //== Deflection < Tolerance
963 //== OU Echantillon < EpsX (normalement la premiere condition est
965 //====================================================================
966 // Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
967 Standard_Real _PolyUInf,_PolyVInf;
969 SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
970 if(SegIndex1onP1 > thePoly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
971 if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
972 _PolyUInf = thePoly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
974 SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
975 if(SegIndex1onP2 > thePoly2.NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
976 if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
977 _PolyVInf = thePoly2.ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
979 //----------------------------------------------------------------------
981 if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
982 if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
984 if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
985 if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
989 PolyUInf= ParamInfOnCurve1;
990 PolyUSup= ParamSupOnCurve1;
991 PolyVInf= ParamInfOnCurve2;
992 PolyVSup= ParamSupOnCurve2;
994 TheCurveTool::D0(C1,PolyUInf,P1);
995 TheCurveTool::D0(C2,PolyVInf,P2);
996 Standard_Real distmemesens = P1.SquareDistance(P2);
997 TheCurveTool::D0(C2,PolyVSup,P2);
998 Standard_Real distdiffsens = P1.SquareDistance(P2);
999 if(distmemesens > distdiffsens) {
1000 Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
1005 if( ( (thePoly1.DeflectionOverEstimation() > TolConf)
1006 ||(thePoly2.DeflectionOverEstimation() > TolConf))
1007 &&(NbIter<NBITER_MAX_POLYGON)) {
1009 IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
1010 ,ParamInfOnCurve1,TolConf
1011 ,TheCurveTool::Value(C1,ParamSupOnCurve1)
1012 ,ParamSupOnCurve1,TolConf);
1013 IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
1014 ,ParamInfOnCurve2,TolConf
1015 ,TheCurveTool::Value(C2,ParamSupOnCurve2)
1016 ,ParamSupOnCurve2,TolConf);
1017 //-- On ne delete pas thePoly1(2) ,
1018 //-- ils sont detruits enfin de fct.
1019 //-- !! Pas de return intempestif !!
1020 Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
1023 //-----------------------------------------------------------------
1024 //-- Calcul des Positions des Points sur la courbe et des
1025 //-- Transitions sur chaque borne du segment
1027 IntRes2d_Position Pos1 = IntRes2d_Middle;
1028 IntRes2d_Position Pos2 = IntRes2d_Middle;
1029 IntRes2d_Transition Trans1,Trans2;
1031 TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
1032 TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
1034 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance()) {
1035 Pos1 = IntRes2d_Head;
1037 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1038 Pos1 = IntRes2d_End;
1040 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance()) {
1041 Pos2 = IntRes2d_Head;
1043 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1044 Pos2 = IntRes2d_End;
1047 if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1048 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1050 else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1051 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1053 else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1054 PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1057 PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1062 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1063 == Standard_False) {
1064 TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
1065 TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
1066 IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1067 Pos2,Tan2,Norm2,Trans2,TolConf);
1069 IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
1070 ,Trans1,Trans2,Standard_False);
1071 //----------------------------------------------------------------------
1073 if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1))
1074 || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2))) {
1078 TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
1079 TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
1080 Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1082 if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance()) {
1083 Pos1 = IntRes2d_Head;
1085 else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1086 Pos1 = IntRes2d_End;
1088 if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance()) {
1089 Pos2 = IntRes2d_Head;
1091 else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1092 Pos2 = IntRes2d_End;
1096 if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1097 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1099 else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1100 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1102 else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1103 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1106 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1109 if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1111 TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1112 TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1113 IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1114 Pos2,Tan2,Norm2,Trans2,TolConf);
1116 IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1117 ,Trans1,Trans2,Standard_False);
1121 Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1122 if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1123 IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1127 IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1133 return Standard_True;