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