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 }
548 _aretes = a->_aretes;
549 if (numberOfEdges() > maxAr)
550 {
551 maxAr = numberOfEdges();
552 if (_has_edges_data)
553 eData.resize(maxAr);
554 if (_has_sweep_src_data)
555 swsData.resize(maxAr);
556 if (_has_sweep_dest_data)
557 swdData.resize(maxAr);
558 if (_has_raster_data)
559 swrData.resize(maxAr);
560 if (_has_back_data)
561 ebData.resize(maxAr);
562 }
563 return 0;
564 }
565 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1 || a->type != shape_polygon)
566 return shape_input_err;
568 a->SortEdges ();
570 a->MakeSweepDestData (true);
571 a->MakeSweepSrcData (true);
573 for (int i = 0; i < a->numberOfEdges(); i++)
574 {
575 // int stP=a->swsData[i].stPt/*,enP=a->swsData[i].enPt*/;
576 int stB = -1, enB = -1;
577 if (dec > 0)
578 {
579 stB = a->CycleNextAt (a->getEdge(i).st, i);
580 enB = a->CyclePrevAt (a->getEdge(i).en, i);
581 }
582 else
583 {
584 stB = a->CyclePrevAt (a->getEdge(i).st, i);
585 enB = a->CycleNextAt (a->getEdge(i).en, i);
586 }
588 NR::Point stD, seD, enD;
589 double stL, seL, enL;
590 stD = a->getEdge(stB).dx;
591 seD = a->getEdge(i).dx;
592 enD = a->getEdge(enB).dx;
594 stL = sqrt (dot(stD,stD));
595 seL = sqrt (dot(seD,seD));
596 enL = sqrt (dot(enD,enD));
597 MiscNormalize (stD);
598 MiscNormalize (enD);
599 MiscNormalize (seD);
601 NR::Point ptP;
602 int stNo, enNo;
603 ptP = a->getPoint(a->getEdge(i).st).x;
604 int usePathID=-1;
605 int usePieceID=0;
606 double useT=0.0;
607 if ( a->_has_back_data ) {
608 if ( a->ebData[i].pathID >= 0 && a->ebData[stB].pathID == a->ebData[i].pathID && a->ebData[stB].pieceID == a->ebData[i].pieceID
609 && a->ebData[stB].tEn == a->ebData[i].tSt ) {
610 usePathID=a->ebData[i].pathID;
611 usePieceID=a->ebData[i].pieceID;
612 useT=a->ebData[i].tSt;
613 } else {
614 usePathID=a->ebData[i].pathID;
615 usePieceID=0;
616 useT=0;
617 }
618 }
619 if (dec > 0)
620 {
621 Path::DoRightJoin (this, dec, join, ptP, stD, seD, miter, stL, seL,
622 stNo, enNo,usePathID,usePieceID,useT);
623 a->swsData[i].stPt = enNo;
624 a->swsData[stB].enPt = stNo;
625 }
626 else
627 {
628 Path::DoLeftJoin (this, -dec, join, ptP, stD, seD, miter, stL, seL,
629 stNo, enNo,usePathID,usePieceID,useT);
630 a->swsData[i].stPt = enNo;
631 a->swsData[stB].enPt = stNo;
632 }
633 }
634 if (dec < 0)
635 {
636 for (int i = 0; i < numberOfEdges(); i++)
637 Inverse (i);
638 }
639 if ( _has_back_data ) {
640 for (int i = 0; i < a->numberOfEdges(); i++)
641 {
642 int nEd=AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
643 ebData[nEd]=a->ebData[i];
644 }
645 } else {
646 for (int i = 0; i < a->numberOfEdges(); i++)
647 {
648 AddEdge (a->swsData[i].stPt, a->swsData[i].enPt);
649 }
650 }
651 a->MakeSweepSrcData (false);
652 a->MakeSweepDestData (false);
654 return 0;
655 }
657 // we found a contour, now reassemble the edges on it, instead of dumping them in the Path "dest" as a
658 // polyline. since it was a DFS, the precParc and suivParc make a nice doubly-linked list of the edges in
659 // the contour. the first and last edges of the contour are startBord and curBord
660 void
661 Shape::AddContour (Path * dest, int nbP, Path * *orig, int startBord, int curBord, bool splitWhenForced)
662 {
663 int bord = startBord;
665 {
666 dest->MoveTo (getPoint(getEdge(bord).st).x);
667 }
669 while (bord >= 0)
670 {
671 int nPiece = ebData[bord].pieceID;
672 int nPath = ebData[bord].pathID;
674 if (nPath < 0 || nPath >= nbP || orig[nPath] == NULL)
675 {
676 // segment batard
677 dest->LineTo (getPoint(getEdge(bord).en).x);
678 bord = swdData[bord].suivParc;
679 }
680 else
681 {
682 Path *from = orig[nPath];
683 if (nPiece < 0 || nPiece >= int(from->descr_cmd.size()))
684 {
685 // segment batard
686 dest->LineTo (getPoint(getEdge(bord).en).x);
687 bord = swdData[bord].suivParc;
688 }
689 else
690 {
691 int nType = from->descr_cmd[nPiece]->getType();
692 if (nType == descr_close || nType == descr_moveto
693 || nType == descr_forced)
694 {
695 // devrait pas arriver
696 dest->LineTo (getPoint(getEdge(bord).en).x);
697 bord = swdData[bord].suivParc;
698 }
699 else if (nType == descr_lineto)
700 {
701 bord = ReFormeLineTo (bord, curBord, dest, from);
702 }
703 else if (nType == descr_arcto)
704 {
705 bord = ReFormeArcTo (bord, curBord, dest, from);
706 }
707 else if (nType == descr_cubicto)
708 {
709 bord = ReFormeCubicTo (bord, curBord, dest, from);
710 }
711 else if (nType == descr_bezierto)
712 {
713 PathDescrBezierTo* nBData =
714 dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
716 if (nBData->nb == 0)
717 {
718 bord = ReFormeLineTo (bord, curBord, dest, from);
719 }
720 else
721 {
722 bord = ReFormeBezierTo (bord, curBord, dest, from);
723 }
724 }
725 else if (nType == descr_interm_bezier)
726 {
727 bord = ReFormeBezierTo (bord, curBord, dest, from);
728 }
729 else
730 {
731 // devrait pas arriver non plus
732 dest->LineTo (getPoint(getEdge(bord).en).x);
733 bord = swdData[bord].suivParc;
734 }
735 if (bord >= 0 && getPoint(getEdge(bord).st).totalDegree() > 2 ) {
736 dest->ForcePoint ();
737 } else if ( bord >= 0 && getPoint(getEdge(bord).st).oldDegree > 2 && getPoint(getEdge(bord).st).totalDegree() == 2) {
738 if ( splitWhenForced ) {
739 // pour les coupures
740 dest->ForcePoint ();
741 } else {
742 if ( _has_back_data ) {
743 int prevEdge=getPoint(getEdge(bord).st).incidentEdge[FIRST];
744 int nextEdge=getPoint(getEdge(bord).st).incidentEdge[LAST];
745 if ( getEdge(prevEdge).en != getEdge(bord).st ) {
746 int swai=prevEdge;prevEdge=nextEdge;nextEdge=swai;
747 }
748 if ( ebData[prevEdge].pieceID == ebData[nextEdge].pieceID && ebData[prevEdge].pathID == ebData[nextEdge].pathID ) {
749 if ( fabs(ebData[prevEdge].tEn-ebData[nextEdge].tSt) < 0.05 ) {
750 } else {
751 dest->ForcePoint ();
752 }
753 } else {
754 dest->ForcePoint ();
755 }
756 } else {
757 dest->ForcePoint ();
758 }
759 }
760 }
761 }
762 }
763 }
764 dest->Close ();
765 }
767 int
768 Shape::ReFormeLineTo (int bord, int curBord, Path * dest, Path * orig)
769 {
770 int nPiece = ebData[bord].pieceID;
771 int nPath = ebData[bord].pathID;
772 double /*ts=ebData[bord].tSt, */ te = ebData[bord].tEn;
773 NR::Point nx = getPoint(getEdge(bord).en).x;
774 bord = swdData[bord].suivParc;
775 while (bord >= 0)
776 {
777 if (getPoint(getEdge(bord).st).totalDegree() > 2
778 || getPoint(getEdge(bord).st).oldDegree > 2)
779 {
780 break;
781 }
782 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
783 {
784 if (fabs (te - ebData[bord].tSt) > 0.0001)
785 break;
786 nx = getPoint(getEdge(bord).en).x;
787 te = ebData[bord].tEn;
788 }
789 else
790 {
791 break;
792 }
793 bord = swdData[bord].suivParc;
794 }
795 {
796 dest->LineTo (nx);
797 }
798 return bord;
799 }
801 int
802 Shape::ReFormeArcTo (int bord, int curBord, Path * dest, Path * from)
803 {
804 int nPiece = ebData[bord].pieceID;
805 int nPath = ebData[bord].pathID;
806 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
807 // double px=pts[getEdge(bord).st].x,py=pts[getEdge(bord).st].y;
808 NR::Point nx = getPoint(getEdge(bord).en).x;
809 bord = swdData[bord].suivParc;
810 while (bord >= 0)
811 {
812 if (getPoint(getEdge(bord).st).totalDegree() > 2
813 || getPoint(getEdge(bord).st).oldDegree > 2)
814 {
815 break;
816 }
817 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
818 {
819 if (fabs (te - ebData[bord].tSt) > 0.0001)
820 {
821 break;
822 }
823 nx = getPoint(getEdge(bord).en).x;
824 te = ebData[bord].tEn;
825 }
826 else
827 {
828 break;
829 }
830 bord = swdData[bord].suivParc;
831 }
832 double sang, eang;
833 PathDescrArcTo* nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
834 bool nLarge = nData->large;
835 bool nClockwise = nData->clockwise;
836 Path::ArcAngles (from->PrevPoint (nPiece - 1), nData->p,nData->rx,nData->ry,nData->angle, nLarge, nClockwise, sang, eang);
837 if (nClockwise)
838 {
839 if (sang < eang)
840 sang += 2 * M_PI;
841 }
842 else
843 {
844 if (sang > eang)
845 sang -= 2 * M_PI;
846 }
847 double delta = eang - sang;
848 double ndelta = delta * (te - ts);
849 if (ts > te)
850 nClockwise = !nClockwise;
851 if (ndelta < 0)
852 ndelta = -ndelta;
853 if (ndelta > M_PI)
854 nLarge = true;
855 else
856 nLarge = false;
857 /* if ( delta < 0 ) delta=-delta;
858 if ( ndelta < 0 ) ndelta=-ndelta;
859 if ( ( delta < M_PI && ndelta < M_PI ) || ( delta >= M_PI && ndelta >= M_PI ) ) {
860 if ( ts < te ) {
861 } else {
862 nClockwise=!(nClockwise);
863 }
864 } else {
865 // nLarge=!(nLarge);
866 nLarge=false; // c'est un sous-segment -> l'arc ne peut que etre plus petit
867 if ( ts < te ) {
868 } else {
869 nClockwise=!(nClockwise);
870 }
871 }*/
872 {
873 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(from->descr_cmd[nPiece]);
874 dest->ArcTo (nx, nData->rx,nData->ry,nData->angle, nLarge, nClockwise);
875 }
876 return bord;
877 }
879 int
880 Shape::ReFormeCubicTo (int bord, int curBord, Path * dest, Path * from)
881 {
882 int nPiece = ebData[bord].pieceID;
883 int nPath = ebData[bord].pathID;
884 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
885 NR::Point nx = getPoint(getEdge(bord).en).x;
886 bord = swdData[bord].suivParc;
887 while (bord >= 0)
888 {
889 if (getPoint(getEdge(bord).st).totalDegree() > 2
890 || getPoint(getEdge(bord).st).oldDegree > 2)
891 {
892 break;
893 }
894 if (ebData[bord].pieceID == nPiece && ebData[bord].pathID == nPath)
895 {
896 if (fabs (te - ebData[bord].tSt) > 0.0001)
897 {
898 break;
899 }
900 nx = getPoint(getEdge(bord).en).x;
901 te = ebData[bord].tEn;
902 }
903 else
904 {
905 break;
906 }
907 bord = swdData[bord].suivParc;
908 }
909 NR::Point prevx = from->PrevPoint (nPiece - 1);
911 NR::Point sDx, eDx;
912 {
913 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(from->descr_cmd[nPiece]);
914 Path::CubicTangent (ts, sDx, prevx,nData->start,nData->p,nData->end);
915 Path::CubicTangent (te, eDx, prevx,nData->start,nData->p,nData->end);
916 }
917 sDx *= (te - ts);
918 eDx *= (te - ts);
919 {
920 dest->CubicTo (nx,sDx,eDx);
921 }
922 return bord;
923 }
925 int
926 Shape::ReFormeBezierTo (int bord, int curBord, Path * dest, Path * from)
927 {
928 int nPiece = ebData[bord].pieceID;
929 int nPath = ebData[bord].pathID;
930 double ts = ebData[bord].tSt, te = ebData[bord].tEn;
931 int ps = nPiece, pe = nPiece;
932 NR::Point px = getPoint(getEdge(bord).st).x;
933 NR::Point nx = getPoint(getEdge(bord).en).x;
934 int inBezier = -1, nbInterm = -1;
935 int typ;
936 typ = from->descr_cmd[nPiece]->getType();
937 PathDescrBezierTo *nBData = NULL;
938 if (typ == descr_bezierto)
939 {
940 nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[nPiece]);
941 inBezier = nPiece;
942 nbInterm = nBData->nb;
943 }
944 else
945 {
946 int n = nPiece - 1;
947 while (n > 0)
948 {
949 typ = from->descr_cmd[n]->getType();
950 if (typ == descr_bezierto)
951 {
952 inBezier = n;
953 nBData = dynamic_cast<PathDescrBezierTo *>(from->descr_cmd[n]);
954 nbInterm = nBData->nb;
955 break;
956 }
957 n--;
958 }
959 if (inBezier < 0)
960 {
961 bord = swdData[bord].suivParc;
962 dest->LineTo (nx);
963 return bord;
964 }
965 }
966 bord = swdData[bord].suivParc;
967 while (bord >= 0)
968 {
969 if (getPoint(getEdge(bord).st).totalDegree() > 2
970 || getPoint(getEdge(bord).st).oldDegree > 2)
971 {
972 break;
973 }
974 if (ebData[bord].pathID == nPath)
975 {
976 if (ebData[bord].pieceID < inBezier
977 || ebData[bord].pieceID >= inBezier + nbInterm)
978 break;
979 if (ebData[bord].pieceID == pe
980 && fabs (te - ebData[bord].tSt) > 0.0001)
981 break;
982 if (ebData[bord].pieceID != pe
983 && (ebData[bord].tSt > 0.0001 && ebData[bord].tSt < 0.9999))
984 break;
985 if (ebData[bord].pieceID != pe && (te > 0.0001 && te < 0.9999))
986 break;
987 nx = getPoint(getEdge(bord).en).x;
988 te = ebData[bord].tEn;
989 pe = ebData[bord].pieceID;
990 }
991 else
992 {
993 break;
994 }
995 bord = swdData[bord].suivParc;
996 }
998 g_return_val_if_fail(nBData != NULL, 0);
1000 if (pe == ps)
1001 {
1002 ReFormeBezierChunk (px, nx, dest, inBezier, nbInterm, from, ps,
1003 ts, te);
1004 }
1005 else if (ps < pe)
1006 {
1007 if (ts < 0.0001)
1008 {
1009 if (te > 0.9999)
1010 {
1011 dest->BezierTo (nx);
1012 for (int i = ps; i <= pe; i++)
1013 {
1014 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1015 dest->IntermBezierTo (nData->p);
1016 }
1017 dest->EndBezierTo ();
1018 }
1019 else
1020 {
1021 NR::Point tx;
1022 {
1023 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1024 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1025 tx = (pnData->p + psData->p) / 2;
1026 }
1027 dest->BezierTo (tx);
1028 for (int i = ps; i < pe; i++)
1029 {
1030 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1031 dest->IntermBezierTo (nData->p);
1032 }
1033 dest->EndBezierTo ();
1034 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1035 from, pe, 0.0, te);
1036 }
1037 }
1038 else
1039 {
1040 if (te > 0.9999)
1041 {
1042 NR::Point tx;
1043 {
1044 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1045 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1046 tx = (psData->p + pnData->p) / 2;
1047 }
1048 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1049 from, ps, ts, 1.0);
1050 dest->BezierTo (nx);
1051 for (int i = ps + 1; i <= pe; i++)
1052 {
1053 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1054 dest->IntermBezierTo (nData->p);
1055 }
1056 dest->EndBezierTo ();
1057 }
1058 else
1059 {
1060 NR::Point tx;
1061 {
1062 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1063 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+2]);
1064 tx = (pnData->p + psData->p) / 2;
1065 }
1066 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1067 from, ps, ts, 1.0);
1068 {
1069 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe]);
1070 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1071 tx = (pnData->p + psData->p) / 2;
1072 }
1073 dest->BezierTo (tx);
1074 for (int i = ps + 1; i <= pe; i++)
1075 {
1076 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1077 dest->IntermBezierTo (nData->p);
1078 }
1079 dest->EndBezierTo ();
1080 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1081 from, pe, 0.0, te);
1082 }
1083 }
1084 }
1085 else
1086 {
1087 if (ts > 0.9999)
1088 {
1089 if (te < 0.0001)
1090 {
1091 dest->BezierTo (nx);
1092 for (int i = ps; i >= pe; i--)
1093 {
1094 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1095 dest->IntermBezierTo (nData->p);
1096 }
1097 dest->EndBezierTo ();
1098 }
1099 else
1100 {
1101 NR::Point tx;
1102 {
1103 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1104 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1105 tx = (pnData->p + psData->p) / 2;
1106 }
1107 dest->BezierTo (tx);
1108 for (int i = ps; i > pe; i--)
1109 {
1110 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i+1]);
1111 dest->IntermBezierTo (nData->p);
1112 }
1113 dest->EndBezierTo ();
1114 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1115 from, pe, 1.0, te);
1116 }
1117 }
1118 else
1119 {
1120 if (te < 0.0001)
1121 {
1122 NR::Point tx;
1123 {
1124 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1125 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1126 tx = (pnData->p + psData->p) / 2;
1127 }
1128 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1129 from, ps, ts, 0.0);
1130 dest->BezierTo (nx);
1131 for (int i = ps + 1; i >= pe; i--)
1132 {
1133 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1134 dest->IntermBezierTo (nData->p);
1135 }
1136 dest->EndBezierTo ();
1137 }
1138 else
1139 {
1140 NR::Point tx;
1141 {
1142 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps]);
1143 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[ps+1]);
1144 tx = (pnData->p + psData->p) / 2;
1145 }
1146 ReFormeBezierChunk (px, tx, dest, inBezier, nbInterm,
1147 from, ps, ts, 0.0);
1148 {
1149 PathDescrIntermBezierTo* psData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+1]);
1150 PathDescrIntermBezierTo* pnData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[pe+2]);
1151 tx = (pnData->p + psData->p) / 2;
1152 }
1153 dest->BezierTo (tx);
1154 for (int i = ps + 1; i > pe; i--)
1155 {
1156 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[i]);
1157 dest->IntermBezierTo (nData->p);
1158 }
1159 dest->EndBezierTo ();
1160 ReFormeBezierChunk (tx, nx, dest, inBezier, nbInterm,
1161 from, pe, 1.0, te);
1162 }
1163 }
1164 }
1165 return bord;
1166 }
1168 void
1169 Shape::ReFormeBezierChunk (NR::Point px, NR::Point nx,
1170 Path * dest, int inBezier, int nbInterm,
1171 Path * from, int p, double ts, double te)
1172 {
1173 PathDescrBezierTo* nBData = dynamic_cast<PathDescrBezierTo*>(from->descr_cmd[inBezier]);
1174 NR::Point bstx = from->PrevPoint (inBezier - 1);
1175 NR::Point benx = nBData->p;
1177 NR::Point mx;
1178 if (p == inBezier)
1179 {
1180 // premier bout
1181 if (nbInterm <= 1)
1182 {
1183 // seul bout de la spline
1184 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1185 mx = nData->p;
1186 }
1187 else
1188 {
1189 // premier bout d'une spline qui en contient plusieurs
1190 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+1]);
1191 mx = nData->p;
1192 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+2]);
1193 benx = (nData->p + mx) / 2;
1194 }
1195 }
1196 else if (p == inBezier + nbInterm - 1)
1197 {
1198 // dernier bout
1199 // si nbInterm == 1, le cas a deja ete traite
1200 // donc dernier bout d'une spline qui en contient plusieurs
1201 PathDescrIntermBezierTo* nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm]);
1202 mx = nData->p;
1203 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[inBezier+nbInterm-1]);
1204 bstx = (nData->p + mx) / 2;
1205 }
1206 else
1207 {
1208 // la spline contient forcément plusieurs bouts, et ce n'est ni le premier ni le dernier
1209 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+1]);
1210 mx = nData->p;
1211 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p]);
1212 bstx = (nData->p + mx) / 2;
1213 nData = dynamic_cast<PathDescrIntermBezierTo*>(from->descr_cmd[p+2]);
1214 benx = (nData->p + mx) / 2;
1215 }
1216 NR::Point cx;
1217 {
1218 Path::QuadraticPoint ((ts + te) / 2, cx, bstx, mx, benx);
1219 }
1220 cx = 2 * cx - (px + nx) / 2;
1221 {
1222 dest->BezierTo (nx);
1223 dest->IntermBezierTo (cx);
1224 dest->EndBezierTo ();
1225 }
1226 }
1228 #undef MiscNormalize