![[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 MakePointData (false);
824 MakeEdgeData (false);
825 MakeSweepSrcData (false);
826 MakeSweepDestData (false);
827 a->CleanupSweep ();
828 type = shape_polygon;
829 return 0;
830 }
832 // technically it's just a ConvertToShape() on 2 polygons at the same time, and different rules
833 // for choosing the edges according to their winding numbers.
834 // probably one of the biggest function i ever wrote.
835 int
836 Shape::Booleen (Shape * a, Shape * b, BooleanOp mod,int cutPathID)
837 {
838 if (a == b || a == NULL || b == NULL)
839 return shape_input_err;
840 Reset (0, 0);
841 if (a->numberOfPoints() <= 1 || a->numberOfEdges() <= 1)
842 return 0;
843 if (b->numberOfPoints() <= 1 || b->numberOfEdges() <= 1)
844 return 0;
845 if ( mod == bool_op_cut ) {
846 } else if ( mod == bool_op_slice ) {
847 } else {
848 if (a->type != shape_polygon)
849 return shape_input_err;
850 if (b->type != shape_polygon)
851 return shape_input_err;
852 }
854 a->ResetSweep ();
855 b->ResetSweep ();
857 if (sTree == NULL) {
858 sTree = new SweepTreeList(a->numberOfEdges() + b->numberOfEdges());
859 }
860 if (sEvts == NULL) {
861 sEvts = new SweepEventQueue(a->numberOfEdges() + b->numberOfEdges());
862 }
864 MakePointData (true);
865 MakeEdgeData (true);
866 MakeSweepSrcData (true);
867 MakeSweepDestData (true);
868 if (a->hasBackData () && b->hasBackData ())
869 {
870 MakeBackData (true);
871 }
872 else
873 {
874 MakeBackData (false);
875 }
877 a->initialisePointData();
878 b->initialisePointData();
880 a->initialiseEdgeData();
881 b->initialiseEdgeData();
883 a->SortPointsRounded ();
884 b->SortPointsRounded ();
886 chgts.clear();
888 double lastChange =
889 (a->pData[0].rx[1] <
890 b->pData[0].rx[1]) ? a->pData[0].rx[1] - 1.0 : b->pData[0].rx[1] - 1.0;
891 int lastChgtPt = 0;
892 int edgeHead = -1;
893 Shape *shapeHead = NULL;
895 clearIncidenceData();
897 int curAPt = 0;
898 int curBPt = 0;
900 while (curAPt < a->numberOfPoints() || curBPt < b->numberOfPoints() || sEvts->size() > 0)
901 {
902 /* for (int i=0;i<sEvts.nbEvt;i++) {
903 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
904 }
905 // cout << endl;
906 if ( sTree.racine ) {
907 SweepTree* ct=static_cast <SweepTree*> (sTree.racine->Leftmost());
908 while ( ct ) {
909 printf("%i %i [%i\n",ct->bord,ct->startPoint,(ct->src==a)?1:0);
910 ct=static_cast <SweepTree*> (ct->elem[RIGHT]);
911 }
912 }
913 printf("\n");*/
915 NR::Point ptX;
916 double ptL, ptR;
917 SweepTree *intersL = NULL;
918 SweepTree *intersR = NULL;
919 int nPt = -1;
920 Shape *ptSh = NULL;
921 bool isIntersection = false;
923 if (sEvts->peek(intersL, intersR, ptX, ptL, ptR))
924 {
925 if (curAPt < a->numberOfPoints())
926 {
927 if (curBPt < b->numberOfPoints())
928 {
929 if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
930 || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
931 && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
932 {
933 if (a->pData[curAPt].pending > 0
934 || (a->pData[curAPt].rx[1] > ptX[1]
935 || (a->pData[curAPt].rx[1] == ptX[1]
936 && a->pData[curAPt].rx[0] > ptX[0])))
937 {
938 /* FIXME: could be pop? */
939 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
940 isIntersection = true;
941 }
942 else
943 {
944 nPt = curAPt++;
945 ptSh = a;
946 ptX = ptSh->pData[nPt].rx;
947 isIntersection = false;
948 }
949 }
950 else
951 {
952 if (b->pData[curBPt].pending > 0
953 || (b->pData[curBPt].rx[1] > ptX[1]
954 || (b->pData[curBPt].rx[1] == ptX[1]
955 && b->pData[curBPt].rx[0] > ptX[0])))
956 {
957 /* FIXME: could be pop? */
958 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
959 isIntersection = true;
960 }
961 else
962 {
963 nPt = curBPt++;
964 ptSh = b;
965 ptX = ptSh->pData[nPt].rx;
966 isIntersection = false;
967 }
968 }
969 }
970 else
971 {
972 if (a->pData[curAPt].pending > 0
973 || (a->pData[curAPt].rx[1] > ptX[1]
974 || (a->pData[curAPt].rx[1] == ptX[1]
975 && a->pData[curAPt].rx[0] > ptX[0])))
976 {
977 /* FIXME: could be pop? */
978 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
979 isIntersection = true;
980 }
981 else
982 {
983 nPt = curAPt++;
984 ptSh = a;
985 ptX = ptSh->pData[nPt].rx;
986 isIntersection = false;
987 }
988 }
989 }
990 else
991 {
992 if (b->pData[curBPt].pending > 0
993 || (b->pData[curBPt].rx[1] > ptX[1]
994 || (b->pData[curBPt].rx[1] == ptX[1]
995 && b->pData[curBPt].rx[0] > ptX[0])))
996 {
997 /* FIXME: could be pop? */
998 sEvts->extract(intersL, intersR, ptX, ptL, ptR);
999 isIntersection = true;
1000 }
1001 else
1002 {
1003 nPt = curBPt++;
1004 ptSh = b;
1005 ptX = ptSh->pData[nPt].rx;
1006 isIntersection = false;
1007 }
1008 }
1009 }
1010 else
1011 {
1012 if (curAPt < a->numberOfPoints())
1013 {
1014 if (curBPt < b->numberOfPoints())
1015 {
1016 if (a->pData[curAPt].rx[1] < b->pData[curBPt].rx[1]
1017 || (a->pData[curAPt].rx[1] == b->pData[curBPt].rx[1]
1018 && a->pData[curAPt].rx[0] < b->pData[curBPt].rx[0]))
1019 {
1020 nPt = curAPt++;
1021 ptSh = a;
1022 }
1023 else
1024 {
1025 nPt = curBPt++;
1026 ptSh = b;
1027 }
1028 }
1029 else
1030 {
1031 nPt = curAPt++;
1032 ptSh = a;
1033 }
1034 }
1035 else
1036 {
1037 nPt = curBPt++;
1038 ptSh = b;
1039 }
1040 ptX = ptSh->pData[nPt].rx;
1041 isIntersection = false;
1042 }
1044 if (isIntersection == false)
1045 {
1046 if (ptSh->getPoint(nPt).dI == 0 && ptSh->getPoint(nPt).dO == 0)
1047 continue;
1048 }
1050 NR::Point rPtX;
1051 rPtX[0]= Round (ptX[0]);
1052 rPtX[1]= Round (ptX[1]);
1053 int lastPointNo = -1;
1054 lastPointNo = AddPoint (rPtX);
1055 pData[lastPointNo].rx = rPtX;
1057 if (rPtX[1] > lastChange)
1058 {
1059 int lastI = AssemblePoints (lastChgtPt, lastPointNo);
1062 Shape *curSh = shapeHead;
1063 int curBo = edgeHead;
1064 while (curSh)
1065 {
1066 curSh->swsData[curBo].leftRnd =
1067 pData[curSh->swsData[curBo].leftRnd].newInd;
1068 curSh->swsData[curBo].rightRnd =
1069 pData[curSh->swsData[curBo].rightRnd].newInd;
1071 Shape *neSh = curSh->swsData[curBo].nextSh;
1072 curBo = curSh->swsData[curBo].nextBo;
1073 curSh = neSh;
1074 }
1076 for (unsigned int i = 0; i < chgts.size(); i++)
1077 {
1078 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
1079 if (chgts[i].type == 0)
1080 {
1081 if (chgts[i].src->getEdge(chgts[i].bord).st <
1082 chgts[i].src->getEdge(chgts[i].bord).en)
1083 {
1084 chgts[i].src->swsData[chgts[i].bord].stPt =
1085 chgts[i].ptNo;
1086 }
1087 else
1088 {
1089 chgts[i].src->swsData[chgts[i].bord].enPt =
1090 chgts[i].ptNo;
1091 }
1092 }
1093 else if (chgts[i].type == 1)
1094 {
1095 if (chgts[i].src->getEdge(chgts[i].bord).st >
1096 chgts[i].src->getEdge(chgts[i].bord).en)
1097 {
1098 chgts[i].src->swsData[chgts[i].bord].stPt =
1099 chgts[i].ptNo;
1100 }
1101 else
1102 {
1103 chgts[i].src->swsData[chgts[i].bord].enPt =
1104 chgts[i].ptNo;
1105 }
1106 }
1107 }
1109 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
1111 CheckEdges (lastI, lastChgtPt, a, b, mod);
1113 for (int i = lastChgtPt; i < lastI; i++)
1114 {
1115 if (pData[i].askForWindingS)
1116 {
1117 Shape *windS = pData[i].askForWindingS;
1118 int windB = pData[i].askForWindingB;
1119 pData[i].nextLinkedPoint =
1120 windS->swsData[windB].firstLinkedPoint;
1121 windS->swsData[windB].firstLinkedPoint = i;
1122 }
1123 }
1125 if (lastI < lastPointNo)
1126 {
1127 _pts[lastI] = getPoint(lastPointNo);
1128 pData[lastI] = pData[lastPointNo];
1129 }
1130 lastPointNo = lastI;
1131 _pts.resize(lastI + 1);
1133 lastChgtPt = lastPointNo;
1134 lastChange = rPtX[1];
1135 chgts.clear();
1136 edgeHead = -1;
1137 shapeHead = NULL;
1138 }
1141 if (isIntersection)
1142 {
1143 // les 2 events de part et d'autre de l'intersection
1144 // (celui de l'intersection a deja ete depile)
1145 intersL->RemoveEvent (*sEvts, LEFT);
1146 intersR->RemoveEvent (*sEvts, RIGHT);
1148 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, INTERSECTION,
1149 intersL->src, intersL->bord, intersR->src, intersR->bord);
1151 intersL->SwapWithRight (*sTree, *sEvts);
1153 TesteIntersection (intersL, LEFT, true);
1154 TesteIntersection (intersR, RIGHT, true);
1155 }
1156 else
1157 {
1158 int cb;
1160 int nbUp = 0, nbDn = 0;
1161 int upNo = -1, dnNo = -1;
1162 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1163 while (cb >= 0 && cb < ptSh->numberOfEdges())
1164 {
1165 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1166 && nPt == ptSh->getEdge(cb).en)
1167 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1168 && nPt == ptSh->getEdge(cb).st))
1169 {
1170 upNo = cb;
1171 nbUp++;
1172 }
1173 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1174 && nPt == ptSh->getEdge(cb).en)
1175 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1176 && nPt == ptSh->getEdge(cb).st))
1177 {
1178 dnNo = cb;
1179 nbDn++;
1180 }
1181 cb = ptSh->NextAt (nPt, cb);
1182 }
1184 if (nbDn <= 0)
1185 {
1186 upNo = -1;
1187 }
1188 if (upNo >= 0 && (SweepTree *) ptSh->swsData[upNo].misc == NULL)
1189 {
1190 upNo = -1;
1191 }
1193 // upNo=-1;
1195 bool doWinding = true;
1197 if (nbUp > 0)
1198 {
1199 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1200 while (cb >= 0 && cb < ptSh->numberOfEdges())
1201 {
1202 if ((ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1203 && nPt == ptSh->getEdge(cb).en)
1204 || (ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1205 && nPt == ptSh->getEdge(cb).st))
1206 {
1207 if (cb != upNo)
1208 {
1209 SweepTree *node =
1210 (SweepTree *) ptSh->swsData[cb].misc;
1211 if (node == NULL)
1212 {
1213 }
1214 else
1215 {
1216 AddChgt (lastPointNo, lastChgtPt, shapeHead,
1217 edgeHead, EDGE_REMOVED, node->src, node->bord,
1218 NULL, -1);
1219 ptSh->swsData[cb].misc = NULL;
1221 int onLeftB = -1, onRightB = -1;
1222 Shape *onLeftS = NULL;
1223 Shape *onRightS = NULL;
1224 if (node->elem[LEFT])
1225 {
1226 onLeftB =
1227 (static_cast <
1228 SweepTree * >(node->elem[LEFT]))->bord;
1229 onLeftS =
1230 (static_cast <
1231 SweepTree * >(node->elem[LEFT]))->src;
1232 }
1233 if (node->elem[RIGHT])
1234 {
1235 onRightB =
1236 (static_cast <
1237 SweepTree * >(node->elem[RIGHT]))->bord;
1238 onRightS =
1239 (static_cast <
1240 SweepTree * >(node->elem[RIGHT]))->src;
1241 }
1243 node->Remove (*sTree, *sEvts, true);
1244 if (onLeftS && onRightS)
1245 {
1246 SweepTree *onLeft =
1247 (SweepTree *) onLeftS->swsData[onLeftB].
1248 misc;
1249 // SweepTree* onRight=(SweepTree*)onRightS->swsData[onRightB].misc;
1250 if (onLeftS == ptSh
1251 && (onLeftS->getEdge(onLeftB).en == nPt
1252 || onLeftS->getEdge(onLeftB).st ==
1253 nPt))
1254 {
1255 }
1256 else
1257 {
1258 if (onRightS == ptSh
1259 && (onRightS->getEdge(onRightB).en ==
1260 nPt
1261 || onRightS->getEdge(onRightB).
1262 st == nPt))
1263 {
1264 }
1265 else
1266 {
1267 TesteIntersection (onLeft, RIGHT, true);
1268 }
1269 }
1270 }
1271 }
1272 }
1273 }
1274 cb = ptSh->NextAt (nPt, cb);
1275 }
1276 }
1278 // traitement du "upNo devient dnNo"
1279 SweepTree *insertionNode = NULL;
1280 if (dnNo >= 0)
1281 {
1282 if (upNo >= 0)
1283 {
1284 SweepTree *node = (SweepTree *) ptSh->swsData[upNo].misc;
1286 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_REMOVED,
1287 node->src, node->bord, NULL, -1);
1289 ptSh->swsData[upNo].misc = NULL;
1291 node->RemoveEvents (*sEvts);
1292 node->ConvertTo (ptSh, dnNo, 1, lastPointNo);
1293 ptSh->swsData[dnNo].misc = node;
1294 TesteIntersection (node, RIGHT, true);
1295 TesteIntersection (node, LEFT, true);
1296 insertionNode = node;
1298 ptSh->swsData[dnNo].curPoint = lastPointNo;
1300 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
1301 node->src, node->bord, NULL, -1);
1302 }
1303 else
1304 {
1305 SweepTree *node = sTree->add(ptSh, dnNo, 1, lastPointNo, this);
1306 ptSh->swsData[dnNo].misc = node;
1307 node->Insert (*sTree, *sEvts, this, lastPointNo, true);
1309 if (doWinding)
1310 {
1311 SweepTree *myLeft =
1312 static_cast < SweepTree * >(node->elem[LEFT]);
1313 if (myLeft)
1314 {
1315 pData[lastPointNo].askForWindingS = myLeft->src;
1316 pData[lastPointNo].askForWindingB = myLeft->bord;
1317 }
1318 else
1319 {
1320 pData[lastPointNo].askForWindingB = -1;
1321 }
1322 doWinding = false;
1323 }
1325 TesteIntersection (node, RIGHT, true);
1326 TesteIntersection (node, LEFT, true);
1327 insertionNode = node;
1329 ptSh->swsData[dnNo].curPoint = lastPointNo;
1331 AddChgt (lastPointNo, lastChgtPt, shapeHead, edgeHead, EDGE_INSERTED,
1332 node->src, node->bord, NULL, -1);
1333 }
1334 }
1336 if (nbDn > 1)
1337 { // si nbDn == 1 , alors dnNo a deja ete traite
1338 cb = ptSh->getPoint(nPt).incidentEdge[FIRST];
1339 while (cb >= 0 && cb < ptSh->numberOfEdges())
1340 {
1341 if ((ptSh->getEdge(cb).st > ptSh->getEdge(cb).en
1342 && nPt == ptSh->getEdge(cb).en)
1343 || (ptSh->getEdge(cb).st < ptSh->getEdge(cb).en
1344 && nPt == ptSh->getEdge(cb).st))
1345 {
1346 if (cb != dnNo)
1347 {
1348 SweepTree *node = sTree->add(ptSh, cb, 1, lastPointNo, this);
1349 ptSh->swsData[cb].misc = node;
1350 // node->Insert(sTree,*sEvts,this,lastPointNo,true);
1351 node->InsertAt (*sTree, *sEvts, this, insertionNode,
1352 nPt, true);
1354 if (doWinding)
1355 {
1356 SweepTree *myLeft =
1357 static_cast < SweepTree * >(node->elem[LEFT]);
1358 if (myLeft)
1359 {
1360 pData[lastPointNo].askForWindingS =
1361 myLeft->src;
1362 pData[lastPointNo].askForWindingB =
1363 myLeft->bord;
1364 }
1365 else
1366 {
1367 pData[lastPointNo].askForWindingB = -1;
1368 }
1369 doWinding = false;
1370 }
1372 TesteIntersection (node, RIGHT, true);
1373 TesteIntersection (node, LEFT, true);
1375 ptSh->swsData[cb].curPoint = lastPointNo;
1377 AddChgt (lastPointNo, lastChgtPt, shapeHead,
1378 edgeHead, EDGE_INSERTED, node->src, node->bord, NULL,
1379 -1);
1380 }
1381 }
1382 cb = ptSh->NextAt (nPt, cb);
1383 }
1384 }
1385 }
1386 }
1387 {
1388 int lastI = AssemblePoints (lastChgtPt, numberOfPoints());
1391 Shape *curSh = shapeHead;
1392 int curBo = edgeHead;
1393 while (curSh)
1394 {
1395 curSh->swsData[curBo].leftRnd =
1396 pData[curSh->swsData[curBo].leftRnd].newInd;
1397 curSh->swsData[curBo].rightRnd =
1398 pData[curSh->swsData[curBo].rightRnd].newInd;
1400 Shape *neSh = curSh->swsData[curBo].nextSh;
1401 curBo = curSh->swsData[curBo].nextBo;
1402 curSh = neSh;
1403 }
1405 /* FIXME: this kind of code seems to appear frequently */
1406 for (unsigned int i = 0; i < chgts.size(); i++)
1407 {
1408 chgts[i].ptNo = pData[chgts[i].ptNo].newInd;
1409 if (chgts[i].type == 0)
1410 {
1411 if (chgts[i].src->getEdge(chgts[i].bord).st <
1412 chgts[i].src->getEdge(chgts[i].bord).en)
1413 {
1414 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
1415 }
1416 else
1417 {
1418 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
1419 }
1420 }
1421 else if (chgts[i].type == 1)
1422 {
1423 if (chgts[i].src->getEdge(chgts[i].bord).st >
1424 chgts[i].src->getEdge(chgts[i].bord).en)
1425 {
1426 chgts[i].src->swsData[chgts[i].bord].stPt = chgts[i].ptNo;
1427 }
1428 else
1429 {
1430 chgts[i].src->swsData[chgts[i].bord].enPt = chgts[i].ptNo;
1431 }
1432 }
1433 }
1435 CheckAdjacencies (lastI, lastChgtPt, shapeHead, edgeHead);
1437 CheckEdges (lastI, lastChgtPt, a, b, mod);
1439 for (int i = lastChgtPt; i < lastI; i++)
1440 {
1441 if (pData[i].askForWindingS)
1442 {
1443 Shape *windS = pData[i].askForWindingS;
1444 int windB = pData[i].askForWindingB;
1445 pData[i].nextLinkedPoint = windS->swsData[windB].firstLinkedPoint;
1446 windS->swsData[windB].firstLinkedPoint = i;
1447 }
1448 }
1450 _pts.resize(lastI);
1452 edgeHead = -1;
1453 shapeHead = NULL;
1454 }
1456 chgts.clear();
1457 clearIncidenceData();
1459 // Plot(190,70,6,400,400,true,false,true,true);
1461 if ( mod == bool_op_cut ) {
1462 AssembleAretes (fill_justDont);
1463 // dupliquer les aretes de la coupure
1464 int i=numberOfEdges()-1;
1465 for (;i>=0;i--) {
1466 if ( ebData[i].pathID == cutPathID ) {
1467 // on duplique
1468 int nEd=AddEdge(getEdge(i).en,getEdge(i).st);
1469 ebData[nEd].pathID=cutPathID;
1470 ebData[nEd].pieceID=ebData[i].pieceID;
1471 ebData[nEd].tSt=ebData[i].tEn;
1472 ebData[nEd].tEn=ebData[i].tSt;
1473 eData[nEd].weight=eData[i].weight;
1474 // lui donner les firstlinkedpoitn si besoin
1475 if ( getEdge(i).en >= getEdge(i).st ) {
1476 int cp = swsData[i].firstLinkedPoint;
1477 while (cp >= 0) {
1478 pData[cp].askForWindingB = nEd;
1479 cp = pData[cp].nextLinkedPoint;
1480 }
1481 swsData[nEd].firstLinkedPoint = swsData[i].firstLinkedPoint;
1482 swsData[i].firstLinkedPoint=-1;
1483 }
1484 }
1485 }
1486 } else if ( mod == bool_op_slice ) {
1487 } else {
1488 AssembleAretes ();
1489 }
1491 for (int i = 0; i < numberOfPoints(); i++)
1492 {
1493 _pts[i].oldDegree = getPoint(i).totalDegree();
1494 }
1496 _need_edges_sorting = true;
1497 if ( mod == bool_op_slice ) {
1498 } else {
1499 GetWindings (a, b, mod, false);
1500 }
1501 // Plot(190,70,6,400,400,true,true,true,true);
1503 if (mod == bool_op_symdiff)
1504 {
1505 for (int i = 0; i < numberOfEdges(); i++)
1506 {
1507 swdData[i].leW = swdData[i].leW % 2;
1508 if (swdData[i].leW < 0)
1509 swdData[i].leW = -swdData[i].leW;
1510 swdData[i].riW = swdData[i].riW;
1511 if (swdData[i].riW < 0)
1512 swdData[i].riW = -swdData[i].riW;
1514 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1515 {
1516 eData[i].weight = 1;
1517 }
1518 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1519 {
1520 Inverse (i);
1521 eData[i].weight = 1;
1522 }
1523 else
1524 {
1525 eData[i].weight = 0;
1526 SubEdge (i);
1527 i--;
1528 }
1529 }
1530 }
1531 else if (mod == bool_op_union || mod == bool_op_diff)
1532 {
1533 for (int i = 0; i < numberOfEdges(); i++)
1534 {
1535 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1536 {
1537 eData[i].weight = 1;
1538 }
1539 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1540 {
1541 Inverse (i);
1542 eData[i].weight = 1;
1543 }
1544 else
1545 {
1546 eData[i].weight = 0;
1547 SubEdge (i);
1548 i--;
1549 }
1550 }
1551 }
1552 else if (mod == bool_op_inters)
1553 {
1554 for (int i = 0; i < numberOfEdges(); i++)
1555 {
1556 if (swdData[i].leW > 1 && swdData[i].riW <= 1)
1557 {
1558 eData[i].weight = 1;
1559 }
1560 else if (swdData[i].leW <= 1 && swdData[i].riW > 1)
1561 {
1562 Inverse (i);
1563 eData[i].weight = 1;
1564 }
1565 else
1566 {
1567 eData[i].weight = 0;
1568 SubEdge (i);
1569 i--;
1570 }
1571 }
1572 } else if ( mod == bool_op_cut ) {
1573 // inverser les aretes de la coupe au besoin
1574 for (int i=0;i<numberOfEdges();i++) {
1575 if ( getEdge(i).st < 0 || getEdge(i).en < 0 ) {
1576 if ( i < numberOfEdges()-1 ) {
1577 // decaler les askForWinding
1578 int cp = swsData[numberOfEdges()-1].firstLinkedPoint;
1579 while (cp >= 0) {
1580 pData[cp].askForWindingB = i;
1581 cp = pData[cp].nextLinkedPoint;
1582 }
1583 }
1584 SwapEdges(i,numberOfEdges()-1);
1585 SubEdge(numberOfEdges()-1);
1586 // SubEdge(i);
1587 i--;
1588 } else if ( ebData[i].pathID == cutPathID ) {
1589 swdData[i].leW=swdData[i].leW%2;
1590 swdData[i].riW=swdData[i].riW%2;
1591 if ( swdData[i].leW < swdData[i].riW ) {
1592 Inverse(i);
1593 }
1594 }
1595 }
1596 } else if ( mod == bool_op_slice ) {
1597 // supprimer les aretes de la coupe
1598 int i=numberOfEdges()-1;
1599 for (;i>=0;i--) {
1600 if ( ebData[i].pathID == cutPathID || getEdge(i).st < 0 || getEdge(i).en < 0 ) {
1601 SubEdge(i);
1602 }
1603 }
1604 }
1605 else
1606 {
1607 for (int i = 0; i < numberOfEdges(); i++)
1608 {
1609 if (swdData[i].leW > 0 && swdData[i].riW <= 0)
1610 {
1611 eData[i].weight = 1;
1612 }
1613 else if (swdData[i].leW <= 0 && swdData[i].riW > 0)
1614 {
1615 Inverse (i);
1616 eData[i].weight = 1;
1617 }
1618 else
1619 {
1620 eData[i].weight = 0;
1621 SubEdge (i);
1622 i--;
1623 }
1624 }
1625 }
1627 delete sTree;
1628 sTree = NULL;
1629 delete sEvts;
1630 sEvts = NULL;
1632 if ( mod == bool_op_cut ) {
1633 // on garde le askForWinding
1634 } else {
1635 MakePointData (false);
1636 }
1637 MakeEdgeData (false);
1638 MakeSweepSrcData (false);
1639 MakeSweepDestData (false);
1640 a->CleanupSweep ();
1641 b->CleanupSweep ();
1643 if (directedEulerian(this) == false)
1644 {
1645 // printf( "pas euclidian2");
1646 _pts.clear();
1647 _aretes.clear();
1648 return shape_euler_err;
1649 }
1650 type = shape_polygon;
1651 return 0;
1652 }
1654 // frontend to the TesteIntersection() below
1655 void Shape::TesteIntersection(SweepTree *t, Side s, bool onlyDiff)
1656 {
1657 SweepTree *tt = static_cast<SweepTree*>(t->elem[s]);
1658 if (tt == NULL) {
1659 return;
1660 }
1662 SweepTree *a = (s == LEFT) ? tt : t;
1663 SweepTree *b = (s == LEFT) ? t : tt;
1665 NR::Point atx;
1666 double atl;
1667 double atr;
1668 if (TesteIntersection(a, b, atx, atl, atr, onlyDiff)) {
1669 sEvts->add(a, b, atx, atl, atr);
1670 }
1671 }
1673 // a crucial piece of code: computing intersections between segments
1674 bool
1675 Shape::TesteIntersection (SweepTree * iL, SweepTree * iR, NR::Point &atx, double &atL, double &atR, bool onlyDiff)
1676 {
1677 int lSt = iL->src->getEdge(iL->bord).st, lEn = iL->src->getEdge(iL->bord).en;
1678 int rSt = iR->src->getEdge(iR->bord).st, rEn = iR->src->getEdge(iR->bord).en;
1679 NR::Point ldir, rdir;
1680 ldir = iL->src->eData[iL->bord].rdx;
1681 rdir = iR->src->eData[iR->bord].rdx;
1682 // first, a round of checks to quickly dismiss edge which obviously dont intersect,
1683 // such as having disjoint bounding boxes
1684 if (lSt < lEn)
1685 {
1686 }
1687 else
1688 {
1689 int swap = lSt;
1690 lSt = lEn;
1691 lEn = swap;
1692 ldir = -ldir;
1693 }
1694 if (rSt < rEn)
1695 {
1696 }
1697 else
1698 {
1699 int swap = rSt;
1700 rSt = rEn;
1701 rEn = swap;
1702 rdir = -rdir;
1703 }
1705 if (iL->src->pData[lSt].rx[0] < iL->src->pData[lEn].rx[0])
1706 {
1707 if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
1708 {
1709 if (iL->src->pData[lSt].rx[0] > iR->src->pData[rEn].rx[0])
1710 return false;
1711 if (iL->src->pData[lEn].rx[0] < iR->src->pData[rSt].rx[0])
1712 return false;
1713 }
1714 else
1715 {
1716 if (iL->src->pData[lSt].rx[0] > iR->src->pData[rSt].rx[0])
1717 return false;
1718 if (iL->src->pData[lEn].rx[0] < iR->src->pData[rEn].rx[0])
1719 return false;
1720 }
1721 }
1722 else
1723 {
1724 if (iR->src->pData[rSt].rx[0] < iR->src->pData[rEn].rx[0])
1725 {
1726 if (iL->src->pData[lEn].rx[0] > iR->src->pData[rEn].rx[0])
1727 return false;
1728 if (iL->src->pData[lSt].rx[0] < iR->src->pData[rSt].rx[0])
1729 return false;
1730 }
1731 else
1732 {
1733 if (iL->src->pData[lEn].rx[0] > iR->src->pData[rSt].rx[0])
1734 return false;
1735 if (iL->src->pData[lSt].rx[0] < iR->src->pData[rEn].rx[0])
1736 return false;
1737 }
1738 }
1740 double ang = cross (rdir, ldir);
1741 // ang*=iL->src->eData[iL->bord].isqlength;
1742 // ang*=iR->src->eData[iR->bord].isqlength;
1743 if (ang <= 0) return false; // edges in opposite directions: <-left ... right ->
1744 // they can't intersect
1746 // d'abord tester les bords qui partent d'un meme point
1747 if (iL->src == iR->src && lSt == rSt)
1748 {
1749 if (iL->src == iR->src && lEn == rEn)
1750 return false; // c'est juste un doublon
1751 atx = iL->src->pData[lSt].rx;
1752 atR = atL = -1;
1753 return true; // l'ordre est mauvais
1754 }
1755 if (iL->src == iR->src && lEn == rEn)
1756 return false; // rien a faire=ils vont terminer au meme endroit
1758 // tester si on est dans une intersection multiple
1760 if (onlyDiff && iL->src == iR->src)
1761 return false;
1763 // on reprend les vrais points
1764 lSt = iL->src->getEdge(iL->bord).st;
1765 lEn = iL->src->getEdge(iL->bord).en;
1766 rSt = iR->src->getEdge(iR->bord).st;
1767 rEn = iR->src->getEdge(iR->bord).en;
1769 // compute intersection (if there is one)
1770 // Boissonat anr Preparata said in one paper that double precision floats were sufficient for get single precision
1771 // coordinates for the intersection, if the endpoints are single precision. i hope they're right...
1772 {
1773 NR::Point sDiff, eDiff;
1774 double slDot, elDot;
1775 double srDot, erDot;
1776 sDiff = iL->src->pData[lSt].rx - iR->src->pData[rSt].rx;
1777 eDiff = iL->src->pData[lEn].rx - iR->src->pData[rSt].rx;
1778 srDot = cross (sDiff,rdir);
1779 erDot = cross (eDiff,rdir);
1780 sDiff = iR->src->pData[rSt].rx - iL->src->pData[lSt].rx;
1781 eDiff = iR->src->pData[rEn].rx - iL->src->pData[lSt].rx;
1782 slDot = cross (sDiff,ldir);
1783 elDot = cross (eDiff,ldir);
1785 if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
1786 {
1787 if (srDot == 0)
1788 {
1789 if (lSt < lEn)
1790 {
1791 atx = iL->src->pData[lSt].rx;
1792 atL = 0;
1793 atR = slDot / (slDot - elDot);
1794 return true;
1795 }
1796 else
1797 {
1798 return false;
1799 }
1800 }
1801 else if (erDot == 0)
1802 {
1803 if (lSt > lEn)
1804 {
1805 atx = iL->src->pData[lEn].rx;
1806 atL = 1;
1807 atR = slDot / (slDot - elDot);
1808 return true;
1809 }
1810 else
1811 {
1812 return false;
1813 }
1814 }
1815 if (srDot > 0 && erDot > 0)
1816 {
1817 if (rEn < rSt)
1818 {
1819 if (srDot < erDot)
1820 {
1821 if (lSt < lEn)
1822 {
1823 atx = iL->src->pData[lSt].rx;
1824 atL = 0;
1825 atR = slDot / (slDot - elDot);
1826 return true;
1827 }
1828 }
1829 else
1830 {
1831 if (lEn < lSt)
1832 {
1833 atx = iL->src->pData[lEn].rx;
1834 atL = 1;
1835 atR = slDot / (slDot - elDot);
1836 return true;
1837 }
1838 }
1839 }
1840 }
1841 if (srDot < 0 && erDot < 0)
1842 {
1843 if (rEn > rSt)
1844 {
1845 if (srDot > erDot)
1846 {
1847 if (lSt < lEn)
1848 {
1849 atx = iL->src->pData[lSt].rx;
1850 atL = 0;
1851 atR = slDot / (slDot - elDot);
1852 return true;
1853 }
1854 }
1855 else
1856 {
1857 if (lEn < lSt)
1858 {
1859 atx = iL->src->pData[lEn].rx;
1860 atL = 1;
1861 atR = slDot / (slDot - elDot);
1862 return true;
1863 }
1864 }
1865 }
1866 }
1867 return false;
1868 }
1869 if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
1870 {
1871 if (slDot == 0)
1872 {
1873 if (rSt < rEn)
1874 {
1875 atx = iR->src->pData[rSt].rx;
1876 atR = 0;
1877 atL = srDot / (srDot - erDot);
1878 return true;
1879 }
1880 else
1881 {
1882 return false;
1883 }
1884 }
1885 else if (elDot == 0)
1886 {
1887 if (rSt > rEn)
1888 {
1889 atx = iR->src->pData[rEn].rx;
1890 atR = 1;
1891 atL = srDot / (srDot - erDot);
1892 return true;
1893 }
1894 else
1895 {
1896 return false;
1897 }
1898 }
1899 if (slDot > 0 && elDot > 0)
1900 {
1901 if (lEn > lSt)
1902 {
1903 if (slDot < elDot)
1904 {
1905 if (rSt < rEn)
1906 {
1907 atx = iR->src->pData[rSt].rx;
1908 atR = 0;
1909 atL = srDot / (srDot - erDot);
1910 return true;
1911 }
1912 }
1913 else
1914 {
1915 if (rEn < rSt)
1916 {
1917 atx = iR->src->pData[rEn].rx;
1918 atR = 1;
1919 atL = srDot / (srDot - erDot);
1920 return true;
1921 }
1922 }
1923 }
1924 }
1925 if (slDot < 0 && elDot < 0)
1926 {
1927 if (lEn < lSt)
1928 {
1929 if (slDot > elDot)
1930 {
1931 if (rSt < rEn)
1932 {
1933 atx = iR->src->pData[rSt].rx;
1934 atR = 0;
1935 atL = srDot / (srDot - erDot);
1936 return true;
1937 }
1938 }
1939 else
1940 {
1941 if (rEn < rSt)
1942 {
1943 atx = iR->src->pData[rEn].rx;
1944 atR = 1;
1945 atL = srDot / (srDot - erDot);
1946 return true;
1947 }
1948 }
1949 }
1950 }
1951 return false;
1952 }
1954 /* double slb=slDot-elDot,srb=srDot-erDot;
1955 if ( slb < 0 ) slb=-slb;
1956 if ( srb < 0 ) srb=-srb;*/
1957 if (iL->src->eData[iL->bord].siEd > iR->src->eData[iR->bord].siEd)
1958 {
1959 atx =
1960 (slDot * iR->src->pData[rEn].rx -
1961 elDot * iR->src->pData[rSt].rx) / (slDot - elDot);
1962 }
1963 else
1964 {
1965 atx =
1966 (srDot * iL->src->pData[lEn].rx -
1967 erDot * iL->src->pData[lSt].rx) / (srDot - erDot);
1968 }
1969 atL = srDot / (srDot - erDot);
1970 atR = slDot / (slDot - elDot);
1971 return true;
1972 }
1974 return true;
1975 }
1977 int
1978 Shape::PushIncidence (Shape * a, int cb, int pt, double theta)
1979 {
1980 if (theta < 0 || theta > 1)
1981 return -1;
1983 if (nbInc >= maxInc)
1984 {
1985 maxInc = 2 * nbInc + 1;
1986 iData =
1987 (incidenceData *) g_realloc(iData, maxInc * sizeof (incidenceData));
1988 }
1989 int n = nbInc++;
1990 iData[n].nextInc = a->swsData[cb].firstLinkedPoint;
1991 iData[n].pt = pt;
1992 iData[n].theta = theta;
1993 a->swsData[cb].firstLinkedPoint = n;
1994 return n;
1995 }
1997 int
1998 Shape::CreateIncidence (Shape * a, int no, int nPt)
1999 {
2000 NR::Point adir, diff;
2001 adir = a->eData[no].rdx;
2002 diff = getPoint(nPt).x - a->pData[a->getEdge(no).st].rx;
2003 double t = dot (diff, adir);
2004 t *= a->eData[no].ilength;
2005 return PushIncidence (a, no, nPt, t);
2006 }
2008 int
2009 Shape::Winding (int nPt) const
2010 {
2011 int askTo = pData[nPt].askForWindingB;
2012 if (askTo < 0 || askTo >= numberOfEdges())
2013 return 0;
2014 if (getEdge(askTo).st < getEdge(askTo).en)
2015 {
2016 return swdData[askTo].leW;
2017 }
2018 else
2019 {
2020 return swdData[askTo].riW;
2021 }
2022 return 0;
2023 }
2025 int
2026 Shape::Winding (const NR::Point px) const
2027 {
2028 int lr = 0, ll = 0, rr = 0;
2030 for (int i = 0; i < numberOfEdges(); i++)
2031 {
2032 NR::Point adir, diff, ast, aen;
2033 adir = eData[i].rdx;
2035 ast = pData[getEdge(i).st].rx;
2036 aen = pData[getEdge(i).en].rx;
2038 int nWeight = eData[i].weight;
2040 if (ast[0] < aen[0])
2041 {
2042 if (ast[0] > px[0])
2043 continue;
2044 if (aen[0] < px[0])
2045 continue;
2046 }
2047 else
2048 {
2049 if (ast[0] < px[0])
2050 continue;
2051 if (aen[0] > px[0])
2052 continue;
2053 }
2054 if (ast[0] == px[0])
2055 {
2056 if (ast[1] >= px[1])
2057 continue;
2058 if (aen[0] == px[0])
2059 continue;
2060 if (aen[0] < px[0])
2061 ll += nWeight;
2062 else
2063 rr -= nWeight;
2064 continue;
2065 }
2066 if (aen[0] == px[0])
2067 {
2068 if (aen[1] >= px[1])
2069 continue;
2070 if (ast[0] == px[0])
2071 continue;
2072 if (ast[0] < px[0])
2073 ll -= nWeight;
2074 else
2075 rr += nWeight;
2076 continue;
2077 }
2079 if (ast[1] < aen[1])
2080 {
2081 if (ast[1] >= px[1])
2082 continue;
2083 }
2084 else
2085 {
2086 if (aen[1] >= px[1])
2087 continue;
2088 }
2090 diff = px - ast;
2091 double cote = cross (diff,adir);
2092 if (cote == 0)
2093 continue;
2094 if (cote < 0)
2095 {
2096 if (ast[0] > px[0])
2097 lr += nWeight;
2098 }
2099 else
2100 {
2101 if (ast[0] < px[0])
2102 lr -= nWeight;
2103 }
2104 }
2105 return lr + (ll + rr) / 2;
2106 }
2108 // merging duplicate points and edges
2109 int
2110 Shape::AssemblePoints (int st, int en)
2111 {
2112 if (en > st) {
2113 for (int i = st; i < en; i++) pData[i].oldInd = i;
2114 // SortPoints(st,en-1);
2115 SortPointsByOldInd (st, en - 1); // SortPointsByOldInd() is required here, because of the edges we have
2116 // associated with the point for later computation of winding numbers.
2117 // specifically, we need the first point we treated, it's the only one with a valid
2118 // associated edge (man, that was a nice bug).
2119 for (int i = st; i < en; i++) pData[pData[i].oldInd].newInd = i;
2121 int lastI = st;
2122 for (int i = st; i < en; i++) {
2123 pData[i].pending = lastI++;
2124 if (i > st && getPoint(i - 1).x[0] == getPoint(i).x[0] && getPoint(i - 1).x[1] == getPoint(i).x[1]) {
2125 pData[i].pending = pData[i - 1].pending;
2126 if (pData[pData[i].pending].askForWindingS == NULL) {
2127 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
2128 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
2129 } else {
2130 if (pData[pData[i].pending].askForWindingS == pData[i].askForWindingS
2131 && pData[pData[i].pending].askForWindingB == pData[i].askForWindingB) {
2132 // meme bord, c bon
2133 } else {
2134 // meme point, mais pas le meme bord: ouille!
2135 // il faut prendre le bord le plus a gauche
2136 // en pratique, n'arrive que si 2 maxima sont dans la meme case -> le mauvais choix prend une arete incidente
2137 // au bon choix
2138 // printf("doh");
2139 }
2140 }
2141 lastI--;
2142 } else {
2143 if (i > pData[i].pending) {
2144 _pts[pData[i].pending].x = getPoint(i).x;
2145 pData[pData[i].pending].rx = getPoint(i).x;
2146 pData[pData[i].pending].askForWindingS = pData[i].askForWindingS;
2147 pData[pData[i].pending].askForWindingB = pData[i].askForWindingB;
2148 }
2149 }
2150 }
2151 for (int i = st; i < en; i++) pData[i].newInd = pData[pData[i].newInd].pending;
2152 return lastI;
2153 }
2154 return en;
2155 }
2157 void
2158 Shape::AssemblePoints (Shape * a)
2159 {
2160 if (hasPoints())
2161 {
2162 int lastI = AssemblePoints (0, numberOfPoints());
2164 for (int i = 0; i < a->numberOfEdges(); i++)
2165 {
2166 a->swsData[i].stPt = pData[a->swsData[i].stPt].newInd;
2167 a->swsData[i].enPt = pData[a->swsData[i].enPt].newInd;
2168 }
2169 for (int i = 0; i < nbInc; i++)
2170 iData[i].pt = pData[iData[i].pt].newInd;
2172 _pts.resize(lastI);
2173 }
2174 }
2175 void
2176 Shape::AssembleAretes (FillRule directed)
2177 {
2178 if ( directed == fill_justDont && _has_back_data == false ) {
2179 directed=fill_nonZero;
2180 }
2182 for (int i = 0; i < numberOfPoints(); i++) {
2183 if (getPoint(i).totalDegree() == 2) {
2184 int cb, cc;
2185 cb = getPoint(i).incidentEdge[FIRST];
2186 cc = getPoint(i).incidentEdge[LAST];
2187 bool doublon=false;
2188 if ((getEdge(cb).st == getEdge(cc).st && getEdge(cb).en == getEdge(cc).en)
2189 || (getEdge(cb).st == getEdge(cc).en && getEdge(cb).en == getEdge(cc).en)) doublon=true;
2190 if ( directed == fill_justDont ) {
2191 if ( doublon ) {
2192 if ( ebData[cb].pathID > ebData[cc].pathID ) {
2193 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2194 cb = getPoint(i).incidentEdge[LAST];
2195 } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
2196 if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
2197 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2198 cb = getPoint(i).incidentEdge[LAST];
2199 } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) {
2200 if ( ebData[cb].tSt > ebData[cc].tSt ) {
2201 cc = getPoint(i).incidentEdge[FIRST]; // on swappe pour enlever cc
2202 cb = getPoint(i).incidentEdge[LAST];
2203 }
2204 }
2205 }
2206 }
2207 if ( doublon ) eData[cc].weight = 0;
2208 } else {
2209 }
2210 if ( doublon ) {
2211 if (getEdge(cb).st == getEdge(cc).st) {
2212 eData[cb].weight += eData[cc].weight;
2213 } else {
2214 eData[cb].weight -= eData[cc].weight;
2215 }
2216 eData[cc].weight = 0;
2218 if (swsData[cc].firstLinkedPoint >= 0) {
2219 int cp = swsData[cc].firstLinkedPoint;
2220 while (cp >= 0) {
2221 pData[cp].askForWindingB = cb;
2222 cp = pData[cp].nextLinkedPoint;
2223 }
2224 if (swsData[cb].firstLinkedPoint < 0) {
2225 swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
2226 } else {
2227 int ncp = swsData[cb].firstLinkedPoint;
2228 while (pData[ncp].nextLinkedPoint >= 0) {
2229 ncp = pData[ncp].nextLinkedPoint;
2230 }
2231 pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
2232 }
2233 }
2235 DisconnectStart (cc);
2236 DisconnectEnd (cc);
2237 if (numberOfEdges() > 1) {
2238 int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
2239 while (cp >= 0) {
2240 pData[cp].askForWindingB = cc;
2241 cp = pData[cp].nextLinkedPoint;
2242 }
2243 }
2244 SwapEdges (cc, numberOfEdges() - 1);
2245 if (cb == numberOfEdges() - 1) {
2246 cb = cc;
2247 }
2248 _aretes.pop_back();
2249 }
2250 } else {
2251 int cb;
2252 cb = getPoint(i).incidentEdge[FIRST];
2253 while (cb >= 0 && cb < numberOfEdges()) {
2254 int other = Other (i, cb);
2255 int cc;
2256 cc = getPoint(i).incidentEdge[FIRST];
2257 while (cc >= 0 && cc < numberOfEdges()) {
2258 int ncc = NextAt (i, cc);
2259 bool doublon=false;
2260 if (cc != cb && Other (i, cc) == other ) doublon=true;
2261 if ( directed == fill_justDont ) {
2262 if ( doublon ) {
2263 if ( ebData[cb].pathID > ebData[cc].pathID ) {
2264 doublon=false;
2265 } else if ( ebData[cb].pathID == ebData[cc].pathID ) {
2266 if ( ebData[cb].pieceID > ebData[cc].pieceID ) {
2267 doublon=false;
2268 } else if ( ebData[cb].pieceID == ebData[cc].pieceID ) {
2269 if ( ebData[cb].tSt > ebData[cc].tSt ) {
2270 doublon=false;
2271 }
2272 }
2273 }
2274 }
2275 if ( doublon ) eData[cc].weight = 0;
2276 } else {
2277 }
2278 if ( doublon ) {
2279 // if (cc != cb && Other (i, cc) == other) {
2280 // doublon
2281 if (getEdge(cb).st == getEdge(cc).st) {
2282 eData[cb].weight += eData[cc].weight;
2283 } else {
2284 eData[cb].weight -= eData[cc].weight;
2285 }
2286 eData[cc].weight = 0;
2288 if (swsData[cc].firstLinkedPoint >= 0) {
2289 int cp = swsData[cc].firstLinkedPoint;
2290 while (cp >= 0) {
2291 pData[cp].askForWindingB = cb;
2292 cp = pData[cp].nextLinkedPoint;
2293 }
2294 if (swsData[cb].firstLinkedPoint < 0) {
2295 swsData[cb].firstLinkedPoint = swsData[cc].firstLinkedPoint;
2296 } else {
2297 int ncp = swsData[cb].firstLinkedPoint;
2298 while (pData[ncp].nextLinkedPoint >= 0) {
2299 ncp = pData[ncp].nextLinkedPoint;
2300 }
2301 pData[ncp].nextLinkedPoint = swsData[cc].firstLinkedPoint;
2302 }
2303 }
2305 DisconnectStart (cc);
2306 DisconnectEnd (cc);
2307 if (numberOfEdges() > 1) {
2308 int cp = swsData[numberOfEdges() - 1].firstLinkedPoint;
2309 while (cp >= 0) {
2310 pData[cp].askForWindingB = cc;
2311 cp = pData[cp].nextLinkedPoint;
2312 }
2313 }
2314 SwapEdges (cc, numberOfEdges() - 1);
2315 if (cb == numberOfEdges() - 1) {
2316 cb = cc;
2317 }
2318 if (ncc == numberOfEdges() - 1) {
2319 ncc = cc;
2320 }
2321 _aretes.pop_back();
2322 }
2323 cc = ncc;
2324 }
2325 cb = NextAt (i, cb);
2326 }
2327 }
2328 }
2330 if ( directed == fill_justDont ) {
2331 for (int i = 0; i < numberOfEdges(); i++) {
2332 if (eData[i].weight == 0) {
2333 // SubEdge(i);
2334 // i--;
2335 } else {
2336 if (eData[i].weight < 0) Inverse (i);
2337 }
2338 }
2339 } else {
2340 for (int i = 0; i < numberOfEdges(); i++) {
2341 if (eData[i].weight == 0) {
2342 // SubEdge(i);
2343 // i--;
2344 } else {
2345 if (eData[i].weight < 0) Inverse (i);
2346 }
2347 }
2348 }
2349 }
2350 void
2351 Shape::GetWindings (Shape * a, Shape * b, BooleanOp mod, bool brutal)
2352 {
2353 // preparation du parcours
2354 for (int i = 0; i < numberOfEdges(); i++)
2355 {
2356 swdData[i].misc = 0;
2357 swdData[i].precParc = swdData[i].suivParc = -1;
2358 }
2360 // chainage
2361 SortEdges ();
2363 int searchInd = 0;
2365 int lastPtUsed = 0;
2366 do
2367 {
2368 int startBord = -1;
2369 int outsideW = 0;
2370 {
2371 int fi = 0;
2372 for (fi = lastPtUsed; fi < numberOfPoints(); fi++)
2373 {
2374 if (getPoint(fi).incidentEdge[FIRST] >= 0 && swdData[getPoint(fi).incidentEdge[FIRST]].misc == 0)
2375 break;
2376 }
2377 lastPtUsed = fi + 1;
2378 if (fi < numberOfPoints())
2379 {
2380 int bestB = getPoint(fi).incidentEdge[FIRST];
2381 if (bestB >= 0)
2382 {
2383 startBord = bestB;
2384 if (fi == 0)
2385 {
2386 outsideW = 0;
2387 }
2388 else
2389 {
2390 if (brutal)
2391 {
2392 outsideW = Winding (getPoint(fi).x);
2393 }
2394 else
2395 {
2396 outsideW = Winding (fi);
2397 }
2398 }
2399 if ( getPoint(fi).totalDegree() == 1 ) {
2400 if ( fi == getEdge(startBord).en ) {
2401 if ( eData[startBord].weight == 0 ) {
2402 // on se contente d'inverser
2403 Inverse(startBord);
2404 } else {
2405 // on passe le askForWinding (sinon ca va rester startBord)
2406 pData[getEdge(startBord).st].askForWindingB=pData[getEdge(startBord).en].askForWindingB;
2407 }
2408 }
2409 }
2410 if (getEdge(startBord).en == fi)
2411 outsideW += eData[startBord].weight;
2412 }
2413 }
2414 }
2415 if (startBord >= 0)
2416 {
2417 // parcours en profondeur pour mettre les leF et riF a leurs valeurs
2418 swdData[startBord].misc = (void *) 1;
2419 swdData[startBord].leW = outsideW;
2420 swdData[startBord].riW = outsideW - eData[startBord].weight;
2421 // if ( doDebug ) printf("part de %d\n",startBord);
2422 int curBord = startBord;
2423 bool curDir = true;
2424 swdData[curBord].precParc = -1;
2425 swdData[curBord].suivParc = -1;
2426 do
2427 {
2428 int cPt;
2429 if (curDir)
2430 cPt = getEdge(curBord).en;
2431 else
2432 cPt = getEdge(curBord).st;
2433 int nb = curBord;
2434 // if ( doDebug ) printf("de curBord= %d avec leF= %d et riF= %d -> ",curBord,swdData[curBord].leW,swdData[curBord].riW);
2435 do
2436 {
2437 int nnb = -1;
2438 if (getEdge(nb).en == cPt)
2439 {
2440 outsideW = swdData[nb].riW;
2441 nnb = CyclePrevAt (cPt, nb);
2442 }
2443 else
2444 {
2445 outsideW = swdData[nb].leW;
2446 nnb = CyclePrevAt (cPt, nb);
2447 }
2448 if (nnb == nb)
2449 {
2450 // cul-de-sac
2451 nb = -1;
2452 break;
2453 }
2454 nb = nnb;
2455 }
2456 while (nb >= 0 && nb != curBord && swdData[nb].misc != 0);
2457 if (nb < 0 || nb == curBord)
2458 {
2459 // retour en arriere
2460 int oPt;
2461 if (curDir)
2462 oPt = getEdge(curBord).st;
2463 else
2464 oPt = getEdge(curBord).en;
2465 curBord = swdData[curBord].precParc;
2466 // if ( doDebug ) printf("retour vers %d\n",curBord);
2467 if (curBord < 0)
2468 break;
2469 if (oPt == getEdge(curBord).en)
2470 curDir = true;
2471 else
2472 curDir = false;
2473 }
2474 else
2475 {
2476 swdData[nb].misc = (void *) 1;
2477 swdData[nb].ind = searchInd++;
2478 if (cPt == getEdge(nb).st)
2479 {
2480 swdData[nb].riW = outsideW;
2481 swdData[nb].leW = outsideW + eData[nb].weight;
2482 }
2483 else
2484 {
2485 swdData[nb].leW = outsideW;
2486 swdData[nb].riW = outsideW - eData[nb].weight;
2487 }
2488 swdData[nb].precParc = curBord;
2489 swdData[curBord].suivParc = nb;
2490 curBord = nb;
2491 // if ( doDebug ) printf("suite %d\n",curBord);
2492 if (cPt == getEdge(nb).en)
2493 curDir = false;
2494 else
2495 curDir = true;
2496 }
2497 }
2498 while (1 /*swdData[curBord].precParc >= 0 */ );
2499 // fin du cas non-oriente
2500 }
2501 }
2502 while (lastPtUsed < numberOfPoints());
2503 // fflush(stdout);
2504 }
2506 bool
2507 Shape::TesteIntersection (Shape * ils, Shape * irs, int ilb, int irb,
2508 NR::Point &atx, double &atL, double &atR,
2509 bool onlyDiff)
2510 {
2511 int lSt = ils->getEdge(ilb).st, lEn = ils->getEdge(ilb).en;
2512 int rSt = irs->getEdge(irb).st, rEn = irs->getEdge(irb).en;
2513 if (lSt == rSt || lSt == rEn)
2514 {
2515 return false;
2516 }
2517 if (lEn == rSt || lEn == rEn)
2518 {
2519 return false;
2520 }
2522 NR::Point ldir, rdir;
2523 ldir = ils->eData[ilb].rdx;
2524 rdir = irs->eData[irb].rdx;
2526 double il = ils->pData[lSt].rx[0], it = ils->pData[lSt].rx[1], ir =
2527 ils->pData[lEn].rx[0], ib = ils->pData[lEn].rx[1];
2528 if (il > ir)
2529 {
2530 double swf = il;
2531 il = ir;
2532 ir = swf;
2533 }
2534 if (it > ib)
2535 {
2536 double swf = it;
2537 it = ib;
2538 ib = swf;
2539 }
2540 double jl = irs->pData[rSt].rx[0], jt = irs->pData[rSt].rx[1], jr =
2541 irs->pData[rEn].rx[0], jb = irs->pData[rEn].rx[1];
2542 if (jl > jr)
2543 {
2544 double swf = jl;
2545 jl = jr;
2546 jr = swf;
2547 }
2548 if (jt > jb)
2549 {
2550 double swf = jt;
2551 jt = jb;
2552 jb = swf;
2553 }
2555 if (il > jr || it > jb || ir < jl || ib < jt)
2556 return false;
2558 // pre-test
2559 {
2560 NR::Point sDiff, eDiff;
2561 double slDot, elDot;
2562 double srDot, erDot;
2563 sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
2564 eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
2565 srDot = cross (sDiff,rdir );
2566 erDot = cross (eDiff,rdir );
2567 if ((srDot >= 0 && erDot >= 0) || (srDot <= 0 && erDot <= 0))
2568 return false;
2570 sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
2571 eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
2572 slDot = cross (sDiff,ldir );
2573 elDot = cross (eDiff,ldir);
2574 if ((slDot >= 0 && elDot >= 0) || (slDot <= 0 && elDot <= 0))
2575 return false;
2577 double slb = slDot - elDot, srb = srDot - erDot;
2578 if (slb < 0)
2579 slb = -slb;
2580 if (srb < 0)
2581 srb = -srb;
2582 if (slb > srb)
2583 {
2584 atx =
2585 (slDot * irs->pData[rEn].rx - elDot * irs->pData[rSt].rx) / (slDot -
2586 elDot);
2587 }
2588 else
2589 {
2590 atx =
2591 (srDot * ils->pData[lEn].rx - erDot * ils->pData[lSt].rx) / (srDot -
2592 erDot);
2593 }
2594 atL = srDot / (srDot - erDot);
2595 atR = slDot / (slDot - elDot);
2596 return true;
2597 }
2599 // a mettre en double precision pour des resultats exacts
2600 NR::Point usvs;
2601 usvs = irs->pData[rSt].rx - ils->pData[lSt].rx;
2603 // pas sur de l'ordre des coefs de m
2604 NR::Matrix m(ldir[0], ldir[1],
2605 rdir[0], rdir[1],
2606 0, 0);
2607 double det = m.det();
2609 double tdet = det * ils->eData[ilb].isqlength * irs->eData[irb].isqlength;
2611 if (tdet > -0.0001 && tdet < 0.0001)
2612 { // ces couillons de vecteurs sont colineaires
2613 NR::Point sDiff, eDiff;
2614 double sDot, eDot;
2615 sDiff = ils->pData[lSt].rx - irs->pData[rSt].rx;
2616 eDiff = ils->pData[lEn].rx - irs->pData[rSt].rx;
2617 sDot = cross (sDiff,rdir );
2618 eDot = cross (eDiff,rdir);
2620 atx =
2621 (sDot * irs->pData[lEn].rx - eDot * irs->pData[lSt].rx) / (sDot -
2622 eDot);
2623 atL = sDot / (sDot - eDot);
2625 sDiff = irs->pData[rSt].rx - ils->pData[lSt].rx;
2626 eDiff = irs->pData[rEn].rx - ils->pData[lSt].rx;
2627 sDot = cross (sDiff,ldir );
2628 eDot = cross (eDiff,ldir );
2630 atR = sDot / (sDot - eDot);
2632 return true;
2633 }
2635 // plus de colinearite ni d'extremites en commun
2636 m[1] = -m[1];
2637 m[2] = -m[2];
2638 {
2639 double swap = m[0];
2640 m[0] = m[3];
2641 m[3] = swap;
2642 }
2644 atL = (m[0]* usvs[0] + m[1] * usvs[1]) / det;
2645 atR = -(m[2] * usvs[0] + m[3] * usvs[1]) / det;
2646 atx = ils->pData[lSt].rx + atL * ldir;
2649 return true;
2650 }
2652 bool
2653 Shape::TesteAdjacency (Shape * a, int no, const NR::Point atx, int nPt,
2654 bool push)
2655 {
2656 if (nPt == a->swsData[no].stPt || nPt == a->swsData[no].enPt)
2657 return false;
2659 NR::Point adir, diff, ast, aen, diff1, diff2, diff3, diff4;
2661 ast = a->pData[a->getEdge(no).st].rx;
2662 aen = a->pData[a->getEdge(no).en].rx;
2664 adir = a->eData[no].rdx;
2666 double sle = a->eData[no].length;
2667 double ile = a->eData[no].ilength;
2669 diff = atx - ast;
2671 double e = IHalfRound ((cross (diff,adir)) * a->eData[no].isqlength);
2672 if (-3 < e && e < 3)
2673 {
2674 double rad = HalfRound (0.501); // when using single precision, 0.505 is better (0.5 would be the correct value,
2675 // but it produces lots of bugs)
2676 diff1[0] = diff[0] - rad;
2677 diff1[1] = diff[1] - rad;
2678 diff2[0] = diff[0] + rad;
2679 diff2[1] = diff[1] - rad;
2680 diff3[0] = diff[0] + rad;
2681 diff3[1] = diff[1] + rad;
2682 diff4[0] = diff[0] - rad;
2683 diff4[1] = diff[1] + rad;
2684 double di1, di2;
2685 bool adjacent = false;
2686 di1 = cross (diff1,adir);
2687 di2 = cross (diff3,adir);
2688 if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
2689 {
2690 adjacent = true;
2691 }
2692 else
2693 {
2694 di1 = cross ( diff2,adir);
2695 di2 = cross (diff4,adir);
2696 if ((di1 < 0 && di2 > 0) || (di1 > 0 && di2 < 0))
2697 {
2698 adjacent = true;
2699 }
2700 }
2701 if (adjacent)
2702 {
2703 double t = dot (diff, adir);
2704 if (t > 0 && t < sle)
2705 {
2706 if (push)
2707 {
2708 t *= ile;
2709 PushIncidence (a, no, nPt, t);
2710 }
2711 return true;
2712 }
2713 }
2714 }
2715 return false;
2716 }
2718 void
2719 Shape::CheckAdjacencies (int lastPointNo, int lastChgtPt, Shape * shapeHead,
2720 int edgeHead)
2721 {
2722 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
2723 {
2724 int chLeN = chgts[cCh].ptNo;
2725 int chRiN = chgts[cCh].ptNo;
2726 if (chgts[cCh].src)
2727 {
2728 Shape *lS = chgts[cCh].src;
2729 int lB = chgts[cCh].bord;
2730 int lftN = lS->swsData[lB].leftRnd;
2731 int rgtN = lS->swsData[lB].rightRnd;
2732 if (lftN < chLeN)
2733 chLeN = lftN;
2734 if (rgtN > chRiN)
2735 chRiN = rgtN;
2736 // for (int n=lftN;n<=rgtN;n++) CreateIncidence(lS,lB,n);
2737 for (int n = lftN - 1; n >= lastChgtPt; n--)
2738 {
2739 if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
2740 false)
2741 break;
2742 lS->swsData[lB].leftRnd = n;
2743 }
2744 for (int n = rgtN + 1; n < lastPointNo; n++)
2745 {
2746 if (TesteAdjacency (lS, lB, getPoint(n).x, n, false) ==
2747 false)
2748 break;
2749 lS->swsData[lB].rightRnd = n;
2750 }
2751 }
2752 if (chgts[cCh].osrc)
2753 {
2754 Shape *rS = chgts[cCh].osrc;
2755 int rB = chgts[cCh].obord;
2756 int lftN = rS->swsData[rB].leftRnd;
2757 int rgtN = rS->swsData[rB].rightRnd;
2758 if (lftN < chLeN)
2759 chLeN = lftN;
2760 if (rgtN > chRiN)
2761 chRiN = rgtN;
2762 // for (int n=lftN;n<=rgtN;n++) CreateIncidence(rS,rB,n);
2763 for (int n = lftN - 1; n >= lastChgtPt; n--)
2764 {
2765 if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
2766 false)
2767 break;
2768 rS->swsData[rB].leftRnd = n;
2769 }
2770 for (int n = rgtN + 1; n < lastPointNo; n++)
2771 {
2772 if (TesteAdjacency (rS, rB, getPoint(n).x, n, false) ==
2773 false)
2774 break;
2775 rS->swsData[rB].rightRnd = n;
2776 }
2777 }
2778 if (chgts[cCh].lSrc)
2779 {
2780 if (chgts[cCh].lSrc->swsData[chgts[cCh].lBrd].leftRnd < lastChgtPt)
2781 {
2782 Shape *nSrc = chgts[cCh].lSrc;
2783 int nBrd = chgts[cCh].lBrd /*,nNo=chgts[cCh].ptNo */ ;
2784 bool hit;
2786 do
2787 {
2788 hit = false;
2789 for (int n = chRiN; n >= chLeN; n--)
2790 {
2791 if (TesteAdjacency
2792 (nSrc, nBrd, getPoint(n).x, n, false))
2793 {
2794 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2795 {
2796 nSrc->swsData[nBrd].leftRnd = n;
2797 nSrc->swsData[nBrd].rightRnd = n;
2798 }
2799 else
2800 {
2801 if (n < nSrc->swsData[nBrd].leftRnd)
2802 nSrc->swsData[nBrd].leftRnd = n;
2803 if (n > nSrc->swsData[nBrd].rightRnd)
2804 nSrc->swsData[nBrd].rightRnd = n;
2805 }
2806 hit = true;
2807 }
2808 }
2809 for (int n = chLeN - 1; n >= lastChgtPt; n--)
2810 {
2811 if (TesteAdjacency
2812 (nSrc, nBrd, getPoint(n).x, n, false) == false)
2813 break;
2814 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2815 {
2816 nSrc->swsData[nBrd].leftRnd = n;
2817 nSrc->swsData[nBrd].rightRnd = n;
2818 }
2819 else
2820 {
2821 if (n < nSrc->swsData[nBrd].leftRnd)
2822 nSrc->swsData[nBrd].leftRnd = n;
2823 if (n > nSrc->swsData[nBrd].rightRnd)
2824 nSrc->swsData[nBrd].rightRnd = n;
2825 }
2826 hit = true;
2827 }
2828 if (hit)
2829 {
2830 SweepTree *node =
2831 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
2832 if (node == NULL)
2833 break;
2834 node = static_cast < SweepTree * >(node->elem[LEFT]);
2835 if (node == NULL)
2836 break;
2837 nSrc = node->src;
2838 nBrd = node->bord;
2839 if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
2840 break;
2841 }
2842 }
2843 while (hit);
2845 }
2846 }
2847 if (chgts[cCh].rSrc)
2848 {
2849 if (chgts[cCh].rSrc->swsData[chgts[cCh].rBrd].leftRnd < lastChgtPt)
2850 {
2851 Shape *nSrc = chgts[cCh].rSrc;
2852 int nBrd = chgts[cCh].rBrd /*,nNo=chgts[cCh].ptNo */ ;
2853 bool hit;
2854 do
2855 {
2856 hit = false;
2857 for (int n = chLeN; n <= chRiN; n++)
2858 {
2859 if (TesteAdjacency
2860 (nSrc, nBrd, getPoint(n).x, n, false))
2861 {
2862 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2863 {
2864 nSrc->swsData[nBrd].leftRnd = n;
2865 nSrc->swsData[nBrd].rightRnd = n;
2866 }
2867 else
2868 {
2869 if (n < nSrc->swsData[nBrd].leftRnd)
2870 nSrc->swsData[nBrd].leftRnd = n;
2871 if (n > nSrc->swsData[nBrd].rightRnd)
2872 nSrc->swsData[nBrd].rightRnd = n;
2873 }
2874 hit = true;
2875 }
2876 }
2877 for (int n = chRiN + 1; n < lastPointNo; n++)
2878 {
2879 if (TesteAdjacency
2880 (nSrc, nBrd, getPoint(n).x, n, false) == false)
2881 break;
2882 if (nSrc->swsData[nBrd].leftRnd < lastChgtPt)
2883 {
2884 nSrc->swsData[nBrd].leftRnd = n;
2885 nSrc->swsData[nBrd].rightRnd = n;
2886 }
2887 else
2888 {
2889 if (n < nSrc->swsData[nBrd].leftRnd)
2890 nSrc->swsData[nBrd].leftRnd = n;
2891 if (n > nSrc->swsData[nBrd].rightRnd)
2892 nSrc->swsData[nBrd].rightRnd = n;
2893 }
2894 hit = true;
2895 }
2896 if (hit)
2897 {
2898 SweepTree *node =
2899 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
2900 if (node == NULL)
2901 break;
2902 node = static_cast < SweepTree * >(node->elem[RIGHT]);
2903 if (node == NULL)
2904 break;
2905 nSrc = node->src;
2906 nBrd = node->bord;
2907 if (nSrc->swsData[nBrd].leftRnd >= lastChgtPt)
2908 break;
2909 }
2910 }
2911 while (hit);
2912 }
2913 }
2914 }
2915 }
2918 void Shape::AddChgt(int lastPointNo, int lastChgtPt, Shape * &shapeHead,
2919 int &edgeHead, sTreeChangeType type, Shape * lS, int lB, Shape * rS,
2920 int rB)
2921 {
2922 sTreeChange c;
2923 c.ptNo = lastPointNo;
2924 c.type = type;
2925 c.src = lS;
2926 c.bord = lB;
2927 c.osrc = rS;
2928 c.obord = rB;
2929 chgts.push_back(c);
2930 const int nCh = chgts.size() - 1;
2932 /* FIXME: this looks like a cut and paste job */
2934 if (lS) {
2935 SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
2936 if (lE && lE->elem[LEFT]) {
2937 SweepTree *llE = static_cast < SweepTree * >(lE->elem[LEFT]);
2938 chgts[nCh].lSrc = llE->src;
2939 chgts[nCh].lBrd = llE->bord;
2940 } else {
2941 chgts[nCh].lSrc = NULL;
2942 chgts[nCh].lBrd = -1;
2943 }
2945 if (lS->swsData[lB].leftRnd < lastChgtPt) {
2946 lS->swsData[lB].leftRnd = lastPointNo;
2947 lS->swsData[lB].nextSh = shapeHead;
2948 lS->swsData[lB].nextBo = edgeHead;
2949 edgeHead = lB;
2950 shapeHead = lS;
2951 } else {
2952 int old = lS->swsData[lB].leftRnd;
2953 if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
2954 lS->swsData[lB].leftRnd = lastPointNo;
2955 }
2956 }
2957 if (lS->swsData[lB].rightRnd < lastChgtPt) {
2958 lS->swsData[lB].rightRnd = lastPointNo;
2959 } else {
2960 int old = lS->swsData[lB].rightRnd;
2961 if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
2962 lS->swsData[lB].rightRnd = lastPointNo;
2963 }
2964 }
2966 if (rS) {
2967 SweepTree *rE = static_cast < SweepTree * >(rS->swsData[rB].misc);
2968 if (rE->elem[RIGHT]) {
2969 SweepTree *rrE = static_cast < SweepTree * >(rE->elem[RIGHT]);
2970 chgts[nCh].rSrc = rrE->src;
2971 chgts[nCh].rBrd = rrE->bord;
2972 } else {
2973 chgts[nCh].rSrc = NULL;
2974 chgts[nCh].rBrd = -1;
2975 }
2977 if (rS->swsData[rB].leftRnd < lastChgtPt) {
2978 rS->swsData[rB].leftRnd = lastPointNo;
2979 rS->swsData[rB].nextSh = shapeHead;
2980 rS->swsData[rB].nextBo = edgeHead;
2981 edgeHead = rB;
2982 shapeHead = rS;
2983 } else {
2984 int old = rS->swsData[rB].leftRnd;
2985 if (getPoint(old).x[0] > getPoint(lastPointNo).x[0]) {
2986 rS->swsData[rB].leftRnd = lastPointNo;
2987 }
2988 }
2989 if (rS->swsData[rB].rightRnd < lastChgtPt) {
2990 rS->swsData[rB].rightRnd = lastPointNo;
2991 } else {
2992 int old = rS->swsData[rB].rightRnd;
2993 if (getPoint(old).x[0] < getPoint(lastPointNo).x[0])
2994 rS->swsData[rB].rightRnd = lastPointNo;
2995 }
2996 } else {
2997 SweepTree *lE = static_cast < SweepTree * >(lS->swsData[lB].misc);
2998 if (lE && lE->elem[RIGHT]) {
2999 SweepTree *rlE = static_cast < SweepTree * >(lE->elem[RIGHT]);
3000 chgts[nCh].rSrc = rlE->src;
3001 chgts[nCh].rBrd = rlE->bord;
3002 } else {
3003 chgts[nCh].rSrc = NULL;
3004 chgts[nCh].rBrd = -1;
3005 }
3006 }
3007 }
3009 // is this a debug function? It's calling localized "printf" ...
3010 void
3011 Shape::Validate (void)
3012 {
3013 for (int i = 0; i < numberOfPoints(); i++)
3014 {
3015 pData[i].rx = getPoint(i).x;
3016 }
3017 for (int i = 0; i < numberOfEdges(); i++)
3018 {
3019 eData[i].rdx = getEdge(i).dx;
3020 }
3021 for (int i = 0; i < numberOfEdges(); i++)
3022 {
3023 for (int j = i + 1; j < numberOfEdges(); j++)
3024 {
3025 NR::Point atx;
3026 double atL, atR;
3027 if (TesteIntersection (this, this, i, j, atx, atL, atR, false))
3028 {
3029 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]);
3030 }
3031 }
3032 }
3033 fflush (stdout);
3034 }
3036 void
3037 Shape::CheckEdges (int lastPointNo, int lastChgtPt, Shape * a, Shape * b,
3038 BooleanOp mod)
3039 {
3041 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
3042 {
3043 if (chgts[cCh].type == 0)
3044 {
3045 Shape *lS = chgts[cCh].src;
3046 int lB = chgts[cCh].bord;
3047 lS->swsData[lB].curPoint = chgts[cCh].ptNo;
3048 }
3049 }
3050 for (unsigned int cCh = 0; cCh < chgts.size(); cCh++)
3051 {
3052 // int chLeN=chgts[cCh].ptNo;
3053 // int chRiN=chgts[cCh].ptNo;
3054 if (chgts[cCh].src)
3055 {
3056 Shape *lS = chgts[cCh].src;
3057 int lB = chgts[cCh].bord;
3058 Avance (lastPointNo, lastChgtPt, lS, lB, a, b, mod);
3059 }
3060 if (chgts[cCh].osrc)
3061 {
3062 Shape *rS = chgts[cCh].osrc;
3063 int rB = chgts[cCh].obord;
3064 Avance (lastPointNo, lastChgtPt, rS, rB, a, b, mod);
3065 }
3066 if (chgts[cCh].lSrc)
3067 {
3068 Shape *nSrc = chgts[cCh].lSrc;
3069 int nBrd = chgts[cCh].lBrd;
3070 while (nSrc->swsData[nBrd].leftRnd >=
3071 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
3072 {
3073 Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
3075 SweepTree *node =
3076 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
3077 if (node == NULL)
3078 break;
3079 node = static_cast < SweepTree * >(node->elem[LEFT]);
3080 if (node == NULL)
3081 break;
3082 nSrc = node->src;
3083 nBrd = node->bord;
3084 }
3085 }
3086 if (chgts[cCh].rSrc)
3087 {
3088 Shape *nSrc = chgts[cCh].rSrc;
3089 int nBrd = chgts[cCh].rBrd;
3090 while (nSrc->swsData[nBrd].rightRnd >=
3091 lastChgtPt /*&& nSrc->swsData[nBrd].doneTo < lastChgtPt */ )
3092 {
3093 Avance (lastPointNo, lastChgtPt, nSrc, nBrd, a, b, mod);
3095 SweepTree *node =
3096 static_cast < SweepTree * >(nSrc->swsData[nBrd].misc);
3097 if (node == NULL)
3098 break;
3099 node = static_cast < SweepTree * >(node->elem[RIGHT]);
3100 if (node == NULL)
3101 break;
3102 nSrc = node->src;
3103 nBrd = node->bord;
3104 }
3105 }
3106 }
3107 }
3109 void
3110 Shape::Avance (int lastPointNo, int lastChgtPt, Shape * lS, int lB, Shape * a,
3111 Shape * b, BooleanOp mod)
3112 {
3113 double dd = HalfRound (1);
3114 bool avoidDiag = false;
3115 // if ( lastChgtPt > 0 && pts[lastChgtPt-1].y+dd == pts[lastChgtPt].y ) avoidDiag=true;
3117 bool direct = true;
3118 if (lS == b && (mod == bool_op_diff || mod == bool_op_symdiff))
3119 direct = false;
3120 int lftN = lS->swsData[lB].leftRnd;
3121 int rgtN = lS->swsData[lB].rightRnd;
3122 if (lS->swsData[lB].doneTo < lastChgtPt)
3123 {
3124 int lp = lS->swsData[lB].curPoint;
3125 if (lp >= 0 && getPoint(lp).x[1] + dd == getPoint(lastChgtPt).x[1])
3126 avoidDiag = true;
3127 if (lS->eData[lB].rdx[1] == 0)
3128 {
3129 // tjs de gauche a droite et pas de diagonale
3130 if (lS->eData[lB].rdx[0] >= 0)
3131 {
3132 for (int p = lftN; p <= rgtN; p++)
3133 {
3134 DoEdgeTo (lS, lB, p, direct, true);
3135 lp = p;
3136 }
3137 }
3138 else
3139 {
3140 for (int p = lftN; p <= rgtN; p++)
3141 {
3142 DoEdgeTo (lS, lB, p, direct, false);
3143 lp = p;
3144 }
3145 }
3146 }
3147 else if (lS->eData[lB].rdx[1] > 0)
3148 {
3149 if (lS->eData[lB].rdx[0] >= 0)
3150 {
3152 for (int p = lftN; p <= rgtN; p++)
3153 {
3154 if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
3155 {
3156 if (lftN > 0 && lftN - 1 >= lastChgtPt
3157 && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
3158 {
3159 DoEdgeTo (lS, lB, lftN - 1, direct, true);
3160 DoEdgeTo (lS, lB, lftN, direct, true);
3161 }
3162 else
3163 {
3164 DoEdgeTo (lS, lB, lftN, direct, true);
3165 }
3166 }
3167 else
3168 {
3169 DoEdgeTo (lS, lB, p, direct, true);
3170 }
3171 lp = p;
3172 }
3173 }
3174 else
3175 {
3177 for (int p = rgtN; p >= lftN; p--)
3178 {
3179 if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
3180 {
3181 if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
3182 && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
3183 {
3184 DoEdgeTo (lS, lB, rgtN + 1, direct, true);
3185 DoEdgeTo (lS, lB, rgtN, direct, true);
3186 }
3187 else
3188 {
3189 DoEdgeTo (lS, lB, rgtN, direct, true);
3190 }
3191 }
3192 else
3193 {
3194 DoEdgeTo (lS, lB, p, direct, true);
3195 }
3196 lp = p;
3197 }
3198 }
3199 }
3200 else
3201 {
3202 if (lS->eData[lB].rdx[0] >= 0)
3203 {
3205 for (int p = rgtN; p >= lftN; p--)
3206 {
3207 if (avoidDiag && p == rgtN && getPoint(rgtN).x[0] == getPoint(lp).x[0] - dd)
3208 {
3209 if (rgtN < numberOfPoints() && rgtN + 1 < lastPointNo
3210 && getPoint(rgtN + 1).x[0] == getPoint(lp).x[0])
3211 {
3212 DoEdgeTo (lS, lB, rgtN + 1, direct, false);
3213 DoEdgeTo (lS, lB, rgtN, direct, false);
3214 }
3215 else
3216 {
3217 DoEdgeTo (lS, lB, rgtN, direct, false);
3218 }
3219 }
3220 else
3221 {
3222 DoEdgeTo (lS, lB, p, direct, false);
3223 }
3224 lp = p;
3225 }
3226 }
3227 else
3228 {
3230 for (int p = lftN; p <= rgtN; p++)
3231 {
3232 if (avoidDiag && p == lftN && getPoint(lftN).x[0] == getPoint(lp).x[0] + dd)
3233 {
3234 if (lftN > 0 && lftN - 1 >= lastChgtPt
3235 && getPoint(lftN - 1).x[0] == getPoint(lp).x[0])
3236 {
3237 DoEdgeTo (lS, lB, lftN - 1, direct, false);
3238 DoEdgeTo (lS, lB, lftN, direct, false);
3239 }
3240 else
3241 {
3242 DoEdgeTo (lS, lB, lftN, direct, false);
3243 }
3244 }
3245 else
3246 {
3247 DoEdgeTo (lS, lB, p, direct, false);
3248 }
3249 lp = p;
3250 }
3251 }
3252 }
3253 lS->swsData[lB].curPoint = lp;
3254 }
3255 lS->swsData[lB].doneTo = lastPointNo - 1;
3256 }
3258 void
3259 Shape::DoEdgeTo (Shape * iS, int iB, int iTo, bool direct, bool sens)
3260 {
3261 int lp = iS->swsData[iB].curPoint;
3262 int ne = -1;
3263 if (sens)
3264 {
3265 if (direct)
3266 ne = AddEdge (lp, iTo);
3267 else
3268 ne = AddEdge (iTo, lp);
3269 }
3270 else
3271 {
3272 if (direct)
3273 ne = AddEdge (iTo, lp);
3274 else
3275 ne = AddEdge (lp, iTo);
3276 }
3277 if (ne >= 0 && _has_back_data)
3278 {
3279 ebData[ne].pathID = iS->ebData[iB].pathID;
3280 ebData[ne].pieceID = iS->ebData[iB].pieceID;
3281 if (iS->eData[iB].length < 0.00001)
3282 {
3283 ebData[ne].tSt = ebData[ne].tEn = iS->ebData[iB].tSt;
3284 }
3285 else
3286 {
3287 double bdl = iS->eData[iB].ilength;
3288 NR::Point bpx = iS->pData[iS->getEdge(iB).st].rx;
3289 NR::Point bdx = iS->eData[iB].rdx;
3290 NR::Point psx = getPoint(getEdge(ne).st).x;
3291 NR::Point pex = getPoint(getEdge(ne).en).x;
3292 NR::Point psbx=psx-bpx;
3293 NR::Point pebx=pex-bpx;
3294 double pst = dot(psbx,bdx) * bdl;
3295 double pet = dot(pebx,bdx) * bdl;
3296 pst = iS->ebData[iB].tSt * (1 - pst) + iS->ebData[iB].tEn * pst;
3297 pet = iS->ebData[iB].tSt * (1 - pet) + iS->ebData[iB].tEn * pet;
3298 ebData[ne].tEn = pet;
3299 ebData[ne].tSt = pst;
3300 }
3301 }
3302 iS->swsData[iB].curPoint = iTo;
3303 if (ne >= 0)
3304 {
3305 int cp = iS->swsData[iB].firstLinkedPoint;
3306 swsData[ne].firstLinkedPoint = iS->swsData[iB].firstLinkedPoint;
3307 while (cp >= 0)
3308 {
3309 pData[cp].askForWindingB = ne;
3310 cp = pData[cp].nextLinkedPoint;
3311 }
3312 iS->swsData[iB].firstLinkedPoint = -1;
3313 }
3314 }