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