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