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