1 /*
2 * ShapeMisc.cpp
3 * nlivarot
4 *
5 * Created by fred on Sun Jul 20 2003.
6 *
7 */
9 #include "livarot/Shape.h"
10 #include <libnr/nr-point-fns.h>
11 #include "livarot/Path.h"
12 #include "livarot/path-description.h"
13 #include <glib.h>
15 /*
16 * polygon offset and polyline to path reassembling (when using back data)
17 */
19 // until i find something better
20 #define MiscNormalize(v) {\
21 double _l=sqrt(dot(v,v)); \
22 if ( _l < 0.0000001 ) { \
23 v[0]=v[1]=0; \
24 } else { \
25 v/=_l; \
26 }\
27 }
29 // extracting the contour of an uncrossed polygon: a mere depth first search
30 // more precisely that's extracting an eulerian path from a graph, but here we want to split
31 // the polygon into contours and avoid holes. so we take a "next counter-clockwise edge first" approach
32 // (make a checkboard and extract its contours to see the difference)
33 void
34 Shape::ConvertToForme (Path * dest)
35 {
36 if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
37 return;
38 if (directedEulerian(this) == false)
39 return;
41 // prepare
42 dest->Reset ();
44 MakePointData (true);
45 MakeEdgeData (true);
46 MakeSweepDestData (true);
48 for (int i = 0; i < numberOfPoints(); i++)
49 {
50 pData[i].rx[0] = Round (getPoint(i).x[0]);
51 pData[i].rx[1] = Round (getPoint(i).x[1]);
52 }
53 for (int i = 0; i < numberOfEdges(); i++)
54 {
55 eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
56 }
58 // sort edge clockwise, with the closest after midnight being first in the doubly-linked list
59 // that's vital to the algorithm...
60 SortEdges ();
62 // depth-first search implies: we make a stack of edges traversed.
63 // precParc: previous in the stack
64 // suivParc: next in the stack
65 for (int i = 0; i < numberOfEdges(); i++)
66 {
67 swdData[i].misc = 0;
68 swdData[i].precParc = swdData[i].suivParc = -1;
69 }
71 int searchInd = 0;
73 int lastPtUsed = 0;
74 do
75 {
76 // first get a starting point, and a starting edge
77 // -> take the upper left point, and take its first edge
78 // points traversed have swdData[].misc != 0, so it's easy
79 int startBord = -1;
80 {
81 int fi = 0;
82 for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
83 {
84 if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
85 break;
86 }
87 lastPtUsed = fi + 1;
88 if (fi < numberOfPoints())
89 {
90 int bestB = getPoint(fi).incidentEdge[FIRST];
91 while (bestB >= 0 && getEdge(bestB).st != fi)
92 bestB = NextAt (fi, bestB);
93 if (bestB >= 0)
94 {
95 startBord = bestB;
96 dest->MoveTo (getPoint(getEdge(startBord).en).x);
97 }
98 }
99 }
100 // and walk the graph, doing contours when needed
101 if (startBord >= 0)
102 {
103 // parcours en profondeur pour mettre les leF et riF a leurs valeurs
104 swdData[startBord].misc = (void *) 1;
105 // printf("part de %d\n",startBord);
106 int curBord = startBord;
107 bool back = false;
108 swdData[curBord].precParc = -1;
109 swdData[curBord].suivParc = -1;
110 do
111 {
112 int cPt = getEdge(curBord).en;
113 int nb = curBord;
114 // printf("de curBord= %d au point %i -> ",curBord,cPt);
115 // get next edge
116 do
117 {
118 int nnb = CycleNextAt (cPt, nb);
119 if (nnb == nb)
120 {
121 // cul-de-sac
122 nb = -1;
123 break;
124 }
125 nb = nnb;
126 if (nb < 0 || nb == curBord)
127 break;
128 }
129 while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
131 if (nb < 0 || nb == curBord)
132 {
133 // no next edge: end of this contour, we get back
134 if (back == false)
135 dest->Close ();
136 back = true;
137 // retour en arriere
138 curBord = swdData[curBord].precParc;
139 // printf("retour vers %d\n",curBord);
140 if (curBord < 0)
141 break;
142 }
143 else
144 {
145 // new edge, maybe for a new contour
146 if (back)
147 {
148 // we were backtracking, so if we have a new edge, that means we're creating a new contour
149 dest->MoveTo (getPoint(cPt).x);
150 back = false;
151 }
152 swdData[nb].misc = (void *) 1;
153 swdData[nb].ind = searchInd++;
154 swdData[nb].precParc = curBord;
155 swdData[curBord].suivParc = nb;
156 curBord = nb;
157 // printf("suite %d\n",curBord);
158 {
159 // add that edge
160 dest->LineTo (getPoint(getEdge(nb).en).x);
161 }
162 }
163 }
164 while (1 /*swdData[curBord].precParc >= 0 */ );
165 // fin du cas non-oriente
166 }
167 }
168 while (lastPtUsed < numberOfPoints());
170 MakePointData (false);
171 MakeEdgeData (false);
172 MakeSweepDestData (false);
173 }
175 // same as before, but each time we have a contour, try to reassemble the segments on it to make chunks of
176 // the original(s) path(s)
177 // originals are in the orig array, whose size is nbP
178 void
179 Shape::ConvertToForme (Path * dest, int nbP, Path * *orig, bool splitWhenForced)
180 {
181 if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
182 return;
183 // if (Eulerian (true) == false)
184 // return;
186 if (_has_back_data == false)
187 {
188 ConvertToForme (dest);
189 return;
190 }
192 dest->Reset ();
194 MakePointData (true);
195 MakeEdgeData (true);
196 MakeSweepDestData (true);
198 for (int i = 0; i < numberOfPoints(); i++)
199 {
200 pData[i].rx[0] = Round (getPoint(i).x[0]);
201 pData[i].rx[1] = Round (getPoint(i).x[1]);
202 }
203 for (int i = 0; i < numberOfEdges(); i++)
204 {
205 eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
206 }
208 SortEdges ();
210 for (int i = 0; i < numberOfEdges(); i++)
211 {
212 swdData[i].misc = 0;
213 swdData[i].precParc = swdData[i].suivParc = -1;
214 }
216 int searchInd = 0;
218 int lastPtUsed = 0;
219 do
220 {
221 int startBord = -1;
222 {
223 int fi = 0;
224 for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
225 {
226 if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
227 break;
228 }
229 lastPtUsed = fi + 1;
230 if (fi < numberOfPoints())
231 {
232 int bestB = getPoint(fi).incidentEdge[FIRST];
233 while (bestB >= 0 && getEdge(bestB).st != fi)
234 bestB = NextAt (fi, bestB);
235 if (bestB >= 0)
236 {
237 startBord = bestB;
238 }
239 }
240 }
241 if (startBord >= 0)
242 {
243 // parcours en profondeur pour mettre les leF et riF a leurs valeurs
244 swdData[startBord].misc = (void *) 1;
245 //printf("part de %d\n",startBord);
246 int curBord = startBord;
247 bool back = false;
248 swdData[curBord].precParc = -1;
249 swdData[curBord].suivParc = -1;
250 int curStartPt=getEdge(curBord).st;
251 do
252 {
253 int cPt = getEdge(curBord).en;
254 int nb = curBord;
255 //printf("de curBord= %d au point %i -> ",curBord,cPt);
256 do
257 {
258 int nnb = CycleNextAt (cPt, nb);
259 if (nnb == nb)
260 {
261 // cul-de-sac
262 nb = -1;
263 break;
264 }
265 nb = nnb;
266 if (nb < 0 || nb == curBord)
267 break;
268 }
269 while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
271 if (nb < 0 || nb == curBord)
272 {
273 if (back == false)
274 {
275 if (curBord == startBord || curBord < 0)
276 {
277 // probleme -> on vire le moveto
278 // dest->descr_nb--;
279 }
280 else
281 {
282 swdData[curBord].suivParc = -1;
283 AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
284 }
285 // dest->Close();
286 }
287 back = true;
288 // retour en arriere
289 curBord = swdData[curBord].precParc;
290 //printf("retour vers %d\n",curBord);
291 if (curBord < 0)
292 break;
293 }
294 else
295 {
296 if (back)
297 {
298 back = false;
299 startBord = nb;
300 curStartPt=getEdge(nb).st;
301 } else {
302 if ( getEdge(curBord).en == curStartPt ) {
303 //printf("contour %i ",curStartPt);
304 swdData[curBord].suivParc = -1;
305 AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
306 startBord=nb;
307 }
308 }
309 swdData[nb].misc = (void *) 1;
310 swdData[nb].ind = searchInd++;
311 swdData[nb].precParc = curBord;
312 swdData[curBord].suivParc = nb;
313 curBord = nb;
314 //printf("suite %d\n",curBord);
315 }
316 }
317 while (1 /*swdData[curBord].precParc >= 0 */ );
318 // fin du cas non-oriente
319 }
320 }
321 while (lastPtUsed < numberOfPoints());
323 MakePointData (false);
324 MakeEdgeData (false);
325 MakeSweepDestData (false);
326 }
327 void
328 Shape::ConvertToFormeNested (Path * dest, int nbP, Path * *orig, int wildPath,int &nbNest,int *&nesting,int *&contStart,bool splitWhenForced)
329 {
330 nesting=NULL;
331 contStart=NULL;
332 nbNest=0;
334 if (numberOfPoints() <= 1 || numberOfEdges() <= 1)
335 return;
336 // if (Eulerian (true) == false)
337 // return;
339 if (_has_back_data == false)
340 {
341 ConvertToForme (dest);
342 return;
343 }
345 dest->Reset ();
347 // MakePointData (true);
348 MakeEdgeData (true);
349 MakeSweepDestData (true);
351 for (int i = 0; i < numberOfPoints(); i++)
352 {
353 pData[i].rx[0] = Round (getPoint(i).x[0]);
354 pData[i].rx[1] = Round (getPoint(i).x[1]);
355 }
356 for (int i = 0; i < numberOfEdges(); i++)
357 {
358 eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
359 }
361 SortEdges ();
363 for (int i = 0; i < numberOfEdges(); i++)
364 {
365 swdData[i].misc = 0;
366 swdData[i].precParc = swdData[i].suivParc = -1;
367 }
369 int searchInd = 0;
371 int lastPtUsed = 0;
372 do
373 {
374 int dadContour=-1;
375 int startBord = -1;
376 {
377 int fi = 0;
378 for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
379 {
380 if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
381 break;
382 }
383 {
384 int askTo = pData[fi].askForWindingB;
385 if (askTo < 0 || askTo >= numberOfEdges() ) {
386 dadContour=-1;
387 } else {
388 dadContour = GPOINTER_TO_INT(swdData[askTo].misc);
389 dadContour-=1; // pour compenser le decalage
390 }
391 }
392 lastPtUsed = fi + 1;
393 if (fi < numberOfPoints())
394 {
395 int bestB = getPoint(fi).incidentEdge[FIRST];
396 while (bestB >= 0 && getEdge(bestB).st != fi)
397 bestB = NextAt (fi, bestB);
398 if (bestB >= 0)
399 {
400 startBord = bestB;
401 }
402 }
403 }
404 if (startBord >= 0)
405 {
406 // parcours en profondeur pour mettre les leF et riF a leurs valeurs
407 swdData[startBord].misc = (void *) (1+nbNest);
408 //printf("part de %d\n",startBord);
409 int curBord = startBord;
410 bool back = false;
411 swdData[curBord].precParc = -1;
412 swdData[curBord].suivParc = -1;
413 int curStartPt=getEdge(curBord).st;
414 do
415 {
416 int cPt = getEdge(curBord).en;
417 int nb = curBord;
418 //printf("de curBord= %d au point %i -> ",curBord,cPt);
419 do
420 {
421 int nnb = CycleNextAt (cPt, nb);
422 if (nnb == nb)
423 {
424 // cul-de-sac
425 nb = -1;
426 break;
427 }
428 nb = nnb;
429 if (nb < 0 || nb == curBord)
430 break;
431 }
432 while (swdData[nb].misc != 0 || getEdge(nb).st != cPt);
434 if (nb < 0 || nb == curBord)
435 {
436 if (back == false)
437 {
438 if (curBord == startBord || curBord < 0)
439 {
440 // probleme -> on vire le moveto
441 // dest->descr_nb--;
442 }
443 else
444 {
445 bool escapePath=false;
446 int tb=curBord;
447 while ( tb >= 0 && tb < numberOfEdges() ) {
448 if ( ebData[tb].pathID == wildPath ) {
449 escapePath=true;
450 break;
451 }
452 tb=swdData[tb].precParc;
453 }
454 nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
455 contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
456 contStart[nbNest]=dest->descr_cmd.size();
457 if ( escapePath ) {
458 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
459 } else {
460 nesting[nbNest++]=dadContour;
461 }
462 swdData[curBord].suivParc = -1;
463 AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
464 }
465 // dest->Close();
466 }
467 back = true;
468 // retour en arriere
469 curBord = swdData[curBord].precParc;
470 //printf("retour vers %d\n",curBord);
471 if (curBord < 0)
472 break;
473 }
474 else
475 {
476 if (back)
477 {
478 back = false;
479 startBord = nb;
480 curStartPt=getEdge(nb).st;
481 } else {
482 if ( getEdge(curBord).en == curStartPt ) {
483 //printf("contour %i ",curStartPt);
485 bool escapePath=false;
486 int tb=curBord;
487 while ( tb >= 0 && tb < numberOfEdges() ) {
488 if ( ebData[tb].pathID == wildPath ) {
489 escapePath=true;
490 break;
491 }
492 tb=swdData[tb].precParc;
493 }
494 nesting=(int*)g_realloc(nesting,(nbNest+1)*sizeof(int));
495 contStart=(int*)g_realloc(contStart,(nbNest+1)*sizeof(int));
496 contStart[nbNest]=dest->descr_cmd.size();
497 if ( escapePath ) {
498 nesting[nbNest++]=-1; // contient des bouts de coupure -> a part
499 } else {
500 nesting[nbNest++]=dadContour;
501 }
503 swdData[curBord].suivParc = -1;
504 AddContour (dest, nbP, orig, startBord, curBord,splitWhenForced);
505 startBord=nb;
506 }
507 }
508 swdData[nb].misc = (void *) (1+nbNest);
509 swdData[nb].ind = searchInd++;
510 swdData[nb].precParc = curBord;
511 swdData[curBord].suivParc = nb;
512 curBord = nb;
513 //printf("suite %d\n",curBord);
514 }
515 }
516 while (1 /*swdData[curBord].precParc >= 0 */ );
517 // fin du cas non-oriente
518 }
519 }
520 while (lastPtUsed < numberOfPoints());
522 MakePointData (false);
523 MakeEdgeData (false);
524 MakeSweepDestData (false);
525 }
527 // offsets
528 // take each edge, offset it, and make joins with previous at edge start and next at edge end (previous and
529 // next being with respect to the clockwise order)
530 // you gotta be very careful with the join, has anything but the right one will fuck everything up
531 // see PathStroke.cpp for the "right" joins
532 int
533 Shape::MakeOffset (Shape * a, double dec, JoinType join, double miter)
534 {
535 Reset (0, 0);
536 MakeBackData(a->_has_back_data);
538 if (dec == 0)
539 {
540 _pts = a->_pts;
541 if (numberOfPoints() > maxPt)
542 {
543 maxPt = numberOfPoints();
544 if (_has_points_data) {
545 pData.resize(maxPt);
546 _point_data_initialised = false;
547 _bbox_up_to_date = false;
548 }
549 }
551 _aretes = a->_aretes;
552 if (numberOfEdges() > maxAr)
553 {
554 maxAr = numberOfEdges();
555 if (_has_edges_data)
556 eData.resize(maxAr);
557 if (_has_sweep_src_data)
558 swsData.resize(maxAr);
559 if (_has_sweep_dest_data)
560 swdData.resize(maxAr);
561 if (_has_raster_data)
562 swrData.resize(maxAr);
563 if (_has_back_data)
564 ebData.resize(maxAr);
565 }
566 return 0;
567 }
568 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
569 return shape_input_err;
571 a->SortEdges ();
573 a->MakeSweepDestData (true);
574 a->MakeSweepSrcData (true);
576 for (int i = 0; i < a->numberOfEdges(); i++)
577 {
578 // int stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/;
579 int stB = -1, enB = -1;
580 if (dec > 0)
581 {
582 stB = a->CycleNextAt (a->getEdge(i).st, i);
583 enB = a->CyclePrevAt (a->getEdge(i).en, i);
584 }
585 else
586 {
587 stB = a->CyclePrevAt (a->getEdge(i).st, i);
588 enB = a->CycleNextAt (a->getEdge(i).en, i);
589 }
591 NR::Point stD, seD, enD;
592 double stL, seL, enL;
593 stD = a->getEdge(stB).dx;
594 seD = a->getEdge(i).dx;
595 enD = a->getEdge(enB).dx;
597 stL = sqrt (dot(stD,stD));
598 seL = sqrt (dot(seD,seD));
599 enL = sqrt (dot(enD,enD));
600 MiscNormalize (stD);
601 MiscNormalize (enD);
602 MiscNormalize (seD);
604 NR::Point ptP;
605 int stNo, enNo;
606 ptP = a->getPoint(a->getEdge(i).st).x;
607 int usePathID=-1;
608 int usePieceID=0;
609 double useT=0.0;
610 if ( a->_has_back_data ) {
611 if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
612 && a->ebData[stB].tEn == a->ebData[i].tSt ) {
613 usePathID=a->ebData[i].pathID;
614 usePieceID=a->ebData[i].pieceID;
615 useT=a->ebData[i].tSt;
616 } else {
617 usePathID=a->ebData[i].pathID;
618 usePieceID=0;
619 useT=0;
620 }
621 }
622 if (dec > 0)
623 {
624 Path::DoRightJoin (this, dec, join, ptP, stD, seD, miter, stL, seL,
625 stNo, enNo,usePathID,usePieceID,useT);
626 a->swsData[i].stPt = enNo;
627 a->swsData[stB].enPt = stNo;
628 }
629 else
630 {
631 Path::DoLeftJoin (this, -dec, join, ptP, stD, seD, miter, stL, seL,
632 stNo, enNo,usePathID,usePieceID,useT);
633 a->swsData[i].stPt = enNo;
634 a->swsData[stB].enPt = stNo;
635 }
636 }
637 if (dec < 0)
638 {
639 for (int i = 0; i < numberOfEdges(); i++)
640 Inverse (i);
641 }
642 if ( _has_back_data ) {
643 for (int i = 0; i < a->numberOfEdges(); i++)
644 {
645 int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
646 ebData[nEd]=a->ebData[i];
647 }
648 } else {
649 for (int i = 0; i < a->numberOfEdges(); i++)
650 {
651 AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
652 }
653 }
654 a->MakeSweepSrcData (false);
655 a->MakeSweepDestData (false);
657 return 0;
658 }
660 // we found a contour, now reassemble the edges on it, instead of dumping them in the Path "dest" as a
661 // polyline. since it was a DFS, the precParc and suivParc make a nice doubly-linked list of the edges in
662 // the contour. the first and last edges of the contour are startBord and curBord
663 void
664 Shape::AddContour (Path * dest, int nbP, Path * *orig, int startBord, int curBord, bool splitWhenForced)
665 {
666 int bord = startBord;
668 {
669 dest->MoveTo (getPoint(getEdge(bord).st).x);
670 }
672 while (bord >= 0)
673 {
674 int nPiece = ebData[bord].pieceID;
675 int nPath = ebData[bord].pathID;
677 if (nPath < 0 || nPath >= nbP || orig[nPath] == NULL)
678 {
679 // segment batard
680 dest->LineTo (getPoint(getEdge(bord).en).x);
681 bord = swdData[bord].suivParc;
682 }
683 else
684 {
685 Path *from = orig[nPath];
686 if (nPiece < 0 || nPiece >= int(from->descr_cmd.size()))
687 {
688 // segment batard
689 dest->LineTo (getPoint(getEdge(bord).en).x);
690 bord = swdData[bord].suivParc;
691 }
692 else
693 {
694 int nType = from->descr_cmd[nPiece]->getType();
695 if (nType == descr_close || nType == descr_moveto
696 || nType == descr_forced)
697 {
698 // devrait pas arriver
699 dest->LineTo (getPoint(getEdge(bord).en).x);
700 bord = swdData[bord].suivParc;
701 }
702 else if (nType == descr_lineto)
703 {
704 bord = ReFormeLineTo (bord, curBord, dest, from);
705 }
706 else if (nType == descr_arcto)
707 {
708 bord = ReFormeArcTo (bord, curBord, dest, from);
709 }
710 else if (nType == descr_cubicto)
711 {
712 bord = ReFormeCubicTo (bord, curBord, dest, from);
713 }
714 else if (nType == descr_bezierto)
715 {
716 PathDescrBezierTo* nBData =
717 dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
719 if (nBData->nb == 0)
720 {
721 bord = ReFormeLineTo (bord, curBord, dest, from);
722 }
723 else
724 {
725 bord = ReFormeBezierTo (bord, curBord, dest, from);
726 }
727 }
728 else if (nType == descr_interm_bezier)
729 {
730 bord = ReFormeBezierTo (bord, curBord, dest, from);
731 }
732 else
733 {
734 // devrait pas arriver non plus
735 dest->LineTo (getPoint(getEdge(bord).en).x);
736 bord = swdData[bord].suivParc;
737 }
738 if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) {
739 dest->ForcePoint ();
740 } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2) {
741 if ( splitWhenForced ) {
742 // pour les coupures
743 dest->ForcePoint ();
744 } else {
745 if ( _has_back_data ) {
746 int prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST];
747 int nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST];
748 if ( getEdge(prevEdge).en != getEdge(bord).st ) {
749 int swai=prevEdge;prevEdge=nextEdge;nextEdge=swai;
750 }
751 if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) {
752 if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) {
753 } else {
754 dest->ForcePoint ();
755 }
756 } else {
757 dest->ForcePoint ();
758 }
759 } else {
760 dest->ForcePoint ();
761 }
762 }
763 }
764 }
765 }
766 }
767 dest->Close ();
768 }
770 int
771 Shape::ReFormeLineTo (int bord, int curBord, Path * dest, Path * orig)
772 {
773 int nPiece = ebData[bord].pieceID;
774 int nPath = ebData[bord].pathID;
775 double /*ts=ebData[bord].tSt, */ te = ebData[bord].tEn;
776 NR::Point nx = getPoint(getEdge(bord).en).x;
777 bord = swdData[bord].suivParc;
778 while (bord >= 0)
779 {
780 if (getPoint(getEdge(bord).st).totalDegree() > 2
781 || getPoint(getEdge(bord).st).oldDegree > 2)
782 {
783 break;
784 }
785 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
786 {
787 if (fabs (te - ebData[bord].tSt) > 0.0001)
788 break;
789 nx = getPoint(getEdge(bord).en).x;
790 te = ebData[bord].tEn;
791 }
792 else
793 {
794 break;
795 }
796 bord = swdData[bord].suivParc;
797 }
798 {
799 dest->LineTo (nx);
800 }
801 return bord;
802 }
804 int
805 Shape::ReFormeArcTo (int bord, int curBord, Path * dest, Path * from)
806 {
807 int nPiece = ebData[bord].pieceID;
808 int nPath = ebData[bord].pathID;
809 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
810 // double px=pts[getEdge(bord).st].x,py=pts[getEdge(bord).st].y;
811 NR::Point nx = getPoint(getEdge(bord).en).x;
812 bord = swdData[bord].suivParc;
813 while (bord >= 0)
814 {
815 if (getPoint(getEdge(bord).st).totalDegree() > 2
816 || getPoint(getEdge(bord).st).oldDegree > 2)
817 {
818 break;
819 }
820 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
821 {
822 if (fabs (te - ebData[bord].tSt) > 0.0001)
823 {
824 break;
825 }
826 nx = getPoint(getEdge(bord).en).x;
827 te = ebData[bord].tEn;
828 }
829 else
830 {
831 break;
832 }
833 bord = swdData[bord].suivParc;
834 }
835 double sang, eang;
836 PathDescrArcTo* nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
837 bool nLarge = nData->large;
838 bool nClockwise = nData->clockwise;
839 Path::ArcAngles (from->PrevPoint (nPiece - 1), nData->p,nData->rx,nData->ry,nData->angle, nLarge, nClockwise, sang, eang);
840 if (nClockwise)
841 {
842 if (sang < eang)
843 sang += 2 * M_PI;
844 }
845 else
846 {
847 if (sang > eang)
848 sang -= 2 * M_PI;
849 }
850 double delta = eang - sang;
851 double ndelta = delta * (te - ts);
852 if (ts > te)
853 nClockwise = !nClockwise;
854 if (ndelta < 0)
855 ndelta = -ndelta;
856 if (ndelta > M_PI)
857 nLarge = true;
858 else
859 nLarge = false;
860 /* if ( delta < 0 ) delta=-delta;
861 if ( ndelta < 0 ) ndelta=-ndelta;
862 if ( ( delta < M_PI && ndelta < M_PI ) || ( delta >= M_PI && ndelta >= M_PI ) ) {
863 if ( ts < te ) {
864 } else {
865 nClockwise=!(nClockwise);
866 }
867 } else {
868 // nLarge=!(nLarge);
869 nLarge=false; // c'est un sous-segment -> l'arc ne peut que etre plus petit
870 if ( ts < te ) {
871 } else {
872 nClockwise=!(nClockwise);
873 }
874 }*/
875 {
876 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
877 dest->ArcTo (nx, nData->rx,nData->ry,nData->angle, nLarge, nClockwise);
878 }
879 return bord;
880 }
882 int
883 Shape::ReFormeCubicTo (int bord, int curBord, Path * dest, Path * from)
884 {
885 int nPiece = ebData[bord].pieceID;
886 int nPath = ebData[bord].pathID;
887 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
888 NR::Point nx = getPoint(getEdge(bord).en).x;
889 bord = swdData[bord].suivParc;
890 while (bord >= 0)
891 {
892 if (getPoint(getEdge(bord).st).totalDegree() > 2
893 || getPoint(getEdge(bord).st).oldDegree > 2)
894 {
895 break;
896 }
897 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
898 {
899 if (fabs (te - ebData[bord].tSt) > 0.0001)
900 {
901 break;
902 }
903 nx = getPoint(getEdge(bord).en).x;
904 te = ebData[bord].tEn;
905 }
906 else
907 {
908 break;
909 }
910 bord = swdData[bord].suivParc;
911 }
912 NR::Point prevx = from->PrevPoint (nPiece - 1);
914 NR::Point sDx, eDx;
915 {
916 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(from->descr_cmd[nPiece]);
917 Path::CubicTangent (ts, sDx, prevx,nData->start,nData->p,nData->end);
918 Path::CubicTangent (te, eDx, prevx,nData->start,nData->p,nData->end);
919 }
920 sDx *= (te - ts);
921 eDx *= (te - ts);
922 {
923 dest->CubicTo (nx,sDx,eDx);
924 }
925 return bord;
926 }
928 int
929 Shape::ReFormeBezierTo (int bord, int curBord, Path * dest, Path * from)
930 {
931 int nPiece = ebData[bord].pieceID;
932 int nPath = ebData[bord].pathID;
933 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
934 int ps = nPiece, pe = nPiece;
935 NR::Point px = getPoint(getEdge(bord).st).x;
936 NR::Point nx = getPoint(getEdge(bord).en).x;
937 int inBezier = -1, nbInterm = -1;
938 int typ;
939 typ = from->descr_cmd[nPiece]->getType();
940 PathDescrBezierTo *nBData = NULL;
941 if (typ == descr_bezierto)
942 {
943 nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
944 inBezier = nPiece;
945 nbInterm = nBData->nb;
946 }
947 else
948 {
949 int n = nPiece - 1;
950 while (n > 0)
951 {
952 typ = from->descr_cmd[n]->getType();
953 if (typ == descr_bezierto)
954 {
955 inBezier = n;
956 nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[n]);
957 nbInterm = nBData->nb;
958 break;
959 }
960 n--;
961 }
962 if (inBezier < 0)
963 {
964 bord = swdData[bord].suivParc;
965 dest->LineTo (nx);
966 return bord;
967 }
968 }
969 bord = swdData[bord].suivParc;
970 while (bord >= 0)
971 {
972 if (getPoint(getEdge(bord).st).totalDegree() > 2
973 || getPoint(getEdge(bord).st).oldDegree > 2)
974 {
975 break;
976 }
977 if (ebData[bord].pathID == nPath)
978 {
979 if (ebData[bord].pieceID < inBezier
980 || ebData[bord].pieceID >= inBezier + nbInterm)
981 break;
982 if (ebData[bord].pieceID == pe
983 && fabs (te - ebData[bord].tSt) > 0.0001)
984 break;
985 if (ebData[bord].pieceID != pe
986 && (ebData[bord].tSt > 0.0001 && ebData[bord].tSt < 0.9999))
987 break;
988 if (ebData[bord].pieceID != pe && (te > 0.0001 && te < 0.9999))
989 break;
990 nx = getPoint(getEdge(bord).en).x;
991 te = ebData[bord].tEn;
992 pe = ebData[bord].pieceID;
993 }
994 else
995 {
996 break;
997 }
998 bord = swdData[bord].suivParc;
999 }
1001 g_return_val_if_fail(nBData != NULL, 0);
1003 if (pe == ps)
1004 {
1005 ReFormeBezierChunk (px, nx, dest, inBezier, nbInterm, from, ps,
1006 ts, te);
1007 }
1008 else if (ps < pe)
1009 {
1010 if (ts < 0.0001)
1011 {
1012 if (te > 0.9999)
1013 {
1014 dest->BezierTo (nx);
1015 for (int i = ps; i <= pe; i++)
1016 {
1017 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1018 dest->IntermBezierTo (nData->p);
1019 }
1020 dest->EndBezierTo ();
1021 }
1022 else
1023 {
1024 NR::Point tx;
1025 {
1026 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1027 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1028 tx = (pnData->p + psData->p) / 2;
1029 }
1030 dest->BezierTo (tx);
1031 for (int i = ps; i < pe; i++)
1032 {
1033 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1034 dest->IntermBezierTo (nData->p);
1035 }
1036 dest->EndBezierTo ();
1037 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1038 from, pe, 0.0, te);
1039 }
1040 }
1041 else
1042 {
1043 if (te > 0.9999)
1044 {
1045 NR::Point tx;
1046 {
1047 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1048 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1049 tx = (psData->p + pnData->p) / 2;
1050 }
1051 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1052 from, ps, ts, 1.0);
1053 dest->BezierTo (nx);
1054 for (int i = ps + 1; i <= pe; i++)
1055 {
1056 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1057 dest->IntermBezierTo (nData->p);
1058 }
1059 dest->EndBezierTo ();
1060 }
1061 else
1062 {
1063 NR::Point tx;
1064 {
1065 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1066 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1067 tx = (pnData->p + psData->p) / 2;
1068 }
1069 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1070 from, ps, ts, 1.0);
1071 {
1072 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1073 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1074 tx = (pnData->p + psData->p) / 2;
1075 }
1076 dest->BezierTo (tx);
1077 for (int i = ps + 1; i <= pe; i++)
1078 {
1079 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1080 dest->IntermBezierTo (nData->p);
1081 }
1082 dest->EndBezierTo ();
1083 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1084 from, pe, 0.0, te);
1085 }
1086 }
1087 }
1088 else
1089 {
1090 if (ts > 0.9999)
1091 {
1092 if (te < 0.0001)
1093 {
1094 dest->BezierTo (nx);
1095 for (int i = ps; i >= pe; i--)
1096 {
1097 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1098 dest->IntermBezierTo (nData->p);
1099 }
1100 dest->EndBezierTo ();
1101 }
1102 else
1103 {
1104 NR::Point tx;
1105 {
1106 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1107 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1108 tx = (pnData->p + psData->p) / 2;
1109 }
1110 dest->BezierTo (tx);
1111 for (int i = ps; i > pe; i--)
1112 {
1113 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1114 dest->IntermBezierTo (nData->p);
1115 }
1116 dest->EndBezierTo ();
1117 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1118 from, pe, 1.0, te);
1119 }
1120 }
1121 else
1122 {
1123 if (te < 0.0001)
1124 {
1125 NR::Point tx;
1126 {
1127 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1128 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1129 tx = (pnData->p + psData->p) / 2;
1130 }
1131 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1132 from, ps, ts, 0.0);
1133 dest->BezierTo (nx);
1134 for (int i = ps + 1; i >= pe; i--)
1135 {
1136 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1137 dest->IntermBezierTo (nData->p);
1138 }
1139 dest->EndBezierTo ();
1140 }
1141 else
1142 {
1143 NR::Point tx;
1144 {
1145 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1146 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1147 tx = (pnData->p + psData->p) / 2;
1148 }
1149 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1150 from, ps, ts, 0.0);
1151 {
1152 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1153 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1154 tx = (pnData->p + psData->p) / 2;
1155 }
1156 dest->BezierTo (tx);
1157 for (int i = ps + 1; i > pe; i--)
1158 {
1159 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1160 dest->IntermBezierTo (nData->p);
1161 }
1162 dest->EndBezierTo ();
1163 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1164 from, pe, 1.0, te);
1165 }
1166 }
1167 }
1168 return bord;
1169 }
1171 void
1172 Shape::ReFormeBezierChunk (NR::Point px, NR::Point nx,
1173 Path * dest, int inBezier, int nbInterm,
1174 Path * from, int p, double ts, double te)
1175 {
1176 PathDescrBezierTo* nBData = dynamic_cast<PathDescrBezierTo*>(from->descr_cmd[inBezier]);
1177 NR::Point bstx = from->PrevPoint (inBezier - 1);
1178 NR::Point benx = nBData->p;
1180 NR::Point mx;
1181 if (p == inBezier)
1182 {
1183 // premier bout
1184 if (nbInterm <= 1)
1185 {
1186 // seul bout de la spline
1187 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1188 mx = nData->p;
1189 }
1190 else
1191 {
1192 // premier bout d'une spline qui en contient plusieurs
1193 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1194 mx = nData->p;
1195 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+2]);
1196 benx = (nData->p + mx) / 2;
1197 }
1198 }
1199 else if (p == inBezier + nbInterm - 1)
1200 {
1201 // dernier bout
1202 // si nbInterm == 1, le cas a deja ete traite
1203 // donc dernier bout d'une spline qui en contient plusieurs
1204 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm]);
1205 mx = nData->p;
1206 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm-1]);
1207 bstx = (nData->p + mx) / 2;
1208 }
1209 else
1210 {
1211 // la spline contient forcément plusieurs bouts, et ce n'est ni le premier ni le dernier
1212 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+1]);
1213 mx = nData->p;
1214 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p]);
1215 bstx = (nData->p + mx) / 2;
1216 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+2]);
1217 benx = (nData->p + mx) / 2;
1218 }
1219 NR::Point cx;
1220 {
1221 Path::QuadraticPoint ((ts + te) / 2, cx, bstx, mx, benx);
1222 }
1223 cx = 2 * cx - (px + nx) / 2;
1224 {
1225 dest->BezierTo (nx);
1226 dest->IntermBezierTo (cx);
1227 dest->EndBezierTo ();
1228 }
1229 }
1231 #undef MiscNormalize