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