![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
1 /*
2 * ShapeSweep.cpp
3 * nlivarot
4 *
5 * Created by fred on Thu Jun 19 2003.
6 *
7 */
9 #include <glib/gmem.h>
10 #include "Shape.h"
11 #include "livarot/sweep-event-queue.h"
12 #include "livarot/sweep-tree-list.h"
13 #include "livarot/sweep-tree.h"
15 #include "libnr/nr-matrix.h"
17 //int doDebug=0;
19 /*
20 * El Intersector.
21 * algorithm: 1) benley ottman to get intersections of all the polygon's edges
22 * 2) rounding of the points of the polygon, Hooby's algorithm
23 * 3) DFS with clockwise choice of the edge to compute the windings
24 * 4) choose edges according to winding numbers and fill rule
25 * some additional nastyness: step 2 needs a seed winding number for the upper-left point of each
26 * connex subgraph of the graph. computing these brutally is O(n^3): baaaad. so during the sweeping in 1)
27 * we keep for each point the edge of the resulting graph (not the original) that lies just on its left;
28 * when the time comes for the point to get its winding number computed, that edge must have been treated,
29 * because its upper end lies above the aforementioned point, meaning we know the winding number of the point.
30 * only, there is a catch: since we're sweeping the polygon, the edge we want to link the point to has not yet been
31 * added (that would be too easy...). so the points are put on a linked list on the original shape's edge, and the list
32 * is flushed when the edge is added.
33 * rounding: to do the rounding, we need to find which edges cross the surrounding of the rounded points (at
34 * each sweepline position). grunt method tries all combination of "rounded points in the sweepline"x"edges crossing
35 * the sweepline". That's bad (and that's what polyboolean does, if i am not mistaken). so for each point
36 * rounded in a given sweepline, keep immediate left and right edges at the time the point is treated.
37 * when edges/points crossing are searched, walk the edge list (in the sweepline at the end of the batch) starting
38 * from the rounded points' left and right from that time. may sound strange, but it works because edges that
39 * end or start in the batch have at least one end in the batch.
40 * all these are the cause of the numerous linked lists of points and edges maintained in the sweeping
41 */
43 void
44 Shape::ResetSweep (void)
45 {
46 MakePointData (true);
47 MakeEdgeData (true);
48 MakeSweepSrcData (true);
49 }
51 void
52 Shape::CleanupSweep (void)
53 {
54 MakePointData (false);
55 MakeEdgeData (false);
56 MakeSweepSrcData (false);
57 }
59 void
60 Shape::ForceToPolygon (void)
61 {
62 type = shape_polygon;
63 }
65 int
66 Shape::Reoriente (Shape * a)
67 {
68 Reset (0, 0);
69 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
70 return 0;
71 if (directedEulerian(a) == false)
72 return shape_input_err;
74 _pts = a->_pts;
75 if (numberOfPoints() > maxPt)
76 {
77 maxPt = numberOfPoints();
78 if (_has_points_data)
79 pData.resize(maxPt);
80 }
82 _aretes = a->_aretes;
83 if (numberOfEdges() > maxAr)
84 {
85 maxAr = numberOfEdges();
86 if (_has_edges_data)
87 eData.resize(maxAr);
88 if (_has_sweep_src_data)
89 swsData.resize(maxAr);
90 if (_has_sweep_dest_data)
91 swdData.resize(maxAr);
92 if (_has_raster_data)
93 swrData.resize(maxAr);
94 }
96 MakePointData (true);
97 MakeEdgeData (true);
98 MakeSweepDestData (true);
100 initialisePointData();
102 for (int i = 0; i < numberOfPoints(); i++) {
103 _pts[i].x = pData[i].rx;
104 _pts[i].oldDegree = getPoint(i).totalDegree();
105 }
107 for (int i = 0; i < a->numberOfEdges(); i++)
108 {
109 eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
110 eData[i].weight = 1;
111 _aretes[i].dx = eData[i].rdx;
112 }
114 SortPointsRounded ();
116 _need_edges_sorting = true;
117 GetWindings (this, NULL, bool_op_union, true);
119 // Plot(341,56,8,400,400,true,true,false,true);
120 for (int i = 0; i < numberOfEdges(); i++)
121 {
122 swdData[i].leW %= 2;
123 swdData[i].riW %= 2;
124 if (swdData[i].leW < 0)
125 swdData[i].leW = -swdData[i].leW;
126 if (swdData[i].riW < 0)
127 swdData[i].riW = -swdData[i].riW;
128 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
129 {
130 eData[i].weight = 1;
131 }
132 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
133 {
134 Inverse (i);
135 eData[i].weight = 1;
136 }
137 else
138 {
139 eData[i].weight = 0;
140 SubEdge (i);
141 i--;
142 }
143 }
145 MakePointData (false);
146 MakeEdgeData (false);
147 MakeSweepDestData (false);
149 if (directedEulerian(this) == false)
150 {
151 // printf( "pas euclidian2");
152 _pts.clear();
153 _aretes.clear();
154 return shape_euler_err;
155 }
157 type = shape_polygon;
158 return 0;
159 }
161 int
162 Shape::ConvertToShape (Shape * a, FillRule directed, bool invert)
163 {
164 Reset (0, 0);
166 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1) {
167 return 0;
168 }
170 if ( directed != fill_justDont && directedEulerian(a) == false ) {
171 return shape_input_err;
172 }
174 a->ResetSweep();
176 if (sTree == NULL) {
177 sTree = new SweepTreeList(a->numberOfEdges());
178 }
179 if (sEvts == NULL) {
180 sEvts = new SweepEventQueue(a->numberOfEdges());
181 }
183 MakePointData(true);
184 MakeEdgeData(true);
185 MakeSweepSrcData(true);
186 MakeSweepDestData(true);
187 MakeBackData(a->_has_back_data);
189 a->initialisePointData();
190 a->initialiseEdgeData();
192 a->SortPointsRounded();
194 chgts.clear();
196 double lastChange = a->pData[0].rx[1] - 1.0;
197 int lastChgtPt = 0;
198 int edgeHead = -1;
199 Shape *shapeHead = NULL;
201 clearIncidenceData();
203 int curAPt = 0;
205 while (curAPt < a->numberOfPoints() || sEvts->size() > 0) {
206 NR::Point ptX;
207 double ptL, ptR;
208 SweepTree *intersL = NULL;
209 SweepTree *intersR = NULL;
210 int nPt = -1;
211 Shape *ptSh = NULL;
212 bool isIntersection = false;
213 if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
214 {
215 if (a->pData[curAPt].pending > 0
216 || (a->pData[curAPt].rx[1] > ptX[1]
217 || (a->pData[curAPt].rx[1] == ptX[1]
218 && a->pData[curAPt].rx[0] > ptX[0])))
219 {
220 /* FIXME: could just be pop? */
221 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
222 isIntersection = true;
223 }
224 else
225 {
226 nPt = curAPt++;
227 ptSh = a;
228 ptX = ptSh->pData[nPt].rx;
229 isIntersection = false;
230 }
231 }
232 else
233 {
234 nPt = curAPt++;
235 ptSh = a;
236 ptX = ptSh->pData[nPt].rx;
237 isIntersection = false;
238 }
240 if (isIntersection == false)
241 {
242 if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
243 continue;
244 }
246 NR::Point rPtX;
247 rPtX[0]= Round (ptX[0]);
248 rPtX[1]= Round (ptX[1]);
249 int lastPointNo = -1;
250 lastPointNo = AddPoint (rPtX);
251 pData[lastPointNo].rx = rPtX;
253 if (rPtX[1] > lastChange)
254 {
255 int lastI = AssemblePoints (lastChgtPt, lastPointNo);
257 Shape *curSh = shapeHead;
258 int curBo = edgeHead;
259 while (curSh)
260 {
261 curSh->swsData[curBo].leftRnd =
262 pData[curSh->swsData[curBo].leftRnd].newInd;
263 curSh->swsData[curBo].rightRnd =
264 pData[curSh->swsData[curBo].rightRnd].newInd;
266 Shape *neSh = curSh->swsData[curBo].nextSh;
267 curBo = curSh->swsData[curBo].nextBo;
268 curSh = neSh;
269 }
271 for (unsigned int i = 0; i < chgts.size(); i++)
272 {
273 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
274 if (chgts[i].type == 0)
275 {
276 if (chgts[i].src->getEdge(chgts[i].bord).st <
277 chgts[i].src->getEdge(chgts[i].bord).en)
278 {
279 chgts[i].src->swsData[chgts[i].bord].stPt =
280 chgts[i].ptNo;
281 }
282 else
283 {
284 chgts[i].src->swsData[chgts[i].bord].enPt =
285 chgts[i].ptNo;
286 }
287 }
288 else if (chgts[i].type == 1)
289 {
290 if (chgts[i].src->getEdge(chgts[i].bord).st >
291 chgts[i].src->getEdge(chgts[i].bord).en)
292 {
293 chgts[i].src->swsData[chgts[i].bord].stPt =
294 chgts[i].ptNo;
295 }
296 else
297 {
298 chgts[i].src->swsData[chgts[i].bord].enPt =
299 chgts[i].ptNo;
300 }
301 }
302 }
304 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
306 CheckEdges (lastI, lastChgtPt, a, NULL, bool_op_union);
308 for (int i = lastChgtPt; i < lastI; i++) {
309 if (pData[i].askForWindingS) {
310 Shape *windS = pData[i].askForWindingS;
311 int windB = pData[i].askForWindingB;
312 pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
313 windS->swsData[windB].firstLinkedPoint = i;
314 }
315 }
317 if (lastI < lastPointNo) {
318 _pts[lastI] = getPoint(lastPointNo);
319 pData[lastI] = pData[lastPointNo];
320 }
321 lastPointNo = lastI;
322 _pts.resize(lastI + 1);
324 lastChgtPt = lastPointNo;
325 lastChange = rPtX[1];
326 chgts.clear();
327 edgeHead = -1;
328 shapeHead = NULL;
329 }
332 if (isIntersection)
333 {
334 // printf("(%i %i [%i %i]) ",intersL->bord,intersR->bord,intersL->startPoint,intersR->startPoint);
335 intersL->RemoveEvent (*sEvts, LEFT);
336 intersR->RemoveEvent (*sEvts, RIGHT);
338 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
339 intersL->src, intersL->bord, intersR->src, intersR->bord);
341 intersL->SwapWithRight (*sTree, *sEvts);
343 TesteIntersection (intersL, LEFT, false);
344 TesteIntersection (intersR, RIGHT, false);
345 }
346 else
347 {
348 int cb;
350 int nbUp = 0, nbDn = 0;
351 int upNo = -1, dnNo = -1;
352 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
353 while (cb >= 0 && cb < ptSh->numberOfEdges())
354 {
355 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
356 && nPt == ptSh->getEdge(cb).en)
357 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
358 && nPt == ptSh->getEdge(cb).st))
359 {
360 upNo = cb;
361 nbUp++;
362 }
363 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
364 && nPt == ptSh->getEdge(cb).en)
365 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
366 && nPt == ptSh->getEdge(cb).st))
367 {
368 dnNo = cb;
369 nbDn++;
370 }
371 cb = ptSh->NextAt (nPt, cb);
372 }
374 if (nbDn <= 0)
375 {
376 upNo = -1;
377 }
378 if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == NULL)
379 {
380 upNo = -1;
381 }
383 bool doWinding = true;
385 if (nbUp > 0)
386 {
387 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
388 while (cb >= 0 && cb < ptSh->numberOfEdges())
389 {
390 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
391 && nPt == ptSh->getEdge(cb).en)
392 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
393 && nPt == ptSh->getEdge(cb).st))
394 {
395 if (cb != upNo)
396 {
397 SweepTree *node =
398 (SweepTree *) ptSh->swsData[cb].misc;
399 if (node == NULL)
400 {
401 }
402 else
403 {
404 AddChgt (lastPointNo, lastChgtPt, shapeHead,
405 edgeHead, EDGE_REMOVED, node->src, node->bord,
406 NULL, -1);
407 ptSh->swsData[cb].misc = NULL;
409 int onLeftB = -1, onRightB = -1;
410 Shape *onLeftS = NULL;
411 Shape *onRightS = NULL;
412 if (node->elem[LEFT])
413 {
414 onLeftB =
415 (static_cast <
416 SweepTree * >(node->elem[LEFT]))->bord;
417 onLeftS =
418 (static_cast <
419 SweepTree * >(node->elem[LEFT]))->src;
420 }
421 if (node->elem[RIGHT])
422 {
423 onRightB =
424 (static_cast <
425 SweepTree * >(node->elem[RIGHT]))->bord;
426 onRightS =
427 (static_cast <
428 SweepTree * >(node->elem[RIGHT]))->src;
429 }
431 node->Remove (*sTree, *sEvts, true);
432 if (onLeftS && onRightS)
433 {
434 SweepTree *onLeft =
435 (SweepTree *) onLeftS->swsData[onLeftB].
436 misc;
437 if (onLeftS == ptSh
438 && (onLeftS->getEdge(onLeftB).en == nPt
439 || onLeftS->getEdge(onLeftB).st ==
440 nPt))
441 {
442 }
443 else
444 {
445 if (onRightS == ptSh
446 && (onRightS->getEdge(onRightB).en ==
447 nPt
448 || onRightS->getEdge(onRightB).
449 st == nPt))
450 {
451 }
452 else
453 {
454 TesteIntersection (onLeft, RIGHT, false);
455 }
456 }
457 }
458 }
459 }
460 }
461 cb = ptSh->NextAt (nPt, cb);
462 }
463 }
465 // traitement du "upNo devient dnNo"
466 SweepTree *insertionNode = NULL;
467 if (dnNo >= 0)
468 {
469 if (upNo >= 0)
470 {
471 SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
473 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
474 node->src, node->bord, NULL, -1);
476 ptSh->swsData[upNo].misc = NULL;
478 node->RemoveEvents (*sEvts);
479 node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
480 ptSh->swsData[dnNo].misc = node;
481 TesteIntersection (node, RIGHT, false);
482 TesteIntersection (node, LEFT, false);
483 insertionNode = node;
485 ptSh->swsData[dnNo].curPoint = lastPointNo;
486 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
487 node->src, node->bord, NULL, -1);
488 }
489 else
490 {
491 SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
492 ptSh->swsData[dnNo].misc = node;
493 node->Insert (*sTree, *sEvts, this, lastPointNo, true);
494 if (doWinding)
495 {
496 SweepTree *myLeft =
497 static_cast < SweepTree * >(node->elem[LEFT]);
498 if (myLeft)
499 {
500 pData[lastPointNo].askForWindingS = myLeft->src;
501 pData[lastPointNo].askForWindingB = myLeft->bord;
502 }
503 else
504 {
505 pData[lastPointNo].askForWindingB = -1;
506 }
507 doWinding = false;
508 }
509 TesteIntersection (node, RIGHT, false);
510 TesteIntersection (node, LEFT, false);
511 insertionNode = node;
513 ptSh->swsData[dnNo].curPoint = lastPointNo;
514 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
515 node->src, node->bord, NULL, -1);
516 }
517 }
519 if (nbDn > 1)
520 { // si nbDn == 1 , alors dnNo a deja ete traite
521 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
522 while (cb >= 0 && cb < ptSh->numberOfEdges())
523 {
524 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
525 && nPt == ptSh->getEdge(cb).en)
526 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
527 && nPt == ptSh->getEdge(cb).st))
528 {
529 if (cb != dnNo)
530 {
531 SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
532 ptSh->swsData[cb].misc = node;
533 node->InsertAt (*sTree, *sEvts, this, insertionNode,
534 nPt, true);
535 if (doWinding)
536 {
537 SweepTree *myLeft =
538 static_cast < SweepTree * >(node->elem[LEFT]);
539 if (myLeft)
540 {
541 pData[lastPointNo].askForWindingS =
542 myLeft->src;
543 pData[lastPointNo].askForWindingB =
544 myLeft->bord;
545 }
546 else
547 {
548 pData[lastPointNo].askForWindingB = -1;
549 }
550 doWinding = false;
551 }
552 TesteIntersection (node, RIGHT, false);
553 TesteIntersection (node, LEFT, false);
555 ptSh->swsData[cb].curPoint = lastPointNo;
556 AddChgt (lastPointNo, lastChgtPt, shapeHead,
557 edgeHead, EDGE_INSERTED, node->src, node->bord, NULL,
558 -1);
559 }
560 }
561 cb = ptSh->NextAt (nPt, cb);
562 }
563 }
564 }
565 }
566 {
567 int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
570 Shape *curSh = shapeHead;
571 int curBo = edgeHead;
572 while (curSh)
573 {
574 curSh->swsData[curBo].leftRnd =
575 pData[curSh->swsData[curBo].leftRnd].newInd;
576 curSh->swsData[curBo].rightRnd =
577 pData[curSh->swsData[curBo].rightRnd].newInd;
579 Shape *neSh = curSh->swsData[curBo].nextSh;
580 curBo = curSh->swsData[curBo].nextBo;
581 curSh = neSh;
582 }
584 for (unsigned int i = 0; i < chgts.size(); i++)
585 {
586 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
587 if (chgts[i].type == 0)
588 {
589 if (chgts[i].src->getEdge(chgts[i].bord).st <
590 chgts[i].src->getEdge(chgts[i].bord).en)
591 {
592 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
593 }
594 else
595 {
596 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
597 }
598 }
599 else if (chgts[i].type == 1)
600 {
601 if (chgts[i].src->getEdge(chgts[i].bord).st >
602 chgts[i].src->getEdge(chgts[i].bord).en)
603 {
604 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
605 }
606 else
607 {
608 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
609 }
610 }
611 }
613 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
615 CheckEdges (lastI, lastChgtPt, a, NULL, bool_op_union);
617 for (int i = lastChgtPt; i < lastI; i++)
618 {
619 if (pData[i].askForWindingS)
620 {
621 Shape *windS = pData[i].askForWindingS;
622 int windB = pData[i].askForWindingB;
623 pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
624 windS->swsData[windB].firstLinkedPoint = i;
625 }
626 }
628 _pts.resize(lastI);
630 edgeHead = -1;
631 shapeHead = NULL;
632 }
634 chgts.clear();
636 // Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
637 // Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
639 // AssemblePoints(a);
641 // GetAdjacencies(a);
643 // MakeAretes(a);
644 clearIncidenceData();
646 AssembleAretes (directed);
648 // Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
650 for (int i = 0; i < numberOfPoints(); i++)
651 {
652 _pts[i].oldDegree = getPoint(i).totalDegree();
653 }
654 // Validate();
656 _need_edges_sorting = true;
657 if ( directed == fill_justDont ) {
658 SortEdges();
659 } else {
660 GetWindings (a);
661 }
662 // Plot (98.0, 112.0, 8.0, 400.0, 400.0, true, true, true, true);
663 // if ( doDebug ) {
664 // a->CalcBBox();
665 // a->Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"orig.svg");
666 // Plot(a->leftX,a->topY,32.0,0.0,0.0,true,true,true,true,"winded.svg");
667 // }
668 if (directed == fill_positive)
669 {
670 if (invert)
671 {
672 for (int i = 0; i < numberOfEdges(); i++)
673 {
674 if (swdData[i].leW < 0 && swdData[i].riW >= 0)
675 {
676 eData[i].weight = 1;
677 }
678 else if (swdData[i].leW >= 0 && swdData[i].riW < 0)
679 {
680 Inverse (i);
681 eData[i].weight = 1;
682 }
683 else
684 {
685 eData[i].weight = 0;
686 SubEdge (i);
687 i--;
688 }
689 }
690 }
691 else
692 {
693 for (int i = 0; i < numberOfEdges(); i++)
694 {
695 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
696 {
697 eData[i].weight = 1;
698 }
699 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
700 {
701 Inverse (i);
702 eData[i].weight = 1;
703 }
704 else
705 {
706 eData[i].weight = 0;
707 SubEdge (i);
708 i--;
709 }
710 }
711 }
712 }
713 else if (directed == fill_nonZero)
714 {
715 if (invert)
716 {
717 for (int i = 0; i < numberOfEdges(); i++)
718 {
719 if (swdData[i].leW < 0 && swdData[i].riW == 0)
720 {
721 eData[i].weight = 1;
722 }
723 else if (swdData[i].leW > 0 && swdData[i].riW == 0)
724 {
725 eData[i].weight = 1;
726 }
727 else if (swdData[i].leW == 0 && swdData[i].riW < 0)
728 {
729 Inverse (i);
730 eData[i].weight = 1;
731 }
732 else if (swdData[i].leW == 0 && swdData[i].riW > 0)
733 {
734 Inverse (i);
735 eData[i].weight = 1;
736 }
737 else
738 {
739 eData[i].weight = 0;
740 SubEdge (i);
741 i--;
742 }
743 }
744 }
745 else
746 {
747 for (int i = 0; i < numberOfEdges(); i++)
748 {
749 if (swdData[i].leW > 0 && swdData[i].riW == 0)
750 {
751 eData[i].weight = 1;
752 }
753 else if (swdData[i].leW < 0 && swdData[i].riW == 0)
754 {
755 eData[i].weight = 1;
756 }
757 else if (swdData[i].leW == 0 && swdData[i].riW > 0)
758 {
759 Inverse (i);
760 eData[i].weight = 1;
761 }
762 else if (swdData[i].leW == 0 && swdData[i].riW < 0)
763 {
764 Inverse (i);
765 eData[i].weight = 1;
766 }
767 else
768 {
769 eData[i].weight = 0;
770 SubEdge (i);
771 i--;
772 }
773 }
774 }
775 }
776 else if (directed == fill_oddEven)
777 {
778 for (int i = 0; i < numberOfEdges(); i++)
779 {
780 swdData[i].leW %= 2;
781 swdData[i].riW %= 2;
782 if (swdData[i].leW < 0)
783 swdData[i].leW = -swdData[i].leW;
784 if (swdData[i].riW < 0)
785 swdData[i].riW = -swdData[i].riW;
786 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
787 {
788 eData[i].weight = 1;
789 }
790 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
791 {
792 Inverse (i);
793 eData[i].weight = 1;
794 }
795 else
796 {
797 eData[i].weight = 0;
798 SubEdge (i);
799 i--;
800 }
801 }
802 } else if ( directed == fill_justDont ) {
803 for (int i=0;i<numberOfEdges();i++) {
804 if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
805 SubEdge(i);
806 i--;
807 } else {
808 eData[i].weight = 0;
809 }
810 }
811 }
813 // Plot(200.0,200.0,2.0,400.0,400.0,true,true,true,true);
815 delete sTree;
816 sTree = NULL;
817 delete sEvts;
818 sEvts = NULL;
820 if ( directed == fill_justDont ) {
821 } else {
822 if (directedEulerian(this) == false)
823 {
824 // Validate();
825 // printf( "pas euclidian2");
826 MakePointData (false);
827 MakeEdgeData (false);
828 MakeSweepSrcData (false);
829 MakeSweepDestData (false);
830 a->CleanupSweep ();
831 _pts.clear();
832 _aretes.clear();
833 return shape_euler_err;
834 }
835 }
836 MakePointData (false);
837 MakeEdgeData (false);
838 MakeSweepSrcData (false);
839 MakeSweepDestData (false);
840 a->CleanupSweep ();
841 type = shape_polygon;
842 return 0;
843 }
845 // technically it's just a ConvertToShape() on 2 polygons at the same time, and different rules
846 // for choosing the edges according to their winding numbers.
847 // probably one of the biggest function i ever wrote.
848 int
849 Shape::Booleen (Shape * a, Shape * b, BooleanOp mod,int cutPathID)
850 {
851 if (a == b || a == NULL || b == NULL)
852 return shape_input_err;
853 Reset (0, 0);
854 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
855 return 0;
856 if (b->numberOfPoints() <= 1 || b->numberOfEdges() <= 1)
857 return 0;
858 if ( mod == bool_op_cut ) {
859 } else if ( mod == bool_op_slice ) {
860 } else {
861 if (a->type != shape_polygon)
862 return shape_input_err;
863 if (b->type != shape_polygon)
864 return shape_input_err;
865 }
867 a->ResetSweep ();
868 b->ResetSweep ();
870 if (sTree == NULL) {
871 sTree = new SweepTreeList(a->numberOfEdges() + b->numberOfEdges());
872 }
873 if (sEvts == NULL) {
874 sEvts = new SweepEventQueue(a->numberOfEdges() + b->numberOfEdges());
875 }
877 MakePointData (true);
878 MakeEdgeData (true);
879 MakeSweepSrcData (true);
880 MakeSweepDestData (true);
881 if (a->hasBackData () && b->hasBackData ())
882 {
883 MakeBackData (true);
884 }
885 else
886 {
887 MakeBackData (false);
888 }
890 a->initialisePointData();
891 b->initialisePointData();
893 a->initialiseEdgeData();
894 b->initialiseEdgeData();
896 a->SortPointsRounded ();
897 b->SortPointsRounded ();
899 chgts.clear();
901 double lastChange =
902 (a->pData[0].rx[1] <
903 b->pData[0].rx[1]) ? a->pData[0].rx[1] - 1.0 : b->pData[0].rx[1] - 1.0;
904 int lastChgtPt = 0;
905 int edgeHead = -1;
906 Shape *shapeHead = NULL;
908 clearIncidenceData();
910 int curAPt = 0;
911 int curBPt = 0;
913 while (curAPt < a->numberOfPoints() || curBPt < b->numberOfPoints() || sEvts->size() > 0)
914 {
915 /* for (int i=0;i<sEvts.nbEvt;i++) {
916 printf("%f %f %i %i\n",sEvts.events[i].posx,sEvts.events[i].posy,sEvts.events[i].leftSweep->bord,sEvts.events[i].rightSweep->bord); // localizing ok
917 }
918 // cout << endl;
919 if ( sTree.racine ) {
920 SweepTree* ct=static_cast <SweepTree*> (sTree.racine->Leftmost());
921 while ( ct ) {
922 printf("%i %i [%i\n",ct->bord,ct->startPoint,(ct->src==a)?1:0);
923 ct=static_cast <SweepTree*> (ct->elem[RIGHT]);
924 }
925 }
926 printf("\n");*/
928 NR::Point ptX;
929 double ptL, ptR;
930 SweepTree *intersL = NULL;
931 SweepTree *intersR = NULL;
932 int nPt = -1;
933 Shape *ptSh = NULL;
934 bool isIntersection = false;
936 if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
937 {
938 if (curAPt < a->numberOfPoints())
939 {
940 if (curBPt < b->numberOfPoints())
941 {
942 if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
943 || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
944 && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
945 {
946 if (a->pData[curAPt].pending > 0
947 || (a->pData[curAPt].rx[1] > ptX[1]
948 || (a->pData[curAPt].rx[1] == ptX[1]
949 && a->pData[curAPt].rx[0] > ptX[0])))
950 {
951 /* FIXME: could be pop? */
952 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
953 isIntersection = true;
954 }
955 else
956 {
957 nPt = curAPt++;
958 ptSh = a;
959 ptX = ptSh->pData[nPt].rx;
960 isIntersection = false;
961 }
962 }
963 else
964 {
965 if (b->pData[curBPt].pending > 0
966 || (b->pData[curBPt].rx[1] > ptX[1]
967 || (b->pData[curBPt].rx[1] == ptX[1]
968 && b->pData[curBPt].rx[0] > ptX[0])))
969 {
970 /* FIXME: could be pop? */
971 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
972 isIntersection = true;
973 }
974 else
975 {
976 nPt = curBPt++;
977 ptSh = b;
978 ptX = ptSh->pData[nPt].rx;
979 isIntersection = false;
980 }
981 }
982 }
983 else
984 {
985 if (a->pData[curAPt].pending > 0
986 || (a->pData[curAPt].rx[1] > ptX[1]
987 || (a->pData[curAPt].rx[1] == ptX[1]
988 && a->pData[curAPt].rx[0] > ptX[0])))
989 {
990 /* FIXME: could be pop? */
991 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
992 isIntersection = true;
993 }
994 else
995 {
996 nPt = curAPt++;
997 ptSh = a;
998 ptX = ptSh->pData[nPt].rx;
999 isIntersection = false;
1000 }
1001 }
1002 }
1003 else
1004 {
1005 if (b->pData[curBPt].pending > 0
1006 || (b->pData[curBPt].rx[1] > ptX[1]
1007 || (b->pData[curBPt].rx[1] == ptX[1]
1008 && b->pData[curBPt].rx[0] > ptX[0])))
1009 {
1010 /* FIXME: could be pop? */
1011 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
1012 isIntersection = true;
1013 }
1014 else
1015 {
1016 nPt = curBPt++;
1017 ptSh = b;
1018 ptX = ptSh->pData[nPt].rx;
1019 isIntersection = false;
1020 }
1021 }
1022 }
1023 else
1024 {
1025 if (curAPt < a->numberOfPoints())
1026 {
1027 if (curBPt < b->numberOfPoints())
1028 {
1029 if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
1030 || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
1031 && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
1032 {
1033 nPt = curAPt++;
1034 ptSh = a;
1035 }
1036 else
1037 {
1038 nPt = curBPt++;
1039 ptSh = b;
1040 }
1041 }
1042 else
1043 {
1044 nPt = curAPt++;
1045 ptSh = a;
1046 }
1047 }
1048 else
1049 {
1050 nPt = curBPt++;
1051 ptSh = b;
1052 }
1053 ptX = ptSh->pData[nPt].rx;
1054 isIntersection = false;
1055 }
1057 if (isIntersection == false)
1058 {
1059 if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
1060 continue;
1061 }
1063 NR::Point rPtX;
1064 rPtX[0]= Round (ptX[0]);
1065 rPtX[1]= Round (ptX[1]);
1066 int lastPointNo = -1;
1067 lastPointNo = AddPoint (rPtX);
1068 pData[lastPointNo].rx = rPtX;
1070 if (rPtX[1] > lastChange)
1071 {
1072 int lastI = AssemblePoints (lastChgtPt, lastPointNo);
1075 Shape *curSh = shapeHead;
1076 int curBo = edgeHead;
1077 while (curSh)
1078 {
1079 curSh->swsData[curBo].leftRnd =
1080 pData[curSh->swsData[curBo].leftRnd].newInd;
1081 curSh->swsData[curBo].rightRnd =
1082 pData[curSh->swsData[curBo].rightRnd].newInd;
1084 Shape *neSh = curSh->swsData[curBo].nextSh;
1085 curBo = curSh->swsData[curBo].nextBo;
1086 curSh = neSh;
1087 }
1089 for (unsigned int i = 0; i < chgts.size(); i++)
1090 {
1091 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
1092 if (chgts[i].type == 0)
1093 {
1094 if (chgts[i].src->getEdge(chgts[i].bord).st <
1095 chgts[i].src->getEdge(chgts[i].bord).en)
1096 {
1097 chgts[i].src->swsData[chgts[i].bord].stPt =
1098 chgts[i].ptNo;
1099 }
1100 else
1101 {
1102 chgts[i].src->swsData[chgts[i].bord].enPt =
1103 chgts[i].ptNo;
1104 }
1105 }
1106 else if (chgts[i].type == 1)
1107 {
1108 if (chgts[i].src->getEdge(chgts[i].bord).st >
1109 chgts[i].src->getEdge(chgts[i].bord).en)
1110 {
1111 chgts[i].src->swsData[chgts[i].bord].stPt =
1112 chgts[i].ptNo;
1113 }
1114 else
1115 {
1116 chgts[i].src->swsData[chgts[i].bord].enPt =
1117 chgts[i].ptNo;
1118 }
1119 }
1120 }
1122 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
1124 CheckEdges (lastI, lastChgtPt, a, b, mod);
1126 for (int i = lastChgtPt; i < lastI; i++)
1127 {
1128 if (pData[i].askForWindingS)
1129 {
1130 Shape *windS = pData[i].askForWindingS;
1131 int windB = pData[i].askForWindingB;
1132 pData[i].nextLinkedPoint =
1133 windS->swsData[windB].firstLinkedPoint;
1134 windS->swsData[windB].firstLinkedPoint = i;
1135 }
1136 }
1138 if (lastI < lastPointNo)
1139 {
1140 _pts[lastI] = getPoint(lastPointNo);
1141 pData[lastI] = pData[lastPointNo];
1142 }
1143 lastPointNo = lastI;
1144 _pts.resize(lastI + 1);
1146 lastChgtPt = lastPointNo;
1147 lastChange = rPtX[1];
1148 chgts.clear();
1149 edgeHead = -1;
1150 shapeHead = NULL;
1151 }
1154 if (isIntersection)
1155 {
1156 // les 2 events de part et d'autre de l'intersection
1157 // (celui de l'intersection a deja ete depile)
1158 intersL->RemoveEvent (*sEvts, LEFT);
1159 intersR->RemoveEvent (*sEvts, RIGHT);
1161 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
1162 intersL->src, intersL->bord, intersR->src, intersR->bord);
1164 intersL->SwapWithRight (*sTree, *sEvts);
1166 TesteIntersection (intersL, LEFT, true);
1167 TesteIntersection (intersR, RIGHT, true);
1168 }
1169 else
1170 {
1171 int cb;
1173 int nbUp = 0, nbDn = 0;
1174 int upNo = -1, dnNo = -1;
1175 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1176 while (cb >= 0 && cb < ptSh->numberOfEdges())
1177 {
1178 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1179 && nPt == ptSh->getEdge(cb).en)
1180 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1181 && nPt == ptSh->getEdge(cb).st))
1182 {
1183 upNo = cb;
1184 nbUp++;
1185 }
1186 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1187 && nPt == ptSh->getEdge(cb).en)
1188 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1189 && nPt == ptSh->getEdge(cb).st))
1190 {
1191 dnNo = cb;
1192 nbDn++;
1193 }
1194 cb = ptSh->NextAt (nPt, cb);
1195 }
1197 if (nbDn <= 0)
1198 {
1199 upNo = -1;
1200 }
1201 if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == NULL)
1202 {
1203 upNo = -1;
1204 }
1206 // upNo=-1;
1208 bool doWinding = true;
1210 if (nbUp > 0)
1211 {
1212 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1213 while (cb >= 0 && cb < ptSh->numberOfEdges())
1214 {
1215 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1216 && nPt == ptSh->getEdge(cb).en)
1217 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1218 && nPt == ptSh->getEdge(cb).st))
1219 {
1220 if (cb != upNo)
1221 {
1222 SweepTree *node =
1223 (SweepTree *) ptSh->swsData[cb].misc;
1224 if (node == NULL)
1225 {
1226 }
1227 else
1228 {
1229 AddChgt (lastPointNo, lastChgtPt, shapeHead,
1230 edgeHead, EDGE_REMOVED, node->src, node->bord,
1231 NULL, -1);
1232 ptSh->swsData[cb].misc = NULL;
1234 int onLeftB = -1, onRightB = -1;
1235 Shape *onLeftS = NULL;
1236 Shape *onRightS = NULL;
1237 if (node->elem[LEFT])
1238 {
1239 onLeftB =
1240 (static_cast <
1241 SweepTree * >(node->elem[LEFT]))->bord;
1242 onLeftS =
1243 (static_cast <
1244 SweepTree * >(node->elem[LEFT]))->src;
1245 }
1246 if (node->elem[RIGHT])
1247 {
1248 onRightB =
1249 (static_cast <
1250 SweepTree * >(node->elem[RIGHT]))->bord;
1251 onRightS =
1252 (static_cast <
1253 SweepTree * >(node->elem[RIGHT]))->src;
1254 }
1256 node->Remove (*sTree, *sEvts, true);
1257 if (onLeftS && onRightS)
1258 {
1259 SweepTree *onLeft =
1260 (SweepTree *) onLeftS->swsData[onLeftB].
1261 misc;
1262 // SweepTree* onRight=(SweepTree*)onRightS->swsData[onRightB].misc;
1263 if (onLeftS == ptSh
1264 && (onLeftS->getEdge(onLeftB).en == nPt
1265 || onLeftS->getEdge(onLeftB).st ==
1266 nPt))
1267 {
1268 }
1269 else
1270 {
1271 if (onRightS == ptSh
1272 && (onRightS->getEdge(onRightB).en ==
1273 nPt
1274 || onRightS->getEdge(onRightB).
1275 st == nPt))
1276 {
1277 }
1278 else
1279 {
1280 TesteIntersection (onLeft, RIGHT, true);
1281 }
1282 }
1283 }
1284 }
1285 }
1286 }
1287 cb = ptSh->NextAt (nPt, cb);
1288 }
1289 }
1291 // traitement du "upNo devient dnNo"
1292 SweepTree *insertionNode = NULL;
1293 if (dnNo >= 0)
1294 {
1295 if (upNo >= 0)
1296 {
1297 SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
1299 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
1300 node->src, node->bord, NULL, -1);
1302 ptSh->swsData[upNo].misc = NULL;
1304 node->RemoveEvents (*sEvts);
1305 node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
1306 ptSh->swsData[dnNo].misc = node;
1307 TesteIntersection (node, RIGHT, true);
1308 TesteIntersection (node, LEFT, true);
1309 insertionNode = node;
1311 ptSh->swsData[dnNo].curPoint = lastPointNo;
1313 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
1314 node->src, node->bord, NULL, -1);
1315 }
1316 else
1317 {
1318 SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
1319 ptSh->swsData[dnNo].misc = node;
1320 node->Insert (*sTree, *sEvts, this, lastPointNo, true);
1322 if (doWinding)
1323 {
1324 SweepTree *myLeft =
1325 static_cast < SweepTree * >(node->elem[LEFT]);
1326 if (myLeft)
1327 {
1328 pData[lastPointNo].askForWindingS = myLeft->src;
1329 pData[lastPointNo].askForWindingB = myLeft->bord;
1330 }
1331 else
1332 {
1333 pData[lastPointNo].askForWindingB = -1;
1334 }
1335 doWinding = false;
1336 }
1338 TesteIntersection (node, RIGHT, true);
1339 TesteIntersection (node, LEFT, true);
1340 insertionNode = node;
1342 ptSh->swsData[dnNo].curPoint = lastPointNo;
1344 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
1345 node->src, node->bord, NULL, -1);
1346 }
1347 }
1349 if (nbDn > 1)
1350 { // si nbDn == 1 , alors dnNo a deja ete traite
1351 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1352 while (cb >= 0 && cb < ptSh->numberOfEdges())
1353 {
1354 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1355 && nPt == ptSh->getEdge(cb).en)
1356 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1357 && nPt == ptSh->getEdge(cb).st))
1358 {
1359 if (cb != dnNo)
1360 {
1361 SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
1362 ptSh->swsData[cb].misc = node;
1363 // node->Insert(sTree,*sEvts,this,lastPointNo,true);
1364 node->InsertAt (*sTree, *sEvts, this, insertionNode,
1365 nPt, true);
1367 if (doWinding)
1368 {
1369 SweepTree *myLeft =
1370 static_cast < SweepTree * >(node->elem[LEFT]);
1371 if (myLeft)
1372 {
1373 pData[lastPointNo].askForWindingS =
1374 myLeft->src;
1375 pData[lastPointNo].askForWindingB =
1376 myLeft->bord;
1377 }
1378 else
1379 {
1380 pData[lastPointNo].askForWindingB = -1;
1381 }
1382 doWinding = false;
1383 }
1385 TesteIntersection (node, RIGHT, true);
1386 TesteIntersection (node, LEFT, true);
1388 ptSh->swsData[cb].curPoint = lastPointNo;
1390 AddChgt (lastPointNo, lastChgtPt, shapeHead,
1391 edgeHead, EDGE_INSERTED, node->src, node->bord, NULL,
1392 -1);
1393 }
1394 }
1395 cb = ptSh->NextAt (nPt, cb);
1396 }
1397 }
1398 }
1399 }
1400 {
1401 int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
1404 Shape *curSh = shapeHead;
1405 int curBo = edgeHead;
1406 while (curSh)
1407 {
1408 curSh->swsData[curBo].leftRnd =
1409 pData[curSh->swsData[curBo].leftRnd].newInd;
1410 curSh->swsData[curBo].rightRnd =
1411 pData[curSh->swsData[curBo].rightRnd].newInd;
1413 Shape *neSh = curSh->swsData[curBo].nextSh;
1414 curBo = curSh->swsData[curBo].nextBo;
1415 curSh = neSh;
1416 }
1418 /* FIXME: this kind of code seems to appear frequently */
1419 for (unsigned int i = 0; i < chgts.size(); i++)
1420 {
1421 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
1422 if (chgts[i].type == 0)
1423 {
1424 if (chgts[i].src->getEdge(chgts[i].bord).st <
1425 chgts[i].src->getEdge(chgts[i].bord).en)
1426 {
1427 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
1428 }
1429 else
1430 {
1431 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
1432 }
1433 }
1434 else if (chgts[i].type == 1)
1435 {
1436 if (chgts[i].src->getEdge(chgts[i].bord).st >
1437 chgts[i].src->getEdge(chgts[i].bord).en)
1438 {
1439 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
1440 }
1441 else
1442 {
1443 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
1444 }
1445 }
1446 }
1448 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
1450 CheckEdges (lastI, lastChgtPt, a, b, mod);
1452 for (int i = lastChgtPt; i < lastI; i++)
1453 {
1454 if (pData[i].askForWindingS)
1455 {
1456 Shape *windS = pData[i].askForWindingS;
1457 int windB = pData[i].askForWindingB;
1458 pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
1459 windS->swsData[windB].firstLinkedPoint = i;
1460 }
1461 }
1463 _pts.resize(lastI);
1465 edgeHead = -1;
1466 shapeHead = NULL;
1467 }
1469 chgts.clear();
1470 clearIncidenceData();
1472 // Plot(190,70,6,400,400,true,false,true,true);
1474 if ( mod == bool_op_cut ) {
1475 AssembleAretes (fill_justDont);
1476 // dupliquer les aretes de la coupure
1477 int i=numberOfEdges()-1;
1478 for (;i>=0;i--) {
1479 if ( ebData[i].pathID == cutPathID ) {
1480 // on duplique
1481 int nEd=AddEdge(getEdge(i).en,getEdge(i).st);
1482 ebData[nEd].pathID=cutPathID;
1483 ebData[nEd].pieceID=ebData[i].pieceID;
1484 ebData[nEd].tSt=ebData[i].tEn;
1485 ebData[nEd].tEn=ebData[i].tSt;
1486 eData[nEd].weight=eData[i].weight;
1487 // lui donner les firstlinkedpoitn si besoin
1488 if ( getEdge(i).en >= getEdge(i).st ) {
1489 int cp = swsData[i].firstLinkedPoint;
1490 while (cp >= 0) {
1491 pData[cp].askForWindingB = nEd;
1492 cp = pData[cp].nextLinkedPoint;
1493 }
1494 swsData[nEd].firstLinkedPoint = swsData[i].firstLinkedPoint;
1495 swsData[i].firstLinkedPoint=-1;
1496 }
1497 }
1498 }
1499 } else if ( mod == bool_op_slice ) {
1500 } else {
1501 AssembleAretes ();
1502 }
1504 for (int i = 0; i < numberOfPoints(); i++)
1505 {
1506 _pts[i].oldDegree = getPoint(i).totalDegree();
1507 }
1509 _need_edges_sorting = true;
1510 if ( mod == bool_op_slice ) {
1511 } else {
1512 GetWindings (a, b, mod, false);
1513 }
1514 // Plot(190,70,6,400,400,true,true,true,true);
1516 if (mod == bool_op_symdiff)
1517 {
1518 for (int i = 0; i < numberOfEdges(); i++)
1519 {
1520 swdData[i].leW = swdData[i].leW % 2;
1521 if (swdData[i].leW < 0)
1522 swdData[i].leW = -swdData[i].leW;
1523 swdData[i].riW = swdData[i].riW;
1524 if (swdData[i].riW < 0)
1525 swdData[i].riW = -swdData[i].riW;
1527 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1528 {
1529 eData[i].weight = 1;
1530 }
1531 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1532 {
1533 Inverse (i);
1534 eData[i].weight = 1;
1535 }
1536 else
1537 {
1538 eData[i].weight = 0;
1539 SubEdge (i);
1540 i--;
1541 }
1542 }
1543 }
1544 else if (mod == bool_op_union || mod == bool_op_diff)
1545 {
1546 for (int i = 0; i < numberOfEdges(); i++)
1547 {
1548 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1549 {
1550 eData[i].weight = 1;
1551 }
1552 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1553 {
1554 Inverse (i);
1555 eData[i].weight = 1;
1556 }
1557 else
1558 {
1559 eData[i].weight = 0;
1560 SubEdge (i);
1561 i--;
1562 }
1563 }
1564 }
1565 else if (mod == bool_op_inters)
1566 {
1567 for (int i = 0; i < numberOfEdges(); i++)
1568 {
1569 if (swdData[i].leW > 1 && swdData[i].riW <= 1)
1570 {
1571 eData[i].weight = 1;
1572 }
1573 else if (swdData[i].leW <= 1 && swdData[i].riW > 1)
1574 {
1575 Inverse (i);
1576 eData[i].weight = 1;
1577 }
1578 else
1579 {
1580 eData[i].weight = 0;
1581 SubEdge (i);
1582 i--;
1583 }
1584 }
1585 } else if ( mod == bool_op_cut ) {
1586 // inverser les aretes de la coupe au besoin
1587 for (int i=0;i<numberOfEdges();i++) {
1588 if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
1589 if ( i < numberOfEdges()-1 ) {
1590 // decaler les askForWinding
1591 int cp = swsData[numberOfEdges()-1].firstLinkedPoint;
1592 while (cp >= 0) {
1593 pData[cp].askForWindingB = i;
1594 cp = pData[cp].nextLinkedPoint;
1595 }
1596 }
1597 SwapEdges(i,numberOfEdges()-1);
1598 SubEdge(numberOfEdges()-1);
1599 // SubEdge(i);
1600 i--;
1601 } else if ( ebData[i].pathID == cutPathID ) {
1602 swdData[i].leW=swdData[i].leW%2;
1603 swdData[i].riW=swdData[i].riW%2;
1604 if ( swdData[i].leW < swdData[i].riW ) {
1605 Inverse(i);
1606 }
1607 }
1608 }
1609 } else if ( mod == bool_op_slice ) {
1610 // supprimer les aretes de la coupe
1611 int i=numberOfEdges()-1;
1612 for (;i>=0;i--) {
1613 if ( ebData[i].pathID == cutPathID || getEdge(i).st < 0 || getEdge(i).en < 0 ) {
1614 SubEdge(i);
1615 }
1616 }
1617 }
1618 else
1619 {
1620 for (int i = 0; i < numberOfEdges(); i++)
1621 {
1622 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1623 {
1624 eData[i].weight = 1;
1625 }
1626 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1627 {
1628 Inverse (i);
1629 eData[i].weight = 1;
1630 }
1631 else
1632 {
1633 eData[i].weight = 0;
1634 SubEdge (i);
1635 i--;
1636 }
1637 }
1638 }
1640 delete sTree;
1641 sTree = NULL;
1642 delete sEvts;
1643 sEvts = NULL;
1645 if ( mod == bool_op_cut ) {
1646 // on garde le askForWinding
1647 } else {
1648 MakePointData (false);
1649 }
1650 MakeEdgeData (false);
1651 MakeSweepSrcData (false);
1652 MakeSweepDestData (false);
1653 a->CleanupSweep ();
1654 b->CleanupSweep ();
1656 if (directedEulerian(this) == false)
1657 {
1658 // printf( "pas euclidian2");
1659 _pts.clear();
1660 _aretes.clear();
1661 return shape_euler_err;
1662 }
1663 type = shape_polygon;
1664 return 0;
1665 }
1667 // frontend to the TesteIntersection() below
1668 void Shape::TesteIntersection(SweepTree *t, Side s, bool onlyDiff)
1669 {
1670 SweepTree *tt = static_cast<SweepTree*>(t->elem[s]);
1671 if (tt == NULL) {
1672 return;
1673 }
1675 SweepTree *a = (s == LEFT) ? tt : t;
1676 SweepTree *b = (s == LEFT) ? t : tt;
1678 NR::Point atx;
1679 double atl;
1680 double atr;
1681 if (TesteIntersection(a, b, atx, atl, atr, onlyDiff)) {
1682 sEvts->add(a, b, atx, atl, atr);
1683 }
1684 }
1686 // a crucial piece of code: computing intersections between segments
1687 bool
1688 Shape::TesteIntersection (SweepTree * iL, SweepTree * iR, NR::Point &atx, double &atL, double &atR, bool onlyDiff)
1689 {
1690 int lSt = iL->src->getEdge(iL->bord).st, lEn = iL->src->getEdge(iL->bord).en;
1691 int rSt = iR->src->getEdge(iR->bord).st, rEn = iR->src->getEdge(iR->bord).en;
1692 NR::Point ldir, rdir;
1693 ldir = iL->src->eData[iL->bord].rdx;
1694 rdir = iR->src->eData[iR->bord].rdx;
1695 // first, a round of checks to quickly dismiss edge which obviously dont intersect,
1696 // such as having disjoint bounding boxes
1697 if (lSt < lEn)
1698 {
1699 }
1700 else
1701 {
1702 int swap = lSt;
1703 lSt = lEn;
1704 lEn = swap;
1705 ldir = -ldir;
1706 }
1707 if (rSt < rEn)
1708 {
1709 }
1710 else
1711 {
1712 int swap = rSt;
1713 rSt = rEn;
1714 rEn = swap;
1715 rdir = -rdir;
1716 }
1718 if (iL->src->pData[lSt].rx[0] < iL->src->pData[lEn].rx[0])
1719 {
1720 if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
1721 {
1722 if (iL->src->pData[lSt].rx[0] > iR->src->pData[rEn].rx[0])
1723 return false;
1724 if (iL->src->pData[lEn].rx[0] < iR->src->pData[rSt].rx[0])
1725 return false;
1726 }
1727 else
1728 {
1729 if (iL->src->pData[lSt].rx[0] > iR->src->pData[rSt].rx[0])
1730 return false;
1731 if (iL->src->pData[lEn].rx[0] < iR->src->pData[rEn].rx[0])
1732 return false;
1733 }
1734 }
1735 else
1736 {
1737 if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
1738 {
1739 if (iL->src->pData[lEn].rx[0] > iR->src->pData[rEn].rx[0])
1740 return false;
1741 if (iL->src->pData[lSt].rx[0] < iR->src->pData[rSt].rx[0])
1742 return false;
1743 }
1744 else
1745 {
1746 if (iL->src->pData[lEn].rx[0] > iR->src->pData[rSt].rx[0])
1747 return false;
1748 if (iL->src->pData[lSt].rx[0] < iR->src->pData[rEn].rx[0])
1749 return false;
1750 }
1751 }
1753 double ang = cross (rdir, ldir);
1754 // ang*=iL->src->eData[iL->bord].isqlength;
1755 // ang*=iR->src->eData[iR->bord].isqlength;
1756 if (ang <= 0) return false; // edges in opposite directions: <-left ... right ->
1757 // they can't intersect
1759 // d'abord tester les bords qui partent d'un meme point
1760 if (iL->src == iR->src && lSt == rSt)
1761 {
1762 if (iL->src == iR->src && lEn == rEn)
1763 return false; // c'est juste un doublon
1764 atx = iL->src->pData[lSt].rx;
1765 atR = atL = -1;
1766 return true; // l'ordre est mauvais
1767 }
1768 if (iL->src == iR->src && lEn == rEn)
1769 return false; // rien a faire=ils vont terminer au meme endroit
1771 // tester si on est dans une intersection multiple
1773 if (onlyDiff && iL->src == iR->src)
1774 return false;
1776 // on reprend les vrais points
1777 lSt = iL->src->getEdge(iL->bord).st;
1778 lEn = iL->src->getEdge(iL->bord).en;
1779 rSt = iR->src->getEdge(iR->bord).st;
1780 rEn = iR->src->getEdge(iR->bord).en;
1782 // compute intersection (if there is one)
1783 // Boissonat anr Preparata said in one paper that double precision floats were sufficient for get single precision
1784 // coordinates for the intersection, if the endpoints are single precision. i hope they're right...
1785 {
1786 NR::Point sDiff, eDiff;
1787 double slDot, elDot;
1788 double srDot, erDot;
1789 sDiff = iL->src->pData[lSt].rx - iR->src->pData[rSt].rx;
1790 eDiff = iL->src->pData[lEn].rx - iR->src->pData[rSt].rx;
1791 srDot = cross (sDiff,rdir);
1792 erDot = cross (eDiff,rdir);
1793 sDiff = iR->src->pData[rSt].rx - iL->src->pData[lSt].rx;
1794 eDiff = iR->src->pData[rEn].rx - iL->src->pData[lSt].rx;
1795 slDot = cross (sDiff,ldir);
1796 elDot = cross (eDiff,ldir);
1798 if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
1799 {
1800 if (srDot == 0)
1801 {
1802 if (lSt < lEn)
1803 {
1804 atx = iL->src->pData[lSt].rx;
1805 atL = 0;
1806 atR = slDot / (slDot - elDot);
1807 return true;
1808 }
1809 else
1810 {
1811 return false;
1812 }
1813 }
1814 else if (erDot == 0)
1815 {
1816 if (lSt > lEn)
1817 {
1818 atx = iL->src->pData[lEn].rx;
1819 atL = 1;
1820 atR = slDot / (slDot - elDot);
1821 return true;
1822 }
1823 else
1824 {
1825 return false;
1826 }
1827 }
1828 if (srDot > 0 && erDot > 0)
1829 {
1830 if (rEn < rSt)
1831 {
1832 if (srDot < erDot)
1833 {
1834 if (lSt < lEn)
1835 {
1836 atx = iL->src->pData[lSt].rx;
1837 atL = 0;
1838 atR = slDot / (slDot - elDot);
1839 return true;
1840 }
1841 }
1842 else
1843 {
1844 if (lEn < lSt)
1845 {
1846 atx = iL->src->pData[lEn].rx;
1847 atL = 1;
1848 atR = slDot / (slDot - elDot);
1849 return true;
1850 }
1851 }
1852 }
1853 }
1854 if (srDot < 0 && erDot < 0)
1855 {
1856 if (rEn > rSt)
1857 {
1858 if (srDot > erDot)
1859 {
1860 if (lSt < lEn)
1861 {
1862 atx = iL->src->pData[lSt].rx;
1863 atL = 0;
1864 atR = slDot / (slDot - elDot);
1865 return true;
1866 }
1867 }
1868 else
1869 {
1870 if (lEn < lSt)
1871 {
1872 atx = iL->src->pData[lEn].rx;
1873 atL = 1;
1874 atR = slDot / (slDot - elDot);
1875 return true;
1876 }
1877 }
1878 }
1879 }
1880 return false;
1881 }
1882 if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
1883 {
1884 if (slDot == 0)
1885 {
1886 if (rSt < rEn)
1887 {
1888 atx = iR->src->pData[rSt].rx;
1889 atR = 0;
1890 atL = srDot / (srDot - erDot);
1891 return true;
1892 }
1893 else
1894 {
1895 return false;
1896 }
1897 }
1898 else if (elDot == 0)
1899 {
1900 if (rSt > rEn)
1901 {
1902 atx = iR->src->pData[rEn].rx;
1903 atR = 1;
1904 atL = srDot / (srDot - erDot);
1905 return true;
1906 }
1907 else
1908 {
1909 return false;
1910 }
1911 }
1912 if (slDot > 0 && elDot > 0)
1913 {
1914 if (lEn > lSt)
1915 {
1916 if (slDot < elDot)
1917 {
1918 if (rSt < rEn)
1919 {
1920 atx = iR->src->pData[rSt].rx;
1921 atR = 0;
1922 atL = srDot / (srDot - erDot);
1923 return true;
1924 }
1925 }
1926 else
1927 {
1928 if (rEn < rSt)
1929 {
1930 atx = iR->src->pData[rEn].rx;
1931 atR = 1;
1932 atL = srDot / (srDot - erDot);
1933 return true;
1934 }
1935 }
1936 }
1937 }
1938 if (slDot < 0 && elDot < 0)
1939 {
1940 if (lEn < lSt)
1941 {
1942 if (slDot > elDot)
1943 {
1944 if (rSt < rEn)
1945 {
1946 atx = iR->src->pData[rSt].rx;
1947 atR = 0;
1948 atL = srDot / (srDot - erDot);
1949 return true;
1950 }
1951 }
1952 else
1953 {
1954 if (rEn < rSt)
1955 {
1956 atx = iR->src->pData[rEn].rx;
1957 atR = 1;
1958 atL = srDot / (srDot - erDot);
1959 return true;
1960 }
1961 }
1962 }
1963 }
1964 return false;
1965 }
1967 /* double slb=slDot-elDot,srb=srDot-erDot;
1968 if ( slb < 0 ) slb=-slb;
1969 if ( srb < 0 ) srb=-srb;*/
1970 if (iL->src->eData[iL->bord].siEd > iR->src->eData[iR->bord].siEd)
1971 {
1972 atx =
1973 (slDot * iR->src->pData[rEn].rx -
1974 elDot * iR->src->pData[rSt].rx) / (slDot - elDot);
1975 }
1976 else
1977 {
1978 atx =
1979 (srDot * iL->src->pData[lEn].rx -
1980 erDot * iL->src->pData[lSt].rx) / (srDot - erDot);
1981 }
1982 atL = srDot / (srDot - erDot);
1983 atR = slDot / (slDot - elDot);
1984 return true;
1985 }
1987 return true;
1988 }
1990 int
1991 Shape::PushIncidence (Shape * a, int cb, int pt, double theta)
1992 {
1993 if (theta < 0 || theta > 1)
1994 return -1;
1996 if (nbInc >= maxInc)
1997 {
1998 maxInc = 2 * nbInc + 1;
1999 iData =
2000 (incidenceData *) g_realloc(iData, maxInc * sizeof (incidenceData));
2001 }
2002 int n = nbInc++;
2003 iData[n].nextInc = a->swsData[cb].firstLinkedPoint;
2004 iData[n].pt = pt;
2005 iData[n].theta = theta;
2006 a->swsData[cb].firstLinkedPoint = n;
2007 return n;
2008 }
2010 int
2011 Shape::CreateIncidence (Shape * a, int no, int nPt)
2012 {
2013 NR::Point adir, diff;
2014 adir = a->eData[no].rdx;
2015 diff = getPoint(nPt).x - a->pData[a->getEdge(no).st].rx;
2016 double t = dot (diff, adir);
2017 t *= a->eData[no].ilength;
2018 return PushIncidence (a, no, nPt, t);
2019 }
2021 int
2022 Shape::Winding (int nPt) const
2023 {
2024 int askTo = pData[nPt].askForWindingB;
2025 if (askTo < 0 || askTo >= numberOfEdges())
2026 return 0;
2027 if (getEdge(askTo).st < getEdge(askTo).en)
2028 {
2029 return swdData[askTo].leW;
2030 }
2031 else
2032 {
2033 return swdData[askTo].riW;
2034 }
2035 return 0;
2036 }
2038 int
2039 Shape::Winding (const NR::Point px) const
2040 {
2041 int lr = 0, ll = 0, rr = 0;
2043 for (int i = 0; i < numberOfEdges(); i++)
2044 {
2045 NR::Point adir, diff, ast, aen;
2046 adir = eData[i].rdx;
2048 ast = pData[getEdge(i).st].rx;
2049 aen = pData[getEdge(i).en].rx;
2051 int nWeight = eData[i].weight;
2053 if (ast[0] < aen[0])
2054 {
2055 if (ast[0] > px[0])
2056 continue;
2057 if (aen[0] < px[0])
2058 continue;
2059 }
2060 else
2061 {
2062 if (ast[0] < px[0])
2063 continue;
2064 if (aen[0] > px[0])
2065 continue;
2066 }
2067 if (ast[0] == px[0])
2068 {
2069 if (ast[1] >= px[1])
2070 continue;
2071 if (aen[0] == px[0])
2072 continue;
2073 if (aen[0] < px[0])
2074 ll += nWeight;
2075 else
2076 rr -= nWeight;
2077 continue;
2078 }
2079 if (aen[0] == px[0])
2080 {
2081 if (aen[1] >= px[1])
2082 continue;
2083 if (ast[0] == px[0])
2084 continue;
2085 if (ast[0] < px[0])
2086 ll -= nWeight;
2087 else
2088 rr += nWeight;
2089 continue;
2090 }
2092 if (ast[1] < aen[1])
2093 {
2094 if (ast[1] >= px[1])
2095 continue;
2096 }
2097 else
2098 {
2099 if (aen[1] >= px[1])
2100 continue;
2101 }
2103 diff = px - ast;
2104 double cote = cross (diff,adir);
2105 if (cote == 0)
2106 continue;
2107 if (cote < 0)
2108 {
2109 if (ast[0] > px[0])
2110 lr += nWeight;
2111 }
2112 else
2113 {
2114 if (ast[0] < px[0])
2115 lr -= nWeight;
2116 }
2117 }
2118 return lr + (ll + rr) / 2;
2119 }
2121 // merging duplicate points and edges
2122 int
2123 Shape::AssemblePoints (int st, int en)
2124 {
2125 if (en > st) {
2126 for (int i = st; i < en; i++) pData[i].oldInd = i;
2127 // SortPoints(st,en-1);
2128 SortPointsByOldInd (st, en - 1); // SortPointsByOldInd() is required here, because of the edges we have
2129 // associated with the point for later computation of winding numbers.
2130 // specifically, we need the first point we treated, it's the only one with a valid
2131 // associated edge (man, that was a nice bug).
2132 for (int i = st; i < en; i++) pData[pData[i].oldInd].newInd = i;
2134 int lastI = st;
2135 for (int i = st; i < en; i++) {
2136 pData[i].pending = lastI++;
2137 if (i > st && getPoint(i - 1).x[0] == getPoint(i).x[0] && getPoint(i - 1).x[1] == getPoint(i).x[1]) {
2138 pData[i].pending = pData[i - 1].pending;
2139 if (pData[pData[i].pending].askForWindingS == NULL) {
2140 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
2141 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
2142 } else {
2143 if (pData[pData[i].pending].askForWindingS == pData[i].askForWindingS
2144 && pData[pData[i].pending].askForWindingB == pData[i].askForWindingB) {
2145 // meme bord, c bon
2146 } else {
2147 // meme point, mais pas le meme bord: ouille!
2148 // il faut prendre le bord le plus a gauche
2149 // en pratique, n'arrive que si 2 maxima sont dans la meme case -> le mauvais choix prend une arete incidente
2150 // au bon choix
2151 // printf("doh");
2152 }
2153 }
2154 lastI--;
2155 } else {
2156 if (i > pData[i].pending) {
2157 _pts[pData[i].pending].x = getPoint(i).x;
2158 pData[pData[i].pending].rx = getPoint(i).x;
2159 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
2160 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
2161 }
2162 }
2163 }
2164 for (int i = st; i < en; i++) pData[i].newInd = pData[pData[i].newInd].pending;
2165 return lastI;
2166 }
2167 return en;
2168 }
2170 void
2171 Shape::AssemblePoints (Shape * a)
2172 {
2173 if (hasPoints())
2174 {
2175 int lastI = AssemblePoints (0, numberOfPoints());
2177 for (int i = 0; i < a->numberOfEdges(); i++)
2178 {
2179 a->swsData[i].stPt = pData[a->swsData[i].stPt].newInd;
2180 a->swsData[i].enPt = pData[a->swsData[i].enPt].newInd;
2181 }
2182 for (int i = 0; i < nbInc; i++)
2183 iData[i].pt = pData[iData[i].pt].newInd;
2185 _pts.resize(lastI);
2186 }
2187 }
2188 void
2189 Shape::AssembleAretes (FillRule directed)
2190 {
2191 if ( directed == fill_justDont && _has_back_data == false ) {
2192 directed=fill_nonZero;
2193 }
2195 for (int i = 0; i < numberOfPoints(); i++) {
2196 if (getPoint(i).totalDegree() == 2) {
2197 int cb, cc;
2198 cb = getPoint(i).incidentEdge[FIRST];
2199 cc = getPoint(i).incidentEdge[LAST];
2200 bool doublon=false;
2201 if ((getEdge(cb).st == getEdge(cc).st && getEdge(cb).en == getEdge(cc).en)
2202 || (getEdge(cb).st == getEdge(cc).en && getEdge(cb).en == getEdge(cc).en)) doublon=true;
2203 if ( directed == fill_justDont ) {
2204 if ( doublon ) {
2205 if ( ebData[cb].pathID > ebData[cc].pathID ) {
2206 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2207 cb = getPoint(i).incidentEdge[LAST];
2208 } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
2209 if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
2210 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2211 cb = getPoint(i).incidentEdge[LAST];
2212 } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) {
2213 if ( ebData[cb].tSt > ebData[cc].tSt ) {
2214 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2215 cb = getPoint(i).incidentEdge[LAST];
2216 }
2217 }
2218 }
2219 }
2220 if ( doublon ) eData[cc].weight = 0;
2221 } else {
2222 }
2223 if ( doublon ) {
2224 if (getEdge(cb).st == getEdge(cc).st) {
2225 eData[cb].weight += eData[cc].weight;
2226 } else {
2227 eData[cb].weight -= eData[cc].weight;
2228 }
2229 eData[cc].weight = 0;
2231 if (swsData[cc].firstLinkedPoint >= 0) {
2232 int cp = swsData[cc].firstLinkedPoint;
2233 while (cp >= 0) {
2234 pData[cp].askForWindingB = cb;
2235 cp = pData[cp].nextLinkedPoint;
2236 }
2237 if (swsData[cb].firstLinkedPoint < 0) {
2238 swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
2239 } else {
2240 int ncp = swsData[cb].firstLinkedPoint;
2241 while (pData[ncp].nextLinkedPoint >= 0) {
2242 ncp = pData[ncp].nextLinkedPoint;
2243 }
2244 pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
2245 }
2246 }
2248 DisconnectStart (cc);
2249 DisconnectEnd (cc);
2250 if (numberOfEdges() > 1) {
2251 int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
2252 while (cp >= 0) {
2253 pData[cp].askForWindingB = cc;
2254 cp = pData[cp].nextLinkedPoint;
2255 }
2256 }
2257 SwapEdges (cc, numberOfEdges() - 1);
2258 if (cb == numberOfEdges() - 1) {
2259 cb = cc;
2260 }
2261 _aretes.pop_back();
2262 }
2263 } else {
2264 int cb;
2265 cb = getPoint(i).incidentEdge[FIRST];
2266 while (cb >= 0 && cb < numberOfEdges()) {
2267 int other = Other (i, cb);
2268 int cc;
2269 cc = getPoint(i).incidentEdge[FIRST];
2270 while (cc >= 0 && cc < numberOfEdges()) {
2271 int ncc = NextAt (i, cc);
2272 bool doublon=false;
2273 if (cc != cb && Other (i, cc) == other ) doublon=true;
2274 if ( directed == fill_justDont ) {
2275 if ( doublon ) {
2276 if ( ebData[cb].pathID > ebData[cc].pathID ) {
2277 doublon=false;
2278 } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
2279 if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
2280 doublon=false;
2281 } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) {
2282 if ( ebData[cb].tSt > ebData[cc].tSt ) {
2283 doublon=false;
2284 }
2285 }
2286 }
2287 }
2288 if ( doublon ) eData[cc].weight = 0;
2289 } else {
2290 }
2291 if ( doublon ) {
2292 // if (cc != cb && Other (i, cc) == other) {
2293 // doublon
2294 if (getEdge(cb).st == getEdge(cc).st) {
2295 eData[cb].weight += eData[cc].weight;
2296 } else {
2297 eData[cb].weight -= eData[cc].weight;
2298 }
2299 eData[cc].weight = 0;
2301 if (swsData[cc].firstLinkedPoint >= 0) {
2302 int cp = swsData[cc].firstLinkedPoint;
2303 while (cp >= 0) {
2304 pData[cp].askForWindingB = cb;
2305 cp = pData[cp].nextLinkedPoint;
2306 }
2307 if (swsData[cb].firstLinkedPoint < 0) {
2308 swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
2309 } else {
2310 int ncp = swsData[cb].firstLinkedPoint;
2311 while (pData[ncp].nextLinkedPoint >= 0) {
2312 ncp = pData[ncp].nextLinkedPoint;
2313 }
2314 pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
2315 }
2316 }
2318 DisconnectStart (cc);
2319 DisconnectEnd (cc);
2320 if (numberOfEdges() > 1) {
2321 int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
2322 while (cp >= 0) {
2323 pData[cp].askForWindingB = cc;
2324 cp = pData[cp].nextLinkedPoint;
2325 }
2326 }
2327 SwapEdges (cc, numberOfEdges() - 1);
2328 if (cb == numberOfEdges() - 1) {
2329 cb = cc;
2330 }
2331 if (ncc == numberOfEdges() - 1) {
2332 ncc = cc;
2333 }
2334 _aretes.pop_back();
2335 }
2336 cc = ncc;
2337 }
2338 cb = NextAt (i, cb);
2339 }
2340 }
2341 }
2343 if ( directed == fill_justDont ) {
2344 for (int i = 0; i < numberOfEdges(); i++) {
2345 if (eData[i].weight == 0) {
2346 // SubEdge(i);
2347 // i--;
2348 } else {
2349 if (eData[i].weight < 0) Inverse (i);
2350 }
2351 }
2352 } else {
2353 for (int i = 0; i < numberOfEdges(); i++) {
2354 if (eData[i].weight == 0) {
2355 // SubEdge(i);
2356 // i--;
2357 } else {
2358 if (eData[i].weight < 0) Inverse (i);
2359 }
2360 }
2361 }
2362 }
2363 void
2364 Shape::GetWindings (Shape * a, Shape * b, BooleanOp mod, bool brutal)
2365 {
2366 // preparation du parcours
2367 for (int i = 0; i < numberOfEdges(); i++)
2368 {
2369 swdData[i].misc = 0;
2370 swdData[i].precParc = swdData[i].suivParc = -1;
2371 }
2373 // chainage
2374 SortEdges ();
2376 int searchInd = 0;
2378 int lastPtUsed = 0;
2379 do
2380 {
2381 int startBord = -1;
2382 int outsideW = 0;
2383 {
2384 int fi = 0;
2385 for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
2386 {
2387 if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
2388 break;
2389 }
2390 lastPtUsed = fi + 1;
2391 if (fi < numberOfPoints())
2392 {
2393 int bestB = getPoint(fi).incidentEdge[FIRST];
2394 if (bestB >= 0)
2395 {
2396 startBord = bestB;
2397 if (fi == 0)
2398 {
2399 outsideW = 0;
2400 }
2401 else
2402 {
2403 if (brutal)
2404 {
2405 outsideW = Winding (getPoint(fi).x);
2406 }
2407 else
2408 {
2409 outsideW = Winding (fi);
2410 }
2411 }
2412 if ( getPoint(fi).totalDegree() == 1 ) {
2413 if ( fi == getEdge(startBord).en ) {
2414 if ( eData[startBord].weight == 0 ) {
2415 // on se contente d'inverser
2416 Inverse(startBord);
2417 } else {
2418 // on passe le askForWinding (sinon ca va rester startBord)
2419 pData[getEdge(startBord).st].askForWindingB=pData[getEdge(startBord).en].askForWindingB;
2420 }
2421 }
2422 }
2423 if (getEdge(startBord).en == fi)
2424 outsideW += eData[startBord].weight;
2425 }
2426 }
2427 }
2428 if (startBord >= 0)
2429 {
2430 // parcours en profondeur pour mettre les leF et riF a leurs valeurs
2431 swdData[startBord].misc = (void *) 1;
2432 swdData[startBord].leW = outsideW;
2433 swdData[startBord].riW = outsideW - eData[startBord].weight;
2434 // if ( doDebug ) printf("part de %d\n",startBord);
2435 int curBord = startBord;
2436 bool curDir = true;
2437 swdData[curBord].precParc = -1;
2438 swdData[curBord].suivParc = -1;
2439 do
2440 {
2441 int cPt;
2442 if (curDir)
2443 cPt = getEdge(curBord).en;
2444 else
2445 cPt = getEdge(curBord).st;
2446 int nb = curBord;
2447 // if ( doDebug ) printf("de curBord= %d avec leF= %d et riF= %d -> ",curBord,swdData[curBord].leW,swdData[curBord].riW);
2448 do
2449 {
2450 int nnb = -1;
2451 if (getEdge(nb).en == cPt)
2452 {
2453 outsideW = swdData[nb].riW;
2454 nnb = CyclePrevAt (cPt, nb);
2455 }
2456 else
2457 {
2458 outsideW = swdData[nb].leW;
2459 nnb = CyclePrevAt (cPt, nb);
2460 }
2461 if (nnb == nb)
2462 {
2463 // cul-de-sac
2464 nb = -1;
2465 break;
2466 }
2467 nb = nnb;
2468 }
2469 while (nb >= 0 && nb != curBord && swdData[nb].misc != 0);
2470 if (nb < 0 || nb == curBord)
2471 {
2472 // retour en arriere
2473 int oPt;
2474 if (curDir)
2475 oPt = getEdge(curBord).st;
2476 else
2477 oPt = getEdge(curBord).en;
2478 curBord = swdData[curBord].precParc;
2479 // if ( doDebug ) printf("retour vers %d\n",curBord);
2480 if (curBord < 0)
2481 break;
2482 if (oPt == getEdge(curBord).en)
2483 curDir = true;
2484 else
2485 curDir = false;
2486 }
2487 else
2488 {
2489 swdData[nb].misc = (void *) 1;
2490 swdData[nb].ind = searchInd++;
2491 if (cPt == getEdge(nb).st)
2492 {
2493 swdData[nb].riW = outsideW;
2494 swdData[nb].leW = outsideW + eData[nb].weight;
2495 }
2496 else
2497 {
2498 swdData[nb].leW = outsideW;
2499 swdData[nb].riW = outsideW - eData[nb].weight;
2500 }
2501 swdData[nb].precParc = curBord;
2502 swdData[curBord].suivParc = nb;
2503 curBord = nb;
2504 // if ( doDebug ) printf("suite %d\n",curBord);
2505 if (cPt == getEdge(nb).en)
2506 curDir = false;
2507 else
2508 curDir = true;
2509 }
2510 }
2511 while (1 /*swdData[curBord].precParc >= 0 */ );
2512 // fin du cas non-oriente
2513 }
2514 }
2515 while (lastPtUsed < numberOfPoints());
2516 // fflush(stdout);
2517 }
2519 bool
2520 Shape::TesteIntersection (Shape * ils, Shape * irs, int ilb, int irb,
2521 NR::Point &atx, double &atL, double &atR,
2522 bool onlyDiff)
2523 {
2524 int lSt = ils->getEdge(ilb).st, lEn = ils->getEdge(ilb).en;
2525 int rSt = irs->getEdge(irb).st, rEn = irs->getEdge(irb).en;
2526 if (lSt == rSt || lSt == rEn)
2527 {
2528 return false;
2529 }
2530 if (lEn == rSt || lEn == rEn)
2531 {
2532 return false;
2533 }
2535 NR::Point ldir, rdir;
2536 ldir = ils->eData[ilb].rdx;
2537 rdir = irs->eData[irb].rdx;
2539 double il = ils->pData[lSt].rx[0], it = ils->pData[lSt].rx[1], ir =
2540 ils->pData[lEn].rx[0], ib = ils->pData[lEn].rx[1];
2541 if (il > ir)
2542 {
2543 double swf = il;
2544 il = ir;
2545 ir = swf;
2546 }
2547 if (it > ib)
2548 {
2549 double swf = it;
2550 it = ib;
2551 ib = swf;
2552 }
2553 double jl = irs->pData[rSt].rx[0], jt = irs->pData[rSt].rx[1], jr =
2554 irs->pData[rEn].rx[0], jb = irs->pData[rEn].rx[1];
2555 if (jl > jr)
2556 {
2557 double swf = jl;
2558 jl = jr;
2559 jr = swf;
2560 }
2561 if (jt > jb)
2562 {
2563 double swf = jt;
2564 jt = jb;
2565 jb = swf;
2566 }
2568 if (il > jr || it > jb || ir < jl || ib < jt)
2569 return false;
2571 // pre-test
2572 {
2573 NR::Point sDiff, eDiff;
2574 double slDot, elDot;
2575 double srDot, erDot;
2576 sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
2577 eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
2578 srDot = cross (sDiff,rdir );
2579 erDot = cross (eDiff,rdir );
2580 if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
2581 return false;
2583 sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
2584 eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
2585 slDot = cross (sDiff,ldir );
2586 elDot = cross (eDiff,ldir);
2587 if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
2588 return false;
2590 double slb = slDot - elDot, srb = srDot - erDot;
2591 if (slb < 0)
2592 slb = -slb;
2593 if (srb < 0)
2594 srb = -srb;
2595 if (slb > srb)
2596 {
2597 atx =
2598 (slDot * irs->pData[rEn].rx - elDot * irs->pData[rSt].rx) / (slDot -
2599 elDot);
2600 }
2601 else
2602 {
2603 atx =
2604 (srDot * ils->pData[lEn].rx - erDot * ils->pData[lSt].rx) / (srDot -
2605 erDot);
2606 }
2607 atL = srDot / (srDot - erDot);
2608 atR = slDot / (slDot - elDot);
2609 return true;
2610 }
2612 // a mettre en double precision pour des resultats exacts
2613 NR::Point usvs;
2614 usvs = irs->pData[rSt].rx - ils->pData[lSt].rx;
2616 // pas sur de l'ordre des coefs de m
2617 NR::Matrix m(ldir[0], ldir[1],
2618 rdir[0], rdir[1],
2619 0, 0);
2620 double det = m.det();
2622 double tdet = det * ils->eData[ilb].isqlength * irs->eData[irb].isqlength;
2624 if (tdet > -0.0001 && tdet < 0.0001)
2625 { // ces couillons de vecteurs sont colineaires
2626 NR::Point sDiff, eDiff;
2627 double sDot, eDot;
2628 sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
2629 eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
2630 sDot = cross (sDiff,rdir );
2631 eDot = cross (eDiff,rdir);
2633 atx =
2634 (sDot * irs->pData[lEn].rx - eDot * irs->pData[lSt].rx) / (sDot -
2635 eDot);
2636 atL = sDot / (sDot - eDot);
2638 sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
2639 eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
2640 sDot = cross (sDiff,ldir );
2641 eDot = cross (eDiff,ldir );
2643 atR = sDot / (sDot - eDot);
2645 return true;
2646 }
2648 // plus de colinearite ni d'extremites en commun
2649 m[1] = -m[1];
2650 m[2] = -m[2];
2651 {
2652 double swap = m[0];
2653 m[0] = m[3];
2654 m[3] = swap;
2655 }
2657 atL = (m[0]* usvs[0] + m[1] * usvs[1]) / det;
2658 atR = -(m[2] * usvs[0] + m[3] * usvs[1]) / det;
2659 atx = ils->pData[lSt].rx + atL * ldir;
2662 return true;
2663 }
2665 bool
2666 Shape::TesteAdjacency (Shape * a, int no, const NR::Point atx, int nPt,
2667 bool push)
2668 {
2669 if (nPt == a->swsData[no].stPt || nPt == a->swsData[no].enPt)
2670 return false;
2672 NR::Point adir, diff, ast, aen, diff1, diff2, diff3, diff4;
2674 ast = a->pData[a->getEdge(no).st].rx;
2675 aen = a->pData[a->getEdge(no).en].rx;
2677 adir = a->eData[no].rdx;
2679 double sle = a->eData[no].length;
2680 double ile = a->eData[no].ilength;
2682 diff = atx - ast;
2684 double e = IHalfRound ((cross (diff,adir)) * a->eData[no].isqlength);
2685 if (-3 < e && e < 3)
2686 {
2687 double rad = HalfRound (0.501); // when using single precision, 0.505 is better (0.5 would be the correct value,
2688 // but it produces lots of bugs)
2689 diff1[0] = diff[0] - rad;
2690 diff1[1] = diff[1] - rad;
2691 diff2[0] = diff[0] + rad;
2692 diff2[1] = diff[1] - rad;
2693 diff3[0] = diff[0] + rad;
2694 diff3[1] = diff[1] + rad;
2695 diff4[0] = diff[0] - rad;
2696 diff4[1] = diff[1] + rad;
2697 double di1, di2;
2698 bool adjacent = false;
2699 di1 = cross (diff1,adir);
2700 di2 = cross (diff3,adir);
2701 if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
2702 {
2703 adjacent = true;
2704 }
2705 else
2706 {
2707 di1 = cross ( diff2,adir);
2708 di2 = cross (diff4,adir);
2709 if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
2710 {
2711 adjacent = true;
2712 }
2713 }
2714 if (adjacent)
2715 {
2716 double t = dot (diff, adir);
2717 if (t > 0 && t < sle)
2718 {
2719 if (push)
2720 {
2721 t *= ile;
2722 PushIncidence (a, no, nPt, t);
2723 }
2724 return true;
2725 }
2726 }
2727 }
2728 return false;
2729 }
2731 void
2732 Shape::CheckAdjacencies (int lastPointNo, int lastChgtPt, Shape * shapeHead,
2733 int edgeHead)
2734 {
2735 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
2736 {
2737 int chLeN = chgts[cCh].ptNo;
2738 int chRiN = chgts[cCh].ptNo;
2739 if (chgts[cCh].src)
2740 {
2741 Shape *lS = chgts[cCh].src;
2742 int lB = chgts[cCh].bord;
2743 int lftN = lS->swsData[lB].leftRnd;
2744 int rgtN = lS->swsData[lB].rightRnd;
2745 if (lftN < chLeN)
2746 chLeN = lftN;
2747 if (rgtN > chRiN)
2748 chRiN = rgtN;
2749 // for (int n=lftN;n<=rgtN;n++) CreateIncidence(lS,lB,n);
2750 for (int n = lftN - 1; n >= lastChgtPt; n--)
2751 {
2752 if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
2753 false)
2754 break;
2755 lS->swsData[lB].leftRnd = n;
2756 }
2757 for (int n = rgtN + 1; n < lastPointNo; n++)
2758 {
2759 if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
2760 false)
2761 break;
2762 lS->swsData[lB].rightRnd = n;
2763 }
2764 }
2765 if (chgts[cCh].osrc)
2766 {
2767 Shape *rS = chgts[cCh].osrc;
2768 int rB = chgts[cCh].obord;
2769 int lftN = rS->swsData[rB].leftRnd;
2770 int rgtN = rS->swsData[rB].rightRnd;
2771 if (lftN < chLeN)
2772 chLeN = lftN;
2773 if (rgtN > chRiN)
2774 chRiN = rgtN;
2775 // for (int n=lftN;n<=rgtN;n++) CreateIncidence(rS,rB,n);
2776 for (int n = lftN - 1; n >= lastChgtPt; n--)
2777 {
2778 if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
2779 false)
2780 break;
2781 rS->swsData[rB].leftRnd = n;
2782 }
2783 for (int n = rgtN + 1; n < lastPointNo; n++)
2784 {
2785 if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
2786 false)
2787 break;
2788 rS->swsData[rB].rightRnd = n;
2789 }
2790 }
2791 if (chgts[cCh].lSrc)
2792 {
2793 if (chgts[cCh].lSrc->swsData[chgts[cCh].lBrd].leftRnd < lastChgtPt)
2794 {
2795 Shape *nSrc = chgts[cCh].lSrc;
2796 int nBrd = chgts[cCh].lBrd /*,nNo=chgts[cCh].ptNo */ ;
2797 bool hit;
2799 do
2800 {
2801 hit = false;
2802 for (int n = chRiN; n >= chLeN; n--)
2803 {
2804 if (TesteAdjacency
2805 (nSrc, nBrd, getPoint(n).x, n, false))
2806 {
2807 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2808 {
2809 nSrc->swsData[nBrd].leftRnd = n;
2810 nSrc->swsData[nBrd].rightRnd = n;
2811 }
2812 else
2813 {
2814 if (n < nSrc->swsData[nBrd].leftRnd)
2815 nSrc->swsData[nBrd].leftRnd = n;
2816 if (n > nSrc->swsData[nBrd].rightRnd)
2817 nSrc->swsData[nBrd].rightRnd = n;
2818 }
2819 hit = true;
2820 }
2821 }
2822 for (int n = chLeN - 1; n >= lastChgtPt; n--)
2823 {
2824 if (TesteAdjacency
2825 (nSrc, nBrd, getPoint(n).x, n, false) == false)
2826 break;
2827 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2828 {
2829 nSrc->swsData[nBrd].leftRnd = n;
2830 nSrc->swsData[nBrd].rightRnd = n;
2831 }
2832 else
2833 {
2834 if (n < nSrc->swsData[nBrd].leftRnd)
2835 nSrc->swsData[nBrd].leftRnd = n;
2836 if (n > nSrc->swsData[nBrd].rightRnd)
2837 nSrc->swsData[nBrd].rightRnd = n;
2838 }
2839 hit = true;
2840 }
2841 if (hit)
2842 {
2843 SweepTree *node =
2844 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
2845 if (node == NULL)
2846 break;
2847 node = static_cast < SweepTree * >(node->elem[LEFT]);
2848 if (node == NULL)
2849 break;
2850 nSrc = node->src;
2851 nBrd = node->bord;
2852 if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
2853 break;
2854 }
2855 }
2856 while (hit);
2858 }
2859 }
2860 if (chgts[cCh].rSrc)
2861 {
2862 if (chgts[cCh].rSrc->swsData[chgts[cCh].rBrd].leftRnd < lastChgtPt)
2863 {
2864 Shape *nSrc = chgts[cCh].rSrc;
2865 int nBrd = chgts[cCh].rBrd /*,nNo=chgts[cCh].ptNo */ ;
2866 bool hit;
2867 do
2868 {
2869 hit = false;
2870 for (int n = chLeN; n <= chRiN; n++)
2871 {
2872 if (TesteAdjacency
2873 (nSrc, nBrd, getPoint(n).x, n, false))
2874 {
2875 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2876 {
2877 nSrc->swsData[nBrd].leftRnd = n;
2878 nSrc->swsData[nBrd].rightRnd = n;
2879 }
2880 else
2881 {
2882 if (n < nSrc->swsData[nBrd].leftRnd)
2883 nSrc->swsData[nBrd].leftRnd = n;
2884 if (n > nSrc->swsData[nBrd].rightRnd)
2885 nSrc->swsData[nBrd].rightRnd = n;
2886 }
2887 hit = true;
2888 }
2889 }
2890 for (int n = chRiN + 1; n < lastPointNo; n++)
2891 {
2892 if (TesteAdjacency
2893 (nSrc, nBrd, getPoint(n).x, n, false) == false)
2894 break;
2895 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2896 {
2897 nSrc->swsData[nBrd].leftRnd = n;
2898 nSrc->swsData[nBrd].rightRnd = n;
2899 }
2900 else
2901 {
2902 if (n < nSrc->swsData[nBrd].leftRnd)
2903 nSrc->swsData[nBrd].leftRnd = n;
2904 if (n > nSrc->swsData[nBrd].rightRnd)
2905 nSrc->swsData[nBrd].rightRnd = n;
2906 }
2907 hit = true;
2908 }
2909 if (hit)
2910 {
2911 SweepTree *node =
2912 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
2913 if (node == NULL)
2914 break;
2915 node = static_cast < SweepTree * >(node->elem[RIGHT]);
2916 if (node == NULL)
2917 break;
2918 nSrc = node->src;
2919 nBrd = node->bord;
2920 if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
2921 break;
2922 }
2923 }
2924 while (hit);
2925 }
2926 }
2927 }
2928 }
2931 void Shape::AddChgt(int lastPointNo, int lastChgtPt, Shape * &shapeHead,
2932 int &edgeHead, sTreeChangeType type, Shape * lS, int lB, Shape * rS,
2933 int rB)
2934 {
2935 sTreeChange c;
2936 c.ptNo = lastPointNo;
2937 c.type = type;
2938 c.src = lS;
2939 c.bord = lB;
2940 c.osrc = rS;
2941 c.obord = rB;
2942 chgts.push_back(c);
2943 const int nCh = chgts.size() - 1;
2945 /* FIXME: this looks like a cut and paste job */
2947 if (lS) {
2948 SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
2949 if (lE && lE->elem[LEFT]) {
2950 SweepTree *llE = static_cast < SweepTree * >(lE->elem[LEFT]);
2951 chgts[nCh].lSrc = llE->src;
2952 chgts[nCh].lBrd = llE->bord;
2953 } else {
2954 chgts[nCh].lSrc = NULL;
2955 chgts[nCh].lBrd = -1;
2956 }
2958 if (lS->swsData[lB].leftRnd < lastChgtPt) {
2959 lS->swsData[lB].leftRnd = lastPointNo;
2960 lS->swsData[lB].nextSh = shapeHead;
2961 lS->swsData[lB].nextBo = edgeHead;
2962 edgeHead = lB;
2963 shapeHead = lS;
2964 } else {
2965 int old = lS->swsData[lB].leftRnd;
2966 if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
2967 lS->swsData[lB].leftRnd = lastPointNo;
2968 }
2969 }
2970 if (lS->swsData[lB].rightRnd < lastChgtPt) {
2971 lS->swsData[lB].rightRnd = lastPointNo;
2972 } else {
2973 int old = lS->swsData[lB].rightRnd;
2974 if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
2975 lS->swsData[lB].rightRnd = lastPointNo;
2976 }
2977 }
2979 if (rS) {
2980 SweepTree *rE = static_cast < SweepTree * >(rS->swsData[rB].misc);
2981 if (rE->elem[RIGHT]) {
2982 SweepTree *rrE = static_cast < SweepTree * >(rE->elem[RIGHT]);
2983 chgts[nCh].rSrc = rrE->src;
2984 chgts[nCh].rBrd = rrE->bord;
2985 } else {
2986 chgts[nCh].rSrc = NULL;
2987 chgts[nCh].rBrd = -1;
2988 }
2990 if (rS->swsData[rB].leftRnd < lastChgtPt) {
2991 rS->swsData[rB].leftRnd = lastPointNo;
2992 rS->swsData[rB].nextSh = shapeHead;
2993 rS->swsData[rB].nextBo = edgeHead;
2994 edgeHead = rB;
2995 shapeHead = rS;
2996 } else {
2997 int old = rS->swsData[rB].leftRnd;
2998 if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
2999 rS->swsData[rB].leftRnd = lastPointNo;
3000 }
3001 }
3002 if (rS->swsData[rB].rightRnd < lastChgtPt) {
3003 rS->swsData[rB].rightRnd = lastPointNo;
3004 } else {
3005 int old = rS->swsData[rB].rightRnd;
3006 if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
3007 rS->swsData[rB].rightRnd = lastPointNo;
3008 }
3009 } else {
3010 SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
3011 if (lE && lE->elem[RIGHT]) {
3012 SweepTree *rlE = static_cast < SweepTree * >(lE->elem[RIGHT]);
3013 chgts[nCh].rSrc = rlE->src;
3014 chgts[nCh].rBrd = rlE->bord;
3015 } else {
3016 chgts[nCh].rSrc = NULL;
3017 chgts[nCh].rBrd = -1;
3018 }
3019 }
3020 }
3022 // is this a debug function? It's calling localized "printf" ...
3023 void
3024 Shape::Validate (void)
3025 {
3026 for (int i = 0; i < numberOfPoints(); i++)
3027 {
3028 pData[i].rx = getPoint(i).x;
3029 }
3030 for (int i = 0; i < numberOfEdges(); i++)
3031 {
3032 eData[i].rdx = getEdge(i).dx;
3033 }
3034 for (int i = 0; i < numberOfEdges(); i++)
3035 {
3036 for (int j = i + 1; j < numberOfEdges(); j++)
3037 {
3038 NR::Point atx;
3039 double atL, atR;
3040 if (TesteIntersection (this, this, i, j, atx, atL, atR, false))
3041 {
3042 printf ("%i %i %f %f di=%f %f dj=%f %f\n", i, j, atx[0],atx[1],getEdge(i).dx[0],getEdge(i).dx[1],getEdge(j).dx[0],getEdge(j).dx[1]);
3043 }
3044 }
3045 }
3046 fflush (stdout);
3047 }
3049 void
3050 Shape::CheckEdges (int lastPointNo, int lastChgtPt, Shape * a, Shape * b,
3051 BooleanOp mod)
3052 {
3054 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
3055 {
3056 if (chgts[cCh].type == 0)
3057 {
3058 Shape *lS = chgts[cCh].src;
3059 int lB = chgts[cCh].bord;
3060 lS->swsData[lB].curPoint = chgts[cCh].ptNo;
3061 }
3062 }
3063 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
3064 {
3065 // int chLeN=chgts[cCh].ptNo;
3066 // int chRiN=chgts[cCh].ptNo;
3067 if (chgts[cCh].src)
3068 {
3069 Shape *lS = chgts[cCh].src;
3070 int lB = chgts[cCh].bord;
3071 Avance (lastPointNo, lastChgtPt, lS, lB, a, b, mod);
3072 }
3073 if (chgts[cCh].osrc)
3074 {
3075 Shape *rS = chgts[cCh].osrc;
3076 int rB = chgts[cCh].obord;
3077 Avance (lastPointNo, lastChgtPt, rS, rB, a, b, mod);
3078 }
3079 if (chgts[cCh].lSrc)
3080 {
3081 Shape *nSrc = chgts[cCh].lSrc;
3082 int nBrd = chgts[cCh].lBrd;
3083 while (nSrc->swsData[nBrd].leftRnd >=
3084 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
3085 {
3086 Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
3088 SweepTree *node =
3089 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
3090 if (node == NULL)
3091 break;
3092 node = static_cast < SweepTree * >(node->elem[LEFT]);
3093 if (node == NULL)
3094 break;
3095 nSrc = node->src;
3096 nBrd = node->bord;
3097 }
3098 }
3099 if (chgts[cCh].rSrc)
3100 {
3101 Shape *nSrc = chgts[cCh].rSrc;
3102 int nBrd = chgts[cCh].rBrd;
3103 while (nSrc->swsData[nBrd].rightRnd >=
3104 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
3105 {
3106 Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
3108 SweepTree *node =
3109 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
3110 if (node == NULL)
3111 break;
3112 node = static_cast < SweepTree * >(node->elem[RIGHT]);
3113 if (node == NULL)
3114 break;
3115 nSrc = node->src;
3116 nBrd = node->bord;
3117 }
3118 }
3119 }
3120 }
3122 void
3123 Shape::Avance (int lastPointNo, int lastChgtPt, Shape * lS, int lB, Shape * a,
3124 Shape * b, BooleanOp mod)
3125 {
3126 double dd = HalfRound (1);
3127 bool avoidDiag = false;
3128 // if ( lastChgtPt > 0 && pts[lastChgtPt-1].y+dd == pts[lastChgtPt].y ) avoidDiag=true;
3130 bool direct = true;
3131 if (lS == b && (mod == bool_op_diff || mod == bool_op_symdiff))
3132 direct = false;
3133 int lftN = lS->swsData[lB].leftRnd;
3134 int rgtN = lS->swsData[lB].rightRnd;
3135 if (lS->swsData[lB].doneTo < lastChgtPt)
3136 {
3137 int lp = lS->swsData[lB].curPoint;
3138 if (lp >= 0 && getPoint(lp).x[1] + dd == getPoint(lastChgtPt).x[1])
3139 avoidDiag = true;
3140 if (lS->eData[lB].rdx[1] == 0)
3141 {
3142 // tjs de gauche a droite et pas de diagonale
3143 if (lS->eData[lB].rdx[0] >= 0)
3144 {
3145 for (int p = lftN; p <= rgtN; p++)
3146 {
3147 DoEdgeTo (lS, lB, p, direct, true);
3148 lp = p;
3149 }
3150 }
3151 else
3152 {
3153 for (int p = lftN; p <= rgtN; p++)
3154 {
3155 DoEdgeTo (lS, lB, p, direct, false);
3156 lp = p;
3157 }
3158 }
3159 }
3160 else if (lS->eData[lB].rdx[1] > 0)
3161 {
3162 if (lS->eData[lB].rdx[0] >= 0)
3163 {
3165 for (int p = lftN; p <= rgtN; p++)
3166 {
3167 if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
3168 {
3169 if (lftN > 0 && lftN - 1 >= lastChgtPt
3170 && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
3171 {
3172 DoEdgeTo (lS, lB, lftN - 1, direct, true);
3173 DoEdgeTo (lS, lB, lftN, direct, true);
3174 }
3175 else
3176 {
3177 DoEdgeTo (lS, lB, lftN, direct, true);
3178 }
3179 }
3180 else
3181 {
3182 DoEdgeTo (lS, lB, p, direct, true);
3183 }
3184 lp = p;
3185 }
3186 }
3187 else
3188 {
3190 for (int p = rgtN; p >= lftN; p--)
3191 {
3192 if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
3193 {
3194 if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
3195 && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
3196 {
3197 DoEdgeTo (lS, lB, rgtN + 1, direct, true);
3198 DoEdgeTo (lS, lB, rgtN, direct, true);
3199 }
3200 else
3201 {
3202 DoEdgeTo (lS, lB, rgtN, direct, true);
3203 }
3204 }
3205 else
3206 {
3207 DoEdgeTo (lS, lB, p, direct, true);
3208 }
3209 lp = p;
3210 }
3211 }
3212 }
3213 else
3214 {
3215 if (lS->eData[lB].rdx[0] >= 0)
3216 {
3218 for (int p = rgtN; p >= lftN; p--)
3219 {
3220 if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
3221 {
3222 if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
3223 && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
3224 {
3225 DoEdgeTo (lS, lB, rgtN + 1, direct, false);
3226 DoEdgeTo (lS, lB, rgtN, direct, false);
3227 }
3228 else
3229 {
3230 DoEdgeTo (lS, lB, rgtN, direct, false);
3231 }
3232 }
3233 else
3234 {
3235 DoEdgeTo (lS, lB, p, direct, false);
3236 }
3237 lp = p;
3238 }
3239 }
3240 else
3241 {
3243 for (int p = lftN; p <= rgtN; p++)
3244 {
3245 if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
3246 {
3247 if (lftN > 0 && lftN - 1 >= lastChgtPt
3248 && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
3249 {
3250 DoEdgeTo (lS, lB, lftN - 1, direct, false);
3251 DoEdgeTo (lS, lB, lftN, direct, false);
3252 }
3253 else
3254 {
3255 DoEdgeTo (lS, lB, lftN, direct, false);
3256 }
3257 }
3258 else
3259 {
3260 DoEdgeTo (lS, lB, p, direct, false);
3261 }
3262 lp = p;
3263 }
3264 }
3265 }
3266 lS->swsData[lB].curPoint = lp;
3267 }
3268 lS->swsData[lB].doneTo = lastPointNo - 1;
3269 }
3271 void
3272 Shape::DoEdgeTo (Shape * iS, int iB, int iTo, bool direct, bool sens)
3273 {
3274 int lp = iS->swsData[iB].curPoint;
3275 int ne = -1;
3276 if (sens)
3277 {
3278 if (direct)
3279 ne = AddEdge (lp, iTo);
3280 else
3281 ne = AddEdge (iTo, lp);
3282 }
3283 else
3284 {
3285 if (direct)
3286 ne = AddEdge (iTo, lp);
3287 else
3288 ne = AddEdge (lp, iTo);
3289 }
3290 if (ne >= 0 && _has_back_data)
3291 {
3292 ebData[ne].pathID = iS->ebData[iB].pathID;
3293 ebData[ne].pieceID = iS->ebData[iB].pieceID;
3294 if (iS->eData[iB].length < 0.00001)
3295 {
3296 ebData[ne].tSt = ebData[ne].tEn = iS->ebData[iB].tSt;
3297 }
3298 else
3299 {
3300 double bdl = iS->eData[iB].ilength;
3301 NR::Point bpx = iS->pData[iS->getEdge(iB).st].rx;
3302 NR::Point bdx = iS->eData[iB].rdx;
3303 NR::Point psx = getPoint(getEdge(ne).st).x;
3304 NR::Point pex = getPoint(getEdge(ne).en).x;
3305 NR::Point psbx=psx-bpx;
3306 NR::Point pebx=pex-bpx;
3307 double pst = dot(psbx,bdx) * bdl;
3308 double pet = dot(pebx,bdx) * bdl;
3309 pst = iS->ebData[iB].tSt * (1 - pst) + iS->ebData[iB].tEn * pst;
3310 pet = iS->ebData[iB].tSt * (1 - pet) + iS->ebData[iB].tEn * pet;
3311 ebData[ne].tEn = pet;
3312 ebData[ne].tSt = pst;
3313 }
3314 }
3315 iS->swsData[iB].curPoint = iTo;
3316 if (ne >= 0)
3317 {
3318 int cp = iS->swsData[iB].firstLinkedPoint;
3319 swsData[ne].firstLinkedPoint = iS->swsData[iB].firstLinkedPoint;
3320 while (cp >= 0)
3321 {
3322 pData[cp].askForWindingB = ne;
3323 cp = pData[cp].nextLinkedPoint;
3324 }
3325 iS->swsData[iB].firstLinkedPoint = -1;
3326 }
3327 }