src/livarot/PathConversion.cpp

   1 /*
   2  *  PathConversion.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Mon Nov 03 2003.
   6  *
   7  */
   8
   9 #include "Path.h"
  10 #include "Shape.h"
  11 #include "livarot/path-description.h"
  12
  13 #include <libnr/nr-matrix.h>
  14 #include <2geom/transforms.h>
  15
  16 /*
  17  * path description -> polyline
  18  * and Path -> Shape (the Fill() function at the bottom)
  19  * nathing fancy here: take each command and append an approximation of it to the polyline
  20  */
  21
  22 void Path::ConvertWithBackData(double treshhold)
  23 {
  24     if ( descr_flags & descr_adding_bezier ) {
  25         CancelBezier();
  26     }
  27
  28     if ( descr_flags & descr_doing_subpath ) {
  29         CloseSubpath();
  30     }
  31
  32     SetBackData(true);
  33     ResetPoints();
  34     if ( descr_cmd.empty() ) {
  35         return;
  36     }
  37
  38     Geom::Point curX;
  39     int curP = 1;
  40     int lastMoveTo = -1;
  41
  42     // The initial moveto.
  43     {
  44         int const firstTyp = descr_cmd[0]->getType();
  45         if ( firstTyp == descr_moveto ) {
  46             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
  47         } else {
  48             curP = 0;
  49             curX[Geom::X] = curX[Geom::Y] = 0;
  50         }
  51         lastMoveTo = AddPoint(curX, 0, 0.0, true);
  52     }
  53
  54     // And the rest, one by one.
  55     while ( curP < int(descr_cmd.size()) ) {
  56
  57         int const nType = descr_cmd[curP]->getType();
  58         Geom::Point nextX;
  59
  60         switch (nType) {
  61             case descr_forced: {
  62                 AddForcedPoint(curX, curP, 1.0);
  63                 curP++;
  64                 break;
  65             }
  66
  67             case descr_moveto: {
  68                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo*>(descr_cmd[curP]);
  69                 nextX = nData->p;
  70                 lastMoveTo = AddPoint(nextX, curP, 0.0, true);
  71                 // et on avance
  72                 curP++;
  73                 break;
  74             }
  75
  76             case descr_close: {
  77                 nextX = pts[lastMoveTo].p;
  78                 int n = AddPoint(nextX, curP, 1.0, false);
  79                 if (n > 0) pts[n].closed = true;
  80                 curP++;
  81                 break;
  82             }
  83
  84             case descr_lineto: {
  85                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
  86                 nextX = nData->p;
  87                 AddPoint(nextX,curP,1.0,false);
  88                 // et on avance
  89                 curP++;
  90                 break;
  91             }
  92
  93             case descr_cubicto: {
  94                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
  95                 nextX = nData->p;
  96                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8, 0.0, 1.0, curP);
  97                 AddPoint(nextX, curP, 1.0, false);
  98                 // et on avance
  99                 curP++;
 100                 break;
 101             }
 102
 103             case descr_arcto: {
 104                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 105                 nextX = nData->p;
 106                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold, curP);
 107                 AddPoint(nextX, curP, 1.0, false);
 108                 // et on avance
 109                 curP++;
 110                 break;
 111             }
 112
 113             case descr_bezierto: {
 114                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 115                 int nbInterm = nBData->nb;
 116                 nextX = nBData->p;
 117
 118                 int ip = curP + 1;
 119                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 120
 121                 if ( nbInterm >= 1 ) {
 122                     Geom::Point bx = curX;
 123                     Geom::Point cx = curX;
 124                     Geom::Point dx = curX;
 125
 126                     dx = nData->p;
 127                     ip++;
 128                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 129
 130                     cx = 2 * bx - dx;
 131
 132                     for (int k = 0; k < nbInterm - 1; k++) {
 133                         bx = cx;
 134                         cx = dx;
 135
 136                         dx = nData->p;
 137                         ip++;
 138                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 139
 140                         Geom::Point stx;
 141                         stx = (bx + cx) / 2;
 142                         if ( k > 0 ) {
 143                             AddPoint(stx,curP - 1+k,1.0,false);
 144                         }
 145
 146                         {
 147                             Geom::Point mx;
 148                             mx = (cx + dx) / 2;
 149                             RecBezierTo(cx, stx, mx, treshhold, 8, 0.0, 1.0, curP + k);
 150                         }
 151                     }
 152                     {
 153                         bx = cx;
 154                         cx = dx;
 155
 156                         dx = nextX;
 157                         dx = 2 * dx - cx;
 158
 159                         Geom::Point stx;
 160                         stx = (bx + cx) / 2;
 161
 162                         if ( nbInterm > 1 ) {
 163                             AddPoint(stx, curP + nbInterm - 2, 1.0, false);
 164                         }
 165
 166                         {
 167                             Geom::Point mx;
 168                             mx = (cx + dx) / 2;
 169                             RecBezierTo(cx, stx, mx, treshhold, 8, 0.0, 1.0, curP + nbInterm - 1);
 170                         }
 171                     }
 172
 173                 }
 174
 175
 176                 AddPoint(nextX, curP - 1 + nbInterm, 1.0, false);
 177
 178                 // et on avance
 179                 curP += 1 + nbInterm;
 180                 break;
 181             }
 182         }
 183         curX = nextX;
 184     }
 185 }
 186
 187
 188 void Path::Convert(double treshhold)
 189 {
 190     if ( descr_flags & descr_adding_bezier ) {
 191         CancelBezier();
 192     }
 193
 194     if ( descr_flags & descr_doing_subpath ) {
 195         CloseSubpath();
 196     }
 197
 198     SetBackData(false);
 199     ResetPoints();
 200     if ( descr_cmd.empty() ) {
 201         return;
 202     }
 203
 204     Geom::Point curX;
 205     int curP = 1;
 206     int lastMoveTo = 0;
 207
 208     // le moveto
 209     {
 210         int const firstTyp = descr_cmd[0]->getType();
 211         if ( firstTyp == descr_moveto ) {
 212             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 213         } else {
 214             curP = 0;
 215             curX[0] = curX[1] = 0;
 216         }
 217         lastMoveTo = AddPoint(curX, true);
 218     }
 219     descr_cmd[0]->associated = lastMoveTo;
 220
 221     // et le reste, 1 par 1
 222     while ( curP < int(descr_cmd.size()) ) {
 223
 224         int const nType = descr_cmd[curP]->getType();
 225         Geom::Point nextX;
 226
 227         switch (nType) {
 228             case descr_forced: {
 229                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 230                 curP++;
 231                 break;
 232             }
 233
 234             case descr_moveto: {
 235                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 236                 nextX = nData->p;
 237                 lastMoveTo = AddPoint(nextX, true);
 238                 descr_cmd[curP]->associated = lastMoveTo;
 239
 240                 // et on avance
 241                 curP++;
 242                 break;
 243             }
 244
 245             case descr_close: {
 246                 nextX = pts[lastMoveTo].p;
 247                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 248                 if ( descr_cmd[curP]->associated < 0 ) {
 249                     if ( curP == 0 ) {
 250                         descr_cmd[curP]->associated = 0;
 251                     } else {
 252                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 253                     }
 254                 }
 255                 if ( descr_cmd[curP]->associated > 0 ) {
 256                     pts[descr_cmd[curP]->associated].closed = true;
 257                 }
 258                 curP++;
 259                 break;
 260             }
 261
 262             case descr_lineto: {
 263                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 264                 nextX = nData->p;
 265                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 266                 if ( descr_cmd[curP]->associated < 0 ) {
 267                     if ( curP == 0 ) {
 268                         descr_cmd[curP]->associated = 0;
 269                     } else {
 270                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 271                     }
 272                 }
 273                 // et on avance
 274                 curP++;
 275                 break;
 276             }
 277
 278             case descr_cubicto: {
 279                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 280                 nextX = nData->p;
 281                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8);
 282                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 283                 if ( descr_cmd[curP]->associated < 0 ) {
 284                     if ( curP == 0 ) {
 285                         descr_cmd[curP]->associated = 0;
 286                     } else {
 287                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 288                     }
 289                 }
 290                 // et on avance
 291                 curP++;
 292                 break;
 293             }
 294
 295             case descr_arcto: {
 296                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 297                 nextX = nData->p;
 298                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 299                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 300                 if ( descr_cmd[curP]->associated < 0 ) {
 301                     if ( curP == 0 ) {
 302                         descr_cmd[curP]->associated = 0;
 303                     } else {
 304                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 305                     }
 306                 }
 307                 // et on avance
 308                 curP++;
 309                 break;
 310             }
 311
 312             case descr_bezierto: {
 313                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 314                 int nbInterm = nBData->nb;
 315                 nextX = nBData->p;
 316                 int curBD = curP;
 317
 318                 curP++;
 319                 int ip = curP;
 320                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 321
 322                 if ( nbInterm == 1 ) {
 323                     Geom::Point const midX = nData->p;
 324                     RecBezierTo(midX, curX, nextX, treshhold, 8);
 325                 } else if ( nbInterm > 1 ) {
 326                     Geom::Point bx = curX;
 327                     Geom::Point cx = curX;
 328                     Geom::Point dx = curX;
 329
 330                     dx = nData->p;
 331                     ip++;
 332                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 333
 334                     cx = 2 * bx - dx;
 335
 336                     for (int k = 0; k < nbInterm - 1; k++) {
 337                         bx = cx;
 338                         cx = dx;
 339
 340                         dx = nData->p;
 341                         ip++;
 342                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 343
 344                         Geom::Point stx = (bx + cx) / 2;
 345                         if ( k > 0 ) {
 346                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 347                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 348                                 if ( curP == 0 ) {
 349                                     descr_cmd[ip - 2]->associated = 0;
 350                                 } else {
 351                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 352                                 }
 353                             }
 354                         }
 355
 356                         {
 357                             Geom::Point const mx = (cx + dx) / 2;
 358                             RecBezierTo(cx, stx, mx, treshhold, 8);
 359                         }
 360                     }
 361
 362                     {
 363                         bx = cx;
 364                         cx = dx;
 365
 366                         dx = nextX;
 367                         dx = 2 * dx - cx;
 368
 369                         Geom::Point stx = (bx + cx) / 2;
 370
 371                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 372                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 373                             if ( curP == 0 ) {
 374                                 descr_cmd[ip - 1]->associated = 0;
 375                             } else {
 376                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 377                             }
 378                         }
 379
 380                         {
 381                             Geom::Point mx = (cx + dx) / 2;
 382                             RecBezierTo(cx, stx, mx, treshhold, 8);
 383                         }
 384                     }
 385                 }
 386
 387                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 388                 if ( descr_cmd[curBD]->associated < 0 ) {
 389                     if ( curP == 0 ) {
 390                         descr_cmd[curBD]->associated = 0;
 391                     } else {
 392                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 393                     }
 394                 }
 395
 396                 // et on avance
 397                 curP += nbInterm;
 398                 break;
 399             }
 400         }
 401
 402         curX = nextX;
 403     }
 404 }
 405
 406 #define POINT_RELATION_TO_AREA(pt, area) ((pt)[0] < (area)->x0 ? 1 : ((pt)[0] > (area)->x1 ? 2 : ((pt)[1] < (area)->y0 ? 3 : ((pt)[1] > (area)->y1 ? 4 : 0))))
 407
 408 void Path::Convert(NRRectL *area, double treshhold)
 409 {
 410     if ( descr_flags & descr_adding_bezier ) {
 411         CancelBezier();
 412     }
 413
 414     if ( descr_flags & descr_doing_subpath ) {
 415         CloseSubpath();
 416     }
 417
 418     SetBackData(false);
 419     ResetPoints();
 420     if ( descr_cmd.empty() ) {
 421         return;
 422     }
 423
 424     Geom::Point curX;
 425     int curP = 1;
 426     int lastMoveTo = 0;
 427     short last_point_relation = 0;
 428     short curent_point_relation = 0;
 429     bool last_start_elimination = false;
 430     bool start_elimination = false;
 431     bool replace = false;
 432
 433     // first point
 434     {
 435         int const firstTyp = descr_cmd[0]->getType();
 436         if ( firstTyp == descr_moveto ) {
 437             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 438         } else {
 439             curP = 0;
 440             curX[0] = curX[1] = 0;
 441         }
 442
 443         last_point_relation = POINT_RELATION_TO_AREA(curX, area);
 444         lastMoveTo = AddPoint(curX, true);
 445     }
 446     descr_cmd[0]->associated = lastMoveTo;
 447
 448     // process nodes one by one
 449     while ( curP < int(descr_cmd.size()) ) {
 450
 451         int const nType = descr_cmd[curP]->getType();
 452         Geom::Point nextX;
 453
 454         switch (nType) {
 455             case descr_forced: {
 456                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 457                 last_point_relation = 0;
 458                 curP++;
 459                 break;
 460             }
 461
 462             case descr_moveto: {
 463                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 464                 nextX = nData->p;
 465                 lastMoveTo = AddPoint(nextX, true);
 466                 descr_cmd[curP]->associated = lastMoveTo;
 467
 468                 last_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 469                 start_elimination = false;
 470
 471                 curP++;
 472                 break;
 473             }
 474
 475             case descr_close: {
 476                 nextX = pts[lastMoveTo].p;
 477                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 478                 if ( descr_cmd[curP]->associated < 0 ) {
 479                     if ( curP == 0 ) {
 480                         descr_cmd[curP]->associated = 0;
 481                     } else {
 482                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 483                     }
 484                 }
 485                 if ( descr_cmd[curP]->associated > 0 ) {
 486                     pts[descr_cmd[curP]->associated].closed = true;
 487                 }
 488                 last_point_relation = 0;
 489                 curP++;
 490                 break;
 491             }
 492
 493             case descr_lineto: {
 494                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 495                 nextX = nData->p;
 496                 curent_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 497                 replace = false;
 498                 last_start_elimination = start_elimination;
 499                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation) {
 500                     if (!start_elimination) {
 501                         start_elimination = true;
 502                     } else {
 503                         replace = true;
 504                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 505                     }
 506                 } else {
 507                     start_elimination = false;
 508                 }
 509
 510                 if (!replace) {
 511                     descr_cmd[curP]->associated = AddPoint(nextX, false);
 512                 }
 513
 514                 if ( descr_cmd[curP]->associated < 0 ) {
 515                     // point is not added as position is equal to the last added
 516                     start_elimination = last_start_elimination;
 517                     if ( curP == 0 ) {
 518                         descr_cmd[curP]->associated = 0;
 519                     } else {
 520                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 521                     }
 522                 }
 523                 last_point_relation = curent_point_relation;
 524                 curP++;
 525                 break;
 526             }
 527
 528             case descr_cubicto: {
 529                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 530                 nextX = nData->p;
 531
 532                 curent_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 533                 replace = false;
 534                 last_start_elimination = start_elimination;
 535                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation &&
 536                     curent_point_relation == POINT_RELATION_TO_AREA(curX + (nData->start), area) &&
 537                     curent_point_relation == POINT_RELATION_TO_AREA(nextX + (nData->end), area))
 538                 {
 539                     if (!start_elimination) {
 540                         start_elimination = true;
 541                     } else {
 542                         replace = true;
 543                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 544                     }
 545                 } else {
 546                     start_elimination = false;
 547                 }
 548
 549                 if (!replace) {
 550                     RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8);
 551                     descr_cmd[curP]->associated = AddPoint(nextX,false);
 552                 }
 553
 554                 if ( descr_cmd[curP]->associated < 0 ) {
 555                     // point is not added as position is equal to the last added
 556                     start_elimination = last_start_elimination;
 557                     if ( curP == 0 ) {
 558                         descr_cmd[curP]->associated = 0;
 559                     } else {
 560                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 561                     }
 562                 }
 563                 last_point_relation = curent_point_relation;
 564                 curP++;
 565                 break;
 566             }
 567
 568             case descr_arcto: {
 569                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 570                 nextX = nData->p;
 571                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 572                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 573                 if ( descr_cmd[curP]->associated < 0 ) {
 574                     if ( curP == 0 ) {
 575                         descr_cmd[curP]->associated = 0;
 576                     } else {
 577                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 578                     }
 579                 }
 580                 last_point_relation = 0;
 581
 582                 curP++;
 583                 break;
 584             }
 585
 586             case descr_bezierto: {
 587                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 588                 int nbInterm = nBData->nb;
 589                 nextX = nBData->p;
 590                 int curBD = curP;
 591
 592                 curP++;
 593                 int ip = curP;
 594                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 595
 596                 if ( nbInterm == 1 ) {
 597                     Geom::Point const midX = nData->p;
 598                     RecBezierTo(midX, curX, nextX, treshhold, 8);
 599                 } else if ( nbInterm > 1 ) {
 600                     Geom::Point bx = curX;
 601                     Geom::Point cx = curX;
 602                     Geom::Point dx = curX;
 603
 604                     dx = nData->p;
 605                     ip++;
 606                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 607
 608                     cx = 2 * bx - dx;
 609
 610                     for (int k = 0; k < nbInterm - 1; k++) {
 611                         bx = cx;
 612                         cx = dx;
 613
 614                         dx = nData->p;
 615                         ip++;
 616                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 617
 618                         Geom::Point stx = (bx + cx) / 2;
 619                         if ( k > 0 ) {
 620                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 621                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 622                                 if ( curP == 0 ) {
 623                                     descr_cmd[ip - 2]->associated = 0;
 624                                 } else {
 625                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 626                                 }
 627                             }
 628                         }
 629
 630                         {
 631                             Geom::Point const mx = (cx + dx) / 2;
 632                             RecBezierTo(cx, stx, mx, treshhold, 8);
 633                         }
 634                     }
 635
 636                     {
 637                         bx = cx;
 638                         cx = dx;
 639
 640                         dx = nextX;
 641                         dx = 2 * dx - cx;
 642
 643                         Geom::Point stx = (bx + cx) / 2;
 644
 645                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 646                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 647                             if ( curP == 0 ) {
 648                                 descr_cmd[ip - 1]->associated = 0;
 649                             } else {
 650                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 651                             }
 652                         }
 653
 654                         {
 655                             Geom::Point mx = (cx + dx) / 2;
 656                             RecBezierTo(cx, stx, mx, treshhold, 8);
 657                         }
 658                     }
 659                 }
 660
 661                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 662                 if ( descr_cmd[curBD]->associated < 0 ) {
 663                     if ( curP == 0 ) {
 664                         descr_cmd[curBD]->associated = 0;
 665                     } else {
 666                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 667                     }
 668                 }
 669
 670                 last_point_relation = 0;
 671
 672                 curP += nbInterm;
 673                 break;
 674             }
 675         }
 676
 677         curX = nextX;
 678     }
 679 }
 680
 681
 682 void Path::ConvertEvenLines(double treshhold)
 683 {
 684     if ( descr_flags & descr_adding_bezier ) {
 685         CancelBezier();
 686     }
 687
 688     if ( descr_flags & descr_doing_subpath ) {
 689         CloseSubpath();
 690     }
 691
 692     SetBackData(false);
 693     ResetPoints();
 694     if ( descr_cmd.empty() ) {
 695         return;
 696     }
 697
 698     Geom::Point curX;
 699     int curP = 1;
 700     int lastMoveTo = 0;
 701
 702     // le moveto
 703     {
 704         int const firstTyp = descr_cmd[0]->getType();
 705         if ( firstTyp == descr_moveto ) {
 706             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 707         } else {
 708             curP = 0;
 709             curX[0] = curX[1] = 0;
 710         }
 711         lastMoveTo = AddPoint(curX, true);
 712     }
 713     descr_cmd[0]->associated = lastMoveTo;
 714
 715     // et le reste, 1 par 1
 716     while ( curP < int(descr_cmd.size()) ) {
 717
 718         int const nType = descr_cmd[curP]->getType();
 719         Geom::Point nextX;
 720
 721         switch (nType) {
 722             case descr_forced: {
 723                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 724                 curP++;
 725                 break;
 726             }
 727
 728             case descr_moveto: {
 729                 PathDescrMoveTo* nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 730                 nextX = nData->p;
 731                 lastMoveTo = AddPoint(nextX,true);
 732                 descr_cmd[curP]->associated = lastMoveTo;
 733
 734                 // et on avance
 735                 curP++;
 736                 break;
 737             }
 738
 739             case descr_close: {
 740                 nextX = pts[lastMoveTo].p;
 741                 {
 742                     Geom::Point nexcur;
 743                     nexcur = nextX - curX;
 744                     const double segL = Geom::L2(nexcur);
 745                     if ( (segL > treshhold) && (treshhold > 0) ) {
 746                         for (double i = treshhold; i < segL; i += treshhold) {
 747                             Geom::Point nX;
 748                             nX = (segL - i) * curX + i * nextX;
 749                             nX /= segL;
 750                             AddPoint(nX);
 751                         }
 752                     }
 753                 }
 754
 755                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 756                 if ( descr_cmd[curP]->associated < 0 ) {
 757                     if ( curP == 0 ) {
 758                         descr_cmd[curP]->associated = 0;
 759                     } else {
 760                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 761                     }
 762                 }
 763                 if ( descr_cmd[curP]->associated > 0 ) {
 764                     pts[descr_cmd[curP]->associated].closed = true;
 765                 }
 766                 curP++;
 767                 break;
 768             }
 769
 770             case descr_lineto: {
 771                 PathDescrLineTo* nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 772                 nextX = nData->p;
 773                 Geom::Point nexcur = nextX - curX;
 774                 const double segL = L2(nexcur);
 775                 if ( (segL > treshhold) && (treshhold > 0)) {
 776                     for (double i = treshhold; i < segL; i += treshhold) {
 777                         Geom::Point nX = ((segL - i) * curX + i * nextX) / segL;
 778                         AddPoint(nX);
 779                     }
 780                 }
 781
 782                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 783                 if ( descr_cmd[curP]->associated < 0 ) {
 784                     if ( curP == 0 ) {
 785                         descr_cmd[curP]->associated = 0;
 786                     } else {
 787                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 788                     }
 789                 }
 790                 // et on avance
 791                 curP++;
 792                 break;
 793             }
 794
 795             case descr_cubicto: {
 796                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 797                 nextX = nData->p;
 798                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8, 4 * treshhold);
 799                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 800                 if ( descr_cmd[curP]->associated < 0 ) {
 801                     if ( curP == 0 ) {
 802                         descr_cmd[curP]->associated = 0;
 803                     } else {
 804                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 805                     }
 806                 }
 807                 // et on avance
 808                 curP++;
 809                 break;
 810             }
 811
 812             case descr_arcto: {
 813                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 814                 nextX = nData->p;
 815                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 816                 descr_cmd[curP]->associated =AddPoint(nextX, false);
 817                 if ( descr_cmd[curP]->associated < 0 ) {
 818                     if ( curP == 0 ) {
 819                         descr_cmd[curP]->associated = 0;
 820                     } else {
 821                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 822                     }
 823                 }
 824
 825                 // et on avance
 826                 curP++;
 827                 break;
 828             }
 829
 830             case descr_bezierto: {
 831                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 832                 int nbInterm = nBData->nb;
 833                 nextX = nBData->p;
 834                 int curBD = curP;
 835
 836                 curP++;
 837                 int ip = curP;
 838                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 839
 840                 if ( nbInterm == 1 ) {
 841                     Geom::Point const midX = nData->p;
 842                     RecBezierTo(midX, curX, nextX, treshhold, 8, 4 * treshhold);
 843                 } else if ( nbInterm > 1 ) {
 844                     Geom::Point bx = curX;
 845                     Geom::Point cx = curX;
 846                     Geom::Point dx = curX;
 847
 848                     dx = nData->p;
 849                     ip++;
 850                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 851
 852                     cx = 2 * bx - dx;
 853
 854                     for (int k = 0; k < nbInterm - 1; k++) {
 855                         bx = cx;
 856                         cx = dx;
 857                         dx = nData->p;
 858
 859                         ip++;
 860                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 861
 862                         Geom::Point stx = (bx+cx) / 2;
 863                         if ( k > 0 ) {
 864                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 865                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 866                                 if ( curP == 0 ) {
 867                                     descr_cmd[ip- 2]->associated = 0;
 868                                 } else {
 869                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 870                                 }
 871                             }
 872                         }
 873
 874                         {
 875                             Geom::Point const mx = (cx + dx) / 2;
 876                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 877                         }
 878                     }
 879
 880                     {
 881                         bx = cx;
 882                         cx = dx;
 883
 884                         dx = nextX;
 885                         dx = 2 * dx - cx;
 886
 887                         Geom::Point const stx = (bx + cx) / 2;
 888
 889                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 890                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 891                             if ( curP == 0 ) {
 892                                 descr_cmd[ip - 1]->associated = 0;
 893                             } else {
 894                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 895                             }
 896                         }
 897
 898                         {
 899                             Geom::Point const mx = (cx + dx) / 2;
 900                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 901                         }
 902                     }
 903                 }
 904
 905                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 906                 if ( descr_cmd[curBD]->associated < 0 ) {
 907                     if ( curP == 0 ) {
 908                         descr_cmd[curBD]->associated = 0;
 909                     } else {
 910                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 911                     }
 912                 }
 913
 914                 // et on avance
 915                 curP += nbInterm;
 916                 break;
 917             }
 918         }
 919         if ( Geom::LInfty(curX - nextX) > 0.00001 ) {
 920             curX = nextX;
 921         }
 922     }
 923 }
 924
 925 const Geom::Point Path::PrevPoint(int i) const
 926 {
 927     /* TODO: I suspect this should assert `(unsigned) i < descr_nb'.  We can probably change
 928        the argument to unsigned.  descr_nb should probably be changed to unsigned too. */
 929     g_assert( i >= 0 );
 930     switch ( descr_cmd[i]->getType() ) {
 931         case descr_moveto: {
 932             PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 933             return nData->p;
 934         }
 935         case descr_lineto: {
 936             PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 937             return nData->p;
 938         }
 939         case descr_arcto: {
 940             PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 941             return nData->p;
 942         }
 943         case descr_cubicto: {
 944             PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 945             return nData->p;
 946         }
 947         case descr_bezierto: {
 948             PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 949             return nData->p;
 950         }
 951         case descr_interm_bezier:
 952         case descr_close:
 953         case descr_forced:
 954             return PrevPoint(i - 1);
 955         default:
 956             g_assert_not_reached();
 957             return Geom::Point(0, 0);
 958     }
 959 }
 960
 961 // utilitaries: given a quadratic bezier curve (start point, control point, end point, ie that's a clamped curve),
 962 // and an abcissis on it, get the point with that abcissis.
 963 // warning: it's NOT a curvilign abcissis (or whatever you call that in english), so "t" is NOT the length of "start point"->"result point"
 964 void Path::QuadraticPoint(double t, Geom::Point &oPt,
 965                           const Geom::Point &iS, const Geom::Point &iM, const Geom::Point &iE)
 966 {
 967     Geom::Point const ax = iE - 2 * iM + iS;
 968     Geom::Point const bx = 2 * iM - 2 * iS;
 969     Geom::Point const cx = iS;
 970
 971     oPt = t * t * ax + t * bx + cx;
 972 }
 973 // idem for cubic bezier patch
 974 void Path::CubicTangent(double t, Geom::Point &oPt, const Geom::Point &iS, const Geom::Point &isD,
 975                         const Geom::Point &iE, const Geom::Point &ieD)
 976 {
 977     Geom::Point const ax = ieD - 2 * iE + 2 * iS + isD;
 978     Geom::Point const bx = 3 * iE - ieD - 2 * isD - 3 * iS;
 979     Geom::Point const cx = isD;
 980
 981     oPt = 3 * t * t * ax + 2 * t * bx + cx;
 982 }
 983
 984 // extract interesting info of a SVG arc description
 985 static void ArcAnglesAndCenter(Geom::Point const &iS, Geom::Point const &iE,
 986                                double rx, double ry, double angle,
 987                                bool large, bool wise,
 988                                double &sang, double &eang, Geom::Point &dr);
 989
 990 void Path::ArcAngles(const Geom::Point &iS, const Geom::Point &iE,
 991                      double rx, double ry, double angle, bool large, bool wise, double &sang, double &eang)
 992 {
 993     Geom::Point dr;
 994     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
 995 }
 996
 997 /* N.B. If iS == iE then sang,eang,dr each become NaN.  Probably a bug. */
 998 static void ArcAnglesAndCenter(Geom::Point const &iS, Geom::Point const &iE,
 999                                double rx, double ry, double angle,
1000                                bool large, bool wise,
1001                                double &sang, double &eang, Geom::Point &dr)
1002 {
1003     Geom::Point se = iE - iS;
1004     Geom::Point ca(cos(angle), sin(angle));
1005     Geom::Point cse(dot(se, ca), cross(se, ca));
1006     cse[0] /= rx;
1007     cse[1] /= ry;
1008     double const lensq = dot(cse,cse);
1009     Geom::Point csd = ( ( lensq < 4
1010                         ? sqrt( 1/lensq - .25 )
1011                         : 0.0 )
1012                       * cse.ccw() );
1013
1014     Geom::Point ra = -csd - 0.5 * cse;
1015     if ( ra[0] <= -1 ) {
1016         sang = M_PI;
1017     } else if ( ra[0] >= 1 ) {
1018         sang = 0;
1019     } else {
1020         sang = acos(ra[0]);
1021         if ( ra[1] < 0 ) {
1022             sang = 2 * M_PI - sang;
1023         }
1024     }
1025
1026     ra = -csd + 0.5 * cse;
1027     if ( ra[0] <= -1 ) {
1028         eang = M_PI;
1029     } else if ( ra[0] >= 1 ) {
1030         eang = 0;
1031     } else {
1032         eang = acos(ra[0]);
1033         if ( ra[1] < 0 ) {
1034             eang = 2 * M_PI - eang;
1035         }
1036     }
1037
1038     csd[0] *= rx;
1039     csd[1] *= ry;
1040     ca[1] = -ca[1]; // because it's the inverse rotation
1041
1042     dr[0] = dot(csd, ca);
1043     dr[1] = cross(csd, ca);
1044
1045     ca[1] = -ca[1];
1046
1047     if ( wise ) {
1048
1049         if (large) {
1050             dr = -dr;
1051             double swap = eang;
1052             eang = sang;
1053             sang = swap;
1054             eang += M_PI;
1055             sang += M_PI;
1056             if ( eang >= 2*M_PI ) {
1057                 eang -= 2*M_PI;
1058             }
1059             if ( sang >= 2*M_PI ) {
1060                 sang -= 2*M_PI;
1061             }
1062         }
1063
1064     } else {
1065         if (!large) {
1066             dr = -dr;
1067             double swap = eang;
1068             eang = sang;
1069             sang = swap;
1070             eang += M_PI;
1071             sang += M_PI;
1072             if ( eang >= 2*M_PI ) {
1073                 eang -= 2 * M_PI;
1074             }
1075             if ( sang >= 2*M_PI ) {
1076                 sang -= 2 * M_PI;
1077             }
1078         }
1079     }
1080
1081     dr += 0.5 * (iS + iE);
1082 }
1083
1084
1085
1086 void Path::DoArc(Geom::Point const &iS, Geom::Point const &iE,
1087                  double const rx, double const ry, double const angle,
1088                  bool const large, bool const wise, double const /*tresh*/)
1089 {
1090     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1091        apart than the diameter.  Also check that we do the right thing for negative radius.
1092        (Same for the other DoArc functions in this file.) */
1093     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1094         return;
1095         // We always add a lineto afterwards, so this is fine.
1096         // [on ajoute toujours un lineto apres, donc c bon]
1097     }
1098
1099     double sang;
1100     double eang;
1101     Geom::Point dr_temp;
1102     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1103     Geom::Point dr = dr_temp;
1104     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1105        the case of low curvature (i.e. very large radius). */
1106
1107     Geom::Scale const ar(rx, ry);
1108     Geom::Rotate cb( angle + sang );
1109     if (wise) {
1110
1111         double const incr = -0.1;
1112         if ( sang < eang ) {
1113             sang += 2*M_PI;
1114         }
1115         Geom::Rotate const omega(incr);
1116         for (double b = sang + incr ; b > eang ; b += incr) {
1117             cb = omega * cb;
1118             AddPoint( cb.vector() * ar + dr );
1119         }
1120
1121     } else {
1122
1123         double const incr = 0.1;
1124         if ( sang > eang ) {
1125             sang -= 2*M_PI;
1126         }
1127         Geom::Rotate const omega(incr);
1128         for (double b = sang + incr ; b < eang ; b += incr) {
1129             cb = omega * cb;
1130             AddPoint( cb.vector() * ar + dr);
1131         }
1132     }
1133 }
1134
1135
1136 void Path::RecCubicTo( Geom::Point const &iS, Geom::Point const &isD,
1137                        Geom::Point const &iE, Geom::Point const &ieD,
1138                        double tresh, int lev, double maxL)
1139 {
1140     Geom::Point se = iE - iS;
1141     const double dC = Geom::L2(se);
1142     if ( dC < 0.01 ) {
1143
1144         const double sC = dot(isD,isD);
1145         const double eC = dot(ieD,ieD);
1146         if ( sC < tresh && eC < tresh ) {
1147             return;
1148         }
1149
1150     } else {
1151         const double sC = fabs(cross(se, isD)) / dC;
1152         const double eC = fabs(cross(se, ieD)) / dC;
1153         if ( sC < tresh && eC < tresh ) {
1154             // presque tt droit -> attention si on nous demande de bien subdiviser les petits segments
1155             if ( maxL > 0 && dC > maxL ) {
1156                 if ( lev <= 0 ) {
1157                     return;
1158                 }
1159                 Geom::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1160                 Geom::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1161
1162                 Geom::Point hisD = 0.5 * isD;
1163                 Geom::Point hieD = 0.5 * ieD;
1164
1165                 RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1166                 AddPoint(m);
1167                 RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1168             }
1169             return;
1170         }
1171     }
1172
1173     if ( lev <= 0 ) {
1174         return;
1175     }
1176
1177     {
1178         Geom::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1179         Geom::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1180
1181         Geom::Point hisD = 0.5 * isD;
1182         Geom::Point hieD = 0.5 * ieD;
1183
1184         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1185         AddPoint(m);
1186         RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1187     }
1188 }
1189
1190
1191
1192 void Path::RecBezierTo(const Geom::Point &iP,
1193                        const Geom::Point &iS,
1194                        const Geom::Point &iE,
1195                        double tresh, int lev, double maxL)
1196 {
1197     if ( lev <= 0 ) {
1198         return;
1199     }
1200
1201     Geom::Point ps = iS - iP;
1202     Geom::Point pe = iE - iP;
1203     Geom::Point se = iE - iS;
1204     double s = fabs(cross(pe, ps));
1205     if ( s < tresh ) {
1206         const double l = L2(se);
1207         if ( maxL > 0 && l > maxL ) {
1208             const Geom::Point m = 0.25 * (iS + iE + 2 * iP);
1209             Geom::Point md = 0.5 * (iS + iP);
1210             RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1211             AddPoint(m);
1212             md = 0.5 * (iP + iE);
1213             RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1214         }
1215         return;
1216     }
1217
1218     {
1219         const Geom::Point m = 0.25 * (iS + iE + 2 * iP);
1220         Geom::Point md = 0.5 * (iS + iP);
1221         RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1222         AddPoint(m);
1223         md = 0.5 * (iP + iE);
1224         RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1225     }
1226 }
1227
1228
1229 void Path::DoArc(Geom::Point const &iS, Geom::Point const &iE,
1230                  double const rx, double const ry, double const angle,
1231                  bool const large, bool const wise, double const /*tresh*/, int const piece)
1232 {
1233     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1234        apart than the diameter.  Also check that we do the right thing for negative radius.
1235        (Same for the other DoArc functions in this file.) */
1236     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1237         return;
1238         // We always add a lineto afterwards, so this is fine.
1239         // [on ajoute toujours un lineto apres, donc c bon]
1240     }
1241
1242     double sang;
1243     double eang;
1244     Geom::Point dr_temp;
1245     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1246     Geom::Point dr = dr_temp;
1247     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1248        the case of low curvature (i.e. very large radius). */
1249
1250     Geom::Scale const ar(rx, ry);
1251     Geom::Rotate cb(angle + sang);
1252     if (wise) {
1253
1254         double const incr = -0.1;
1255         if ( sang < eang ) {
1256             sang += 2*M_PI;
1257         }
1258         Geom::Rotate const omega(incr);
1259         for (double b = sang + incr; b > eang; b += incr) {
1260             cb = omega * cb;
1261             AddPoint(cb.vector() * ar + dr, piece, (sang - b) / (sang - eang));
1262         }
1263
1264     } else {
1265
1266         double const incr = 0.1;
1267         if ( sang > eang ) {
1268             sang -= 2 * M_PI;
1269         }
1270         Geom::Rotate const omega(incr);
1271         for (double b = sang + incr ; b < eang ; b += incr) {
1272             cb = omega * cb;
1273             AddPoint(cb.vector() * ar + dr, piece, (b - sang) / (eang - sang));
1274         }
1275     }
1276 }
1277
1278 void Path::RecCubicTo(Geom::Point const &iS, Geom::Point const &isD,
1279                       Geom::Point const &iE, Geom::Point const &ieD,
1280                       double tresh, int lev, double st, double et, int piece)
1281 {
1282     const Geom::Point se = iE - iS;
1283     const double dC = Geom::L2(se);
1284     if ( dC < 0.01 ) {
1285         const double sC = dot(isD, isD);
1286         const double eC = dot(ieD, ieD);
1287         if ( sC < tresh && eC < tresh ) {
1288             return;
1289         }
1290     } else {
1291         const double sC = fabs(cross(se, isD)) / dC;
1292         const double eC = fabs(cross(se, ieD)) / dC;
1293         if ( sC < tresh && eC < tresh ) {
1294             return;
1295         }
1296     }
1297
1298     if ( lev <= 0 ) {
1299         return;
1300     }
1301
1302     Geom::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1303     Geom::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1304     double mt = (st + et) / 2;
1305
1306     Geom::Point hisD = 0.5 * isD;
1307     Geom::Point hieD = 0.5 * ieD;
1308
1309     RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece);
1310     AddPoint(m, piece, mt);
1311     RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece);
1312
1313 }
1314
1315
1316
1317 void Path::RecBezierTo(Geom::Point const &iP,
1318                        Geom::Point const &iS,
1319                        Geom::Point const &iE,
1320                        double tresh, int lev, double st, double et, int piece)
1321 {
1322     if ( lev <= 0 ) {
1323         return;
1324     }
1325
1326     Geom::Point ps = iS - iP;
1327     Geom::Point pe = iE - iP;
1328     const double s = fabs(cross(pe, ps));
1329     if ( s < tresh ) {
1330         return;
1331     }
1332
1333     {
1334         const double mt = (st + et) / 2;
1335         const Geom::Point m = 0.25 * (iS + iE + 2 * iP);
1336         RecBezierTo(0.5 * (iS + iP), iS, m, tresh, lev - 1, st, mt, piece);
1337         AddPoint(m, piece, mt);
1338         RecBezierTo(0.5 * (iP + iE), m, iE, tresh, lev - 1, mt, et, piece);
1339     }
1340 }
1341
1342
1343
1344 void Path::DoArc(Geom::Point const &iS, Geom::Point const &iE,
1345                  double const rx, double const ry, double const angle,
1346                  bool const large, bool const wise, double const /*tresh*/,
1347                  int const piece, offset_orig &/*orig*/)
1348 {
1349     // Will never arrive here, as offsets are made of cubics.
1350     // [on n'arrivera jamais ici, puisque les offsets sont fait de cubiques]
1351     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1352        apart than the diameter.  Also check that we do the right thing for negative radius.
1353        (Same for the other DoArc functions in this file.) */
1354     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1355         return;
1356         // We always add a lineto afterwards, so this is fine.
1357         // [on ajoute toujours un lineto apres, donc c bon]
1358     }
1359
1360     double sang;
1361     double eang;
1362     Geom::Point dr_temp;
1363     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1364     Geom::Point dr = dr_temp;
1365     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1366        the case of low curvature (i.e. very large radius). */
1367
1368     Geom::Scale const ar(rx, ry);
1369     Geom::Rotate cb(angle + sang);
1370     if (wise) {
1371
1372         double const incr = -0.1;
1373         if ( sang < eang ) {
1374             sang += 2*M_PI;
1375         }
1376         Geom::Rotate const omega(incr);
1377         for (double b = sang + incr; b > eang ;b += incr) {
1378             cb = omega * cb;
1379             AddPoint(cb.vector() * ar + dr, piece, (sang - b) / (sang - eang));
1380         }
1381
1382     } else {
1383         double const incr = 0.1;
1384         if ( sang > eang ) {
1385             sang -= 2*M_PI;
1386         }
1387         Geom::Rotate const omega(incr);
1388         for (double b = sang + incr ; b < eang ; b += incr) {
1389             cb = omega * cb;
1390             AddPoint(cb.vector() * ar + dr, piece, (b - sang) / (eang - sang));
1391         }
1392     }
1393 }
1394
1395
1396 void Path::RecCubicTo(Geom::Point const &iS, Geom::Point const &isD,
1397                       Geom::Point const &iE, Geom::Point const &ieD,
1398                       double tresh, int lev, double st, double et,
1399                       int piece, offset_orig &orig)
1400 {
1401     const Geom::Point se = iE - iS;
1402     const double dC = Geom::L2(se);
1403     bool doneSub = false;
1404     if ( dC < 0.01 ) {
1405         const double sC = dot(isD, isD);
1406         const double eC = dot(ieD, ieD);
1407         if ( sC < tresh && eC < tresh ) {
1408             return;
1409         }
1410     } else {
1411         const double sC = fabs(cross(se, isD)) / dC;
1412         const double eC = fabs(cross(se, ieD)) / dC;
1413         if ( sC < tresh && eC < tresh ) {
1414             doneSub = true;
1415         }
1416     }
1417
1418     if ( lev <= 0 ) {
1419         doneSub = true;
1420     }
1421
1422     // test des inversions
1423     bool stInv = false;
1424     bool enInv = false;
1425     {
1426         Geom::Point os_pos;
1427         Geom::Point os_tgt;
1428         Geom::Point oe_pos;
1429         Geom::Point oe_tgt;
1430
1431         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1432         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1433
1434
1435         Geom::Point n_tgt = isD;
1436         double si = dot(n_tgt, os_tgt);
1437         if ( si < 0 ) {
1438             stInv = true;
1439         }
1440         n_tgt = ieD;
1441         si = dot(n_tgt, oe_tgt);
1442         if ( si < 0 ) {
1443             enInv = true;
1444         }
1445         if ( stInv && enInv ) {
1446
1447             AddPoint(os_pos, -1, 0.0);
1448             AddPoint(iE, piece, et);
1449             AddPoint(iS, piece, st);
1450             AddPoint(oe_pos, -1, 0.0);
1451             return;
1452
1453         } else if ( ( stInv && !enInv ) || ( !stInv && enInv ) ) {
1454             return;
1455         }
1456
1457     }
1458
1459     if ( ( !stInv && !enInv && doneSub ) || lev <= 0 ) {
1460         return;
1461     }
1462
1463     {
1464         const Geom::Point m = 0.5 * (iS+iE) + 0.125 * (isD - ieD);
1465         const Geom::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1466         const double mt = (st + et) / 2;
1467         const Geom::Point hisD = 0.5 * isD;
1468         const Geom::Point hieD = 0.5 * ieD;
1469
1470         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece, orig);
1471         AddPoint(m, piece, mt);
1472         RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece, orig);
1473     }
1474 }
1475
1476
1477
1478 void Path::RecBezierTo(Geom::Point const &iP, Geom::Point const &iS,Geom::Point const &iE,
1479                        double tresh, int lev, double st, double et,
1480                        int piece, offset_orig& orig)
1481 {
1482     bool doneSub = false;
1483     if ( lev <= 0 ) {
1484         return;
1485     }
1486
1487     const Geom::Point ps = iS - iP;
1488     const Geom::Point pe = iE - iP;
1489     const double s = fabs(cross(pe, ps));
1490     if ( s < tresh ) {
1491         doneSub = true ;
1492     }
1493
1494     // test des inversions
1495     bool stInv = false;
1496     bool enInv = false;
1497     {
1498         Geom::Point os_pos;
1499         Geom::Point os_tgt;
1500         Geom::Point oe_pos;
1501         Geom::Point oe_tgt;
1502         Geom::Point n_tgt;
1503         Geom::Point n_pos;
1504
1505         double n_len;
1506         double n_rad;
1507         PathDescrIntermBezierTo mid(iP);
1508         PathDescrBezierTo fin(iE, 1);
1509
1510         TangentOnBezAt(0.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1511         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1512         double si = dot(n_tgt, os_tgt);
1513         if ( si < 0 ) {
1514             stInv = true;
1515         }
1516
1517         TangentOnBezAt(1.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1518         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1519         si = dot(n_tgt, oe_tgt);
1520         if ( si < 0 ) {
1521             enInv = true;
1522         }
1523
1524         if ( stInv && enInv ) {
1525             AddPoint(os_pos, -1, 0.0);
1526             AddPoint(iE, piece, et);
1527             AddPoint(iS, piece, st);
1528             AddPoint(oe_pos, -1, 0.0);
1529             return;
1530         }
1531     }
1532
1533     if ( !stInv && !enInv && doneSub ) {
1534         return;
1535     }
1536
1537     {
1538         double mt = (st + et) / 2;
1539         Geom::Point m = 0.25 * (iS + iE + 2 * iP);
1540         Geom::Point md = 0.5 * (iS + iP);
1541         RecBezierTo(md, iS, m, tresh, lev - 1, st, mt, piece, orig);
1542         AddPoint(m, piece, mt);
1543         md = 0.5 * (iP + iE);
1544         RecBezierTo(md, m, iE, tresh, lev - 1, mt, et, piece, orig);
1545     }
1546 }
1547
1548
1549 /*
1550  * put a polyline in a Shape instance, for further fun
1551  * pathID is the ID you want this Path instance to be associated with, for when you're going to recompose the polyline
1552  * in a path description ( you need to have prepared the back data for that, of course)
1553  */
1554
1555 void Path::Fill(Shape* dest, int pathID, bool justAdd, bool closeIfNeeded, bool invert)
1556 {
1557     if ( dest == NULL ) {
1558         return;
1559     }
1560
1561     if ( justAdd == false ) {
1562         dest->Reset(pts.size(), pts.size());
1563     }
1564
1565     if ( pts.size() <= 1 ) {
1566         return;
1567     }
1568
1569     int first = dest->numberOfPoints();
1570
1571     if ( back ) {
1572         dest->MakeBackData(true);
1573     }
1574
1575     if ( invert ) {
1576         if ( back ) {
1577             {
1578                 // invert && back && !weighted
1579                 for (int i = 0; i < int(pts.size()); i++) {
1580                     dest->AddPoint(pts[i].p);
1581                 }
1582                 int lastM = 0;
1583                 int curP = 1;
1584                 int pathEnd = 0;
1585                 bool closed = false;
1586                 int lEdge = -1;
1587
1588                 while ( curP < int(pts.size()) ) {
1589                     int sbp = curP;
1590                     int lm = lastM;
1591                     int prp = pathEnd;
1592
1593                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1594
1595                         if ( closeIfNeeded ) {
1596                             if ( closed && lEdge >= 0 ) {
1597                                 dest->DisconnectStart(lEdge);
1598                                 dest->ConnectStart(first + lastM, lEdge);
1599                             } else {
1600                                 lEdge = dest->AddEdge(first + lastM, first+pathEnd);
1601                                 if ( lEdge >= 0 ) {
1602                                     dest->ebData[lEdge].pathID = pathID;
1603                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1604                                     dest->ebData[lEdge].tSt = 1.0;
1605                                     dest->ebData[lEdge].tEn = 0.0;
1606                                 }
1607                             }
1608                         }
1609
1610                         lastM = curP;
1611                         pathEnd = curP;
1612                         closed = false;
1613                         lEdge = -1;
1614
1615                     } else {
1616
1617                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1618                             lEdge = dest->AddEdge(first + curP, first + pathEnd);
1619                             if ( lEdge >= 0 ) {
1620                                 dest->ebData[lEdge].pathID = pathID;
1621                                 dest->ebData[lEdge].pieceID = pts[sbp].piece;
1622                                 if ( pts[sbp].piece == pts[prp].piece ) {
1623                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1624                                     dest->ebData[lEdge].tEn = pts[prp].t;
1625                                 } else {
1626                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1627                                     dest->ebData[lEdge].tEn = 0.0;
1628                                 }
1629                             }
1630                             pathEnd = curP;
1631                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1632                                 closed = true;
1633                             } else {
1634                                 closed = false;
1635                             }
1636                         }
1637                     }
1638
1639                     curP++;
1640                 }
1641
1642                 if ( closeIfNeeded ) {
1643                     if ( closed && lEdge >= 0 ) {
1644                         dest->DisconnectStart(lEdge);
1645                         dest->ConnectStart(first + lastM, lEdge);
1646                     } else {
1647                         int lm = lastM;
1648                         lEdge = dest->AddEdge(first + lastM, first + pathEnd);
1649                         if ( lEdge >= 0 ) {
1650                             dest->ebData[lEdge].pathID = pathID;
1651                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1652                             dest->ebData[lEdge].tSt = 1.0;
1653                             dest->ebData[lEdge].tEn = 0.0;
1654                         }
1655                     }
1656                 }
1657             }
1658
1659         } else {
1660
1661             {
1662                 // invert && !back && !weighted
1663                 for (int i = 0; i < int(pts.size()); i++) {
1664                     dest->AddPoint(pts[i].p);
1665                 }
1666                 int lastM = 0;
1667                 int curP = 1;
1668                 int pathEnd = 0;
1669                 bool closed = false;
1670                 int lEdge = -1;
1671                 while ( curP < int(pts.size()) ) {
1672                     int sbp = curP;
1673                     int lm = lastM;
1674                     int prp = pathEnd;
1675                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1676                         if ( closeIfNeeded ) {
1677                             if ( closed && lEdge >= 0 ) {
1678                                 dest->DisconnectStart(lEdge);
1679                                 dest->ConnectStart(first + lastM, lEdge);
1680                             } else {
1681                                 dest->AddEdge(first + lastM, first + pathEnd);
1682                             }
1683                         }
1684                         lastM = curP;
1685                         pathEnd = curP;
1686                         closed = false;
1687                         lEdge = -1;
1688                     } else {
1689                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1690                             lEdge = dest->AddEdge(first+curP, first+pathEnd);
1691                             pathEnd = curP;
1692                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1693                                 closed = true;
1694                             } else {
1695                                 closed = false;
1696                             }
1697                         }
1698                     }
1699                     curP++;
1700                 }
1701
1702                 if ( closeIfNeeded ) {
1703                     if ( closed && lEdge >= 0 ) {
1704                         dest->DisconnectStart(lEdge);
1705                         dest->ConnectStart(first + lastM, lEdge);
1706                     } else {
1707                         dest->AddEdge(first + lastM, first + pathEnd);
1708                     }
1709                 }
1710
1711             }
1712         }
1713
1714     } else {
1715
1716         if ( back ) {
1717             {
1718                 // !invert && back && !weighted
1719                 for (int i = 0; i < int(pts.size()); i++) {
1720                     dest->AddPoint(pts[i].p);
1721                 }
1722
1723                 int lastM = 0;
1724                 int curP = 1;
1725                 int pathEnd = 0;
1726                 bool closed = false;
1727                 int lEdge = -1;
1728                 while ( curP < int(pts.size()) ) {
1729                     int sbp = curP;
1730                     int lm = lastM;
1731                     int prp = pathEnd;
1732                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1733                         if ( closeIfNeeded ) {
1734                             if ( closed && lEdge >= 0 ) {
1735                                 dest->DisconnectEnd(lEdge);
1736                                 dest->ConnectEnd(first + lastM, lEdge);
1737                             } else {
1738                                 lEdge = dest->AddEdge(first + pathEnd, first+lastM);
1739                                 if ( lEdge >= 0 ) {
1740                                     dest->ebData[lEdge].pathID = pathID;
1741                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1742                                     dest->ebData[lEdge].tSt = 0.0;
1743                                     dest->ebData[lEdge].tEn = 1.0;
1744                                 }
1745                             }
1746                         }
1747                         lastM = curP;
1748                         pathEnd = curP;
1749                         closed = false;
1750                         lEdge = -1;
1751                     } else {
1752                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1753                             lEdge = dest->AddEdge(first + pathEnd, first + curP);
1754                             dest->ebData[lEdge].pathID = pathID;
1755                             dest->ebData[lEdge].pieceID = pts[sbp].piece;
1756                             if ( pts[sbp].piece == pts[prp].piece ) {
1757                                 dest->ebData[lEdge].tSt = pts[prp].t;
1758                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1759                             } else {
1760                                 dest->ebData[lEdge].tSt = 0.0;
1761                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1762                             }
1763                             pathEnd = curP;
1764                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1765                                 closed = true;
1766                             } else {
1767                                 closed = false;
1768                             }
1769                         }
1770                     }
1771                     curP++;
1772                 }
1773
1774                 if ( closeIfNeeded ) {
1775                     if ( closed && lEdge >= 0 ) {
1776                         dest->DisconnectEnd(lEdge);
1777                         dest->ConnectEnd(first + lastM, lEdge);
1778                     } else {
1779                         int lm = lastM;
1780                         lEdge = dest->AddEdge(first + pathEnd, first + lastM);
1781                         if ( lEdge >= 0 ) {
1782                             dest->ebData[lEdge].pathID = pathID;
1783                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1784                             dest->ebData[lEdge].tSt = 0.0;
1785                             dest->ebData[lEdge].tEn = 1.0;
1786                         }
1787                     }
1788                 }
1789             }
1790
1791         } else {
1792             {
1793                 // !invert && !back && !weighted
1794                 for (int i = 0;i < int(pts.size()); i++) {
1795                     dest->AddPoint(pts[i].p);
1796                 }
1797
1798                 int lastM = 0;
1799                 int curP = 1;
1800                 int pathEnd = 0;
1801                 bool closed = false;
1802                 int lEdge = -1;
1803                 while ( curP < int(pts.size()) ) {
1804                     int sbp = curP;
1805                     int lm = lastM;
1806                     int prp = pathEnd;
1807                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1808                         if ( closeIfNeeded ) {
1809                             if ( closed && lEdge >= 0 ) {
1810                                 dest->DisconnectEnd(lEdge);
1811                                 dest->ConnectEnd(first + lastM, lEdge);
1812                             } else {
1813                                 dest->AddEdge(first + pathEnd, first + lastM);
1814                             }
1815                         }
1816                         lastM = curP;
1817                         pathEnd = curP;
1818                         closed = false;
1819                         lEdge = -1;
1820                     } else {
1821                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1822                             lEdge = dest->AddEdge(first+pathEnd, first+curP);
1823                             pathEnd = curP;
1824                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1825                                 closed = true;
1826                             } else {
1827                                 closed = false;
1828                             }
1829                         }
1830                     }
1831                     curP++;
1832                 }
1833
1834                 if ( closeIfNeeded ) {
1835                     if ( closed && lEdge >= 0 ) {
1836                         dest->DisconnectEnd(lEdge);
1837                         dest->ConnectEnd(first + lastM, lEdge);
1838                     } else {
1839                         dest->AddEdge(first + pathEnd, first + lastM);
1840                     }
1841                 }
1842
1843             }
1844         }
1845     }
1846 }
1847
1848 /*
1849   Local Variables:
1850   mode:c++
1851   c-file-style:"stroustrup"
1852   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1853   indent-tabs-mode:nil
1854   fill-column:99
1855   End:
1856 */
1857 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :