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   if (directedEulerian(this) == false)
  39     return;
  40
  41   // prepare
  42   dest->Reset ();
  43
  44   MakePointData (true);
  45   MakeEdgeData (true);
  46   MakeSweepDestData (true);
  47
  48   for (int i = 0; i < numberOfPoints(); i++)
  49   {
  50     pData[i].rx[0] = Round (getPoint(i).x[0]);
  51     pData[i].rx[1] = Round (getPoint(i).x[1]);
  52   }
  53   for (int i = 0; i < numberOfEdges(); i++)
  54   {
  55     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
  56   }
  57
  58   // sort edge clockwise, with the closest after midnight being first in the doubly-linked list
  59   // that's vital to the algorithm...
  60   SortEdges ();
  61
  62   // depth-first search implies: we make a stack of edges traversed.
  63   // precParc: previous in the stack
  64   // suivParc: next in the stack
  65   for (int i = 0; i < numberOfEdges(); i++)
  66   {
  67     swdData[i].misc = 0;
  68     swdData[i].precParc = swdData[i].suivParc = -1;
  69   }
  70
  71   int searchInd = 0;
  72
  73   int lastPtUsed = 0;
  74   do
  75   {
  76     // first get a starting point, and a starting edge
  77     // -> take the upper left point, and take its first edge
  78     // points traversed have swdData[].misc != 0, so it's easy
  79     int startBord = -1;
  80     {
  81       int fi = 0;
  82       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
  83       {
  84         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
  85           break;
  86       }
  87       lastPtUsed = fi + 1;
  88       if (fi < numberOfPoints())
  89       {
  90         int bestB = getPoint(fi).incidentEdge[FIRST];
  91         while (bestB >= 0 && getEdge(bestB).st != fi)
  92           bestB = NextAt (fi, bestB);
  93         if (bestB >= 0)
  94               {
  95           startBord = bestB;
  96           dest->MoveTo (getPoint(getEdge(startBord).en).x);
  97               }
  98       }
  99     }
 100     // and walk the graph, doing contours when needed
 101     if (startBord >= 0)
 102     {
 103       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 104       swdData[startBord].misc = (void *) 1;
 105       //                      printf("part de %d\n",startBord);
 106       int curBord = startBord;
 107       bool back = false;
 108       swdData[curBord].precParc = -1;
 109       swdData[curBord].suivParc = -1;
 110       do
 111             {
 112               int cPt = getEdge(curBord).en;
 113               int nb = curBord;
 114         //                              printf("de curBord= %d au point %i  -> ",curBord,cPt);
 115         // get next edge
 116               do
 117         {
 118           int nnb = CycleNextAt (cPt, nb);
 119           if (nnb == nb)
 120           {
 121             // cul-de-sac
 122             nb = -1;
 123             break;
 124           }
 125           nb = nnb;
 126           if (nb < 0 || nb == curBord)
 127             break;
 128         }
 129               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 130
 131               if (nb < 0 || nb == curBord)
 132         {
 133           // no next edge: end of this contour, we get back
 134           if (back == false)
 135             dest->Close ();
 136           back = true;
 137           // retour en arriere
 138           curBord = swdData[curBord].precParc;
 139           //                                      printf("retour vers %d\n",curBord);
 140           if (curBord < 0)
 141             break;
 142         }
 143               else
 144         {
 145           // new edge, maybe for a new contour
 146           if (back)
 147           {
 148             // we were backtracking, so if we have a new edge, that means we're creating a new contour
 149             dest->MoveTo (getPoint(cPt).x);
 150             back = false;
 151           }
 152           swdData[nb].misc = (void *) 1;
 153           swdData[nb].ind = searchInd++;
 154           swdData[nb].precParc = curBord;
 155           swdData[curBord].suivParc = nb;
 156           curBord = nb;
 157           //                                      printf("suite %d\n",curBord);
 158           {
 159             // add that edge
 160             dest->LineTo (getPoint(getEdge(nb).en).x);
 161           }
 162         }
 163             }
 164       while (1 /*swdData[curBord].precParc >= 0 */ );
 165       // fin du cas non-oriente
 166     }
 167   }
 168   while (lastPtUsed < numberOfPoints());
 169
 170   MakePointData (false);
 171   MakeEdgeData (false);
 172   MakeSweepDestData (false);
 173 }
 174
 175 // same as before, but each time we have a contour, try to reassemble the segments on it to make chunks of
 176 // the original(s) path(s)
 177 // originals are in the orig array, whose size is nbP
 178 void
 179 Shape::ConvertToForme (Path * dest, int nbP, Path * *orig, bool splitWhenForced)
 180 {
 181   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
 182     return;
 183 //  if (Eulerian (true) == false)
 184 //    return;
 185
 186   if (_has_back_data == false)
 187   {
 188     ConvertToForme (dest);
 189     return;
 190   }
 191
 192   dest->Reset ();
 193
 194   MakePointData (true);
 195   MakeEdgeData (true);
 196   MakeSweepDestData (true);
 197
 198   for (int i = 0; i < numberOfPoints(); i++)
 199   {
 200     pData[i].rx[0] = Round (getPoint(i).x[0]);
 201     pData[i].rx[1] = Round (getPoint(i).x[1]);
 202   }
 203   for (int i = 0; i < numberOfEdges(); i++)
 204   {
 205     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
 206   }
 207
 208   SortEdges ();
 209
 210   for (int i = 0; i < numberOfEdges(); i++)
 211   {
 212     swdData[i].misc = 0;
 213     swdData[i].precParc = swdData[i].suivParc = -1;
 214   }
 215
 216   int searchInd = 0;
 217
 218   int lastPtUsed = 0;
 219   do
 220   {
 221     int startBord = -1;
 222     {
 223       int fi = 0;
 224       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
 225       {
 226         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
 227           break;
 228       }
 229       lastPtUsed = fi + 1;
 230       if (fi < numberOfPoints())
 231       {
 232         int bestB = getPoint(fi).incidentEdge[FIRST];
 233         while (bestB >= 0 && getEdge(bestB).st != fi)
 234           bestB = NextAt (fi, bestB);
 235         if (bestB >= 0)
 236               {
 237           startBord = bestB;
 238               }
 239       }
 240     }
 241     if (startBord >= 0)
 242     {
 243       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 244       swdData[startBord].misc = (void *) 1;
 245       //printf("part de %d\n",startBord);
 246       int curBord = startBord;
 247       bool back = false;
 248       swdData[curBord].precParc = -1;
 249       swdData[curBord].suivParc = -1;
 250       int curStartPt=getEdge(curBord).st;
 251       do
 252             {
 253               int cPt = getEdge(curBord).en;
 254               int nb = curBord;
 255         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
 256               do
 257         {
 258           int nnb = CycleNextAt (cPt, nb);
 259           if (nnb == nb)
 260           {
 261             // cul-de-sac
 262             nb = -1;
 263             break;
 264           }
 265           nb = nnb;
 266           if (nb < 0 || nb == curBord)
 267             break;
 268         }
 269               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 270
 271               if (nb < 0 || nb == curBord)
 272         {
 273           if (back == false)
 274           {
 275             if (curBord == startBord || curBord < 0)
 276             {
 277               // probleme -> on vire le moveto
 278               //                                                      dest->descr_nb--;
 279             }
 280             else
 281             {
 282               swdData[curBord].suivParc = -1;
 283               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 284             }
 285             //                                              dest->Close();
 286           }
 287           back = true;
 288           // retour en arriere
 289           curBord = swdData[curBord].precParc;
 290           //printf("retour vers %d\n",curBord);
 291           if (curBord < 0)
 292             break;
 293         }
 294               else
 295         {
 296           if (back)
 297           {
 298             back = false;
 299             startBord = nb;
 300             curStartPt=getEdge(nb).st;
 301           } else {
 302             if ( getEdge(curBord).en == curStartPt ) {
 303               //printf("contour %i ",curStartPt);
 304               swdData[curBord].suivParc = -1;
 305               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 306               startBord=nb;
 307             }
 308           }
 309           swdData[nb].misc = (void *) 1;
 310           swdData[nb].ind = searchInd++;
 311           swdData[nb].precParc = curBord;
 312           swdData[curBord].suivParc = nb;
 313           curBord = nb;
 314           //printf("suite %d\n",curBord);
 315         }
 316             }
 317       while (1 /*swdData[curBord].precParc >= 0 */ );
 318       // fin du cas non-oriente
 319     }
 320   }
 321   while (lastPtUsed < numberOfPoints());
 322
 323   MakePointData (false);
 324   MakeEdgeData (false);
 325   MakeSweepDestData (false);
 326 }
 327 void
 328 Shape::ConvertToFormeNested (Path * dest, int nbP, Path * *orig, int wildPath,int &nbNest,int *&nesting,int *&contStart,bool splitWhenForced)
 329 {
 330   nesting=NULL;
 331   contStart=NULL;
 332   nbNest=0;
 333
 334   if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
 335     return;
 336   //  if (Eulerian (true) == false)
 337   //    return;
 338
 339   if (_has_back_data == false)
 340   {
 341     ConvertToForme (dest);
 342     return;
 343   }
 344
 345   dest->Reset ();
 346
 347 //  MakePointData (true);
 348   MakeEdgeData (true);
 349   MakeSweepDestData (true);
 350
 351   for (int i = 0; i < numberOfPoints(); i++)
 352   {
 353     pData[i].rx[0] = Round (getPoint(i).x[0]);
 354     pData[i].rx[1] = Round (getPoint(i).x[1]);
 355   }
 356   for (int i = 0; i < numberOfEdges(); i++)
 357   {
 358     eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
 359   }
 360
 361   SortEdges ();
 362
 363   for (int i = 0; i < numberOfEdges(); i++)
 364   {
 365     swdData[i].misc = 0;
 366     swdData[i].precParc = swdData[i].suivParc = -1;
 367   }
 368
 369   int searchInd = 0;
 370
 371   int lastPtUsed = 0;
 372   do
 373   {
 374     int dadContour=-1;
 375     int startBord = -1;
 376     {
 377       int fi = 0;
 378       for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
 379       {
 380         if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
 381           break;
 382       }
 383       {
 384         int askTo = pData[fi].askForWindingB;
 385         if (askTo < 0 || askTo >= numberOfEdges() ) {
 386           dadContour=-1;
 387         } else {
 388           dadContour = GPOINTER_TO_INT(swdData[askTo].misc);
 389           dadContour-=1; // pour compenser le decalage
 390         }
 391       }
 392       lastPtUsed = fi + 1;
 393       if (fi < numberOfPoints())
 394       {
 395         int bestB = getPoint(fi).incidentEdge[FIRST];
 396         while (bestB >= 0 && getEdge(bestB).st != fi)
 397           bestB = NextAt (fi, bestB);
 398         if (bestB >= 0)
 399               {
 400           startBord = bestB;
 401               }
 402       }
 403     }
 404     if (startBord >= 0)
 405     {
 406       // parcours en profondeur pour mettre les leF et riF a leurs valeurs
 407       swdData[startBord].misc = (void *) (1+nbNest);
 408       //printf("part de %d\n",startBord);
 409       int curBord = startBord;
 410       bool back = false;
 411       swdData[curBord].precParc = -1;
 412       swdData[curBord].suivParc = -1;
 413       int curStartPt=getEdge(curBord).st;
 414       do
 415             {
 416               int cPt = getEdge(curBord).en;
 417               int nb = curBord;
 418         //printf("de curBord= %d au point %i  -> ",curBord,cPt);
 419               do
 420         {
 421           int nnb = CycleNextAt (cPt, nb);
 422           if (nnb == nb)
 423           {
 424             // cul-de-sac
 425             nb = -1;
 426             break;
 427           }
 428           nb = nnb;
 429           if (nb < 0 || nb == curBord)
 430             break;
 431         }
 432               while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
 433
 434               if (nb < 0 || nb == curBord)
 435         {
 436           if (back == false)
 437           {
 438             if (curBord == startBord || curBord < 0)
 439             {
 440               // probleme -> on vire le moveto
 441               //                                                      dest->descr_nb--;
 442             }
 443             else
 444             {
 445               bool escapePath=false;
 446               int tb=curBord;
 447               while ( tb >= 0 && tb < numberOfEdges() ) {
 448                 if ( ebData[tb].pathID == wildPath ) {
 449                   escapePath=true;
 450                   break;
 451                 }
 452                 tb=swdData[tb].precParc;
 453               }
 454               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
 455               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
 456               contStart[nbNest]=dest->descr_cmd.size();
 457               if ( escapePath ) {
 458                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
 459               } else {
 460                 nesting[nbNest++]=dadContour;
 461               }
 462               swdData[curBord].suivParc = -1;
 463               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 464             }
 465             //                                              dest->Close();
 466           }
 467           back = true;
 468           // retour en arriere
 469           curBord = swdData[curBord].precParc;
 470           //printf("retour vers %d\n",curBord);
 471           if (curBord < 0)
 472             break;
 473         }
 474               else
 475         {
 476           if (back)
 477           {
 478             back = false;
 479             startBord = nb;
 480             curStartPt=getEdge(nb).st;
 481           } else {
 482             if ( getEdge(curBord).en == curStartPt ) {
 483               //printf("contour %i ",curStartPt);
 484
 485               bool escapePath=false;
 486               int tb=curBord;
 487               while ( tb >= 0 && tb < numberOfEdges() ) {
 488                 if ( ebData[tb].pathID == wildPath ) {
 489                   escapePath=true;
 490                   break;
 491                 }
 492                 tb=swdData[tb].precParc;
 493               }
 494               nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
 495               contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
 496               contStart[nbNest]=dest->descr_cmd.size();
 497               if ( escapePath ) {
 498                 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
 499               } else {
 500                 nesting[nbNest++]=dadContour;
 501               }
 502
 503               swdData[curBord].suivParc = -1;
 504               AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
 505               startBord=nb;
 506             }
 507           }
 508           swdData[nb].misc = (void *) (1+nbNest);
 509           swdData[nb].ind = searchInd++;
 510           swdData[nb].precParc = curBord;
 511           swdData[curBord].suivParc = nb;
 512           curBord = nb;
 513           //printf("suite %d\n",curBord);
 514         }
 515             }
 516       while (1 /*swdData[curBord].precParc >= 0 */ );
 517       // fin du cas non-oriente
 518     }
 519   }
 520   while (lastPtUsed < numberOfPoints());
 521
 522   MakePointData (false);
 523   MakeEdgeData (false);
 524   MakeSweepDestData (false);
 525 }
 526
 527 // offsets
 528 // take each edge, offset it, and make joins with previous at edge start and next at edge end (previous and
 529 // next being with respect to the clockwise order)
 530 // you gotta be very careful with the join, has anything but the right one will fuck everything up
 531 // see PathStroke.cpp for the "right" joins
 532 int
 533 Shape::MakeOffset (Shape * a, double dec, JoinType join, double miter)
 534 {
 535   Reset (0, 0);
 536   MakeBackData(a->_has_back_data);
 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     int   usePathID=-1;
 608     int   usePieceID=0;
 609     double useT=0.0;
 610     if ( a->_has_back_data ) {
 611       if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
 612            && a->ebData[stB].tEn == a->ebData[i].tSt ) {
 613         usePathID=a->ebData[i].pathID;
 614         usePieceID=a->ebData[i].pieceID;
 615         useT=a->ebData[i].tSt;
 616       } else {
 617         usePathID=a->ebData[i].pathID;
 618         usePieceID=0;
 619         useT=0;
 620       }
 621     }
 622     if (dec > 0)
 623     {
 624       Path::DoRightJoin (this, dec, join, ptP, stD, seD, miter, stL, seL,
 625                          stNo, enNo,usePathID,usePieceID,useT);
 626       a->swsData[i].stPt = enNo;
 627       a->swsData[stB].enPt = stNo;
 628     }
 629     else
 630     {
 631       Path::DoLeftJoin (this, -dec, join, ptP, stD, seD, miter, stL, seL,
 632                         stNo, enNo,usePathID,usePieceID,useT);
 633       a->swsData[i].stPt = enNo;
 634       a->swsData[stB].enPt = stNo;
 635     }
 636   }
 637   if (dec < 0)
 638   {
 639     for (int i = 0; i < numberOfEdges(); i++)
 640       Inverse (i);
 641   }
 642   if ( _has_back_data ) {
 643     for (int i = 0; i < a->numberOfEdges(); i++)
 644     {
 645       int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 646       ebData[nEd]=a->ebData[i];
 647     }
 648   } else {
 649     for (int i = 0; i < a->numberOfEdges(); i++)
 650     {
 651       AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
 652     }
 653   }
 654   a->MakeSweepSrcData (false);
 655   a->MakeSweepDestData (false);
 656
 657   return 0;
 658 }
 659
 660 // we found a contour, now reassemble the edges on it, instead of dumping them in the Path "dest" as a
 661 // polyline. since it was a DFS, the precParc and suivParc make a nice doubly-linked list of the edges in
 662 // the contour. the first and last edges of the contour are startBord and curBord
 663 void
 664 Shape::AddContour (Path * dest, int nbP, Path * *orig, int startBord, int curBord, bool splitWhenForced)
 665 {
 666   int bord = startBord;
 667
 668   {
 669     dest->MoveTo (getPoint(getEdge(bord).st).x);
 670   }
 671
 672   while (bord >= 0)
 673   {
 674     int nPiece = ebData[bord].pieceID;
 675     int nPath = ebData[bord].pathID;
 676
 677     if (nPath < 0 || nPath >= nbP || orig[nPath] == NULL)
 678     {
 679       // segment batard
 680       dest->LineTo (getPoint(getEdge(bord).en).x);
 681       bord = swdData[bord].suivParc;
 682     }
 683     else
 684     {
 685       Path *from = orig[nPath];
 686       if (nPiece < 0 || nPiece >= int(from->descr_cmd.size()))
 687             {
 688               // segment batard
 689               dest->LineTo (getPoint(getEdge(bord).en).x);
 690               bord = swdData[bord].suivParc;
 691             }
 692       else
 693             {
 694               int nType = from->descr_cmd[nPiece]->getType();
 695               if (nType == descr_close || nType == descr_moveto
 696             || nType == descr_forced)
 697         {
 698           // devrait pas arriver
 699           dest->LineTo (getPoint(getEdge(bord).en).x);
 700           bord = swdData[bord].suivParc;
 701         }
 702               else if (nType == descr_lineto)
 703         {
 704           bord = ReFormeLineTo (bord, curBord, dest, from);
 705         }
 706               else if (nType == descr_arcto)
 707         {
 708           bord = ReFormeArcTo (bord, curBord, dest, from);
 709         }
 710               else if (nType == descr_cubicto)
 711         {
 712           bord = ReFormeCubicTo (bord, curBord, dest, from);
 713         }
 714               else if (nType == descr_bezierto)
 715         {
 716           PathDescrBezierTo* nBData =
 717             dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
 718
 719           if (nBData->nb == 0)
 720           {
 721             bord = ReFormeLineTo (bord, curBord, dest, from);
 722           }
 723           else
 724           {
 725             bord = ReFormeBezierTo (bord, curBord, dest, from);
 726           }
 727         }
 728               else if (nType == descr_interm_bezier)
 729         {
 730           bord = ReFormeBezierTo (bord, curBord, dest, from);
 731         }
 732               else
 733         {
 734           // devrait pas arriver non plus
 735           dest->LineTo (getPoint(getEdge(bord).en).x);
 736           bord = swdData[bord].suivParc;
 737         }
 738               if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) {
 739           dest->ForcePoint ();
 740         } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2)  {
 741           if ( splitWhenForced ) {
 742             // pour les coupures
 743             dest->ForcePoint ();
 744          } else {
 745             if ( _has_back_data ) {
 746               int   prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST];
 747               int   nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST];
 748               if ( getEdge(prevEdge).en != getEdge(bord).st ) {
 749                 int  swai=prevEdge;prevEdge=nextEdge;nextEdge=swai;
 750               }
 751               if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID  && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) {
 752                 if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) {
 753                 } else {
 754                   dest->ForcePoint ();
 755                 }
 756               } else {
 757                 dest->ForcePoint ();
 758               }
 759             } else {
 760               dest->ForcePoint ();
 761             }
 762           }
 763         }
 764       }
 765     }
 766   }
 767   dest->Close ();
 768 }
 769
 770 int
 771 Shape::ReFormeLineTo (int bord, int curBord, Path * dest, Path * orig)
 772 {
 773   int nPiece = ebData[bord].pieceID;
 774   int nPath = ebData[bord].pathID;
 775   double /*ts=ebData[bord].tSt, */ te = ebData[bord].tEn;
 776   NR::Point nx = getPoint(getEdge(bord).en).x;
 777   bord = swdData[bord].suivParc;
 778   while (bord >= 0)
 779   {
 780     if (getPoint(getEdge(bord).st).totalDegree() > 2
 781         || getPoint(getEdge(bord).st).oldDegree > 2)
 782     {
 783       break;
 784     }
 785     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
 786     {
 787       if (fabs (te - ebData[bord].tSt) > 0.0001)
 788         break;
 789       nx = getPoint(getEdge(bord).en).x;
 790       te = ebData[bord].tEn;
 791     }
 792     else
 793     {
 794       break;
 795     }
 796     bord = swdData[bord].suivParc;
 797   }
 798   {
 799     dest->LineTo (nx);
 800   }
 801   return bord;
 802 }
 803
 804 int
 805 Shape::ReFormeArcTo (int bord, int curBord, Path * dest, Path * from)
 806 {
 807   int nPiece = ebData[bord].pieceID;
 808   int nPath = ebData[bord].pathID;
 809   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
 810   //      double  px=pts[getEdge(bord).st].x,py=pts[getEdge(bord).st].y;
 811   NR::Point nx = getPoint(getEdge(bord).en).x;
 812   bord = swdData[bord].suivParc;
 813   while (bord >= 0)
 814   {
 815     if (getPoint(getEdge(bord).st).totalDegree() > 2
 816         || getPoint(getEdge(bord).st).oldDegree > 2)
 817     {
 818       break;
 819     }
 820     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
 821     {
 822       if (fabs (te - ebData[bord].tSt) > 0.0001)
 823             {
 824               break;
 825             }
 826       nx = getPoint(getEdge(bord).en).x;
 827       te = ebData[bord].tEn;
 828     }
 829     else
 830     {
 831       break;
 832     }
 833     bord = swdData[bord].suivParc;
 834   }
 835   double sang, eang;
 836   PathDescrArcTo* nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
 837   bool nLarge = nData->large;
 838   bool nClockwise = nData->clockwise;
 839   Path::ArcAngles (from->PrevPoint (nPiece - 1), nData->p,nData->rx,nData->ry,nData->angle, nLarge, nClockwise,  sang, eang);
 840   if (nClockwise)
 841   {
 842     if (sang < eang)
 843       sang += 2 * M_PI;
 844   }
 845   else
 846   {
 847     if (sang > eang)
 848       sang -= 2 * M_PI;
 849   }
 850   double delta = eang - sang;
 851   double ndelta = delta * (te - ts);
 852   if (ts > te)
 853     nClockwise = !nClockwise;
 854   if (ndelta < 0)
 855     ndelta = -ndelta;
 856   if (ndelta > M_PI)
 857     nLarge = true;
 858   else
 859     nLarge = false;
 860   /*    if ( delta < 0 ) delta=-delta;
 861         if ( ndelta < 0 ) ndelta=-ndelta;
 862         if ( ( delta < M_PI && ndelta < M_PI ) || ( delta >= M_PI && ndelta >= M_PI ) ) {
 863                 if ( ts < te ) {
 864                 } else {
 865                         nClockwise=!(nClockwise);
 866                 }
 867         } else {
 868     //          nLarge=!(nLarge);
 869                 nLarge=false; // c'est un sous-segment -> l'arc ne peut que etre plus petit
 870                 if ( ts < te ) {
 871                 } else {
 872                         nClockwise=!(nClockwise);
 873                 }
 874         }*/
 875   {
 876     PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
 877     dest->ArcTo (nx, nData->rx,nData->ry,nData->angle, nLarge, nClockwise);
 878   }
 879   return bord;
 880 }
 881
 882 int
 883 Shape::ReFormeCubicTo (int bord, int curBord, Path * dest, Path * from)
 884 {
 885   int nPiece = ebData[bord].pieceID;
 886   int nPath = ebData[bord].pathID;
 887   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
 888   NR::Point nx = getPoint(getEdge(bord).en).x;
 889   bord = swdData[bord].suivParc;
 890   while (bord >= 0)
 891   {
 892     if (getPoint(getEdge(bord).st).totalDegree() > 2
 893         || getPoint(getEdge(bord).st).oldDegree > 2)
 894     {
 895       break;
 896     }
 897     if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
 898     {
 899       if (fabs (te - ebData[bord].tSt) > 0.0001)
 900             {
 901               break;
 902             }
 903       nx = getPoint(getEdge(bord).en).x;
 904       te = ebData[bord].tEn;
 905     }
 906     else
 907     {
 908       break;
 909     }
 910     bord = swdData[bord].suivParc;
 911   }
 912   NR::Point prevx = from->PrevPoint (nPiece - 1);
 913
 914   NR::Point sDx, eDx;
 915   {
 916     PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(from->descr_cmd[nPiece]);
 917     Path::CubicTangent (ts, sDx, prevx,nData->start,nData->p,nData->end);
 918     Path::CubicTangent (te, eDx, prevx,nData->start,nData->p,nData->end);
 919   }
 920   sDx *= (te - ts);
 921   eDx *= (te - ts);
 922   {
 923     dest->CubicTo (nx,sDx,eDx);
 924   }
 925   return bord;
 926 }
 927
 928 int
 929 Shape::ReFormeBezierTo (int bord, int curBord, Path * dest, Path * from)
 930 {
 931   int nPiece = ebData[bord].pieceID;
 932   int nPath = ebData[bord].pathID;
 933   double ts = ebData[bord].tSt, te = ebData[bord].tEn;
 934   int ps = nPiece, pe = nPiece;
 935   NR::Point px = getPoint(getEdge(bord).st).x;
 936   NR::Point nx = getPoint(getEdge(bord).en).x;
 937   int inBezier = -1, nbInterm = -1;
 938   int typ;
 939   typ = from->descr_cmd[nPiece]->getType();
 940   PathDescrBezierTo *nBData = NULL;
 941   if (typ == descr_bezierto)
 942   {
 943     nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
 944     inBezier = nPiece;
 945     nbInterm = nBData->nb;
 946   }
 947   else
 948   {
 949     int n = nPiece - 1;
 950     while (n > 0)
 951     {
 952       typ = from->descr_cmd[n]->getType();
 953       if (typ == descr_bezierto)
 954       {
 955         inBezier = n;
 956         nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[n]);
 957         nbInterm = nBData->nb;
 958         break;
 959       }
 960       n--;
 961     }
 962     if (inBezier < 0)
 963     {
 964       bord = swdData[bord].suivParc;
 965       dest->LineTo (nx);
 966       return bord;
 967     }
 968   }
 969   bord = swdData[bord].suivParc;
 970   while (bord >= 0)
 971   {
 972     if (getPoint(getEdge(bord).st).totalDegree() > 2
 973         || getPoint(getEdge(bord).st).oldDegree > 2)
 974     {
 975       break;
 976     }
 977     if (ebData[bord].pathID == nPath)
 978     {
 979       if (ebData[bord].pieceID < inBezier
 980           || ebData[bord].pieceID >= inBezier + nbInterm)
 981         break;
 982       if (ebData[bord].pieceID == pe
 983           && fabs (te - ebData[bord].tSt) > 0.0001)
 984         break;
 985       if (ebData[bord].pieceID != pe
 986           && (ebData[bord].tSt > 0.0001 && ebData[bord].tSt < 0.9999))
 987         break;
 988       if (ebData[bord].pieceID != pe && (te > 0.0001 && te < 0.9999))
 989         break;
 990       nx = getPoint(getEdge(bord).en).x;
 991       te = ebData[bord].tEn;
 992       pe = ebData[bord].pieceID;
 993     }
 994     else
 995     {
 996       break;
 997     }
 998     bord = swdData[bord].suivParc;
 999   }
1000
1001   g_return_val_if_fail(nBData != NULL, 0);
1002
1003   if (pe == ps)
1004   {
1005     ReFormeBezierChunk (px, nx, dest, inBezier, nbInterm, from, ps,
1006                         ts, te);
1007   }
1008   else if (ps < pe)
1009   {
1010     if (ts < 0.0001)
1011     {
1012       if (te > 0.9999)
1013       {
1014         dest->BezierTo (nx);
1015         for (int i = ps; i <= pe; i++)
1016         {
1017           PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1018           dest->IntermBezierTo (nData->p);
1019         }
1020         dest->EndBezierTo ();
1021       }
1022       else
1023       {
1024         NR::Point tx;
1025         {
1026           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1027           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1028           tx = (pnData->p + psData->p) / 2;
1029         }
1030         dest->BezierTo (tx);
1031         for (int i = ps; i < pe; i++)
1032         {
1033           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1034           dest->IntermBezierTo (nData->p);
1035         }
1036         dest->EndBezierTo ();
1037         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1038                             from, pe, 0.0, te);
1039       }
1040     }
1041     else
1042     {
1043       if (te > 0.9999)
1044       {
1045         NR::Point tx;
1046         {
1047           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1048           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1049           tx = (psData->p +  pnData->p) / 2;
1050         }
1051         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1052                             from, ps, ts, 1.0);
1053         dest->BezierTo (nx);
1054         for (int i = ps + 1; i <= pe; i++)
1055         {
1056           PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1057           dest->IntermBezierTo (nData->p);
1058         }
1059         dest->EndBezierTo ();
1060       }
1061       else
1062       {
1063         NR::Point tx;
1064         {
1065           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1066           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1067           tx = (pnData->p + psData->p) / 2;
1068         }
1069         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1070                             from, ps, ts, 1.0);
1071         {
1072           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1073           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1074           tx = (pnData->p + psData->p) / 2;
1075         }
1076          dest->BezierTo (tx);
1077         for (int i = ps + 1; i <= pe; i++)
1078         {
1079           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1080           dest->IntermBezierTo (nData->p);
1081         }
1082         dest->EndBezierTo ();
1083         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1084                             from, pe, 0.0, te);
1085       }
1086     }
1087   }
1088   else
1089   {
1090     if (ts > 0.9999)
1091     {
1092       if (te < 0.0001)
1093       {
1094         dest->BezierTo (nx);
1095         for (int i = ps; i >= pe; i--)
1096         {
1097           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1098           dest->IntermBezierTo (nData->p);
1099         }
1100         dest->EndBezierTo ();
1101       }
1102       else
1103       {
1104         NR::Point tx;
1105         {
1106           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1107           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1108           tx = (pnData->p + psData->p) / 2;
1109         }
1110         dest->BezierTo (tx);
1111         for (int i = ps; i > pe; i--)
1112         {
1113           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1114           dest->IntermBezierTo (nData->p);
1115         }
1116         dest->EndBezierTo ();
1117         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1118                             from, pe, 1.0, te);
1119       }
1120     }
1121     else
1122     {
1123       if (te < 0.0001)
1124       {
1125         NR::Point tx;
1126         {
1127           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1128           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1129           tx = (pnData->p + psData->p) / 2;
1130         }
1131          ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1132                             from, ps, ts, 0.0);
1133         dest->BezierTo (nx);
1134         for (int i = ps + 1; i >= pe; i--)
1135         {
1136           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1137           dest->IntermBezierTo (nData->p);
1138         }
1139         dest->EndBezierTo ();
1140       }
1141       else
1142       {
1143         NR::Point tx;
1144         {
1145           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1146           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1147           tx = (pnData->p + psData->p) / 2;
1148         }
1149         ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1150                             from, ps, ts, 0.0);
1151         {
1152           PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1153           PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1154           tx = (pnData->p + psData->p) / 2;
1155         }
1156         dest->BezierTo (tx);
1157         for (int i = ps + 1; i > pe; i--)
1158         {
1159           PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1160           dest->IntermBezierTo (nData->p);
1161         }
1162         dest->EndBezierTo ();
1163         ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1164                             from, pe, 1.0, te);
1165       }
1166     }
1167   }
1168   return bord;
1169 }
1170
1171 void
1172 Shape::ReFormeBezierChunk (NR::Point px, NR::Point nx,
1173                            Path * dest, int inBezier, int nbInterm,
1174                            Path * from, int p, double ts, double te)
1175 {
1176   PathDescrBezierTo* nBData = dynamic_cast<PathDescrBezierTo*>(from->descr_cmd[inBezier]);
1177   NR::Point bstx = from->PrevPoint (inBezier - 1);
1178   NR::Point benx = nBData->p;
1179
1180   NR::Point mx;
1181   if (p == inBezier)
1182   {
1183     // premier bout
1184     if (nbInterm <= 1)
1185     {
1186       // seul bout de la spline
1187       PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1188       mx = nData->p;
1189     }
1190     else
1191     {
1192       // premier bout d'une spline qui en contient plusieurs
1193       PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1194       mx = nData->p;
1195       nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+2]);
1196       benx = (nData->p + mx) / 2;
1197     }
1198   }
1199   else if (p == inBezier + nbInterm - 1)
1200   {
1201     // dernier bout
1202     // si nbInterm == 1, le cas a deja ete traite
1203     // donc dernier bout d'une spline qui en contient plusieurs
1204     PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm]);
1205     mx = nData->p;
1206     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm-1]);
1207     bstx = (nData->p + mx) / 2;
1208   }
1209   else
1210   {
1211     // la spline contient forcément plusieurs bouts, et ce n'est ni le premier ni le dernier
1212     PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+1]);
1213     mx = nData->p;
1214     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p]);
1215     bstx = (nData->p + mx) / 2;
1216     nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+2]);
1217     benx = (nData->p + mx) / 2;
1218   }
1219   NR::Point cx;
1220   {
1221     Path::QuadraticPoint ((ts + te) / 2, cx, bstx, mx, benx);
1222   }
1223   cx = 2 * cx - (px + nx) / 2;
1224   {
1225     dest->BezierTo (nx);
1226     dest->IntermBezierTo (cx);
1227     dest->EndBezierTo ();
1228   }
1229 }
1230
1231 #undef MiscNormalize