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