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