src/livarot/PathCutting.cpp

   1 /*
   2  *  PathCutting.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on someday in 2004.
   6  *  public domain
   7  *
   8  *  Additional Code by Authors:
   9  *   Richard Hughes <cyreve@users.sf.net>
  10  *
  11  *  Copyright (C) 2005 Richard Hughes
  12  *
  13  *  Released under GNU GPL, read the file 'COPYING' for more information
  14  */
  15
  16 #include <cstring>
  17 #include <string>
  18 #include <cstdio>
  19 #include <typeinfo>
  20 #include "Path.h"
  21 #include "style.h"
  22 #include "livarot/path-description.h"
  23 #include "libnr/nr-point-matrix-ops.h"
  24 #include "libnr/nr-convert2geom.h"
  25 #include <2geom/pathvector.h>
  26 #include <2geom/point.h>
  27 #include <2geom/matrix.h>
  28 #include <2geom/sbasis-to-bezier.h>
  29 #include <2geom/curves.h>
  30 #include "../display/canvas-bpath.h"
  31 #include "helper/geom-curves.h"
  32 #include "helper/geom.h"
  33
  34 #include "svg/svg.h"
  35
  36 void  Path::DashPolyline(float head,float tail,float body,int nbD,float *dashs,bool stPlain,float stOffset)
  37 {
  38   if ( nbD <= 0 || body <= 0.0001 ) return; // pas de tirets, en fait
  39
  40   std::vector<path_lineto> orig_pts = pts;
  41   pts.clear();
  42
  43   int       lastMI=-1;
  44   int curP = 0;
  45   int lastMP = -1;
  46
  47   for (int i = 0; i < int(orig_pts.size()); i++) {
  48     if ( orig_pts[curP].isMoveTo == polyline_moveto ) {
  49       if ( lastMI >= 0 && lastMI < i-1 ) { // au moins 2 points
  50         DashSubPath(i-lastMI,lastMP, orig_pts, head,tail,body,nbD,dashs,stPlain,stOffset);
  51       }
  52       lastMI=i;
  53       lastMP=curP;
  54     }
  55     curP++;
  56   }
  57   if ( lastMI >= 0 && lastMI < int(orig_pts.size()) - 1 ) {
  58     DashSubPath(orig_pts.size() - lastMI, lastMP, orig_pts, head, tail, body, nbD, dashs, stPlain, stOffset);
  59   }
  60 }
  61
  62 void  Path::DashPolylineFromStyle(SPStyle *style, float scale, float min_len)
  63 {
  64     if (style->stroke_dash.n_dash) {
  65
  66         double dlen = 0.0;
  67         for (int i = 0; i < style->stroke_dash.n_dash; i++) {
  68             dlen += style->stroke_dash.dash[i] * scale;
  69         }
  70         if (dlen >= min_len) {
  71             NRVpathDash dash;
  72             dash.offset = style->stroke_dash.offset * scale;
  73             dash.n_dash = style->stroke_dash.n_dash;
  74             dash.dash = g_new(double, dash.n_dash);
  75             for (int i = 0; i < dash.n_dash; i++) {
  76                 dash.dash[i] = style->stroke_dash.dash[i] * scale;
  77             }
  78             int    nbD=dash.n_dash;
  79             float  *dashs=(float*)malloc((nbD+1)*sizeof(float));
  80             while ( dash.offset >= dlen ) dash.offset-=dlen;
  81             dashs[0]=dash.dash[0];
  82             for (int i=1; i<nbD; i++) {
  83                 dashs[i]=dashs[i-1]+dash.dash[i];
  84             }
  85             // modulo dlen
  86             this->DashPolyline(0.0, 0.0, dlen, nbD, dashs, true, dash.offset);
  87             free(dashs);
  88             g_free(dash.dash);
  89         }
  90     }
  91 }
  92
  93
  94 void Path::DashSubPath(int spL, int spP, std::vector<path_lineto> const &orig_pts, float head,float tail,float body,int nbD,float *dashs,bool stPlain,float stOffset)
  95 {
  96   if ( spL <= 0 || spP == -1 ) return;
  97
  98   double      totLength=0;
  99   Geom::Point   lastP;
 100   lastP = orig_pts[spP].p;
 101   for (int i=1;i<spL;i++) {
 102     Geom::Point const n = orig_pts[spP + i].p;
 103     Geom::Point d=n-lastP;
 104     double    nl=Geom::L2(d);
 105     if ( nl > 0.0001 ) {
 106       totLength+=nl;
 107       lastP=n;
 108     }
 109   }
 110
 111   if ( totLength <= head+tail ) return; // tout mange par la tete et la queue
 112
 113   double    curLength=0;
 114   double    dashPos=0;
 115   int       dashInd=0;
 116   bool      dashPlain=false;
 117   double    lastT=0;
 118   int       lastPiece=-1;
 119   lastP = orig_pts[spP].p;
 120   for (int i=1;i<spL;i++) {
 121     Geom::Point   n;
 122     int         nPiece=-1;
 123     double      nT=0;
 124     if ( back ) {
 125       n = orig_pts[spP + i].p;
 126       nPiece = orig_pts[spP + i].piece;
 127       nT = orig_pts[spP + i].t;
 128     } else {
 129       n = orig_pts[spP + i].p;
 130     }
 131     Geom::Point d=n-lastP;
 132     double    nl=Geom::L2(d);
 133     if ( nl > 0.0001 ) {
 134       double   stLength=curLength;
 135       double   enLength=curLength+nl;
 136       // couper les bouts en trop
 137       if ( curLength <= head && curLength+nl > head ) {
 138         nl-=head-curLength;
 139         curLength=head;
 140         dashInd=0;
 141         dashPos=stOffset;
 142         bool nPlain=stPlain;
 143         while ( dashs[dashInd] < stOffset ) {
 144           dashInd++;
 145           nPlain=!(nPlain);
 146           if ( dashInd >= nbD ) {
 147             dashPos=0;
 148             dashInd=0;
 149             break;
 150           }
 151         }
 152         if ( nPlain == true && dashPlain == false ) {
 153           Geom::Point  p=(enLength-curLength)*lastP+(curLength-stLength)*n;
 154           p/=(enLength-stLength);
 155           if ( back ) {
 156             double pT=0;
 157             if ( nPiece == lastPiece ) {
 158               pT=(lastT*(enLength-curLength)+nT*(curLength-stLength))/(enLength-stLength);
 159             } else {
 160               pT=(nPiece*(curLength-stLength))/(enLength-stLength);
 161             }
 162             AddPoint(p,nPiece,pT,true);
 163           } else {
 164             AddPoint(p,true);
 165           }
 166         } else if ( nPlain == false && dashPlain == true ) {
 167         }
 168         dashPlain=nPlain;
 169       }
 170       // faire les tirets
 171       if ( curLength >= head /*&& curLength+nl <= totLength-tail*/ ) {
 172         while ( curLength <= totLength-tail && nl > 0 ) {
 173           if ( enLength <= totLength-tail ) nl=enLength-curLength; else nl=totLength-tail-curLength;
 174           double  leftInDash=body-dashPos;
 175           if ( dashInd < nbD ) {
 176             leftInDash=dashs[dashInd]-dashPos;
 177           }
 178           if ( leftInDash <= nl ) {
 179             bool nPlain=false;
 180             if ( dashInd < nbD ) {
 181               dashPos=dashs[dashInd];
 182               dashInd++;
 183               if ( dashPlain ) nPlain=false; else nPlain=true;
 184             } else {
 185               dashInd=0;
 186               dashPos=0;
 187               //nPlain=stPlain;
 188               nPlain=dashPlain;
 189             }
 190             if ( nPlain == true && dashPlain == false ) {
 191               Geom::Point  p=(enLength-curLength-leftInDash)*lastP+(curLength+leftInDash-stLength)*n;
 192               p/=(enLength-stLength);
 193               if ( back ) {
 194                 double pT=0;
 195                 if ( nPiece == lastPiece ) {
 196                   pT=(lastT*(enLength-curLength-leftInDash)+nT*(curLength+leftInDash-stLength))/(enLength-stLength);
 197                 } else {
 198                   pT=(nPiece*(curLength+leftInDash-stLength))/(enLength-stLength);
 199                 }
 200                 AddPoint(p,nPiece,pT,true);
 201               } else {
 202                 AddPoint(p,true);
 203               }
 204             } else if ( nPlain == false && dashPlain == true ) {
 205               Geom::Point  p=(enLength-curLength-leftInDash)*lastP+(curLength+leftInDash-stLength)*n;
 206               p/=(enLength-stLength);
 207               if ( back ) {
 208                 double pT=0;
 209                 if ( nPiece == lastPiece ) {
 210                   pT=(lastT*(enLength-curLength-leftInDash)+nT*(curLength+leftInDash-stLength))/(enLength-stLength);
 211                 } else {
 212                   pT=(nPiece*(curLength+leftInDash-stLength))/(enLength-stLength);
 213                 }
 214                 AddPoint(p,nPiece,pT,false);
 215               } else {
 216                 AddPoint(p,false);
 217               }
 218             }
 219             dashPlain=nPlain;
 220
 221             curLength+=leftInDash;
 222             nl-=leftInDash;
 223           } else {
 224             dashPos+=nl;
 225             curLength+=nl;
 226             nl=0;
 227           }
 228         }
 229         if ( dashPlain ) {
 230           if ( back ) {
 231             AddPoint(n,nPiece,nT,false);
 232           } else {
 233             AddPoint(n,false);
 234           }
 235         }
 236         nl=enLength-curLength;
 237       }
 238       if ( curLength <= totLength-tail && curLength+nl > totLength-tail ) {
 239         nl=totLength-tail-curLength;
 240         dashInd=0;
 241         dashPos=0;
 242         bool nPlain=false;
 243         if ( nPlain == true && dashPlain == false ) {
 244         } else if ( nPlain == false && dashPlain == true ) {
 245           Geom::Point  p=(enLength-curLength)*lastP+(curLength-stLength)*n;
 246           p/=(enLength-stLength);
 247           if ( back ) {
 248             double pT=0;
 249             if ( nPiece == lastPiece ) {
 250               pT=(lastT*(enLength-curLength)+nT*(curLength-stLength))/(enLength-stLength);
 251             } else {
 252               pT=(nPiece*(curLength-stLength))/(enLength-stLength);
 253             }
 254             AddPoint(p,nPiece,pT,false);
 255           } else {
 256             AddPoint(p,false);
 257           }
 258         }
 259         dashPlain=nPlain;
 260       }
 261       // continuer
 262       curLength=enLength;
 263       lastP=n;
 264       lastPiece=nPiece;
 265       lastT=nT;
 266     }
 267   }
 268 }
 269
 270 Geom::PathVector *
 271 Path::MakePathVector()
 272 {
 273     Geom::PathVector *pv = new Geom::PathVector();
 274     Geom::Path * currentpath = NULL;
 275
 276     Geom::Point   lastP,bezSt,bezEn;
 277     int         bezNb=0;
 278     for (int i=0;i<int(descr_cmd.size());i++) {
 279         int const typ = descr_cmd[i]->getType();
 280         switch ( typ ) {
 281             case descr_close:
 282             {
 283                 currentpath->close(true);
 284             }
 285             break;
 286
 287             case descr_lineto:
 288             {
 289                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 290                 currentpath->appendNew<Geom::LineSegment>(Geom::Point(nData->p[0], nData->p[1]));
 291                 lastP = nData->p;
 292             }
 293             break;
 294
 295             case descr_moveto:
 296             {
 297                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 298                 pv->push_back(Geom::Path());
 299                 currentpath = &pv->back();
 300                 currentpath->start(Geom::Point(nData->p[0], nData->p[1]));
 301                 lastP = nData->p;
 302             }
 303             break;
 304
 305             case descr_arcto:
 306             {
 307                 /* TODO: add testcase for this descr_arcto case */
 308                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 309                 currentpath->appendNew<Geom::SVGEllipticalArc>( nData->rx, nData->ry, nData->angle, nData->large, !nData->clockwise, nData->p );
 310                 lastP = nData->p;
 311             }
 312             break;
 313
 314             case descr_cubicto:
 315             {
 316                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 317                 gdouble x1=lastP[0]+0.333333*nData->start[0];
 318                 gdouble y1=lastP[1]+0.333333*nData->start[1];
 319                 gdouble x2=nData->p[0]-0.333333*nData->end[0];
 320                 gdouble y2=nData->p[1]-0.333333*nData->end[1];
 321                 gdouble x3=nData->p[0];
 322                 gdouble y3=nData->p[1];
 323                 currentpath->appendNew<Geom::CubicBezier>( Geom::Point(x1,y1) , Geom::Point(x2,y2) , Geom::Point(x3,y3) );
 324                 lastP = nData->p;
 325             }
 326             break;
 327
 328             case descr_bezierto:
 329             {
 330                 PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 331                 if ( nData->nb <= 0 ) {
 332                     currentpath->appendNew<Geom::LineSegment>( Geom::Point(nData->p[0], nData->p[1]) );
 333                     bezNb=0;
 334                 } else if ( nData->nb == 1 ){
 335                     PathDescrIntermBezierTo *iData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i+1]);
 336                     gdouble x1=0.333333*(lastP[0]+2*iData->p[0]);
 337                     gdouble y1=0.333333*(lastP[1]+2*iData->p[1]);
 338                     gdouble x2=0.333333*(nData->p[0]+2*iData->p[0]);
 339                     gdouble y2=0.333333*(nData->p[1]+2*iData->p[1]);
 340                     gdouble x3=nData->p[0];
 341                     gdouble y3=nData->p[1];
 342                     currentpath->appendNew<Geom::CubicBezier>( Geom::Point(x1,y1) , Geom::Point(x2,y2) , Geom::Point(x3,y3) );
 343                     bezNb=0;
 344                 } else {
 345                     bezSt = 2*lastP-nData->p;
 346                     bezEn = nData->p;
 347                     bezNb = nData->nb;
 348                 }
 349                 lastP = nData->p;
 350             }
 351             break;
 352
 353             case descr_interm_bezier:
 354             {
 355                 if ( bezNb > 0 ) {
 356                     PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
 357                     Geom::Point p_m=nData->p,p_s=0.5*(bezSt+p_m),p_e;
 358                     if ( bezNb > 1 ) {
 359                         PathDescrIntermBezierTo *iData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i+1]);
 360                         p_e=0.5*(p_m+iData->p);
 361                     } else {
 362                         p_e=bezEn;
 363                     }
 364
 365                     Geom::Point  cp1=0.333333*(p_s+2*p_m),cp2=0.333333*(2*p_m+p_e);
 366                     gdouble x1=cp1[0];
 367                     gdouble y1=cp1[1];
 368                     gdouble x2=cp2[0];
 369                     gdouble y2=cp2[1];
 370                     gdouble x3=p_e[0];
 371                     gdouble y3=p_e[1];
 372                     currentpath->appendNew<Geom::CubicBezier>( Geom::Point(x1,y1) , Geom::Point(x2,y2) , Geom::Point(x3,y3) );
 373
 374                     bezNb--;
 375                 }
 376             }
 377             break;
 378         }
 379     }
 380
 381     return pv;
 382 }
 383
 384 void  Path::AddCurve(Geom::Curve const &c)
 385 {
 386     if( is_straight_curve(c) )
 387     {
 388         LineTo( c.finalPoint() );
 389     }
 390     /*
 391     else if(Geom::QuadraticBezier const *quadratic_bezier = dynamic_cast<Geom::QuadraticBezier const  *>(c)) {
 392         ...
 393     }
 394     */
 395     else if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const *>(&c)) {
 396         Geom::Point tmp = (*cubic_bezier)[3];
 397         Geom::Point tms = 3 * ((*cubic_bezier)[1] - (*cubic_bezier)[0]);
 398         Geom::Point tme = 3 * ((*cubic_bezier)[3] - (*cubic_bezier)[2]);
 399         CubicTo (tmp, tms, tme);
 400     }
 401     else if(Geom::SVGEllipticalArc const *svg_elliptical_arc = dynamic_cast<Geom::SVGEllipticalArc const *>(&c)) {
 402         ArcTo( svg_elliptical_arc->finalPoint(),
 403                svg_elliptical_arc->ray(0), svg_elliptical_arc->ray(1),
 404                svg_elliptical_arc->rotation_angle(),  /// \todo check that this parameter is in radians (rotation_angle returns the angle in radians!)
 405                svg_elliptical_arc->large_arc_flag(), !svg_elliptical_arc->sweep_flag() );
 406     } else {
 407         //this case handles sbasis as well as all other curve types
 408         Geom::Path sbasis_path = Geom::cubicbezierpath_from_sbasis(c.toSBasis(), 0.1);
 409
 410         //recurse to convert the new path resulting from the sbasis to svgd
 411         for(Geom::Path::iterator iter = sbasis_path.begin(); iter != sbasis_path.end(); ++iter) {
 412             AddCurve(*iter);
 413         }
 414     }
 415 }
 416
 417 /**  append is false by default: it means that the path should be resetted. If it is true, the path is not resetted and Geom::Path will be appended as a new path
 418  */
 419 void  Path::LoadPath(Geom::Path const &path, Geom::Matrix const &tr, bool doTransformation, bool append)
 420 {
 421     if (!append) {
 422         SetBackData (false);
 423         Reset();
 424     }
 425     if (path.empty())
 426         return;
 427
 428     // TODO: this can be optimized by not generating a new path here, but doing the transform in AddCurve
 429     //       directly on the curve parameters
 430
 431     Geom::Path const pathtr = doTransformation ? path * tr : path;
 432
 433     MoveTo( pathtr.initialPoint() );
 434
 435     for(Geom::Path::const_iterator cit = pathtr.begin(); cit != pathtr.end_open(); ++cit) {
 436         AddCurve(*cit);
 437     }
 438
 439     if (pathtr.closed()) {
 440         // check if closing segment is empty before adding it
 441         Geom::Curve const &crv = pathtr.back_closed();
 442         if ( !crv.isDegenerate() ) {
 443             AddCurve(crv);
 444         }
 445
 446         Close();
 447     }
 448 }
 449
 450 void  Path::LoadPathVector(Geom::PathVector const &pv)
 451 {
 452     LoadPathVector(pv, Geom::Matrix(), false);
 453 }
 454
 455 void  Path::LoadPathVector(Geom::PathVector const &pv, Geom::Matrix const &tr, bool doTransformation)
 456 {
 457     SetBackData (false);
 458     Reset();
 459
 460     // FIXME: 2geom is currently unable to maintain SVGElliptical arcs through transformation, and
 461     // sometimes it crashes on a continuity error during conversions, therefore convert to beziers here.
 462     // (the fix is of course to fix 2geom and then remove this if-statement, and just execute the 'else'-clause)
 463     if (doTransformation) {
 464         Geom::PathVector pvbezier = pathv_to_linear_and_cubic_beziers(pv);
 465         for(Geom::PathVector::const_iterator it = pvbezier.begin(); it != pvbezier.end(); ++it) {
 466             LoadPath(*it, tr, doTransformation, true);
 467         }
 468     } else {
 469         for(Geom::PathVector::const_iterator it = pv.begin(); it != pv.end(); ++it) {
 470             LoadPath(*it, tr, doTransformation, true);
 471         }
 472     }
 473 }
 474
 475 /**
 476  *    \return Length of the lines in the pts vector.
 477  */
 478
 479 double Path::Length()
 480 {
 481     if ( pts.empty() ) {
 482         return 0;
 483     }
 484
 485     Geom::Point lastP = pts[0].p;
 486
 487     double len = 0;
 488     for (std::vector<path_lineto>::const_iterator i = pts.begin(); i != pts.end(); i++) {
 489
 490         if ( i->isMoveTo != polyline_moveto ) {
 491             len += Geom::L2(i->p - lastP);
 492         }
 493
 494         lastP = i->p;
 495     }
 496
 497     return len;
 498 }
 499
 500
 501 double Path::Surface()
 502 {
 503     if ( pts.empty() ) {
 504         return 0;
 505     }
 506
 507     Geom::Point lastM = pts[0].p;
 508     Geom::Point lastP = lastM;
 509
 510     double surf = 0;
 511     for (std::vector<path_lineto>::const_iterator i = pts.begin(); i != pts.end(); i++) {
 512
 513         if ( i->isMoveTo == polyline_moveto ) {
 514             surf += NR::cross(lastM - lastP, lastM);
 515             lastP = lastM = i->p;
 516         } else {
 517             surf += NR::cross(i->p - lastP, i->p);
 518             lastP = i->p;
 519         }
 520
 521     }
 522
 523   return surf;
 524 }
 525
 526
 527 Path**      Path::SubPaths(int &outNb,bool killNoSurf)
 528 {
 529   int      nbRes=0;
 530   Path**   res=NULL;
 531   Path*    curAdd=NULL;
 532
 533   for (int i=0;i<int(descr_cmd.size());i++) {
 534     int const typ = descr_cmd[i]->getType();
 535     switch ( typ ) {
 536       case descr_moveto:
 537         if ( curAdd ) {
 538           if ( curAdd->descr_cmd.size() > 1 ) {
 539             curAdd->Convert(1.0);
 540             double addSurf=curAdd->Surface();
 541             if ( fabs(addSurf) > 0.0001 || killNoSurf == false ) {
 542               res=(Path**)g_realloc(res,(nbRes+1)*sizeof(Path*));
 543               res[nbRes++]=curAdd;
 544             } else {
 545               delete curAdd;
 546             }
 547           } else {
 548             delete curAdd;
 549           }
 550           curAdd=NULL;
 551         }
 552         curAdd=new Path;
 553         curAdd->SetBackData(false);
 554         {
 555           PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 556           curAdd->MoveTo(nData->p);
 557         }
 558           break;
 559       case descr_close:
 560       {
 561         curAdd->Close();
 562       }
 563         break;
 564       case descr_lineto:
 565       {
 566         PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 567         curAdd->LineTo(nData->p);
 568       }
 569         break;
 570       case descr_cubicto:
 571       {
 572         PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 573         curAdd->CubicTo(nData->p,nData->start,nData->end);
 574       }
 575         break;
 576       case descr_arcto:
 577       {
 578         PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 579         curAdd->ArcTo(nData->p,nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise);
 580       }
 581         break;
 582       case descr_bezierto:
 583       {
 584         PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 585         curAdd->BezierTo(nData->p);
 586       }
 587         break;
 588       case descr_interm_bezier:
 589       {
 590         PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
 591         curAdd->IntermBezierTo(nData->p);
 592       }
 593         break;
 594       default:
 595         break;
 596     }
 597   }
 598   if ( curAdd ) {
 599     if ( curAdd->descr_cmd.size() > 1 ) {
 600       curAdd->Convert(1.0);
 601       double addSurf=curAdd->Surface();
 602       if ( fabs(addSurf) > 0.0001 || killNoSurf == false  ) {
 603         res=(Path**)g_realloc(res,(nbRes+1)*sizeof(Path*));
 604         res[nbRes++]=curAdd;
 605       } else {
 606         delete curAdd;
 607       }
 608     } else {
 609       delete curAdd;
 610     }
 611   }
 612   curAdd=NULL;
 613
 614   outNb=nbRes;
 615   return res;
 616 }
 617 Path**      Path::SubPathsWithNesting(int &outNb,bool killNoSurf,int nbNest,int* nesting,int* conts)
 618 {
 619   int      nbRes=0;
 620   Path**   res=NULL;
 621   Path*    curAdd=NULL;
 622   bool     increment=false;
 623
 624   for (int i=0;i<int(descr_cmd.size());i++) {
 625     int const typ = descr_cmd[i]->getType();
 626     switch ( typ ) {
 627       case descr_moveto:
 628       {
 629         if ( curAdd && increment == false ) {
 630           if ( curAdd->descr_cmd.size() > 1 ) {
 631             // sauvegarder descr_cmd[0]->associated
 632             int savA=curAdd->descr_cmd[0]->associated;
 633             curAdd->Convert(1.0);
 634             curAdd->descr_cmd[0]->associated=savA; // associated n'est pas utilise apres
 635             double addSurf=curAdd->Surface();
 636             if ( fabs(addSurf) > 0.0001 || killNoSurf == false ) {
 637               res=(Path**)g_realloc(res,(nbRes+1)*sizeof(Path*));
 638               res[nbRes++]=curAdd;
 639             } else {
 640               delete curAdd;
 641             }
 642           } else {
 643             delete curAdd;
 644           }
 645           curAdd=NULL;
 646         }
 647         Path*  hasDad=NULL;
 648         for (int j=0;j<nbNest;j++) {
 649           if ( conts[j] == i && nesting[j] >= 0 ) {
 650             int  dadMvt=conts[nesting[j]];
 651             for (int k=0;k<nbRes;k++) {
 652               if ( res[k] && res[k]->descr_cmd.empty() == false && res[k]->descr_cmd[0]->associated == dadMvt ) {
 653                 hasDad=res[k];
 654                 break;
 655               }
 656             }
 657           }
 658           if ( conts[j] > i  ) break;
 659         }
 660         if ( hasDad ) {
 661           curAdd=hasDad;
 662           increment=true;
 663         } else {
 664           curAdd=new Path;
 665           curAdd->SetBackData(false);
 666           increment=false;
 667         }
 668         PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 669         int mNo=curAdd->MoveTo(nData->p);
 670         curAdd->descr_cmd[mNo]->associated=i;
 671         }
 672         break;
 673       case descr_close:
 674       {
 675         curAdd->Close();
 676       }
 677         break;
 678       case descr_lineto:
 679       {
 680         PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 681         curAdd->LineTo(nData->p);
 682       }
 683         break;
 684       case descr_cubicto:
 685       {
 686         PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 687         curAdd->CubicTo(nData->p,nData->start,nData->end);
 688       }
 689         break;
 690       case descr_arcto:
 691       {
 692         PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 693         curAdd->ArcTo(nData->p,nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise);
 694       }
 695         break;
 696       case descr_bezierto:
 697       {
 698         PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 699         curAdd->BezierTo(nData->p);
 700       }
 701         break;
 702       case descr_interm_bezier:
 703       {
 704         PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
 705         curAdd->IntermBezierTo(nData->p);
 706       }
 707         break;
 708       default:
 709         break;
 710     }
 711   }
 712   if ( curAdd && increment == false ) {
 713     if ( curAdd->descr_cmd.size() > 1 ) {
 714       curAdd->Convert(1.0);
 715       double addSurf=curAdd->Surface();
 716       if ( fabs(addSurf) > 0.0001 || killNoSurf == false  ) {
 717         res=(Path**)g_realloc(res,(nbRes+1)*sizeof(Path*));
 718         res[nbRes++]=curAdd;
 719       } else {
 720         delete curAdd;
 721       }
 722     } else {
 723       delete curAdd;
 724     }
 725   }
 726   curAdd=NULL;
 727
 728   outNb=nbRes;
 729   return res;
 730 }
 731
 732
 733 void Path::ConvertForcedToVoid()
 734 {
 735     for (int i=0; i < int(descr_cmd.size()); i++) {
 736         if ( descr_cmd[i]->getType() == descr_forced) {
 737             delete descr_cmd[i];
 738             descr_cmd.erase(descr_cmd.begin() + i);
 739         }
 740     }
 741 }
 742
 743
 744 void Path::ConvertForcedToMoveTo()
 745 {
 746     Geom::Point lastSeen(0, 0);
 747     Geom::Point lastMove(0, 0);
 748
 749     {
 750         Geom::Point lastPos(0, 0);
 751         for (int i = int(descr_cmd.size()) - 1; i >= 0; i--) {
 752             int const typ = descr_cmd[i]->getType();
 753             switch ( typ ) {
 754             case descr_forced:
 755             {
 756                 PathDescrForced *d = dynamic_cast<PathDescrForced *>(descr_cmd[i]);
 757                 d->p = lastPos;
 758                 break;
 759             }
 760             case descr_close:
 761             {
 762                 PathDescrClose *d = dynamic_cast<PathDescrClose *>(descr_cmd[i]);
 763                 d->p = lastPos;
 764                 break;
 765             }
 766             case descr_moveto:
 767             {
 768                 PathDescrMoveTo *d = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 769                 lastPos = d->p;
 770                 break;
 771             }
 772             case descr_lineto:
 773             {
 774                 PathDescrLineTo *d = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 775                 lastPos = d->p;
 776                 break;
 777             }
 778             case descr_arcto:
 779             {
 780                 PathDescrArcTo *d = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 781                 lastPos = d->p;
 782                 break;
 783             }
 784             case descr_cubicto:
 785             {
 786                 PathDescrCubicTo *d = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 787                 lastPos = d->p;
 788                 break;
 789             }
 790             case descr_bezierto:
 791             {
 792                 PathDescrBezierTo *d = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 793                 lastPos = d->p;
 794                 break;
 795             }
 796             case descr_interm_bezier:
 797             {
 798                 PathDescrIntermBezierTo *d = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
 799                 lastPos = d->p;
 800                 break;
 801             }
 802             default:
 803                 break;
 804             }
 805         }
 806     }
 807
 808     bool hasMoved = false;
 809     for (int i = 0; i < int(descr_cmd.size()); i++) {
 810         int const typ = descr_cmd[i]->getType();
 811         switch ( typ ) {
 812         case descr_forced:
 813             if ( i < int(descr_cmd.size()) - 1 && hasMoved ) { // sinon il termine le chemin
 814
 815                 delete descr_cmd[i];
 816                 descr_cmd[i] = new PathDescrMoveTo(lastSeen);
 817                 lastMove = lastSeen;
 818                 hasMoved = true;
 819             }
 820             break;
 821
 822         case descr_moveto:
 823         {
 824           PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 825           lastMove = lastSeen = nData->p;
 826           hasMoved = true;
 827         }
 828         break;
 829       case descr_close:
 830       {
 831         lastSeen=lastMove;
 832       }
 833         break;
 834       case descr_lineto:
 835       {
 836         PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 837         lastSeen=nData->p;
 838       }
 839         break;
 840       case descr_cubicto:
 841       {
 842         PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 843         lastSeen=nData->p;
 844      }
 845         break;
 846       case descr_arcto:
 847       {
 848         PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 849         lastSeen=nData->p;
 850       }
 851         break;
 852       case descr_bezierto:
 853       {
 854         PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 855         lastSeen=nData->p;
 856      }
 857         break;
 858       case descr_interm_bezier:
 859       {
 860         PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
 861         lastSeen=nData->p;
 862       }
 863         break;
 864       default:
 865         break;
 866     }
 867   }
 868 }
 869 static int       CmpPosition(const void * p1, const void * p2) {
 870   Path::cut_position *cp1=(Path::cut_position*)p1;
 871   Path::cut_position *cp2=(Path::cut_position*)p2;
 872   if ( cp1->piece < cp2->piece ) return -1;
 873   if ( cp1->piece > cp2->piece ) return 1;
 874   if ( cp1->t < cp2->t ) return -1;
 875   if ( cp1->t > cp2->t ) return 1;
 876   return 0;
 877 }
 878 static int       CmpCurv(const void * p1, const void * p2) {
 879   double *cp1=(double*)p1;
 880   double *cp2=(double*)p2;
 881   if ( *cp1 < *cp2 ) return -1;
 882   if ( *cp1 > *cp2 ) return 1;
 883   return 0;
 884 }
 885
 886
 887 Path::cut_position* Path::CurvilignToPosition(int nbCv, double *cvAbs, int &nbCut)
 888 {
 889     if ( nbCv <= 0 || pts.empty() || back == false ) {
 890         return NULL;
 891     }
 892
 893     qsort(cvAbs, nbCv, sizeof(double), CmpCurv);
 894
 895     cut_position *res = NULL;
 896     nbCut = 0;
 897     int curCv = 0;
 898
 899     double len = 0;
 900     double lastT = 0;
 901     int lastPiece = -1;
 902
 903     Geom::Point lastM = pts[0].p;
 904     Geom::Point lastP = lastM;
 905
 906     for (std::vector<path_lineto>::const_iterator i = pts.begin(); i != pts.end(); i++) {
 907
 908         if ( i->isMoveTo == polyline_moveto ) {
 909
 910             lastP = lastM = i->p;
 911             lastT = i->t;
 912             lastPiece = i->piece;
 913
 914         } else {
 915
 916             double const add = Geom::L2(i->p - lastP);
 917             double curPos = len;
 918             double curAdd = add;
 919
 920             while ( curAdd > 0.0001 && curCv < nbCv && curPos + curAdd >= cvAbs[curCv] ) {
 921                 double const theta = (cvAbs[curCv] - len) / add;
 922                 res = (cut_position*) g_realloc(res, (nbCut + 1) * sizeof(cut_position));
 923                 res[nbCut].piece = i->piece;
 924                 res[nbCut].t = theta * i->t + (1 - theta) * ( (lastPiece != i->piece) ? 0 : lastT);
 925                 nbCut++;
 926                 curAdd -= cvAbs[curCv] - curPos;
 927                 curPos = cvAbs[curCv];
 928                 curCv++;
 929             }
 930
 931             len += add;
 932             lastPiece = i->piece;
 933             lastP = i->p;
 934             lastT = i->t;
 935         }
 936     }
 937
 938     return res;
 939 }
 940
 941 /*
 942 Moved from Layout-TNG-OutIter.cpp
 943 TODO: clean up uses of the original function and remove
 944
 945 Original Comment:
 946 "this function really belongs to Path. I'll probably move it there eventually,
 947 hence the Path-esque coding style"
 948
 949 */
 950 template<typename T> inline static T square(T x) {return x*x;}
 951 Path::cut_position Path::PointToCurvilignPosition(Geom::Point const &pos, unsigned seg) const
 952 {
 953     // if the parameter "seg" == 0, then all segments will be considered
 954     // In however e.g. "seg" == 6 , then only the 6th segment will be considered
 955
 956     unsigned bestSeg = 0;
 957     double bestRangeSquared = DBL_MAX;
 958     double bestT = 0.0; // you need a sentinel, or make sure that you prime with correct values.
 959
 960     for (unsigned i = 1 ; i < pts.size() ; i++) {
 961         if (pts[i].isMoveTo == polyline_moveto || (seg > 0 && i != seg)) continue;
 962         Geom::Point p1, p2, localPos;
 963         double thisRangeSquared;
 964         double t;
 965
 966         if (pts[i - 1].p == pts[i].p) {
 967             thisRangeSquared = square(pts[i].p[Geom::X] - pos[Geom::X]) + square(pts[i].p[Geom::Y] - pos[Geom::Y]);
 968             t = 0.0;
 969         } else {
 970             // we rotate all our coordinates so we're always looking at a mostly vertical line.
 971             if (fabs(pts[i - 1].p[Geom::X] - pts[i].p[Geom::X]) < fabs(pts[i - 1].p[Geom::Y] - pts[i].p[Geom::Y])) {
 972                 p1 = pts[i - 1].p;
 973                 p2 = pts[i].p;
 974                 localPos = pos;
 975             } else {
 976                 p1 = pts[i - 1].p.cw();
 977                 p2 = pts[i].p.cw();
 978                 localPos = pos.cw();
 979             }
 980             double gradient = (p2[Geom::X] - p1[Geom::X]) / (p2[Geom::Y] - p1[Geom::Y]);
 981             double intersection = p1[Geom::X] - gradient * p1[Geom::Y];
 982             /*
 983               orthogonalGradient = -1.0 / gradient; // you are going to have numerical problems here.
 984               orthogonalIntersection = localPos[Geom::X] - orthogonalGradient * localPos[Geom::Y];
 985               nearestY = (orthogonalIntersection - intersection) / (gradient - orthogonalGradient);
 986
 987               expand out nearestY fully :
 988               nearestY = (localPos[Geom::X] - (-1.0 / gradient) * localPos[Geom::Y] - intersection) / (gradient - (-1.0 / gradient));
 989
 990               multiply top and bottom by gradient:
 991               nearestY = (localPos[Geom::X] * gradient - (-1.0) * localPos[Geom::Y] - intersection * gradient) / (gradient * gradient - (-1.0));
 992
 993               and simplify to get:
 994             */
 995             double nearestY =  (localPos[Geom::X] * gradient + localPos[Geom::Y] - intersection * gradient)
 996                              / (gradient * gradient + 1.0);
 997             t = (nearestY - p1[Geom::Y]) / (p2[Geom::Y] - p1[Geom::Y]);
 998             if (t <= 0.0) {
 999                 thisRangeSquared = square(p1[Geom::X] - localPos[Geom::X]) + square(p1[Geom::Y] - localPos[Geom::Y]);
1000                 t = 0.0;
1001             } else if (t >= 1.0) {
1002                 thisRangeSquared = square(p2[Geom::X] - localPos[Geom::X]) + square(p2[Geom::Y] - localPos[Geom::Y]);
1003                 t = 1.0;
1004             } else {
1005                 thisRangeSquared = square(nearestY * gradient + intersection - localPos[Geom::X]) + square(nearestY - localPos[Geom::Y]);
1006             }
1007         }
1008
1009         if (thisRangeSquared < bestRangeSquared) {
1010             bestSeg = i;
1011             bestRangeSquared = thisRangeSquared;
1012             bestT = t;
1013         }
1014     }
1015     Path::cut_position result;
1016     if (bestSeg == 0) {
1017         result.piece = 0;
1018         result.t = 0.0;
1019     } else {
1020         result.piece = pts[bestSeg].piece;
1021         if (result.piece == pts[bestSeg - 1].piece) {
1022             result.t = pts[bestSeg - 1].t * (1.0 - bestT) + pts[bestSeg].t * bestT;
1023         } else {
1024             result.t = pts[bestSeg].t * bestT;
1025         }
1026     }
1027     return result;
1028 }
1029 /*
1030     this one also belongs to Path
1031     returns the length of the path up to the position indicated by t (0..1)
1032
1033     TODO: clean up uses of the original function and remove
1034
1035     should this take a cut_position as a parameter?
1036 */
1037 double Path::PositionToLength(int piece, double t)
1038 {
1039     double length = 0.0;
1040     for (unsigned i = 1 ; i < pts.size() ; i++) {
1041         if (pts[i].isMoveTo == polyline_moveto) continue;
1042         if (pts[i].piece == piece && t < pts[i].t) {
1043             length += Geom::L2((t - pts[i - 1].t) / (pts[i].t - pts[i - 1].t) * (pts[i].p - pts[i - 1].p));
1044             break;
1045         }
1046         length += Geom::L2(pts[i].p - pts[i - 1].p);
1047     }
1048     return length;
1049 }
1050
1051 void Path::ConvertPositionsToForced(int nbPos, cut_position *poss)
1052 {
1053     if ( nbPos <= 0 ) {
1054         return;
1055     }
1056
1057     {
1058         Geom::Point lastPos(0, 0);
1059         for (int i = int(descr_cmd.size()) - 1; i >= 0; i--) {
1060             int const typ = descr_cmd[i]->getType();
1061             switch ( typ ) {
1062
1063             case descr_forced:
1064             {
1065                 PathDescrForced *d = dynamic_cast<PathDescrForced *>(descr_cmd[i]);
1066                 d->p = lastPos;
1067                 break;
1068             }
1069
1070             case descr_close:
1071             {
1072                 delete descr_cmd[i];
1073                 descr_cmd[i] = new PathDescrLineTo(Geom::Point(0, 0));
1074
1075                 int fp = i - 1;
1076                 while ( fp >= 0 && (descr_cmd[fp]->getType()) != descr_moveto ) {
1077                     fp--;
1078                 }
1079
1080                 if ( fp >= 0 ) {
1081                     PathDescrMoveTo *oData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[fp]);
1082                     dynamic_cast<PathDescrLineTo*>(descr_cmd[i])->p = oData->p;
1083                 }
1084             }
1085             break;
1086
1087             case descr_bezierto:
1088             {
1089                 PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
1090                 Geom::Point theP = nData->p;
1091                 if ( nData->nb == 0 ) {
1092                     lastPos = theP;
1093                 }
1094             }
1095             break;
1096
1097         case descr_moveto:
1098         {
1099             PathDescrMoveTo *d = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
1100             lastPos = d->p;
1101             break;
1102         }
1103         case descr_lineto:
1104         {
1105             PathDescrLineTo *d = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
1106             lastPos = d->p;
1107             break;
1108         }
1109         case descr_arcto:
1110         {
1111             PathDescrArcTo *d = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
1112             lastPos = d->p;
1113             break;
1114         }
1115         case descr_cubicto:
1116         {
1117             PathDescrCubicTo *d = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
1118             lastPos = d->p;
1119             break;
1120         }
1121         case descr_interm_bezier:
1122         {
1123             PathDescrIntermBezierTo *d = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
1124             lastPos = d->p;
1125             break;
1126         }
1127         default:
1128           break;
1129       }
1130     }
1131   }
1132
1133   qsort(poss, nbPos, sizeof(cut_position), CmpPosition);
1134
1135   for (int curP=0;curP<nbPos;curP++) {
1136     int   cp=poss[curP].piece;
1137     if ( cp < 0 || cp >= int(descr_cmd.size()) ) break;
1138     float ct=poss[curP].t;
1139     if ( ct < 0 ) continue;
1140     if ( ct > 1 ) continue;
1141
1142     int const typ = descr_cmd[cp]->getType();
1143     if ( typ == descr_moveto || typ == descr_forced || typ == descr_close ) {
1144       // ponctuel= rien a faire
1145     } else if ( typ == descr_lineto || typ == descr_arcto || typ == descr_cubicto ) {
1146       // facile: creation d'un morceau et d'un forced -> 2 commandes
1147       Geom::Point        theP;
1148       Geom::Point        theT;
1149       Geom::Point        startP;
1150       startP=PrevPoint(cp-1);
1151       if ( typ == descr_cubicto ) {
1152         double           len,rad;
1153         Geom::Point        stD,enD,endP;
1154         {
1155           PathDescrCubicTo *oData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[cp]);
1156           stD=oData->start;
1157           enD=oData->end;
1158           endP=oData->p;
1159           TangentOnCubAt (ct, startP, *oData,true, theP,theT,len,rad);
1160         }
1161
1162         theT*=len;
1163
1164         InsertCubicTo(endP,(1-ct)*theT,(1-ct)*enD,cp+1);
1165         InsertForcePoint(cp+1);
1166         {
1167           PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[cp]);
1168           nData->start=ct*stD;
1169           nData->end=ct*theT;
1170           nData->p=theP;
1171         }
1172         // decalages dans le tableau des positions de coupe
1173         for (int j=curP+1;j<nbPos;j++) {
1174           if ( poss[j].piece == cp ) {
1175             poss[j].piece+=2;
1176             poss[j].t=(poss[j].t-ct)/(1-ct);
1177           } else {
1178             poss[j].piece+=2;
1179           }
1180         }
1181       } else if ( typ == descr_lineto ) {
1182         Geom::Point        endP;
1183         {
1184           PathDescrLineTo *oData = dynamic_cast<PathDescrLineTo *>(descr_cmd[cp]);
1185           endP=oData->p;
1186         }
1187
1188         theP=ct*endP+(1-ct)*startP;
1189
1190         InsertLineTo(endP,cp+1);
1191         InsertForcePoint(cp+1);
1192         {
1193           PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[cp]);
1194           nData->p=theP;
1195         }
1196         // decalages dans le tableau des positions de coupe
1197        for (int j=curP+1;j<nbPos;j++) {
1198           if ( poss[j].piece == cp ) {
1199             poss[j].piece+=2;
1200             poss[j].t=(poss[j].t-ct)/(1-ct);
1201           } else {
1202             poss[j].piece+=2;
1203           }
1204         }
1205       } else if ( typ == descr_arcto ) {
1206         Geom::Point        endP;
1207         double           rx,ry,angle;
1208         bool             clockw,large;
1209         double   delta=0;
1210         {
1211           PathDescrArcTo *oData = dynamic_cast<PathDescrArcTo *>(descr_cmd[cp]);
1212           endP=oData->p;
1213           rx=oData->rx;
1214           ry=oData->ry;
1215           angle=oData->angle;
1216           clockw=oData->clockwise;
1217           large=oData->large;
1218         }
1219         {
1220           double      sang,eang;
1221           ArcAngles(startP,endP,rx,ry,angle,large,clockw,sang,eang);
1222
1223           if (clockw) {
1224             if ( sang < eang ) sang += 2*M_PI;
1225             delta=eang-sang;
1226           } else {
1227             if ( sang > eang ) sang -= 2*M_PI;
1228             delta=eang-sang;
1229           }
1230           if ( delta < 0 ) delta=-delta;
1231         }
1232
1233         PointAt (cp,ct, theP);
1234
1235         if ( delta*(1-ct) > M_PI ) {
1236           InsertArcTo(endP,rx,ry,angle,true,clockw,cp+1);
1237         } else {
1238           InsertArcTo(endP,rx,ry,angle,false,clockw,cp+1);
1239         }
1240         InsertForcePoint(cp+1);
1241         {
1242           PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[cp]);
1243           nData->p=theP;
1244           if ( delta*ct > M_PI ) {
1245             nData->clockwise=true;
1246           } else {
1247             nData->clockwise=false;
1248           }
1249         }
1250         // decalages dans le tableau des positions de coupe
1251         for (int j=curP+1;j<nbPos;j++) {
1252           if ( poss[j].piece == cp ) {
1253             poss[j].piece+=2;
1254             poss[j].t=(poss[j].t-ct)/(1-ct);
1255           } else {
1256             poss[j].piece+=2;
1257           }
1258         }
1259       }
1260     } else if ( typ == descr_bezierto || typ == descr_interm_bezier ) {
1261       // dur
1262       int theBDI=cp;
1263       while ( theBDI >= 0 && (descr_cmd[theBDI]->getType()) != descr_bezierto ) theBDI--;
1264       if ( (descr_cmd[theBDI]->getType()) == descr_bezierto ) {
1265         PathDescrBezierTo theBD=*(dynamic_cast<PathDescrBezierTo *>(descr_cmd[theBDI]));
1266         if ( cp >= theBDI && cp < theBDI+theBD.nb ) {
1267           if ( theBD.nb == 1 ) {
1268             Geom::Point        endP=theBD.p;
1269             Geom::Point        midP;
1270             Geom::Point        startP;
1271             startP=PrevPoint(theBDI-1);
1272             {
1273               PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[theBDI+1]);
1274               midP=nData->p;
1275             }
1276             Geom::Point       aP=ct*midP+(1-ct)*startP;
1277             Geom::Point       bP=ct*endP+(1-ct)*midP;
1278             Geom::Point       knotP=ct*bP+(1-ct)*aP;
1279
1280             InsertIntermBezierTo(bP,theBDI+2);
1281             InsertBezierTo(knotP,1,theBDI+2);
1282             InsertForcePoint(theBDI+2);
1283             {
1284               PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[theBDI+1]);
1285               nData->p=aP;
1286             }
1287             {
1288               PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[theBDI]);
1289               nData->p=knotP;
1290             }
1291             // decalages dans le tableau des positions de coupe
1292             for (int j=curP+1;j<nbPos;j++) {
1293               if ( poss[j].piece == cp ) {
1294                 poss[j].piece+=3;
1295                 poss[j].t=(poss[j].t-ct)/(1-ct);
1296               } else {
1297                 poss[j].piece+=3;
1298               }
1299             }
1300
1301           } else {
1302             // decouper puis repasser
1303             if ( cp > theBDI ) {
1304               Geom::Point   pcP,ncP;
1305               {
1306                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[cp]);
1307                 pcP=nData->p;
1308               }
1309               {
1310                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[cp+1]);
1311                 ncP=nData->p;
1312               }
1313               Geom::Point knotP=0.5*(pcP+ncP);
1314
1315               InsertBezierTo(knotP,theBD.nb-(cp-theBDI),cp+1);
1316               {
1317                 PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[theBDI]);
1318                 nData->nb=cp-theBDI;
1319               }
1320
1321               // decalages dans le tableau des positions de coupe
1322               for (int j=curP;j<nbPos;j++) {
1323                 if ( poss[j].piece == cp ) {
1324                   poss[j].piece+=1;
1325                 } else {
1326                   poss[j].piece+=1;
1327                 }
1328               }
1329               curP--;
1330             } else {
1331               Geom::Point   pcP,ncP;
1332               {
1333                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[cp+1]);
1334                 pcP=nData->p;
1335               }
1336               {
1337                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[cp+2]);
1338                 ncP=nData->p;
1339               }
1340               Geom::Point knotP=0.5*(pcP+ncP);
1341
1342               InsertBezierTo(knotP,theBD.nb-1,cp+2);
1343               {
1344                 PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[theBDI]);
1345                 nData->nb=1;
1346               }
1347
1348               // decalages dans le tableau des positions de coupe
1349               for (int j=curP;j<nbPos;j++) {
1350                 if ( poss[j].piece == cp ) {
1351 //                  poss[j].piece+=1;
1352                 } else {
1353                   poss[j].piece+=1;
1354                 }
1355               }
1356               curP--;
1357             }
1358           }
1359         } else {
1360           // on laisse aussi tomber
1361         }
1362       } else {
1363         // on laisse tomber
1364       }
1365     }
1366   }
1367 }
1368
1369 void        Path::ConvertPositionsToMoveTo(int nbPos,cut_position* poss)
1370 {
1371   ConvertPositionsToForced(nbPos,poss);
1372 //  ConvertForcedToMoveTo();
1373   // on fait une version customizee a la place
1374
1375   Path*  res=new Path;
1376
1377   Geom::Point    lastP(0,0);
1378   for (int i=0;i<int(descr_cmd.size());i++) {
1379     int const typ = descr_cmd[i]->getType();
1380     if ( typ == descr_moveto ) {
1381       Geom::Point  np;
1382       {
1383         PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
1384         np=nData->p;
1385       }
1386       Geom::Point  endP;
1387       bool       hasClose=false;
1388       int        hasForced=-1;
1389       bool       doesClose=false;
1390       int        j=i+1;
1391       for (;j<int(descr_cmd.size());j++) {
1392         int const ntyp = descr_cmd[j]->getType();
1393         if ( ntyp == descr_moveto ) {
1394           j--;
1395           break;
1396         } else if ( ntyp == descr_forced ) {
1397           if ( hasForced < 0 ) hasForced=j;
1398         } else if ( ntyp == descr_close ) {
1399           hasClose=true;
1400           break;
1401         } else if ( ntyp == descr_lineto ) {
1402           PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[j]);
1403           endP=nData->p;
1404         } else if ( ntyp == descr_arcto ) {
1405           PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[j]);
1406           endP=nData->p;
1407         } else if ( ntyp == descr_cubicto ) {
1408           PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[j]);
1409           endP=nData->p;
1410         } else if ( ntyp == descr_bezierto ) {
1411           PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[j]);
1412           endP=nData->p;
1413         } else {
1414         }
1415       }
1416       if ( Geom::LInfty(endP-np) < 0.00001 ) {
1417         doesClose=true;
1418       }
1419       if ( ( doesClose || hasClose ) && hasForced >= 0 ) {
1420  //       printf("nasty i=%i j=%i frc=%i\n",i,j,hasForced);
1421         // aghhh.
1422         Geom::Point   nMvtP=PrevPoint(hasForced);
1423         res->MoveTo(nMvtP);
1424         Geom::Point   nLastP=nMvtP;
1425         for (int k = hasForced + 1; k < j; k++) {
1426           int ntyp=descr_cmd[k]->getType();
1427           if ( ntyp == descr_moveto ) {
1428             // ne doit pas arriver
1429           } else if ( ntyp == descr_forced ) {
1430             res->MoveTo(nLastP);
1431           } else if ( ntyp == descr_close ) {
1432             // rien a faire ici; de plus il ne peut y en avoir qu'un
1433           } else if ( ntyp == descr_lineto ) {
1434             PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[k]);
1435             res->LineTo(nData->p);
1436             nLastP=nData->p;
1437           } else if ( ntyp == descr_arcto ) {
1438             PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[k]);
1439             res->ArcTo(nData->p,nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise);
1440             nLastP=nData->p;
1441           } else if ( ntyp == descr_cubicto ) {
1442             PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[k]);
1443             res->CubicTo(nData->p,nData->start,nData->end);
1444             nLastP=nData->p;
1445           } else if ( ntyp == descr_bezierto ) {
1446             PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[k]);
1447             res->BezierTo(nData->p);
1448             nLastP=nData->p;
1449           } else if ( ntyp == descr_interm_bezier ) {
1450             PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[k]);
1451             res->IntermBezierTo(nData->p);
1452           } else {
1453           }
1454         }
1455         if ( doesClose == false ) res->LineTo(np);
1456         nLastP=np;
1457         for (int k=i+1;k<hasForced;k++) {
1458           int ntyp=descr_cmd[k]->getType();
1459           if ( ntyp == descr_moveto ) {
1460             // ne doit pas arriver
1461           } else if ( ntyp == descr_forced ) {
1462             res->MoveTo(nLastP);
1463           } else if ( ntyp == descr_close ) {
1464             // rien a faire ici; de plus il ne peut y en avoir qu'un
1465           } else if ( ntyp == descr_lineto ) {
1466             PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[k]);
1467             res->LineTo(nData->p);
1468             nLastP=nData->p;
1469           } else if ( ntyp == descr_arcto ) {
1470             PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[k]);
1471             res->ArcTo(nData->p,nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise);
1472             nLastP=nData->p;
1473           } else if ( ntyp == descr_cubicto ) {
1474             PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[k]);
1475             res->CubicTo(nData->p,nData->start,nData->end);
1476             nLastP=nData->p;
1477           } else if ( ntyp == descr_bezierto ) {
1478             PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[k]);
1479             res->BezierTo(nData->p);
1480             nLastP=nData->p;
1481           } else if ( ntyp == descr_interm_bezier ) {
1482             PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[k]);
1483             res->IntermBezierTo(nData->p);
1484           } else {
1485           }
1486         }
1487         lastP=nMvtP;
1488         i=j;
1489       } else {
1490         // regular, just move on
1491         res->MoveTo(np);
1492         lastP=np;
1493       }
1494     } else if ( typ == descr_close ) {
1495       res->Close();
1496     } else if ( typ == descr_forced ) {
1497       res->MoveTo(lastP);
1498     } else if ( typ == descr_lineto ) {
1499       PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
1500       res->LineTo(nData->p);
1501       lastP=nData->p;
1502     } else if ( typ == descr_arcto ) {
1503       PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
1504       res->ArcTo(nData->p,nData->rx,nData->ry,nData->angle,nData->large,nData->clockwise);
1505       lastP=nData->p;
1506     } else if ( typ == descr_cubicto ) {
1507       PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
1508       res->CubicTo(nData->p,nData->start,nData->end);
1509       lastP=nData->p;
1510     } else if ( typ == descr_bezierto ) {
1511       PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
1512       res->BezierTo(nData->p);
1513       lastP=nData->p;
1514     } else if ( typ == descr_interm_bezier ) {
1515       PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[i]);
1516       res->IntermBezierTo(nData->p);
1517     } else {
1518     }
1519   }
1520
1521   Copy(res);
1522   delete res;
1523   return;
1524 }
1525
1526 /*
1527   Local Variables:
1528   mode:c++
1529   c-file-style:"stroustrup"
1530   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1531   indent-tabs-mode:nil
1532   fill-column:99
1533   End:
1534 */
1535 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :