src/livarot/Shape.cpp

   1 /*
   2  *  Shape.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Thu Jun 12 2003.
   6  *
   7  */
   8
   9 #include <cstdio>
  10 #include <cstdlib>
  11 #include <glib/gmem.h>
  12 #include "Shape.h"
  13 #include "livarot/sweep-event-queue.h"
  14 #include "livarot/sweep-tree-list.h"
  15 #include <libnr/nr-point-fns.h>
  16
  17 /*
  18  * Shape instances handling.
  19  * never (i repeat: never) modify edges and points links; use Connect() and Disconnect() instead
  20  * the graph is stored as a set of points and edges, with edges in a doubly-linked list for each point.
  21  */
  22
  23 Shape::Shape()
  24   : qrsData(NULL),
  25     iData(NULL),
  26     sTree(NULL),
  27     sEvts(NULL),
  28     _need_points_sorting(false),
  29     _need_edges_sorting(false),
  30     _has_points_data(false),
  31     _point_data_initialised(false),
  32     _has_edges_data(false),
  33     _has_sweep_src_data(false),
  34     _has_sweep_dest_data(false),
  35     _has_raster_data(false),
  36     _has_quick_raster_data(false),
  37     _has_back_data(false),
  38     _has_voronoi_data(false),
  39     _bbox_up_to_date(false)
  40 {
  41   leftX = topY = rightX = bottomY = 0;
  42   maxPt = 0;
  43   maxAr = 0;
  44
  45   type = shape_polygon;
  46 }
  47 Shape::~Shape (void)
  48 {
  49   maxPt = 0;
  50   maxAr = 0;
  51   free(qrsData);
  52 }
  53
  54 void Shape::Affiche(void)
  55 {
  56   printf("sh=%p nbPt=%i nbAr=%i\n", this, static_cast<int>(_pts.size()), static_cast<int>(_aretes.size())); // localizing ok
  57   for (unsigned int i=0; i<_pts.size(); i++) {
  58     printf("pt %i : x=(%f %f) dI=%i dO=%i\n",i, _pts[i].x[0], _pts[i].x[1], _pts[i].dI, _pts[i].dO); // localizing ok
  59   }
  60   for (unsigned int i=0; i<_aretes.size(); i++) {
  61     printf("ar %i : dx=(%f %f) st=%i en=%i\n",i, _aretes[i].dx[0], _aretes[i].dx[1], _aretes[i].st, _aretes[i].en); // localizing ok
  62   }
  63 }
  64
  65 /**
  66  * Allocates space for point cache or clears the cache
  67  \param  nVal   Allocate a cache (true) or clear it (false)
  68  */
  69 void
  70 Shape::MakePointData (bool nVal)
  71 {
  72   if (nVal)
  73     {
  74       if (_has_points_data == false)
  75         {
  76           _has_points_data = true;
  77           _point_data_initialised = false;
  78           _bbox_up_to_date = false;
  79           pData.resize(maxPt);
  80         }
  81     }
  82     /* no need to clean point data - keep it cached*/
  83 }
  84
  85 void
  86 Shape::MakeEdgeData (bool nVal)
  87 {
  88   if (nVal)
  89     {
  90       if (_has_edges_data == false)
  91         {
  92           _has_edges_data = true;
  93           eData.resize(maxAr);
  94         }
  95     }
  96   else
  97     {
  98       if (_has_edges_data)
  99         {
 100           _has_edges_data = false;
 101           eData.clear();
 102         }
 103     }
 104 }
 105
 106 void
 107 Shape::MakeRasterData (bool nVal)
 108 {
 109   if (nVal)
 110     {
 111       if (_has_raster_data == false)
 112         {
 113           _has_raster_data = true;
 114           swrData.resize(maxAr);
 115         }
 116     }
 117   else
 118     {
 119       if (_has_raster_data)
 120         {
 121           _has_raster_data = false;
 122           swrData.clear();
 123         }
 124     }
 125 }
 126 void
 127 Shape::MakeQuickRasterData (bool nVal)
 128 {
 129   if (nVal)
 130     {
 131       if (_has_quick_raster_data == false)
 132         {
 133           _has_quick_raster_data = true;
 134           qrsData = (quick_raster_data*)realloc(qrsData, maxAr * sizeof(quick_raster_data));
 135         }
 136     }
 137   else
 138     {
 139       if (_has_quick_raster_data)
 140         {
 141           _has_quick_raster_data = false;
 142         }
 143     }
 144 }
 145 void
 146 Shape::MakeSweepSrcData (bool nVal)
 147 {
 148   if (nVal)
 149     {
 150       if (_has_sweep_src_data == false)
 151         {
 152           _has_sweep_src_data = true;
 153           swsData.resize(maxAr);
 154         }
 155     }
 156   else
 157     {
 158       if (_has_sweep_src_data)
 159         {
 160           _has_sweep_src_data = false;
 161           swsData.clear();
 162         }
 163     }
 164 }
 165 void
 166 Shape::MakeSweepDestData (bool nVal)
 167 {
 168   if (nVal)
 169     {
 170       if (_has_sweep_dest_data == false)
 171         {
 172           _has_sweep_dest_data = true;
 173           swdData.resize(maxAr);
 174         }
 175     }
 176   else
 177     {
 178       if (_has_sweep_dest_data)
 179         {
 180           _has_sweep_dest_data = false;
 181           swdData.clear();
 182         }
 183     }
 184 }
 185 void
 186 Shape::MakeBackData (bool nVal)
 187 {
 188   if (nVal)
 189     {
 190       if (_has_back_data == false)
 191         {
 192           _has_back_data = true;
 193           ebData.resize(maxAr);
 194         }
 195     }
 196   else
 197     {
 198       if (_has_back_data)
 199         {
 200           _has_back_data = false;
 201           ebData.clear();
 202         }
 203     }
 204 }
 205 void
 206 Shape::MakeVoronoiData (bool nVal)
 207 {
 208   if (nVal)
 209     {
 210       if (_has_voronoi_data == false)
 211         {
 212           _has_voronoi_data = true;
 213           vorpData.resize(maxPt);
 214           voreData.resize(maxAr);
 215         }
 216     }
 217   else
 218     {
 219       if (_has_voronoi_data)
 220         {
 221           _has_voronoi_data = false;
 222           vorpData.clear();
 223           voreData.clear();
 224         }
 225     }
 226 }
 227
 228
 229 /**
 230  *  Copy point and edge data from `who' into this object, discarding
 231  *  any cached data that we have.
 232  */
 233 void
 234 Shape::Copy (Shape * who)
 235 {
 236   if (who == NULL)
 237     {
 238       Reset (0, 0);
 239       return;
 240     }
 241   MakePointData (false);
 242   MakeEdgeData (false);
 243   MakeSweepSrcData (false);
 244   MakeSweepDestData (false);
 245   MakeRasterData (false);
 246   MakeQuickRasterData (false);
 247   MakeBackData (false);
 248
 249   delete sTree;
 250   sTree = NULL;
 251   delete sEvts;
 252   sEvts = NULL;
 253
 254   Reset (who->numberOfPoints(), who->numberOfEdges());
 255   type = who->type;
 256   _need_points_sorting = who->_need_points_sorting;
 257   _need_edges_sorting = who->_need_edges_sorting;
 258   _has_points_data = false;
 259   _point_data_initialised = false;
 260   _has_edges_data = false;
 261   _has_sweep_src_data = false;
 262   _has_sweep_dest_data = false;
 263   _has_raster_data = false;
 264   _has_quick_raster_data = false;
 265   _has_back_data = false;
 266   _has_voronoi_data = false;
 267   _bbox_up_to_date = false;
 268
 269   _pts = who->_pts;
 270   _aretes = who->_aretes;
 271 }
 272
 273 /**
 274  *  Clear points and edges and prepare internal data using new size.
 275  */
 276 void
 277 Shape::Reset (int pointCount, int edgeCount)
 278 {
 279   _pts.clear();
 280   _aretes.clear();
 281
 282   type = shape_polygon;
 283   if (pointCount > maxPt)
 284     {
 285       maxPt = pointCount;
 286       if (_has_points_data)
 287         pData.resize(maxPt);
 288       if (_has_voronoi_data)
 289         vorpData.resize(maxPt);
 290     }
 291   if (edgeCount > maxAr)
 292     {
 293       maxAr = edgeCount;
 294       if (_has_edges_data)
 295         eData.resize(maxAr);
 296       if (_has_sweep_dest_data)
 297         swdData.resize(maxAr);
 298       if (_has_sweep_src_data)
 299         swsData.resize(maxAr);
 300       if (_has_back_data)
 301         ebData.resize(maxAr);
 302       if (_has_voronoi_data)
 303         voreData.resize(maxAr);
 304     }
 305   _need_points_sorting = false;
 306   _need_edges_sorting = false;
 307   _point_data_initialised = false;
 308   _bbox_up_to_date = false;
 309 }
 310
 311 int
 312 Shape::AddPoint (const Geom::Point x)
 313 {
 314   if (numberOfPoints() >= maxPt)
 315     {
 316       maxPt = 2 * numberOfPoints() + 1;
 317       if (_has_points_data)
 318         pData.resize(maxPt);
 319       if (_has_voronoi_data)
 320         vorpData.resize(maxPt);
 321     }
 322
 323   dg_point p;
 324   p.x = x;
 325   p.dI = p.dO = 0;
 326   p.incidentEdge[FIRST] = p.incidentEdge[LAST] = -1;
 327   p.oldDegree = -1;
 328   _pts.push_back(p);
 329   int const n = _pts.size() - 1;
 330
 331   if (_has_points_data)
 332     {
 333       pData[n].pending = 0;
 334       pData[n].edgeOnLeft = -1;
 335       pData[n].nextLinkedPoint = -1;
 336       pData[n].askForWindingS = NULL;
 337       pData[n].askForWindingB = -1;
 338       pData[n].rx[0] = Round(p.x[0]);
 339       pData[n].rx[1] = Round(p.x[1]);
 340     }
 341   if (_has_voronoi_data)
 342     {
 343       vorpData[n].value = 0.0;
 344       vorpData[n].winding = -2;
 345     }
 346   _need_points_sorting = true;
 347
 348   return n;
 349 }
 350
 351 void
 352 Shape::SubPoint (int p)
 353 {
 354   if (p < 0 || p >= numberOfPoints())
 355     return;
 356   _need_points_sorting = true;
 357   int cb;
 358   cb = getPoint(p).incidentEdge[FIRST];
 359   while (cb >= 0 && cb < numberOfEdges())
 360     {
 361       if (getEdge(cb).st == p)
 362         {
 363           int ncb = getEdge(cb).nextS;
 364           _aretes[cb].nextS = _aretes[cb].prevS = -1;
 365           _aretes[cb].st = -1;
 366           cb = ncb;
 367         }
 368       else if (getEdge(cb).en == p)
 369         {
 370           int ncb = getEdge(cb).nextE;
 371           _aretes[cb].nextE = _aretes[cb].prevE = -1;
 372           _aretes[cb].en = -1;
 373           cb = ncb;
 374         }
 375       else
 376         {
 377           break;
 378         }
 379     }
 380   _pts[p].incidentEdge[FIRST] = _pts[p].incidentEdge[LAST] = -1;
 381   if (p < numberOfPoints() - 1)
 382     SwapPoints (p, numberOfPoints() - 1);
 383   _pts.pop_back();
 384 }
 385
 386 void
 387 Shape::SwapPoints (int a, int b)
 388 {
 389   if (a == b)
 390     return;
 391   if (getPoint(a).totalDegree() == 2 && getPoint(b).totalDegree() == 2)
 392     {
 393       int cb = getPoint(a).incidentEdge[FIRST];
 394       if (getEdge(cb).st == a)
 395         {
 396           _aretes[cb].st = numberOfPoints();
 397         }
 398       else if (getEdge(cb).en == a)
 399         {
 400           _aretes[cb].en = numberOfPoints();
 401         }
 402       cb = getPoint(a).incidentEdge[LAST];
 403       if (getEdge(cb).st == a)
 404         {
 405           _aretes[cb].st = numberOfPoints();
 406         }
 407       else if (getEdge(cb).en == a)
 408         {
 409           _aretes[cb].en = numberOfPoints();
 410         }
 411
 412       cb = getPoint(b).incidentEdge[FIRST];
 413       if (getEdge(cb).st == b)
 414         {
 415           _aretes[cb].st = a;
 416         }
 417       else if (getEdge(cb).en == b)
 418         {
 419           _aretes[cb].en = a;
 420         }
 421       cb = getPoint(b).incidentEdge[LAST];
 422       if (getEdge(cb).st == b)
 423         {
 424           _aretes[cb].st = a;
 425         }
 426       else if (getEdge(cb).en == b)
 427         {
 428           _aretes[cb].en = a;
 429         }
 430
 431       cb = getPoint(a).incidentEdge[FIRST];
 432       if (getEdge(cb).st == numberOfPoints())
 433         {
 434           _aretes[cb].st = b;
 435         }
 436       else if (getEdge(cb).en == numberOfPoints())
 437         {
 438           _aretes[cb].en = b;
 439         }
 440       cb = getPoint(a).incidentEdge[LAST];
 441       if (getEdge(cb).st == numberOfPoints())
 442         {
 443           _aretes[cb].st = b;
 444         }
 445       else if (getEdge(cb).en == numberOfPoints())
 446         {
 447           _aretes[cb].en = b;
 448         }
 449
 450     }
 451   else
 452     {
 453       int cb;
 454       cb = getPoint(a).incidentEdge[FIRST];
 455       while (cb >= 0)
 456         {
 457           int ncb = NextAt (a, cb);
 458           if (getEdge(cb).st == a)
 459             {
 460               _aretes[cb].st = numberOfPoints();
 461             }
 462           else if (getEdge(cb).en == a)
 463             {
 464               _aretes[cb].en = numberOfPoints();
 465             }
 466           cb = ncb;
 467         }
 468       cb = getPoint(b).incidentEdge[FIRST];
 469       while (cb >= 0)
 470         {
 471           int ncb = NextAt (b, cb);
 472           if (getEdge(cb).st == b)
 473             {
 474               _aretes[cb].st = a;
 475             }
 476           else if (getEdge(cb).en == b)
 477             {
 478               _aretes[cb].en = a;
 479             }
 480           cb = ncb;
 481         }
 482       cb = getPoint(a).incidentEdge[FIRST];
 483       while (cb >= 0)
 484         {
 485           int ncb = NextAt (numberOfPoints(), cb);
 486           if (getEdge(cb).st == numberOfPoints())
 487             {
 488               _aretes[cb].st = b;
 489             }
 490           else if (getEdge(cb).en == numberOfPoints())
 491             {
 492               _aretes[cb].en = b;
 493             }
 494           cb = ncb;
 495         }
 496     }
 497   {
 498     dg_point swap = getPoint(a);
 499     _pts[a] = getPoint(b);
 500     _pts[b] = swap;
 501   }
 502   if (_has_points_data)
 503     {
 504       point_data swad = pData[a];
 505       pData[a] = pData[b];
 506       pData[b] = swad;
 507       //              pData[pData[a].oldInd].newInd=a;
 508       //              pData[pData[b].oldInd].newInd=b;
 509     }
 510   if (_has_voronoi_data)
 511     {
 512       voronoi_point swav = vorpData[a];
 513       vorpData[a] = vorpData[b];
 514       vorpData[b] = swav;
 515     }
 516 }
 517 void
 518 Shape::SwapPoints (int a, int b, int c)
 519 {
 520   if (a == b || b == c || a == c)
 521     return;
 522   SwapPoints (a, b);
 523   SwapPoints (b, c);
 524 }
 525
 526 void
 527 Shape::SortPoints (void)
 528 {
 529   if (_need_points_sorting && hasPoints())
 530     SortPoints (0, numberOfPoints() - 1);
 531   _need_points_sorting = false;
 532 }
 533
 534 void
 535 Shape::SortPointsRounded (void)
 536 {
 537   if (hasPoints())
 538     SortPointsRounded (0, numberOfPoints() - 1);
 539 }
 540
 541 void
 542 Shape::SortPoints (int s, int e)
 543 {
 544   if (s >= e)
 545     return;
 546   if (e == s + 1)
 547     {
 548       if (getPoint(s).x[1] > getPoint(e).x[1]
 549           || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] > getPoint(e).x[0]))
 550         SwapPoints (s, e);
 551       return;
 552     }
 553
 554   int ppos = (s + e) / 2;
 555   int plast = ppos;
 556   double pvalx = getPoint(ppos).x[0];
 557   double pvaly = getPoint(ppos).x[1];
 558
 559   int le = s, ri = e;
 560   while (le < ppos || ri > plast)
 561     {
 562       if (le < ppos)
 563         {
 564           do
 565             {
 566               int test = 0;
 567               if (getPoint(le).x[1] > pvaly)
 568                 {
 569                   test = 1;
 570                 }
 571               else if (getPoint(le).x[1] == pvaly)
 572                 {
 573                   if (getPoint(le).x[0] > pvalx)
 574                     {
 575                       test = 1;
 576                     }
 577                   else if (getPoint(le).x[0] == pvalx)
 578                     {
 579                       test = 0;
 580                     }
 581                   else
 582                     {
 583                       test = -1;
 584                     }
 585                 }
 586               else
 587                 {
 588                   test = -1;
 589                 }
 590               if (test == 0)
 591                 {
 592                   // on colle les valeurs egales au pivot ensemble
 593                   if (le < ppos - 1)
 594                     {
 595                       SwapPoints (le, ppos - 1, ppos);
 596                       ppos--;
 597                       continue; // sans changer le
 598                     }
 599                   else if (le == ppos - 1)
 600                     {
 601                       ppos--;
 602                       break;
 603                     }
 604                   else
 605                     {
 606                       // oupsie
 607                       break;
 608                     }
 609                 }
 610               if (test > 0)
 611                 {
 612                   break;
 613                 }
 614               le++;
 615             }
 616           while (le < ppos);
 617         }
 618       if (ri > plast)
 619         {
 620           do
 621             {
 622               int test = 0;
 623               if (getPoint(ri).x[1] > pvaly)
 624                 {
 625                   test = 1;
 626                 }
 627               else if (getPoint(ri).x[1] == pvaly)
 628                 {
 629                   if (getPoint(ri).x[0] > pvalx)
 630                     {
 631                       test = 1;
 632                     }
 633                   else if (getPoint(ri).x[0] == pvalx)
 634                     {
 635                       test = 0;
 636                     }
 637                   else
 638                     {
 639                       test = -1;
 640                     }
 641                 }
 642               else
 643                 {
 644                   test = -1;
 645                 }
 646               if (test == 0)
 647                 {
 648                   // on colle les valeurs egales au pivot ensemble
 649                   if (ri > plast + 1)
 650                     {
 651                       SwapPoints (ri, plast + 1, plast);
 652                       plast++;
 653                       continue; // sans changer ri
 654                     }
 655                   else if (ri == plast + 1)
 656                     {
 657                       plast++;
 658                       break;
 659                     }
 660                   else
 661                     {
 662                       // oupsie
 663                       break;
 664                     }
 665                 }
 666               if (test < 0)
 667                 {
 668                   break;
 669                 }
 670               ri--;
 671             }
 672           while (ri > plast);
 673         }
 674       if (le < ppos)
 675         {
 676           if (ri > plast)
 677             {
 678               SwapPoints (le, ri);
 679               le++;
 680               ri--;
 681             }
 682           else
 683             {
 684               if (le < ppos - 1)
 685                 {
 686                   SwapPoints (ppos - 1, plast, le);
 687                   ppos--;
 688                   plast--;
 689                 }
 690               else if (le == ppos - 1)
 691                 {
 692                   SwapPoints (plast, le);
 693                   ppos--;
 694                   plast--;
 695                 }
 696             }
 697         }
 698       else
 699         {
 700           if (ri > plast + 1)
 701             {
 702               SwapPoints (plast + 1, ppos, ri);
 703               ppos++;
 704               plast++;
 705             }
 706           else if (ri == plast + 1)
 707             {
 708               SwapPoints (ppos, ri);
 709               ppos++;
 710               plast++;
 711             }
 712           else
 713             {
 714               break;
 715             }
 716         }
 717     }
 718   SortPoints (s, ppos - 1);
 719   SortPoints (plast + 1, e);
 720 }
 721
 722 void
 723 Shape::SortPointsByOldInd (int s, int e)
 724 {
 725   if (s >= e)
 726     return;
 727   if (e == s + 1)
 728     {
 729       if (getPoint(s).x[1] > getPoint(e).x[1] || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] > getPoint(e).x[0])
 730           || (getPoint(s).x[1] == getPoint(e).x[1] && getPoint(s).x[0] == getPoint(e).x[0]
 731               && pData[s].oldInd > pData[e].oldInd))
 732         SwapPoints (s, e);
 733       return;
 734     }
 735
 736   int ppos = (s + e) / 2;
 737   int plast = ppos;
 738   double pvalx = getPoint(ppos).x[0];
 739   double pvaly = getPoint(ppos).x[1];
 740   int pvali = pData[ppos].oldInd;
 741
 742   int le = s, ri = e;
 743   while (le < ppos || ri > plast)
 744     {
 745       if (le < ppos)
 746         {
 747           do
 748             {
 749               int test = 0;
 750               if (getPoint(le).x[1] > pvaly)
 751                 {
 752                   test = 1;
 753                 }
 754               else if (getPoint(le).x[1] == pvaly)
 755                 {
 756                   if (getPoint(le).x[0] > pvalx)
 757                     {
 758                       test = 1;
 759                     }
 760                   else if (getPoint(le).x[0] == pvalx)
 761                     {
 762                       if (pData[le].oldInd > pvali)
 763                         {
 764                           test = 1;
 765                         }
 766                       else if (pData[le].oldInd == pvali)
 767                         {
 768                           test = 0;
 769                         }
 770                       else
 771                         {
 772                           test = -1;
 773                         }
 774                     }
 775                   else
 776                     {
 777                       test = -1;
 778                     }
 779                 }
 780               else
 781                 {
 782                   test = -1;
 783                 }
 784               if (test == 0)
 785                 {
 786                   // on colle les valeurs egales au pivot ensemble
 787                   if (le < ppos - 1)
 788                     {
 789                       SwapPoints (le, ppos - 1, ppos);
 790                       ppos--;
 791                       continue; // sans changer le
 792                     }
 793                   else if (le == ppos - 1)
 794                     {
 795                       ppos--;
 796                       break;
 797                     }
 798                   else
 799                     {
 800                       // oupsie
 801                       break;
 802                     }
 803                 }
 804               if (test > 0)
 805                 {
 806                   break;
 807                 }
 808               le++;
 809             }
 810           while (le < ppos);
 811         }
 812       if (ri > plast)
 813         {
 814           do
 815             {
 816               int test = 0;
 817               if (getPoint(ri).x[1] > pvaly)
 818                 {
 819                   test = 1;
 820                 }
 821               else if (getPoint(ri).x[1] == pvaly)
 822                 {
 823                   if (getPoint(ri).x[0] > pvalx)
 824                     {
 825                       test = 1;
 826                     }
 827                   else if (getPoint(ri).x[0] == pvalx)
 828                     {
 829                       if (pData[ri].oldInd > pvali)
 830                         {
 831                           test = 1;
 832                         }
 833                       else if (pData[ri].oldInd == pvali)
 834                         {
 835                           test = 0;
 836                         }
 837                       else
 838                         {
 839                           test = -1;
 840                         }
 841                     }
 842                   else
 843                     {
 844                       test = -1;
 845                     }
 846                 }
 847               else
 848                 {
 849                   test = -1;
 850                 }
 851               if (test == 0)
 852                 {
 853                   // on colle les valeurs egales au pivot ensemble
 854                   if (ri > plast + 1)
 855                     {
 856                       SwapPoints (ri, plast + 1, plast);
 857                       plast++;
 858                       continue; // sans changer ri
 859                     }
 860                   else if (ri == plast + 1)
 861                     {
 862                       plast++;
 863                       break;
 864                     }
 865                   else
 866                     {
 867                       // oupsie
 868                       break;
 869                     }
 870                 }
 871               if (test < 0)
 872                 {
 873                   break;
 874                 }
 875               ri--;
 876             }
 877           while (ri > plast);
 878         }
 879       if (le < ppos)
 880         {
 881           if (ri > plast)
 882             {
 883               SwapPoints (le, ri);
 884               le++;
 885               ri--;
 886             }
 887           else
 888             {
 889               if (le < ppos - 1)
 890                 {
 891                   SwapPoints (ppos - 1, plast, le);
 892                   ppos--;
 893                   plast--;
 894                 }
 895               else if (le == ppos - 1)
 896                 {
 897                   SwapPoints (plast, le);
 898                   ppos--;
 899                   plast--;
 900                 }
 901             }
 902         }
 903       else
 904         {
 905           if (ri > plast + 1)
 906             {
 907               SwapPoints (plast + 1, ppos, ri);
 908               ppos++;
 909               plast++;
 910             }
 911           else if (ri == plast + 1)
 912             {
 913               SwapPoints (ppos, ri);
 914               ppos++;
 915               plast++;
 916             }
 917           else
 918             {
 919               break;
 920             }
 921         }
 922     }
 923   SortPointsByOldInd (s, ppos - 1);
 924   SortPointsByOldInd (plast + 1, e);
 925 }
 926
 927 void
 928 Shape::SortPointsRounded (int s, int e)
 929 {
 930   if (s >= e)
 931     return;
 932   if (e == s + 1)
 933     {
 934       if (pData[s].rx[1] > pData[e].rx[1]
 935           || (pData[s].rx[1] == pData[e].rx[1] && pData[s].rx[0] > pData[e].rx[0]))
 936         SwapPoints (s, e);
 937       return;
 938     }
 939
 940   int ppos = (s + e) / 2;
 941   int plast = ppos;
 942   double pvalx = pData[ppos].rx[0];
 943   double pvaly = pData[ppos].rx[1];
 944
 945   int le = s, ri = e;
 946   while (le < ppos || ri > plast)
 947     {
 948       if (le < ppos)
 949         {
 950           do
 951             {
 952               int test = 0;
 953               if (pData[le].rx[1] > pvaly)
 954                 {
 955                   test = 1;
 956                 }
 957               else if (pData[le].rx[1] == pvaly)
 958                 {
 959                   if (pData[le].rx[0] > pvalx)
 960                     {
 961                       test = 1;
 962                     }
 963                   else if (pData[le].rx[0] == pvalx)
 964                     {
 965                       test = 0;
 966                     }
 967                   else
 968                     {
 969                       test = -1;
 970                     }
 971                 }
 972               else
 973                 {
 974                   test = -1;
 975                 }
 976               if (test == 0)
 977                 {
 978                   // on colle les valeurs egales au pivot ensemble
 979                   if (le < ppos - 1)
 980                     {
 981                       SwapPoints (le, ppos - 1, ppos);
 982                       ppos--;
 983                       continue; // sans changer le
 984                     }
 985                   else if (le == ppos - 1)
 986                     {
 987                       ppos--;
 988                       break;
 989                     }
 990                   else
 991                     {
 992                       // oupsie
 993                       break;
 994                     }
 995                 }
 996               if (test > 0)
 997                 {
 998                   break;
 999                 }
1000               le++;
1001             }
1002           while (le < ppos);
1003         }
1004       if (ri > plast)
1005         {
1006           do
1007             {
1008               int test = 0;
1009               if (pData[ri].rx[1] > pvaly)
1010                 {
1011                   test = 1;
1012                 }
1013               else if (pData[ri].rx[1] == pvaly)
1014                 {
1015                   if (pData[ri].rx[0] > pvalx)
1016                     {
1017                       test = 1;
1018                     }
1019                   else if (pData[ri].rx[0] == pvalx)
1020                     {
1021                       test = 0;
1022                     }
1023                   else
1024                     {
1025                       test = -1;
1026                     }
1027                 }
1028               else
1029                 {
1030                   test = -1;
1031                 }
1032               if (test == 0)
1033                 {
1034                   // on colle les valeurs egales au pivot ensemble
1035                   if (ri > plast + 1)
1036                     {
1037                       SwapPoints (ri, plast + 1, plast);
1038                       plast++;
1039                       continue; // sans changer ri
1040                     }
1041                   else if (ri == plast + 1)
1042                     {
1043                       plast++;
1044                       break;
1045                     }
1046                   else
1047                     {
1048                       // oupsie
1049                       break;
1050                     }
1051                 }
1052               if (test < 0)
1053                 {
1054                   break;
1055                 }
1056               ri--;
1057             }
1058           while (ri > plast);
1059         }
1060       if (le < ppos)
1061         {
1062           if (ri > plast)
1063             {
1064               SwapPoints (le, ri);
1065               le++;
1066               ri--;
1067             }
1068           else
1069             {
1070               if (le < ppos - 1)
1071                 {
1072                   SwapPoints (ppos - 1, plast, le);
1073                   ppos--;
1074                   plast--;
1075                 }
1076               else if (le == ppos - 1)
1077                 {
1078                   SwapPoints (plast, le);
1079                   ppos--;
1080                   plast--;
1081                 }
1082             }
1083         }
1084       else
1085         {
1086           if (ri > plast + 1)
1087             {
1088               SwapPoints (plast + 1, ppos, ri);
1089               ppos++;
1090               plast++;
1091             }
1092           else if (ri == plast + 1)
1093             {
1094               SwapPoints (ppos, ri);
1095               ppos++;
1096               plast++;
1097             }
1098           else
1099             {
1100               break;
1101             }
1102         }
1103     }
1104   SortPointsRounded (s, ppos - 1);
1105   SortPointsRounded (plast + 1, e);
1106 }
1107
1108 /*
1109  *
1110  */
1111 int
1112 Shape::AddEdge (int st, int en)
1113 {
1114   if (st == en)
1115     return -1;
1116   if (st < 0 || en < 0)
1117     return -1;
1118   type = shape_graph;
1119   if (numberOfEdges() >= maxAr)
1120     {
1121       maxAr = 2 * numberOfEdges() + 1;
1122       if (_has_edges_data)
1123         eData.resize(maxAr);
1124       if (_has_sweep_src_data)
1125         swsData.resize(maxAr);
1126       if (_has_sweep_dest_data)
1127         swdData.resize(maxAr);
1128       if (_has_raster_data)
1129         swrData.resize(maxAr);
1130       if (_has_back_data)
1131         ebData.resize(maxAr);
1132       if (_has_voronoi_data)
1133         voreData.resize(maxAr);
1134     }
1135
1136   dg_arete a;
1137   a.dx = Geom::Point(0, 0);
1138   a.st = a.en = -1;
1139   a.prevS = a.nextS = -1;
1140   a.prevE = a.nextE = -1;
1141   if (st >= 0 && en >= 0) {
1142     a.dx = getPoint(en).x - getPoint(st).x;
1143   }
1144
1145   _aretes.push_back(a);
1146   int const n = numberOfEdges() - 1;
1147
1148   ConnectStart (st, n);
1149   ConnectEnd (en, n);
1150   if (_has_edges_data)
1151     {
1152       eData[n].weight = 1;
1153       eData[n].rdx = getEdge(n).dx;
1154     }
1155   if (_has_sweep_src_data)
1156     {
1157       swsData[n].misc = NULL;
1158       swsData[n].firstLinkedPoint = -1;
1159     }
1160   if (_has_back_data)
1161     {
1162       ebData[n].pathID = -1;
1163       ebData[n].pieceID = -1;
1164       ebData[n].tSt = ebData[n].tEn = 0;
1165     }
1166   if (_has_voronoi_data)
1167     {
1168       voreData[n].leF = -1;
1169       voreData[n].riF = -1;
1170     }
1171   _need_edges_sorting = true;
1172   return n;
1173 }
1174
1175 int
1176 Shape::AddEdge (int st, int en, int leF, int riF)
1177 {
1178   if (st == en)
1179     return -1;
1180   if (st < 0 || en < 0)
1181     return -1;
1182   {
1183     int cb = getPoint(st).incidentEdge[FIRST];
1184     while (cb >= 0)
1185       {
1186         if (getEdge(cb).st == st && getEdge(cb).en == en)
1187           return -1;            // doublon
1188         if (getEdge(cb).st == en && getEdge(cb).en == st)
1189           return -1;            // doublon
1190         cb = NextAt (st, cb);
1191       }
1192   }
1193   type = shape_graph;
1194   if (numberOfEdges() >= maxAr)
1195     {
1196       maxAr = 2 * numberOfEdges() + 1;
1197       if (_has_edges_data)
1198         eData.resize(maxAr);
1199       if (_has_sweep_src_data)
1200         swsData.resize(maxAr);
1201       if (_has_sweep_dest_data)
1202         swdData.resize(maxAr);
1203       if (_has_raster_data)
1204         swrData.resize(maxAr);
1205       if (_has_back_data)
1206         ebData.resize(maxAr);
1207       if (_has_voronoi_data)
1208         voreData.resize(maxAr);
1209     }
1210
1211   dg_arete a;
1212   a.dx = Geom::Point(0, 0);
1213   a.st = a.en = -1;
1214   a.prevS = a.nextS = -1;
1215   a.prevE = a.nextE = -1;
1216   if (st >= 0 && en >= 0) {
1217     a.dx = getPoint(en).x - getPoint(st).x;
1218   }
1219
1220   _aretes.push_back(a);
1221   int const n = numberOfEdges() - 1;
1222
1223   ConnectStart (st, n);
1224   ConnectEnd (en, n);
1225   if (_has_edges_data)
1226     {
1227       eData[n].weight = 1;
1228       eData[n].rdx = getEdge(n).dx;
1229     }
1230   if (_has_sweep_src_data)
1231     {
1232       swsData[n].misc = NULL;
1233       swsData[n].firstLinkedPoint = -1;
1234     }
1235   if (_has_back_data)
1236     {
1237       ebData[n].pathID = -1;
1238       ebData[n].pieceID = -1;
1239       ebData[n].tSt = ebData[n].tEn = 0;
1240     }
1241   if (_has_voronoi_data)
1242     {
1243       voreData[n].leF = leF;
1244       voreData[n].riF = riF;
1245     }
1246   _need_edges_sorting = true;
1247   return n;
1248 }
1249
1250 void
1251 Shape::SubEdge (int e)
1252 {
1253   if (e < 0 || e >= numberOfEdges())
1254     return;
1255   type = shape_graph;
1256   DisconnectStart (e);
1257   DisconnectEnd (e);
1258   if (e < numberOfEdges() - 1)
1259     SwapEdges (e, numberOfEdges() - 1);
1260   _aretes.pop_back();
1261   _need_edges_sorting = true;
1262 }
1263
1264 void
1265 Shape::SwapEdges (int a, int b)
1266 {
1267   if (a == b)
1268     return;
1269   if (getEdge(a).prevS >= 0 && getEdge(a).prevS != b)
1270     {
1271       if (getEdge(getEdge(a).prevS).st == getEdge(a).st)
1272         {
1273           _aretes[getEdge(a).prevS].nextS = b;
1274         }
1275       else if (getEdge(getEdge(a).prevS).en == getEdge(a).st)
1276         {
1277           _aretes[getEdge(a).prevS].nextE = b;
1278         }
1279     }
1280   if (getEdge(a).nextS >= 0 && getEdge(a).nextS != b)
1281     {
1282       if (getEdge(getEdge(a).nextS).st == getEdge(a).st)
1283         {
1284           _aretes[getEdge(a).nextS].prevS = b;
1285         }
1286       else if (getEdge(getEdge(a).nextS).en == getEdge(a).st)
1287         {
1288           _aretes[getEdge(a).nextS].prevE = b;
1289         }
1290     }
1291   if (getEdge(a).prevE >= 0 && getEdge(a).prevE != b)
1292     {
1293       if (getEdge(getEdge(a).prevE).st == getEdge(a).en)
1294         {
1295           _aretes[getEdge(a).prevE].nextS = b;
1296         }
1297       else if (getEdge(getEdge(a).prevE).en == getEdge(a).en)
1298         {
1299           _aretes[getEdge(a).prevE].nextE = b;
1300         }
1301     }
1302   if (getEdge(a).nextE >= 0 && getEdge(a).nextE != b)
1303     {
1304       if (getEdge(getEdge(a).nextE).st == getEdge(a).en)
1305         {
1306           _aretes[getEdge(a).nextE].prevS = b;
1307         }
1308       else if (getEdge(getEdge(a).nextE).en == getEdge(a).en)
1309         {
1310           _aretes[getEdge(a).nextE].prevE = b;
1311         }
1312     }
1313   if (getEdge(a).st >= 0)
1314     {
1315       if (getPoint(getEdge(a).st).incidentEdge[FIRST] == a)
1316         _pts[getEdge(a).st].incidentEdge[FIRST] = numberOfEdges();
1317       if (getPoint(getEdge(a).st).incidentEdge[LAST] == a)
1318         _pts[getEdge(a).st].incidentEdge[LAST] = numberOfEdges();
1319     }
1320   if (getEdge(a).en >= 0)
1321     {
1322       if (getPoint(getEdge(a).en).incidentEdge[FIRST] == a)
1323         _pts[getEdge(a).en].incidentEdge[FIRST] = numberOfEdges();
1324       if (getPoint(getEdge(a).en).incidentEdge[LAST] == a)
1325         _pts[getEdge(a).en].incidentEdge[LAST] = numberOfEdges();
1326     }
1327
1328
1329   if (getEdge(b).prevS >= 0 && getEdge(b).prevS != a)
1330     {
1331       if (getEdge(getEdge(b).prevS).st == getEdge(b).st)
1332         {
1333           _aretes[getEdge(b).prevS].nextS = a;
1334         }
1335       else if (getEdge(getEdge(b).prevS).en == getEdge(b).st)
1336         {
1337           _aretes[getEdge(b).prevS].nextE = a;
1338         }
1339     }
1340   if (getEdge(b).nextS >= 0 && getEdge(b).nextS != a)
1341     {
1342       if (getEdge(getEdge(b).nextS).st == getEdge(b).st)
1343         {
1344           _aretes[getEdge(b).nextS].prevS = a;
1345         }
1346       else if (getEdge(getEdge(b).nextS).en == getEdge(b).st)
1347         {
1348           _aretes[getEdge(b).nextS].prevE = a;
1349         }
1350     }
1351   if (getEdge(b).prevE >= 0 && getEdge(b).prevE != a)
1352     {
1353       if (getEdge(getEdge(b).prevE).st == getEdge(b).en)
1354         {
1355           _aretes[getEdge(b).prevE].nextS = a;
1356         }
1357       else if (getEdge(getEdge(b).prevE).en == getEdge(b).en)
1358         {
1359           _aretes[getEdge(b).prevE].nextE = a;
1360         }
1361     }
1362   if (getEdge(b).nextE >= 0 && getEdge(b).nextE != a)
1363     {
1364       if (getEdge(getEdge(b).nextE).st == getEdge(b).en)
1365         {
1366           _aretes[getEdge(b).nextE].prevS = a;
1367         }
1368       else if (getEdge(getEdge(b).nextE).en == getEdge(b).en)
1369         {
1370           _aretes[getEdge(b).nextE].prevE = a;
1371         }
1372     }
1373
1374
1375   for (int i = 0; i < 2; i++) {
1376     int p = getEdge(b).st;
1377     if (p >= 0) {
1378       if (getPoint(p).incidentEdge[i] == b) {
1379         _pts[p].incidentEdge[i] = a;
1380       }
1381     }
1382
1383     p = getEdge(b).en;
1384     if (p >= 0) {
1385       if (getPoint(p).incidentEdge[i] == b) {
1386         _pts[p].incidentEdge[i] = a;
1387       }
1388     }
1389
1390     p = getEdge(a).st;
1391     if (p >= 0) {
1392       if (getPoint(p).incidentEdge[i] == numberOfEdges()) {
1393         _pts[p].incidentEdge[i] = b;
1394       }
1395     }
1396
1397     p = getEdge(a).en;
1398     if (p >= 0) {
1399       if (getPoint(p).incidentEdge[i] == numberOfEdges()) {
1400         _pts[p].incidentEdge[i] = b;
1401       }
1402     }
1403
1404   }
1405
1406   if (getEdge(a).prevS == b)
1407     _aretes[a].prevS = a;
1408   if (getEdge(a).prevE == b)
1409     _aretes[a].prevE = a;
1410   if (getEdge(a).nextS == b)
1411     _aretes[a].nextS = a;
1412   if (getEdge(a).nextE == b)
1413     _aretes[a].nextE = a;
1414   if (getEdge(b).prevS == a)
1415     _aretes[a].prevS = b;
1416   if (getEdge(b).prevE == a)
1417     _aretes[a].prevE = b;
1418   if (getEdge(b).nextS == a)
1419     _aretes[a].nextS = b;
1420   if (getEdge(b).nextE == a)
1421     _aretes[a].nextE = b;
1422
1423   dg_arete swap = getEdge(a);
1424   _aretes[a] = getEdge(b);
1425   _aretes[b] = swap;
1426   if (_has_edges_data)
1427     {
1428       edge_data swae = eData[a];
1429       eData[a] = eData[b];
1430       eData[b] = swae;
1431     }
1432   if (_has_sweep_src_data)
1433     {
1434       sweep_src_data swae = swsData[a];
1435       swsData[a] = swsData[b];
1436       swsData[b] = swae;
1437     }
1438   if (_has_sweep_dest_data)
1439     {
1440       sweep_dest_data swae = swdData[a];
1441       swdData[a] = swdData[b];
1442       swdData[b] = swae;
1443     }
1444   if (_has_raster_data)
1445     {
1446       raster_data swae = swrData[a];
1447       swrData[a] = swrData[b];
1448       swrData[b] = swae;
1449     }
1450   if (_has_back_data)
1451     {
1452       back_data swae = ebData[a];
1453       ebData[a] = ebData[b];
1454       ebData[b] = swae;
1455     }
1456   if (_has_voronoi_data)
1457     {
1458       voronoi_edge swav = voreData[a];
1459       voreData[a] = voreData[b];
1460       voreData[b] = swav;
1461     }
1462 }
1463 void
1464 Shape::SwapEdges (int a, int b, int c)
1465 {
1466   if (a == b || b == c || a == c)
1467     return;
1468   SwapEdges (a, b);
1469   SwapEdges (b, c);
1470 }
1471
1472 void
1473 Shape::SortEdges (void)
1474 {
1475   if (_need_edges_sorting == false) {
1476     return;
1477   }
1478   _need_edges_sorting = false;
1479
1480   edge_list *list = (edge_list *) g_malloc(numberOfEdges() * sizeof (edge_list));
1481   for (int p = 0; p < numberOfPoints(); p++)
1482     {
1483       int const d = getPoint(p).totalDegree();
1484       if (d > 1)
1485         {
1486           int cb;
1487           cb = getPoint(p).incidentEdge[FIRST];
1488           int nb = 0;
1489           while (cb >= 0)
1490             {
1491               int n = nb++;
1492               list[n].no = cb;
1493               if (getEdge(cb).st == p)
1494                 {
1495                   list[n].x = getEdge(cb).dx;
1496                   list[n].starting = true;
1497                 }
1498               else
1499                 {
1500                   list[n].x = -getEdge(cb).dx;
1501                   list[n].starting = false;
1502                 }
1503               cb = NextAt (p, cb);
1504             }
1505           SortEdgesList (list, 0, nb - 1);
1506           _pts[p].incidentEdge[FIRST] = list[0].no;
1507           _pts[p].incidentEdge[LAST] = list[nb - 1].no;
1508           for (int i = 0; i < nb; i++)
1509             {
1510               if (list[i].starting)
1511                 {
1512                   if (i > 0)
1513                     {
1514                       _aretes[list[i].no].prevS = list[i - 1].no;
1515                     }
1516                   else
1517                     {
1518                       _aretes[list[i].no].prevS = -1;
1519                     }
1520                   if (i < nb - 1)
1521                     {
1522                       _aretes[list[i].no].nextS = list[i + 1].no;
1523                     }
1524                   else
1525                     {
1526                       _aretes[list[i].no].nextS = -1;
1527                     }
1528                 }
1529               else
1530                 {
1531                   if (i > 0)
1532                     {
1533                       _aretes[list[i].no].prevE = list[i - 1].no;
1534                     }
1535                   else
1536                     {
1537                       _aretes[list[i].no].prevE = -1;
1538                     }
1539                   if (i < nb - 1)
1540                     {
1541                       _aretes[list[i].no].nextE = list[i + 1].no;
1542                     }
1543                   else
1544                     {
1545                       _aretes[list[i].no].nextE = -1;
1546                     }
1547                 }
1548             }
1549         }
1550     }
1551   g_free(list);
1552 }
1553
1554 int
1555 Shape::CmpToVert (Geom::Point ax, Geom::Point bx,bool as,bool bs)
1556 {
1557   int tstAX = 0;
1558   int tstAY = 0;
1559   int tstBX = 0;
1560   int tstBY = 0;
1561   if (ax[0] > 0)
1562     tstAX = 1;
1563   if (ax[0] < 0)
1564     tstAX = -1;
1565   if (ax[1] > 0)
1566     tstAY = 1;
1567   if (ax[1] < 0)
1568     tstAY = -1;
1569   if (bx[0] > 0)
1570     tstBX = 1;
1571   if (bx[0] < 0)
1572     tstBX = -1;
1573   if (bx[1] > 0)
1574     tstBY = 1;
1575   if (bx[1] < 0)
1576     tstBY = -1;
1577
1578   int quadA = 0, quadB = 0;
1579   if (tstAX < 0)
1580     {
1581       if (tstAY < 0)
1582         {
1583           quadA = 7;
1584         }
1585       else if (tstAY == 0)
1586         {
1587           quadA = 6;
1588         }
1589       else if (tstAY > 0)
1590         {
1591           quadA = 5;
1592         }
1593     }
1594   else if (tstAX == 0)
1595     {
1596       if (tstAY < 0)
1597         {
1598           quadA = 0;
1599         }
1600       else if (tstAY == 0)
1601         {
1602           quadA = -1;
1603         }
1604       else if (tstAY > 0)
1605         {
1606           quadA = 4;
1607         }
1608     }
1609   else if (tstAX > 0)
1610     {
1611       if (tstAY < 0)
1612         {
1613           quadA = 1;
1614         }
1615       else if (tstAY == 0)
1616         {
1617           quadA = 2;
1618         }
1619       else if (tstAY > 0)
1620         {
1621           quadA = 3;
1622         }
1623     }
1624   if (tstBX < 0)
1625     {
1626       if (tstBY < 0)
1627         {
1628           quadB = 7;
1629         }
1630       else if (tstBY == 0)
1631         {
1632           quadB = 6;
1633         }
1634       else if (tstBY > 0)
1635         {
1636           quadB = 5;
1637         }
1638     }
1639   else if (tstBX == 0)
1640     {
1641       if (tstBY < 0)
1642         {
1643           quadB = 0;
1644         }
1645       else if (tstBY == 0)
1646         {
1647           quadB = -1;
1648         }
1649       else if (tstBY > 0)
1650         {
1651           quadB = 4;
1652         }
1653     }
1654   else if (tstBX > 0)
1655     {
1656       if (tstBY < 0)
1657         {
1658           quadB = 1;
1659         }
1660       else if (tstBY == 0)
1661         {
1662           quadB = 2;
1663         }
1664       else if (tstBY > 0)
1665         {
1666           quadB = 3;
1667         }
1668     }
1669   if (quadA < quadB)
1670     return 1;
1671   if (quadA > quadB)
1672     return -1;
1673
1674   Geom::Point av, bv;
1675   av = ax;
1676   bv = bx;
1677   double si = cross (bv, av);
1678   int tstSi = 0;
1679   if (si > 0.000001) tstSi = 1;
1680   if (si < -0.000001) tstSi = -1;
1681   if ( tstSi == 0 ) {
1682     if ( as == true && bs == false ) return -1;
1683     if ( as == false && bs == true ) return 1;
1684   }
1685   return tstSi;
1686 }
1687
1688 void
1689 Shape::SortEdgesList (edge_list * list, int s, int e)
1690 {
1691   if (s >= e)
1692     return;
1693   if (e == s + 1) {
1694     int cmpval=CmpToVert (list[e].x, list[s].x,list[e].starting,list[s].starting);
1695     if ( cmpval > 0 )  { // priorite aux sortants
1696       edge_list swap = list[s];
1697       list[s] = list[e];
1698       list[e] = swap;
1699     }
1700     return;
1701  }
1702
1703   int ppos = (s + e) / 2;
1704   int plast = ppos;
1705   Geom::Point pvalx = list[ppos].x;
1706   bool      pvals = list[ppos].starting;
1707
1708   int le = s, ri = e;
1709   while (le < ppos || ri > plast)
1710     {
1711       if (le < ppos)
1712         {
1713           do
1714             {
1715         int test = CmpToVert (pvalx, list[le].x,pvals,list[le].starting);
1716               if (test == 0)
1717                 {
1718                   // on colle les valeurs egales au pivot ensemble
1719                   if (le < ppos - 1)
1720                     {
1721                       edge_list swap = list[le];
1722                       list[le] = list[ppos - 1];
1723                       list[ppos - 1] = list[ppos];
1724                       list[ppos] = swap;
1725                       ppos--;
1726                       continue; // sans changer le
1727                     }
1728                   else if (le == ppos - 1)
1729                     {
1730                       ppos--;
1731                       break;
1732                     }
1733                   else
1734                     {
1735                       // oupsie
1736                       break;
1737                     }
1738                 }
1739               if (test > 0)
1740                 {
1741                   break;
1742                 }
1743               le++;
1744             }
1745           while (le < ppos);
1746         }
1747       if (ri > plast)
1748         {
1749           do
1750             {
1751         int test = CmpToVert (pvalx, list[ri].x,pvals,list[ri].starting);
1752               if (test == 0)
1753                 {
1754                   // on colle les valeurs egales au pivot ensemble
1755                   if (ri > plast + 1)
1756                     {
1757                       edge_list swap = list[ri];
1758                       list[ri] = list[plast + 1];
1759                       list[plast + 1] = list[plast];
1760                       list[plast] = swap;
1761                       plast++;
1762                       continue; // sans changer ri
1763                     }
1764                   else if (ri == plast + 1)
1765                     {
1766                       plast++;
1767                       break;
1768                     }
1769                   else
1770                     {
1771                       // oupsie
1772                       break;
1773                     }
1774                 }
1775               if (test < 0)
1776                 {
1777                   break;
1778                 }
1779               ri--;
1780             }
1781           while (ri > plast);
1782         }
1783
1784       if (le < ppos)
1785         {
1786           if (ri > plast)
1787             {
1788               edge_list swap = list[le];
1789               list[le] = list[ri];
1790               list[ri] = swap;
1791               le++;
1792               ri--;
1793             }
1794           else if (le < ppos - 1)
1795             {
1796               edge_list swap = list[ppos - 1];
1797               list[ppos - 1] = list[plast];
1798               list[plast] = list[le];
1799               list[le] = swap;
1800               ppos--;
1801               plast--;
1802             }
1803           else if (le == ppos - 1)
1804             {
1805               edge_list swap = list[plast];
1806               list[plast] = list[le];
1807               list[le] = swap;
1808               ppos--;
1809               plast--;
1810             }
1811           else
1812             {
1813               break;
1814             }
1815         }
1816       else
1817         {
1818           if (ri > plast + 1)
1819             {
1820               edge_list swap = list[plast + 1];
1821               list[plast + 1] = list[ppos];
1822               list[ppos] = list[ri];
1823               list[ri] = swap;
1824               ppos++;
1825               plast++;
1826             }
1827           else if (ri == plast + 1)
1828             {
1829               edge_list swap = list[ppos];
1830               list[ppos] = list[ri];
1831               list[ri] = swap;
1832               ppos++;
1833               plast++;
1834             }
1835           else
1836             {
1837               break;
1838             }
1839         }
1840     }
1841   SortEdgesList (list, s, ppos - 1);
1842   SortEdgesList (list, plast + 1, e);
1843
1844 }
1845
1846
1847
1848 /*
1849  *
1850  */
1851 void
1852 Shape::ConnectStart (int p, int b)
1853 {
1854   if (getEdge(b).st >= 0)
1855     DisconnectStart (b);
1856
1857   _aretes[b].st = p;
1858   _pts[p].dO++;
1859   _aretes[b].nextS = -1;
1860   _aretes[b].prevS = getPoint(p).incidentEdge[LAST];
1861   if (getPoint(p).incidentEdge[LAST] >= 0)
1862     {
1863       if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
1864         {
1865           _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
1866         }
1867       else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
1868         {
1869           _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
1870         }
1871     }
1872   _pts[p].incidentEdge[LAST] = b;
1873   if (getPoint(p).incidentEdge[FIRST] < 0)
1874     _pts[p].incidentEdge[FIRST] = b;
1875 }
1876
1877 void
1878 Shape::ConnectEnd (int p, int b)
1879 {
1880   if (getEdge(b).en >= 0)
1881     DisconnectEnd (b);
1882   _aretes[b].en = p;
1883   _pts[p].dI++;
1884   _aretes[b].nextE = -1;
1885   _aretes[b].prevE = getPoint(p).incidentEdge[LAST];
1886   if (getPoint(p).incidentEdge[LAST] >= 0)
1887     {
1888       if (getEdge(getPoint(p).incidentEdge[LAST]).st == p)
1889         {
1890           _aretes[getPoint(p).incidentEdge[LAST]].nextS = b;
1891         }
1892       else if (getEdge(getPoint(p).incidentEdge[LAST]).en == p)
1893         {
1894           _aretes[getPoint(p).incidentEdge[LAST]].nextE = b;
1895         }
1896     }
1897   _pts[p].incidentEdge[LAST] = b;
1898   if (getPoint(p).incidentEdge[FIRST] < 0)
1899     _pts[p].incidentEdge[FIRST] = b;
1900 }
1901
1902 void
1903 Shape::DisconnectStart (int b)
1904 {
1905   if (getEdge(b).st < 0)
1906     return;
1907   _pts[getEdge(b).st].dO--;
1908   if (getEdge(b).prevS >= 0)
1909     {
1910       if (getEdge(getEdge(b).prevS).st == getEdge(b).st)
1911         {
1912           _aretes[getEdge(b).prevS].nextS = getEdge(b).nextS;
1913         }
1914       else if (getEdge(getEdge(b).prevS).en == getEdge(b).st)
1915         {
1916           _aretes[getEdge(b).prevS].nextE = getEdge(b).nextS;
1917         }
1918     }
1919   if (getEdge(b).nextS >= 0)
1920     {
1921       if (getEdge(getEdge(b).nextS).st == getEdge(b).st)
1922         {
1923           _aretes[getEdge(b).nextS].prevS = getEdge(b).prevS;
1924         }
1925       else if (getEdge(getEdge(b).nextS).en == getEdge(b).st)
1926         {
1927           _aretes[getEdge(b).nextS].prevE = getEdge(b).prevS;
1928         }
1929     }
1930   if (getPoint(getEdge(b).st).incidentEdge[FIRST] == b)
1931     _pts[getEdge(b).st].incidentEdge[FIRST] = getEdge(b).nextS;
1932   if (getPoint(getEdge(b).st).incidentEdge[LAST] == b)
1933     _pts[getEdge(b).st].incidentEdge[LAST] = getEdge(b).prevS;
1934   _aretes[b].st = -1;
1935 }
1936
1937 void
1938 Shape::DisconnectEnd (int b)
1939 {
1940   if (getEdge(b).en < 0)
1941     return;
1942   _pts[getEdge(b).en].dI--;
1943   if (getEdge(b).prevE >= 0)
1944     {
1945       if (getEdge(getEdge(b).prevE).st == getEdge(b).en)
1946         {
1947           _aretes[getEdge(b).prevE].nextS = getEdge(b).nextE;
1948         }
1949       else if (getEdge(getEdge(b).prevE).en == getEdge(b).en)
1950         {
1951           _aretes[getEdge(b).prevE].nextE = getEdge(b).nextE;
1952         }
1953     }
1954   if (getEdge(b).nextE >= 0)
1955     {
1956       if (getEdge(getEdge(b).nextE).st == getEdge(b).en)
1957         {
1958           _aretes[getEdge(b).nextE].prevS = getEdge(b).prevE;
1959         }
1960       else if (getEdge(getEdge(b).nextE).en == getEdge(b).en)
1961         {
1962           _aretes[getEdge(b).nextE].prevE = getEdge(b).prevE;
1963         }
1964     }
1965   if (getPoint(getEdge(b).en).incidentEdge[FIRST] == b)
1966     _pts[getEdge(b).en].incidentEdge[FIRST] = getEdge(b).nextE;
1967   if (getPoint(getEdge(b).en).incidentEdge[LAST] == b)
1968     _pts[getEdge(b).en].incidentEdge[LAST] = getEdge(b).prevE;
1969   _aretes[b].en = -1;
1970 }
1971
1972
1973 void
1974 Shape::Inverse (int b)
1975 {
1976   int swap;
1977   swap = getEdge(b).st;
1978   _aretes[b].st = getEdge(b).en;
1979   _aretes[b].en = swap;
1980   swap = getEdge(b).prevE;
1981   _aretes[b].prevE = getEdge(b).prevS;
1982   _aretes[b].prevS = swap;
1983   swap = getEdge(b).nextE;
1984   _aretes[b].nextE = getEdge(b).nextS;
1985   _aretes[b].nextS = swap;
1986   _aretes[b].dx = -getEdge(b).dx;
1987   if (getEdge(b).st >= 0)
1988     {
1989       _pts[getEdge(b).st].dO++;
1990       _pts[getEdge(b).st].dI--;
1991     }
1992   if (getEdge(b).en >= 0)
1993     {
1994       _pts[getEdge(b).en].dO--;
1995       _pts[getEdge(b).en].dI++;
1996     }
1997   if (_has_edges_data)
1998     eData[b].weight = -eData[b].weight;
1999   if (_has_sweep_dest_data)
2000     {
2001       int swap = swdData[b].leW;
2002       swdData[b].leW = swdData[b].riW;
2003       swdData[b].riW = swap;
2004     }
2005   if (_has_back_data)
2006     {
2007       double swat = ebData[b].tSt;
2008       ebData[b].tSt = ebData[b].tEn;
2009       ebData[b].tEn = swat;
2010     }
2011   if (_has_voronoi_data)
2012     {
2013       int swai = voreData[b].leF;
2014       voreData[b].leF = voreData[b].riF;
2015       voreData[b].riF = swai;
2016     }
2017 }
2018 void
2019 Shape::CalcBBox (bool strict_degree)
2020 {
2021   if (_bbox_up_to_date)
2022     return;
2023   if (hasPoints() == false)
2024   {
2025     leftX = rightX = topY = bottomY = 0;
2026     _bbox_up_to_date = true;
2027     return;
2028   }
2029   leftX = rightX = getPoint(0).x[0];
2030   topY = bottomY = getPoint(0).x[1];
2031   bool not_set=true;
2032   for (int i = 0; i < numberOfPoints(); i++)
2033   {
2034     if ( strict_degree == false || getPoint(i).dI > 0 || getPoint(i).dO > 0 ) {
2035       if ( not_set ) {
2036         leftX = rightX = getPoint(i).x[0];
2037         topY = bottomY = getPoint(i).x[1];
2038         not_set=false;
2039       } else {
2040         if (  getPoint(i).x[0] < leftX) leftX = getPoint(i).x[0];
2041         if (  getPoint(i).x[0] > rightX) rightX = getPoint(i).x[0];
2042         if (  getPoint(i).x[1] < topY) topY = getPoint(i).x[1];
2043         if (  getPoint(i).x[1] > bottomY) bottomY = getPoint(i).x[1];
2044       }
2045     }
2046   }
2047
2048   _bbox_up_to_date = true;
2049 }
2050
2051 // winding of a point with respect to the Shape
2052 // 0= outside
2053 // 1= inside (or -1, that usually the same)
2054 // other=depends on your fill rule
2055 // if the polygon is uncrossed, it's all the same, usually
2056 int
2057 Shape::PtWinding (const Geom::Point px) const
2058 {
2059   int lr = 0, ll = 0, rr = 0;
2060
2061   for (int i = 0; i < numberOfEdges(); i++)
2062   {
2063     Geom::Point const adir = getEdge(i).dx;
2064
2065     Geom::Point const ast = getPoint(getEdge(i).st).x;
2066     Geom::Point const aen = getPoint(getEdge(i).en).x;
2067
2068     //int const nWeight = eData[i].weight;
2069     int const nWeight = 1;
2070
2071     if (ast[0] < aen[0]) {
2072       if (ast[0] > px[0]) continue;
2073       if (aen[0] < px[0]) continue;
2074     } else {
2075       if (ast[0] < px[0]) continue;
2076       if (aen[0] > px[0]) continue;
2077     }
2078     if (ast[0] == px[0]) {
2079       if (ast[1] >= px[1]) continue;
2080       if (aen[0] == px[0]) continue;
2081       if (aen[0] < px[0]) ll += nWeight;  else rr -= nWeight;
2082       continue;
2083     }
2084     if (aen[0] == px[0]) {
2085       if (aen[1] >= px[1]) continue;
2086       if (ast[0] == px[0]) continue;
2087       if (ast[0] < px[0]) ll -= nWeight; else rr += nWeight;
2088       continue;
2089     }
2090
2091     if (ast[1] < aen[1]) {
2092       if (ast[1] >= px[1])  continue;
2093     } else {
2094       if (aen[1] >= px[1]) continue;
2095     }
2096
2097     Geom::Point const diff = px - ast;
2098     double const cote = cross(diff, adir);
2099     if (cote == 0) continue;
2100     if (cote < 0) {
2101       if (ast[0] > px[0]) lr += nWeight;
2102     } else {
2103       if (ast[0] < px[0]) lr -= nWeight;
2104     }
2105   }
2106   return lr + (ll + rr) / 2;
2107 }
2108
2109
2110 void Shape::initialisePointData()
2111 {
2112     if (_point_data_initialised)
2113         return;
2114     int const N = numberOfPoints();
2115
2116     for (int i = 0; i < N; i++) {
2117         pData[i].pending = 0;
2118         pData[i].edgeOnLeft = -1;
2119         pData[i].nextLinkedPoint = -1;
2120         pData[i].rx[0] = Round(getPoint(i).x[0]);
2121         pData[i].rx[1] = Round(getPoint(i).x[1]);
2122     }
2123
2124     _point_data_initialised = true;
2125 }
2126
2127 void Shape::initialiseEdgeData()
2128 {
2129     int const N = numberOfEdges();
2130
2131     for (int i = 0; i < N; i++) {
2132         eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
2133         eData[i].length = dot(eData[i].rdx, eData[i].rdx);
2134         eData[i].ilength = 1 / eData[i].length;
2135         eData[i].sqlength = sqrt(eData[i].length);
2136         eData[i].isqlength = 1 / eData[i].sqlength;
2137         eData[i].siEd = eData[i].rdx[1] * eData[i].isqlength;
2138         eData[i].coEd = eData[i].rdx[0] * eData[i].isqlength;
2139
2140         if (eData[i].siEd < 0) {
2141             eData[i].siEd = -eData[i].siEd;
2142             eData[i].coEd = -eData[i].coEd;
2143         }
2144
2145         swsData[i].misc = NULL;
2146         swsData[i].firstLinkedPoint = -1;
2147         swsData[i].stPt = swsData[i].enPt = -1;
2148         swsData[i].leftRnd = swsData[i].rightRnd = -1;
2149         swsData[i].nextSh = NULL;
2150         swsData[i].nextBo = -1;
2151         swsData[i].curPoint = -1;
2152         swsData[i].doneTo = -1;
2153   }
2154 }
2155
2156
2157 void Shape::clearIncidenceData()
2158 {
2159     g_free(iData);
2160     iData = NULL;
2161     nbInc = maxInc = 0;
2162 }
2163
2164
2165
2166 /**
2167  *    A directed graph is Eulerian iff every vertex has equal indegree and outdegree.
2168  *    http://mathworld.wolfram.com/EulerianGraph.html
2169  *
2170  *    \param s Directed shape.
2171  *    \return true if s is Eulerian.
2172  */
2173
2174 bool directedEulerian(Shape const *s)
2175 {
2176     for (int i = 0; i < s->numberOfPoints(); i++) {
2177         if (s->getPoint(i).dI != s->getPoint(i).dO) {
2178             return false;
2179         }
2180     }
2181
2182     return true;
2183 }
2184
2185
2186
2187 /**
2188  *    \param s Shape.
2189  *    \param p Point.
2190  *    \return Minimum distance from p to any of the points or edges of s.
2191  */
2192
2193 double distance(Shape const *s, Geom::Point const &p)
2194 {
2195     if ( s->hasPoints() == false) {
2196         return 0.0;
2197     }
2198
2199     /* Find the minimum distance from p to one of the points on s.
2200     ** Computing the dot product of the difference vector gives
2201     ** us the distance squared; we can leave the square root
2202     ** until the end.
2203     */
2204     double bdot = Geom::dot(p - s->getPoint(0).x, p - s->getPoint(0).x);
2205
2206     for (int i = 0; i < s->numberOfPoints(); i++) {
2207         Geom::Point const offset( p - s->getPoint(i).x );
2208         double ndot = Geom::dot(offset, offset);
2209         if ( ndot < bdot ) {
2210             bdot = ndot;
2211         }
2212     }
2213
2214     for (int i = 0; i < s->numberOfEdges(); i++) {
2215         if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
2216             /* The edge has start and end points */
2217             Geom::Point const st(s->getPoint(s->getEdge(i).st).x); // edge start
2218             Geom::Point const en(s->getPoint(s->getEdge(i).en).x); // edge end
2219
2220             Geom::Point const d(p - st);       // vector between p and edge start
2221             Geom::Point const e(en - st);      // vector of the edge
2222             double const el = Geom::dot(e, e); // edge length
2223
2224             /* Update bdot if appropriate */
2225             if ( el > 0.001 ) {
2226                 double const npr = Geom::dot(d, e);
2227                 if ( npr > 0 && npr < el ) {
2228                     double const nl = fabs( NR::cross(d, e) );
2229                     double ndot = nl * nl / el;
2230                     if ( ndot < bdot ) {
2231                         bdot = ndot;
2232                     }
2233                 }
2234             }
2235         }
2236     }
2237
2238     return sqrt(bdot);
2239 }
2240
2241
2242
2243 /**
2244  *    Returns true iff the L2 distance from \a thePt to this shape is <= \a max_l2.
2245  *    Distance = the min of distance to its points and distance to its edges.
2246  *    Points without edges are considered, which is maybe unwanted...
2247  *
2248  *    This is largely similar to distance().
2249  *
2250  *    \param s Shape.
2251  *    \param p Point.
2252  *    \param max_l2 L2 distance.
2253  */
2254
2255 bool distanceLessThanOrEqual(Shape const *s, Geom::Point const &p, double const max_l2)
2256 {
2257     if ( s->hasPoints() == false ) {
2258         return false;
2259     }
2260
2261     /* TODO: Consider using bbox to return early, perhaps conditional on nbPt or nbAr. */
2262
2263     /* TODO: Efficiency: In one test case (scribbling with the freehand tool to create a small number of long
2264     ** path elements), changing from a Distance method to a DistanceLE method reduced this
2265     ** function's CPU time from about 21% of total inkscape CPU time to 14-15% of total inkscape
2266     ** CPU time, due to allowing early termination.  I don't know how much the L1 test helps, it
2267     ** may well be a case of premature optimization.  Consider testing dot(offset, offset)
2268     ** instead.
2269     */
2270
2271     double const max_l1 = max_l2 * M_SQRT2;
2272     for (int i = 0; i < s->numberOfPoints(); i++) {
2273         Geom::Point const offset( p - s->getPoint(i).x );
2274         double const l1 = NR::L1(offset);
2275         if ( (l1 <= max_l2) || ((l1 <= max_l1) && (Geom::L2(offset) <= max_l2)) ) {
2276             return true;
2277         }
2278     }
2279
2280     for (int i = 0; i < s->numberOfEdges(); i++) {
2281         if ( s->getEdge(i).st >= 0 && s->getEdge(i).en >= 0 ) {
2282             Geom::Point const st(s->getPoint(s->getEdge(i).st).x);
2283             Geom::Point const en(s->getPoint(s->getEdge(i).en).x);
2284             Geom::Point const d(p - st);
2285             Geom::Point const e(en - st);
2286             double const el = Geom::L2(e);
2287             if ( el > 0.001 ) {
2288                 Geom::Point const e_unit(e / el);
2289                 double const npr = Geom::dot(d, e_unit);
2290                 if ( npr > 0 && npr < el ) {
2291                     double const nl = fabs(NR::cross(d, e_unit));
2292                     if ( nl <= max_l2 ) {
2293                         return true;
2294                     }
2295                 }
2296             }
2297         }
2298     }
2299
2300     return false;
2301 }
2302
2303 //};
2304