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