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