src/livarot/ShapeMisc.cpp

   1 /*
   2  *  ShapeMisc.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Sun Jul 20 2003.
   6  *
   7  */
   8
   9 #include "livarot/Shape.h"
  10 #include <libnr/nr-matrix-fns.h>
  11 #include <libnr/nr-point-fns.h>
  12 #include "livarot/Path.h"
  13 #include "livarot/path-description.h"
  14 #include <glib.h>
  15 #include <cstdio>
  16 #include <cstdlib>
  17 #include <cstring>
  18
  19 /*
  20  * polygon offset and polyline to path reassembling (when using back data)
  21  */
  22
  23 // until i find something better
  24 #define MiscNormalize(v) {\
  25   double _l=sqrt(dot(v,v)); \
  26     if ( _l < 0.0000001 ) { \
  27       v[0]=v[1]=0; \
  28     } else { \
  29       v/=_l; \
  30     }\
  31 }
  32
  33 // extracting the contour of an uncrossed polygon: a mere depth first search
  34 // more precisely that's extracting an eulerian path from a graph, but here we want to split
  35 // the polygon into contours and avoid holes. so we take a "next counter-clockwise edge first" approach
  36 // (make a checkboard and extract its contours to see the difference)
  37 void
  38 Shape::ConvertToForme (Path * dest)
  39 {
  40   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
  41     return;
  42
  43   // prepare
  44   dest->Reset ();
  45
  46   MakePointData (true);
  47   MakeEdgeData (true);
  48   MakeSweepDestData (true);
  49
  50   for (int i = 0; i < numberOfPoints(); i++)
  51   {
  52     pData[i].rx[0] = Round (getPoint(i).x[0]);
  53     pData[i].rx[1] = Round (getPoint(i).x[1]);
  54   }
  55   for (int i = 0; i < numberOfEdges(); i++)
  56   {
  57     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
  58   }
  59
  60   // sort edge clockwise, with the closest after midnight being first in the doubly-linked list
  61   // that's vital to the algorithm...
  62   SortEdges ();
  63
  64   // depth-first search implies: we make a stack of edges traversed.
  65   // precParc: previous in the stack
  66   // suivParc: next in the stack
  67   for (int i = 0; i < numberOfEdges(); i++)
  68   {
  69     swdData[i].misc = 0;
  70     swdData[i].precParc = swdData[i].suivParc = -1;
  71   }
  72
  73   int searchInd = 0;
  74
  75   int lastPtUsed = 0;
  76   do
  77   {
  78     // first get a starting point, and a starting edge
  79     // -> take the upper left point, and take its first edge
  80     // points traversed have swdData[].misc != 0, so it's easy
  81     int startBord = -1;
  82     {
  83       int fi = 0;
  84       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
  85       {
  86         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
  87           break;
  88       }
  89       lastPtUsed = fi + 1;
  90       if (fi < numberOfPoints())
  91       {
  92         int bestB = getPoint(fi).incidentEdge[FIRST];
  93         while (bestB >= 0 && getEdge(bestB).st != fi)
  94           bestB = NextAt (fi, bestB);
  95         if (bestB >= 0)
  96               {
  97           startBord = bestB;
  98           dest->MoveTo (getPoint(getEdge(startBord).en).x);
  99               }
 100       }
 101     }
 102     // and walk the graph, doing contours when needed
 103     if (startBord >= 0)
 104     {
 105       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 106       swdData[startBord].misc = (void *) 1;
 107       //                      printf("part de %d\n",startBord);
 108       int curBord = startBord;
 109       bool back = false;
 110       swdData[curBord].precParc = -1;
 111       swdData[curBord].suivParc = -1;
 112       do
 113             {
 114               int cPt = getEdge(curBord).en;
 115               int nb = curBord;
 116         //                              printf("de curBord= %d au point %i  -> ",curBord,cPt);
 117         // get next edge
 118               do
 119         {
 120           int nnb = CycleNextAt (cPt, nb);
 121           if (nnb == nb)
 122           {
 123             // cul-de-sac
 124             nb = -1;
 125             break;
 126           }
 127           nb = nnb;
 128           if (nb < 0 || nb == curBord)
 129             break;
 130         }
 131               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 132
 133               if (nb < 0 || nb == curBord)
 134         {
 135           // no next edge: end of this contour, we get back
 136           if (back == false)
 137             dest->Close ();
 138           back = true;
 139           // retour en arriere
 140           curBord = swdData[curBord].precParc;
 141           //                                      printf("retour vers %d\n",curBord);
 142           if (curBord < 0)
 143             break;
 144         }
 145               else
 146         {
 147           // new edge, maybe for a new contour
 148           if (back)
 149           {
 150             // we were backtracking, so if we have a new edge, that means we're creating a new contour
 151             dest->MoveTo (getPoint(cPt).x);
 152             back = false;
 153           }
 154           swdData[nb].misc = (void *) 1;
 155           swdData[nb].ind = searchInd++;
 156           swdData[nb].precParc = curBord;
 157           swdData[curBord].suivParc = nb;
 158           curBord = nb;
 159           //                                      printf("suite %d\n",curBord);
 160           {
 161             // add that edge
 162             dest->LineTo (getPoint(getEdge(nb).en).x);
 163           }
 164         }
 165             }
 166       while (1 /*swdData[curBord].precParc >= 0 */ );
 167       // fin du cas non-oriente
 168     }
 169   }
 170   while (lastPtUsed < numberOfPoints());
 171
 172   MakePointData (false);
 173   MakeEdgeData (false);
 174   MakeSweepDestData (false);
 175 }
 176
 177 // same as before, but each time we have a contour, try to reassemble the segments on it to make chunks of
 178 // the original(s) path(s)
 179 // originals are in the orig array, whose size is nbP
 180 void
 181 Shape::ConvertToForme (Path * dest, int nbP, Path * *orig, bool splitWhenForced)
 182 {
 183   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
 184     return;
 185 //  if (Eulerian (true) == false)
 186 //    return;
 187
 188   if (_has_back_data == false)
 189   {
 190     ConvertToForme (dest);
 191     return;
 192   }
 193
 194   dest->Reset ();
 195
 196   MakePointData (true);
 197   MakeEdgeData (true);
 198   MakeSweepDestData (true);
 199
 200   for (int i = 0; i < numberOfPoints(); i++)
 201   {
 202     pData[i].rx[0] = Round (getPoint(i).x[0]);
 203     pData[i].rx[1] = Round (getPoint(i).x[1]);
 204   }
 205   for (int i = 0; i < numberOfEdges(); i++)
 206   {
 207     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
 208   }
 209
 210   SortEdges ();
 211
 212   for (int i = 0; i < numberOfEdges(); i++)
 213   {
 214     swdData[i].misc = 0;
 215     swdData[i].precParc = swdData[i].suivParc = -1;
 216   }
 217
 218   int searchInd = 0;
 219
 220   int lastPtUsed = 0;
 221   do
 222   {
 223     int startBord = -1;
 224     {
 225       int fi = 0;
 226       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
 227       {
 228         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
 229           break;
 230       }
 231       lastPtUsed = fi + 1;
 232       if (fi < numberOfPoints())
 233       {
 234         int bestB = getPoint(fi).incidentEdge[FIRST];
 235         while (bestB >= 0 && getEdge(bestB).st != fi)
 236           bestB = NextAt (fi, bestB);
 237         if (bestB >= 0)
 238               {
 239           startBord = bestB;
 240               }
 241       }
 242     }
 243     if (startBord >= 0)
 244     {
 245       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 246       swdData[startBord].misc = (void *) 1;
 247       //printf("part de %d\n",startBord);
 248       int curBord = startBord;
 249       bool back = false;
 250       swdData[curBord].precParc = -1;
 251       swdData[curBord].suivParc = -1;
 252       int curStartPt=getEdge(curBord).st;
 253       do
 254             {
 255               int cPt = getEdge(curBord).en;
 256               int nb = curBord;
 257         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
 258               do
 259         {
 260           int nnb = CycleNextAt (cPt, nb);
 261           if (nnb == nb)
 262           {
 263             // cul-de-sac
 264             nb = -1;
 265             break;
 266           }
 267           nb = nnb;
 268           if (nb < 0 || nb == curBord)
 269             break;
 270         }
 271               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 272
 273               if (nb < 0 || nb == curBord)
 274         {
 275           if (back == false)
 276           {
 277             if (curBord == startBord || curBord < 0)
 278             {
 279               // probleme -> on vire le moveto
 280               //                                                      dest->descr_nb--;
 281             }
 282             else
 283             {
 284               swdData[curBord].suivParc = -1;
 285               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 286             }
 287             //                                              dest->Close();
 288           }
 289           back = true;
 290           // retour en arriere
 291           curBord = swdData[curBord].precParc;
 292           //printf("retour vers %d\n",curBord);
 293           if (curBord < 0)
 294             break;
 295         }
 296               else
 297         {
 298           if (back)
 299           {
 300             back = false;
 301             startBord = nb;
 302             curStartPt=getEdge(nb).st;
 303           } else {
 304             if ( getEdge(curBord).en == curStartPt ) {
 305               //printf("contour %i ",curStartPt);
 306               swdData[curBord].suivParc = -1;
 307               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 308               startBord=nb;
 309             }
 310           }
 311           swdData[nb].misc = (void *) 1;
 312           swdData[nb].ind = searchInd++;
 313           swdData[nb].precParc = curBord;
 314           swdData[curBord].suivParc = nb;
 315           curBord = nb;
 316           //printf("suite %d\n",curBord);
 317         }
 318             }
 319       while (1 /*swdData[curBord].precParc >= 0 */ );
 320       // fin du cas non-oriente
 321     }
 322   }
 323   while (lastPtUsed < numberOfPoints());
 324
 325   MakePointData (false);
 326   MakeEdgeData (false);
 327   MakeSweepDestData (false);
 328 }
 329 void
 330 Shape::ConvertToFormeNested (Path * dest, int nbP, Path * *orig, int wildPath,int &nbNest,int *&nesting,int *&contStart,bool splitWhenForced)
 331 {
 332   nesting=NULL;
 333   contStart=NULL;
 334   nbNest=0;
 335
 336   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
 337     return;
 338   //  if (Eulerian (true) == false)
 339   //    return;
 340
 341   if (_has_back_data == false)
 342   {
 343     ConvertToForme (dest);
 344     return;
 345   }
 346
 347   dest->Reset ();
 348
 349 //  MakePointData (true);
 350   MakeEdgeData (true);
 351   MakeSweepDestData (true);
 352
 353   for (int i = 0; i < numberOfPoints(); i++)
 354   {
 355     pData[i].rx[0] = Round (getPoint(i).x[0]);
 356     pData[i].rx[1] = Round (getPoint(i).x[1]);
 357   }
 358   for (int i = 0; i < numberOfEdges(); i++)
 359   {
 360     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
 361   }
 362
 363   SortEdges ();
 364
 365   for (int i = 0; i < numberOfEdges(); i++)
 366   {
 367     swdData[i].misc = 0;
 368     swdData[i].precParc = swdData[i].suivParc = -1;
 369   }
 370
 371   int searchInd = 0;
 372
 373   int lastPtUsed = 0;
 374   do
 375   {
 376     int dadContour=-1;
 377     int startBord = -1;
 378     {
 379       int fi = 0;
 380       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
 381       {
 382         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
 383           break;
 384       }
 385       {
 386         int askTo = pData[fi].askForWindingB;
 387         if (askTo < 0 || askTo >= numberOfEdges() ) {
 388           dadContour=-1;
 389         } else {
 390           dadContour = GPOINTER_TO_INT(swdData[askTo].misc);
 391           dadContour-=1; // pour compenser le decalage
 392         }
 393       }
 394       lastPtUsed = fi + 1;
 395       if (fi < numberOfPoints())
 396       {
 397         int bestB = getPoint(fi).incidentEdge[FIRST];
 398         while (bestB >= 0 && getEdge(bestB).st != fi)
 399           bestB = NextAt (fi, bestB);
 400         if (bestB >= 0)
 401               {
 402           startBord = bestB;
 403               }
 404       }
 405     }
 406     if (startBord >= 0)
 407     {
 408       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 409       swdData[startBord].misc = (void *) (1+nbNest);
 410       //printf("part de %d\n",startBord);
 411       int curBord = startBord;
 412       bool back = false;
 413       swdData[curBord].precParc = -1;
 414       swdData[curBord].suivParc = -1;
 415       int curStartPt=getEdge(curBord).st;
 416       do
 417             {
 418               int cPt = getEdge(curBord).en;
 419               int nb = curBord;
 420         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
 421               do
 422         {
 423           int nnb = CycleNextAt (cPt, nb);
 424           if (nnb == nb)
 425           {
 426             // cul-de-sac
 427             nb = -1;
 428             break;
 429           }
 430           nb = nnb;
 431           if (nb < 0 || nb == curBord)
 432             break;
 433         }
 434               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 435
 436               if (nb < 0 || nb == curBord)
 437         {
 438           if (back == false)
 439           {
 440             if (curBord == startBord || curBord < 0)
 441             {
 442               // probleme -> on vire le moveto
 443               //                                                      dest->descr_nb--;
 444             }
 445             else
 446             {
 447               bool escapePath=false;
 448               int tb=curBord;
 449               while ( tb >= 0 && tb < numberOfEdges() ) {
 450                 if ( ebData[tb].pathID == wildPath ) {
 451                   escapePath=true;
 452                   break;
 453                 }
 454                 tb=swdData[tb].precParc;
 455               }
 456               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
 457               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
 458               contStart[nbNest]=dest->descr_cmd.size();
 459               if ( escapePath ) {
 460                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
 461               } else {
 462                 nesting[nbNest++]=dadContour;
 463               }
 464               swdData[curBord].suivParc = -1;
 465               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 466             }
 467             //                                              dest->Close();
 468           }
 469           back = true;
 470           // retour en arriere
 471           curBord = swdData[curBord].precParc;
 472           //printf("retour vers %d\n",curBord);
 473           if (curBord < 0)
 474             break;
 475         }
 476               else
 477         {
 478           if (back)
 479           {
 480             back = false;
 481             startBord = nb;
 482             curStartPt=getEdge(nb).st;
 483           } else {
 484             if ( getEdge(curBord).en == curStartPt ) {
 485               //printf("contour %i ",curStartPt);
 486
 487               bool escapePath=false;
 488               int tb=curBord;
 489               while ( tb >= 0 && tb < numberOfEdges() ) {
 490                 if ( ebData[tb].pathID == wildPath ) {
 491                   escapePath=true;
 492                   break;
 493                 }
 494                 tb=swdData[tb].precParc;
 495               }
 496               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
 497               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
 498               contStart[nbNest]=dest->descr_cmd.size();
 499               if ( escapePath ) {
 500                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
 501               } else {
 502                 nesting[nbNest++]=dadContour;
 503               }
 504
 505               swdData[curBord].suivParc = -1;
 506               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 507               startBord=nb;
 508             }
 509           }
 510           swdData[nb].misc = (void *) (1+nbNest);
 511           swdData[nb].ind = searchInd++;
 512           swdData[nb].precParc = curBord;
 513           swdData[curBord].suivParc = nb;
 514           curBord = nb;
 515           //printf("suite %d\n",curBord);
 516         }
 517             }
 518       while (1 /*swdData[curBord].precParc >= 0 */ );
 519       // fin du cas non-oriente
 520     }
 521   }
 522   while (lastPtUsed < numberOfPoints());
 523
 524   MakePointData (false);
 525   MakeEdgeData (false);
 526   MakeSweepDestData (false);
 527 }
 528
 529
 530 int
 531 Shape::MakeTweak (int mode, Shape *a, double power, JoinType join, double miter, bool do_profile, Geom::Point c, Geom::Point vector, double radius, Geom::Matrix *i2doc)
 532 {
 533   Reset (0, 0);
 534   MakeBackData(a->_has_back_data);
 535
 536         bool done_something = false;
 537
 538   if (power == 0)
 539   {
 540     _pts = a->_pts;
 541     if (numberOfPoints() > maxPt)
 542     {
 543       maxPt = numberOfPoints();
 544       if (_has_points_data) {
 545         pData.resize(maxPt);
 546         _point_data_initialised = false;
 547         _bbox_up_to_date = false;
 548         }
 549     }
 550
 551     _aretes = a->_aretes;
 552     if (numberOfEdges() > maxAr)
 553     {
 554       maxAr = numberOfEdges();
 555       if (_has_edges_data)
 556               eData.resize(maxAr);
 557       if (_has_sweep_src_data)
 558         swsData.resize(maxAr);
 559       if (_has_sweep_dest_data)
 560         swdData.resize(maxAr);
 561       if (_has_raster_data)
 562         swrData.resize(maxAr);
 563       if (_has_back_data)
 564         ebData.resize(maxAr);
 565     }
 566     return 0;
 567   }
 568   if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
 569     return shape_input_err;
 570
 571   a->SortEdges ();
 572
 573   a->MakeSweepDestData (true);
 574   a->MakeSweepSrcData (true);
 575
 576   for (int i = 0; i < a->numberOfEdges(); i++)
 577   {
 578     int stB = -1, enB = -1;
 579     if (power <= 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen)  {
 580       stB = a->CyclePrevAt (a->getEdge(i).st, i);
 581       enB = a->CycleNextAt (a->getEdge(i).en, i);
 582     } else {
 583       stB = a->CycleNextAt (a->getEdge(i).st, i);
 584       enB = a->CyclePrevAt (a->getEdge(i).en, i);
 585     }
 586
 587     Geom::Point stD, seD, enD;
 588     double stL, seL, enL;
 589     stD = a->getEdge(stB).dx;
 590     seD = a->getEdge(i).dx;
 591     enD = a->getEdge(enB).dx;
 592
 593     stL = sqrt (dot(stD,stD));
 594     seL = sqrt (dot(seD,seD));
 595     enL = sqrt (dot(enD,enD));
 596     MiscNormalize (stD);
 597     MiscNormalize (enD);
 598     MiscNormalize (seD);
 599
 600     Geom::Point ptP;
 601     int stNo, enNo;
 602     ptP = a->getPoint(a->getEdge(i).st).x;
 603
 604         Geom::Point to_center = ptP * (*i2doc) - c;
 605         Geom::Point to_center_normalized = (1/Geom::L2(to_center)) * to_center;
 606
 607                 double this_power;
 608                 if (do_profile && i2doc) {
 609                         double alpha = 1;
 610                         double x;
 611                 if (mode == tweak_mode_repel) {
 612                                 x = (Geom::L2(to_center)/radius);
 613                         } else {
 614                                 x = (Geom::L2(ptP * (*i2doc) - c)/radius);
 615                         }
 616                         if (x > 1) {
 617                                 this_power = 0;
 618                         } else if (x <= 0) {
 619                 if (mode == tweak_mode_repel) {
 620                                         this_power = 0;
 621                                 } else {
 622                                         this_power = power;
 623                                 }
 624                         } else {
 625                                 this_power = power * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5);
 626                         }
 627                 } else {
 628                 if (mode == tweak_mode_repel) {
 629                                 this_power = 0;
 630                         } else {
 631                                 this_power = power;
 632                         }
 633                 }
 634
 635                 if (this_power != 0)
 636                         done_something = true;
 637
 638                 double scaler = 1 / (*i2doc).descrim();
 639
 640                 Geom::Point this_vec(0,0);
 641     if (mode == tweak_mode_push) {
 642                         Geom::Matrix tovec (*i2doc);
 643                         tovec[4] = tovec[5] = 0;
 644                         tovec = tovec.inverse();
 645                         this_vec = this_power * (vector * tovec) ;
 646                 } else if (mode == tweak_mode_repel) {
 647                         this_vec = this_power * scaler * to_center_normalized;
 648                 } else if (mode == tweak_mode_roughen) {
 649                 double angle = g_random_double_range(0, 2*M_PI);
 650                 this_vec = g_random_double_range(0, 1) * this_power * scaler * Geom::Point(sin(angle), cos(angle));
 651                 }
 652
 653     int   usePathID=-1;
 654     int   usePieceID=0;
 655     double useT=0.0;
 656     if ( a->_has_back_data ) {
 657       if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
 658            && a->ebData[stB].tEn == a->ebData[i].tSt ) {
 659         usePathID=a->ebData[i].pathID;
 660         usePieceID=a->ebData[i].pieceID;
 661         useT=a->ebData[i].tSt;
 662       } else {
 663         usePathID=a->ebData[i].pathID;
 664         usePieceID=0;
 665         useT=0;
 666       }
 667     }
 668
 669                 if (mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen) {
 670                         Path::DoLeftJoin (this, 0, join, ptP+this_vec, stD+this_vec, seD+this_vec, miter, stL, seL,
 671                                                                                                 stNo, enNo,usePathID,usePieceID,useT);
 672                         a->swsData[i].stPt = enNo;
 673                         a->swsData[stB].enPt = stNo;
 674                 } else {
 675                         if (power > 0) {
 676                                 Path::DoRightJoin (this, this_power * scaler, join, ptP, stD, seD, miter, stL, seL,
 677                                                                                                          stNo, enNo,usePathID,usePieceID,useT);
 678                                 a->swsData[i].stPt = enNo;
 679                                 a->swsData[stB].enPt = stNo;
 680                         } else {
 681                                 Path::DoLeftJoin (this, -this_power * scaler, join, ptP, stD, seD, miter, stL, seL,
 682                                                                                                         stNo, enNo,usePathID,usePieceID,useT);
 683                                 a->swsData[i].stPt = enNo;
 684                                 a->swsData[stB].enPt = stNo;
 685                         }
 686                 }
 687   }
 688
 689   if (power < 0 || mode == tweak_mode_push || mode == tweak_mode_repel || mode == tweak_mode_roughen)
 690   {
 691     for (int i = 0; i < numberOfEdges(); i++)
 692       Inverse (i);
 693   }
 694
 695   if ( _has_back_data ) {
 696     for (int i = 0; i < a->numberOfEdges(); i++)
 697     {
 698       int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 699       ebData[nEd]=a->ebData[i];
 700     }
 701   } else {
 702     for (int i = 0; i < a->numberOfEdges(); i++)
 703     {
 704       AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 705     }
 706   }
 707
 708   a->MakeSweepSrcData (false);
 709   a->MakeSweepDestData (false);
 710
 711   return (done_something? 0 : shape_nothing_to_do);
 712 }
 713
 714
 715 // offsets
 716 // take each edge, offset it, and make joins with previous at edge start and next at edge end (previous and
 717 // next being with respect to the clockwise order)
 718 // you gotta be very careful with the join, as anything but the right one will fuck everything up
 719 // see PathStroke.cpp for the "right" joins
 720 int
 721 Shape::MakeOffset (Shape * a, double dec, JoinType join, double miter, bool do_profile, double cx, double cy, double radius, Geom::Matrix *i2doc)
 722 {
 723   Reset (0, 0);
 724   MakeBackData(a->_has_back_data);
 725
 726         bool done_something = false;
 727
 728   if (dec == 0)
 729   {
 730     _pts = a->_pts;
 731     if (numberOfPoints() > maxPt)
 732     {
 733       maxPt = numberOfPoints();
 734       if (_has_points_data) {
 735         pData.resize(maxPt);
 736         _point_data_initialised = false;
 737         _bbox_up_to_date = false;
 738         }
 739     }
 740
 741     _aretes = a->_aretes;
 742     if (numberOfEdges() > maxAr)
 743     {
 744       maxAr = numberOfEdges();
 745       if (_has_edges_data)
 746         eData.resize(maxAr);
 747       if (_has_sweep_src_data)
 748         swsData.resize(maxAr);
 749       if (_has_sweep_dest_data)
 750         swdData.resize(maxAr);
 751       if (_has_raster_data)
 752         swrData.resize(maxAr);
 753       if (_has_back_data)
 754         ebData.resize(maxAr);
 755     }
 756     return 0;
 757   }
 758   if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
 759     return shape_input_err;
 760
 761   a->SortEdges ();
 762
 763   a->MakeSweepDestData (true);
 764   a->MakeSweepSrcData (true);
 765
 766   for (int i = 0; i < a->numberOfEdges(); i++)
 767   {
 768     //              int    stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/;
 769     int stB = -1, enB = -1;
 770     if (dec > 0)
 771     {
 772       stB = a->CycleNextAt (a->getEdge(i).st, i);
 773       enB = a->CyclePrevAt (a->getEdge(i).en, i);
 774     }
 775     else
 776     {
 777       stB = a->CyclePrevAt (a->getEdge(i).st, i);
 778       enB = a->CycleNextAt (a->getEdge(i).en, i);
 779     }
 780
 781     Geom::Point stD, seD, enD;
 782     double stL, seL, enL;
 783     stD = a->getEdge(stB).dx;
 784     seD = a->getEdge(i).dx;
 785     enD = a->getEdge(enB).dx;
 786
 787     stL = sqrt (dot(stD,stD));
 788     seL = sqrt (dot(seD,seD));
 789     enL = sqrt (dot(enD,enD));
 790     MiscNormalize (stD);
 791     MiscNormalize (enD);
 792     MiscNormalize (seD);
 793
 794     Geom::Point ptP;
 795     int stNo, enNo;
 796     ptP = a->getPoint(a->getEdge(i).st).x;
 797
 798                 double this_dec;
 799                 if (do_profile && i2doc) {
 800                         double alpha = 1;
 801                         double x = (Geom::L2(ptP * (*i2doc) - Geom::Point(cx,cy))/radius);
 802                         if (x > 1) {
 803                                 this_dec = 0;
 804                         } else if (x <= 0) {
 805                                 this_dec = dec;
 806                         } else {
 807                                 this_dec = dec * (0.5 * cos (M_PI * (pow(x, alpha))) + 0.5);
 808                         }
 809                 } else {
 810                         this_dec = dec;
 811                 }
 812
 813                 if (this_dec != 0)
 814                         done_something = true;
 815
 816     int   usePathID=-1;
 817     int   usePieceID=0;
 818     double useT=0.0;
 819     if ( a->_has_back_data ) {
 820       if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
 821            && a->ebData[stB].tEn == a->ebData[i].tSt ) {
 822         usePathID=a->ebData[i].pathID;
 823         usePieceID=a->ebData[i].pieceID;
 824         useT=a->ebData[i].tSt;
 825       } else {
 826         usePathID=a->ebData[i].pathID;
 827         usePieceID=0;
 828         useT=0;
 829       }
 830     }
 831     if (dec > 0)
 832     {
 833       Path::DoRightJoin (this, this_dec, join, ptP, stD, seD, miter, stL, seL,
 834                          stNo, enNo,usePathID,usePieceID,useT);
 835       a->swsData[i].stPt = enNo;
 836       a->swsData[stB].enPt = stNo;
 837     }
 838     else
 839     {
 840       Path::DoLeftJoin (this, -this_dec, join, ptP, stD, seD, miter, stL, seL,
 841                         stNo, enNo,usePathID,usePieceID,useT);
 842       a->swsData[i].stPt = enNo;
 843       a->swsData[stB].enPt = stNo;
 844     }
 845   }
 846
 847   if (dec < 0)
 848   {
 849     for (int i = 0; i < numberOfEdges(); i++)
 850       Inverse (i);
 851   }
 852
 853   if ( _has_back_data ) {
 854     for (int i = 0; i < a->numberOfEdges(); i++)
 855     {
 856       int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 857       ebData[nEd]=a->ebData[i];
 858     }
 859   } else {
 860     for (int i = 0; i < a->numberOfEdges(); i++)
 861     {
 862       AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 863     }
 864   }
 865
 866   a->MakeSweepSrcData (false);
 867   a->MakeSweepDestData (false);
 868
 869   return (done_something? 0 : shape_nothing_to_do);
 870 }
 871
 872
 873
 874 // we found a contour, now reassemble the edges on it, instead of dumping them in the Path "dest" as a
 875 // polyline. since it was a DFS, the precParc and suivParc make a nice doubly-linked list of the edges in
 876 // the contour. the first and last edges of the contour are startBord and curBord
 877 void
 878 Shape::AddContour (Path * dest, int nbP, Path * *orig, int startBord, int curBord, bool splitWhenForced)
 879 {
 880   int bord = startBord;
 881
 882   {
 883     dest->MoveTo (getPoint(getEdge(bord).st).x);
 884   }
 885
 886   while (bord >= 0)
 887   {
 888     int nPiece = ebData[bord].pieceID;
 889     int nPath = ebData[bord].pathID;
 890
 891     if (nPath < 0 || nPath >= nbP || orig[nPath] == NULL)
 892     {
 893       // segment batard
 894       dest->LineTo (getPoint(getEdge(bord).en).x);
 895       bord = swdData[bord].suivParc;
 896     }
 897     else
 898     {
 899       Path *from = orig[nPath];
 900       if (nPiece < 0 || nPiece >= int(from->descr_cmd.size()))
 901             {
 902               // segment batard
 903               dest->LineTo (getPoint(getEdge(bord).en).x);
 904               bord = swdData[bord].suivParc;
 905             }
 906       else
 907             {
 908               int nType = from->descr_cmd[nPiece]->getType();
 909               if (nType == descr_close || nType == descr_moveto
 910             || nType == descr_forced)
 911         {
 912           // devrait pas arriver
 913           dest->LineTo (getPoint(getEdge(bord).en).x);
 914           bord = swdData[bord].suivParc;
 915         }
 916               else if (nType == descr_lineto)
 917         {
 918           bord = ReFormeLineTo (bord, curBord, dest, from);
 919         }
 920               else if (nType == descr_arcto)
 921         {
 922           bord = ReFormeArcTo (bord, curBord, dest, from);
 923         }
 924               else if (nType == descr_cubicto)
 925         {
 926           bord = ReFormeCubicTo (bord, curBord, dest, from);
 927         }
 928               else if (nType == descr_bezierto)
 929         {
 930           PathDescrBezierTo* nBData =
 931             dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
 932
 933           if (nBData->nb == 0)
 934           {
 935             bord = ReFormeLineTo (bord, curBord, dest, from);
 936           }
 937           else
 938           {
 939             bord = ReFormeBezierTo (bord, curBord, dest, from);
 940           }
 941         }
 942               else if (nType == descr_interm_bezier)
 943         {
 944           bord = ReFormeBezierTo (bord, curBord, dest, from);
 945         }
 946               else
 947         {
 948           // devrait pas arriver non plus
 949           dest->LineTo (getPoint(getEdge(bord).en).x);
 950           bord = swdData[bord].suivParc;
 951         }
 952               if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) {
 953           dest->ForcePoint ();
 954         } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2)  {
 955           if ( splitWhenForced ) {
 956             // pour les coupures
 957             dest->ForcePoint ();
 958          } else {
 959             if ( _has_back_data ) {
 960               int   prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST];
 961               int   nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST];
 962               if ( getEdge(prevEdge).en != getEdge(bord).st ) {
 963                 int  swai=prevEdge;prevEdge=nextEdge;nextEdge=swai;
 964               }
 965               if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID  && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) {
 966                 if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) {
 967                 } else {
 968                   dest->ForcePoint ();
 969                 }
 970               } else {
 971                 dest->ForcePoint ();
 972               }
 973             } else {
 974               dest->ForcePoint ();
 975             }
 976           }
 977         }
 978       }
 979     }
 980   }
 981   dest->Close ();
 982 }
 983
 984 int
 985 Shape::ReFormeLineTo (int bord, int /*curBord*/, Path * dest, Path * /*orig*/)
 986 {
 987   int nPiece = ebData[bord].pieceID;
 988   int nPath = ebData[bord].pathID;
 989   double /*ts=ebData[bord].tSt, */ te = ebData[bord].tEn;
 990   Geom::Point nx = getPoint(getEdge(bord).en).x;
 991   bord = swdData[bord].suivParc;
 992   while (bord >= 0)
 993   {
 994     if (getPoint(getEdge(bord).st).totalDegree() > 2
 995         || getPoint(getEdge(bord).st).oldDegree > 2)
 996     {
 997       break;
 998     }
 999     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
1000     {
1001       if (fabs (te - ebData[bord].tSt) > 0.0001)
1002         break;
1003       nx = getPoint(getEdge(bord).en).x;
1004       te = ebData[bord].tEn;
1005     }
1006     else
1007     {
1008       break;
1009     }
1010     bord = swdData[bord].suivParc;
1011   }
1012   {
1013     dest->LineTo (nx);
1014   }
1015   return bord;
1016 }
1017
1018 int
1019 Shape::ReFormeArcTo (int bord, int /*curBord*/, Path * dest, Path * from)
1020 {
1021   int nPiece = ebData[bord].pieceID;
1022   int nPath = ebData[bord].pathID;
1023   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
1024   //      double  px=pts[getEdge(bord).st].x,py=pts[getEdge(bord).st].y;
1025   Geom::Point nx = getPoint(getEdge(bord).en).x;
1026   bord = swdData[bord].suivParc;
1027   while (bord >= 0)
1028   {
1029     if (getPoint(getEdge(bord).st).totalDegree() > 2
1030         || getPoint(getEdge(bord).st).oldDegree > 2)
1031     {
1032       break;
1033     }
1034     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
1035     {
1036       if (fabs (te - ebData[bord].tSt) > 0.0001)
1037             {
1038               break;
1039             }
1040       nx = getPoint(getEdge(bord).en).x;
1041       te = ebData[bord].tEn;
1042     }
1043     else
1044     {
1045       break;
1046     }
1047     bord = swdData[bord].suivParc;
1048   }
1049   double sang, eang;
1050   PathDescrArcTo* nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
1051   bool nLarge = nData->large;
1052   bool nClockwise = nData->clockwise;
1053   Path::ArcAngles (from->PrevPoint (nPiece - 1), nData->p,nData->rx,nData->ry,nData->angle, nLarge, nClockwise,  sang, eang);
1054   if (nClockwise)
1055   {
1056     if (sang < eang)
1057       sang += 2 * M_PI;
1058   }
1059   else
1060   {
1061     if (sang > eang)
1062       sang -= 2 * M_PI;
1063   }
1064   double delta = eang - sang;
1065   double ndelta = delta * (te - ts);
1066   if (ts > te)
1067     nClockwise = !nClockwise;
1068   if (ndelta < 0)
1069     ndelta = -ndelta;
1070   if (ndelta > M_PI)
1071     nLarge = true;
1072   else
1073     nLarge = false;
1074   /*    if ( delta < 0 ) delta=-delta;
1075         if ( ndelta < 0 ) ndelta=-ndelta;
1076         if ( ( delta < M_PI && ndelta < M_PI ) || ( delta >= M_PI && ndelta >= M_PI ) ) {
1077                 if ( ts < te ) {
1078                 } else {
1079                         nClockwise=!(nClockwise);
1080                 }
1081         } else {
1082     //          nLarge=!(nLarge);
1083                 nLarge=false; // c'est un sous-segment -> l'arc ne peut que etre plus petit
1084                 if ( ts < te ) {
1085                 } else {
1086                         nClockwise=!(nClockwise);
1087                 }
1088         }*/
1089   {
1090     PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
1091     dest->ArcTo (nx, nData->rx,nData->ry,nData->angle, nLarge, nClockwise);
1092   }
1093   return bord;
1094 }
1095
1096 int
1097 Shape::ReFormeCubicTo (int bord, int /*curBord*/, Path * dest, Path * from)
1098 {
1099   int nPiece = ebData[bord].pieceID;
1100   int nPath = ebData[bord].pathID;
1101   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
1102   Geom::Point nx = getPoint(getEdge(bord).en).x;
1103   bord = swdData[bord].suivParc;
1104   while (bord >= 0)
1105   {
1106     if (getPoint(getEdge(bord).st).totalDegree() > 2
1107         || getPoint(getEdge(bord).st).oldDegree > 2)
1108     {
1109       break;
1110     }
1111     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
1112     {
1113       if (fabs (te - ebData[bord].tSt) > 0.0001)
1114             {
1115               break;
1116             }
1117       nx = getPoint(getEdge(bord).en).x;
1118       te = ebData[bord].tEn;
1119     }
1120     else
1121     {
1122       break;
1123     }
1124     bord = swdData[bord].suivParc;
1125   }
1126   Geom::Point prevx = from->PrevPoint (nPiece - 1);
1127
1128   Geom::Point sDx, eDx;
1129   {
1130     PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(from->descr_cmd[nPiece]);
1131     Path::CubicTangent (ts, sDx, prevx,nData->start,nData->p,nData->end);
1132     Path::CubicTangent (te, eDx, prevx,nData->start,nData->p,nData->end);
1133   }
1134   sDx *= (te - ts);
1135   eDx *= (te - ts);
1136   {
1137     dest->CubicTo (nx,sDx,eDx);
1138   }
1139   return bord;
1140 }
1141
1142 int
1143 Shape::ReFormeBezierTo (int bord, int /*curBord*/, Path * dest, Path * from)
1144 {
1145   int nPiece = ebData[bord].pieceID;
1146   int nPath = ebData[bord].pathID;
1147   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
1148   int ps = nPiece, pe = nPiece;
1149   Geom::Point px = getPoint(getEdge(bord).st).x;
1150   Geom::Point nx = getPoint(getEdge(bord).en).x;
1151   int inBezier = -1, nbInterm = -1;
1152   int typ;
1153   typ = from->descr_cmd[nPiece]->getType();
1154   PathDescrBezierTo *nBData = NULL;
1155   if (typ == descr_bezierto)
1156   {
1157     nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
1158     inBezier = nPiece;
1159     nbInterm = nBData->nb;
1160   }
1161   else
1162   {
1163     int n = nPiece - 1;
1164     while (n > 0)
1165     {
1166       typ = from->descr_cmd[n]->getType();
1167       if (typ == descr_bezierto)
1168       {
1169         inBezier = n;
1170         nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[n]);
1171         nbInterm = nBData->nb;
1172         break;
1173       }
1174       n--;
1175     }
1176     if (inBezier < 0)
1177     {
1178       bord = swdData[bord].suivParc;
1179       dest->LineTo (nx);
1180       return bord;
1181     }
1182   }
1183   bord = swdData[bord].suivParc;
1184   while (bord >= 0)
1185   {
1186     if (getPoint(getEdge(bord).st).totalDegree() > 2
1187         || getPoint(getEdge(bord).st).oldDegree > 2)
1188     {
1189       break;
1190     }
1191     if (ebData[bord].pathID == nPath)
1192     {
1193       if (ebData[bord].pieceID < inBezier
1194           || ebData[bord].pieceID >= inBezier + nbInterm)
1195         break;
1196       if (ebData[bord].pieceID == pe
1197           && fabs (te - ebData[bord].tSt) > 0.0001)
1198         break;
1199       if (ebData[bord].pieceID != pe
1200           && (ebData[bord].tSt > 0.0001 && ebData[bord].tSt < 0.9999))
1201         break;
1202       if (ebData[bord].pieceID != pe && (te > 0.0001 && te < 0.9999))
1203         break;
1204       nx = getPoint(getEdge(bord).en).x;
1205       te = ebData[bord].tEn;
1206       pe = ebData[bord].pieceID;
1207     }
1208     else
1209     {
1210       break;
1211     }
1212     bord = swdData[bord].suivParc;
1213   }
1214
1215   g_return_val_if_fail(nBData != NULL, 0);
1216
1217   if (pe == ps)
1218   {
1219     ReFormeBezierChunk (px, nx, dest, inBezier, nbInterm, from, ps,
1220                         ts, te);
1221   }
1222   else if (ps < pe)
1223   {
1224     if (ts < 0.0001)
1225     {
1226       if (te > 0.9999)
1227       {
1228         dest->BezierTo (nx);
1229         for (int i = ps; i <= pe; i++)
1230         {
1231           PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1232           dest->IntermBezierTo (nData->p);
1233         }
1234         dest->EndBezierTo ();
1235       }
1236       else
1237       {
1238         Geom::Point tx;
1239         {
1240           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1241           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1242           tx = (pnData->p + psData->p) / 2;
1243         }
1244         dest->BezierTo (tx);
1245         for (int i = ps; i < pe; i++)
1246         {
1247           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1248           dest->IntermBezierTo (nData->p);
1249         }
1250         dest->EndBezierTo ();
1251         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1252                             from, pe, 0.0, te);
1253       }
1254     }
1255     else
1256     {
1257       if (te > 0.9999)
1258       {
1259         Geom::Point tx;
1260         {
1261           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1262           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1263           tx = (psData->p +  pnData->p) / 2;
1264         }
1265         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1266                             from, ps, ts, 1.0);
1267         dest->BezierTo (nx);
1268         for (int i = ps + 1; i <= pe; i++)
1269         {
1270           PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1271           dest->IntermBezierTo (nData->p);
1272         }
1273         dest->EndBezierTo ();
1274       }
1275       else
1276       {
1277         Geom::Point tx;
1278         {
1279           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1280           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1281           tx = (pnData->p + psData->p) / 2;
1282         }
1283         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1284                             from, ps, ts, 1.0);
1285         {
1286           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1287           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1288           tx = (pnData->p + psData->p) / 2;
1289         }
1290          dest->BezierTo (tx);
1291         for (int i = ps + 1; i <= pe; i++)
1292         {
1293           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1294           dest->IntermBezierTo (nData->p);
1295         }
1296         dest->EndBezierTo ();
1297         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1298                             from, pe, 0.0, te);
1299       }
1300     }
1301   }
1302   else
1303   {
1304     if (ts > 0.9999)
1305     {
1306       if (te < 0.0001)
1307       {
1308         dest->BezierTo (nx);
1309         for (int i = ps; i >= pe; i--)
1310         {
1311           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1312           dest->IntermBezierTo (nData->p);
1313         }
1314         dest->EndBezierTo ();
1315       }
1316       else
1317       {
1318         Geom::Point tx;
1319         {
1320           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1321           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1322           tx = (pnData->p + psData->p) / 2;
1323         }
1324         dest->BezierTo (tx);
1325         for (int i = ps; i > pe; i--)
1326         {
1327           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1328           dest->IntermBezierTo (nData->p);
1329         }
1330         dest->EndBezierTo ();
1331         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1332                             from, pe, 1.0, te);
1333       }
1334     }
1335     else
1336     {
1337       if (te < 0.0001)
1338       {
1339         Geom::Point tx;
1340         {
1341           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1342           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1343           tx = (pnData->p + psData->p) / 2;
1344         }
1345          ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1346                             from, ps, ts, 0.0);
1347         dest->BezierTo (nx);
1348         for (int i = ps + 1; i >= pe; i--)
1349         {
1350           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1351           dest->IntermBezierTo (nData->p);
1352         }
1353         dest->EndBezierTo ();
1354       }
1355       else
1356       {
1357         Geom::Point tx;
1358         {
1359           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1360           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1361           tx = (pnData->p + psData->p) / 2;
1362         }
1363         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1364                             from, ps, ts, 0.0);
1365         {
1366           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1367           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1368           tx = (pnData->p + psData->p) / 2;
1369         }
1370         dest->BezierTo (tx);
1371         for (int i = ps + 1; i > pe; i--)
1372         {
1373           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1374           dest->IntermBezierTo (nData->p);
1375         }
1376         dest->EndBezierTo ();
1377         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1378                             from, pe, 1.0, te);
1379       }
1380     }
1381   }
1382   return bord;
1383 }
1384
1385 void
1386 Shape::ReFormeBezierChunk (Geom::Point px, Geom::Point nx,
1387                            Path * dest, int inBezier, int nbInterm,
1388                            Path * from, int p, double ts, double te)
1389 {
1390   PathDescrBezierTo* nBData = dynamic_cast<PathDescrBezierTo*>(from->descr_cmd[inBezier]);
1391   Geom::Point bstx = from->PrevPoint (inBezier - 1);
1392   Geom::Point benx = nBData->p;
1393
1394   Geom::Point mx;
1395   if (p == inBezier)
1396   {
1397     // premier bout
1398     if (nbInterm <= 1)
1399     {
1400       // seul bout de la spline
1401       PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1402       mx = nData->p;
1403     }
1404     else
1405     {
1406       // premier bout d'une spline qui en contient plusieurs
1407       PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1408       mx = nData->p;
1409       nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+2]);
1410       benx = (nData->p + mx) / 2;
1411     }
1412   }
1413   else if (p == inBezier + nbInterm - 1)
1414   {
1415     // dernier bout
1416     // si nbInterm == 1, le cas a deja ete traite
1417     // donc dernier bout d'une spline qui en contient plusieurs
1418     PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm]);
1419     mx = nData->p;
1420     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm-1]);
1421     bstx = (nData->p + mx) / 2;
1422   }
1423   else
1424   {
1425     // la spline contient forcément plusieurs bouts, et ce n'est ni le premier ni le dernier
1426     PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+1]);
1427     mx = nData->p;
1428     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p]);
1429     bstx = (nData->p + mx) / 2;
1430     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+2]);
1431     benx = (nData->p + mx) / 2;
1432   }
1433   Geom::Point cx;
1434   {
1435     Path::QuadraticPoint ((ts + te) / 2, cx, bstx, mx, benx);
1436   }
1437   cx = 2 * cx - (px + nx) / 2;
1438   {
1439     dest->BezierTo (nx);
1440     dest->IntermBezierTo (cx);
1441     dest->EndBezierTo ();
1442   }
1443 }
1444
1445 #undef MiscNormalize