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