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