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