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