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