?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Version 6.1.0.2, tag libreoffice-6.1.0.2
[LibreOffice.git] / basegfx / source / polygon / b2dpolypolygoncutter.cxx
blob4fd7bf369d857d43fd5e8d8e3418f118853afb76
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
20 #include <basegfx/numeric/ftools.hxx>
21 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
22 #include <basegfx/point/b2dpoint.hxx>
23 #include <basegfx/vector/b2dvector.hxx>
24 #include <basegfx/polygon/b2dpolygon.hxx>
25 #include <basegfx/polygon/b2dpolygontools.hxx>
26 #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
27 #include <basegfx/range/b2drange.hxx>
28 #include <basegfx/polygon/b2dpolypolygontools.hxx>
29 #include <basegfx/curve/b2dcubicbezier.hxx>
30 #include <vector>
31 #include <algorithm>
32
33 namespace basegfx
34 {
35 namespace
36 {
37
38 struct StripHelper
39 {
40 B2DRange maRange;
41 sal_Int32 mnDepth;
42 B2VectorOrientation meOrinetation;
43 };
44
45 struct PN
46 {
47 public:
48 B2DPoint maPoint;
49 sal_uInt32 mnI;
50 sal_uInt32 mnIP;
51 sal_uInt32 mnIN;
52 };
53
54 struct VN
55 {
56 public:
57 B2DVector maPrev;
58 B2DVector maNext;
59
60 // to have the correct curve segments in the crossover checks,
61 // it is necessary to keep the original next vectors, too. Else,
62 // it may happen to use a already switched next vector which
63 // would interpolate the wrong comparison point
64 B2DVector maOriginalNext;
65 };
66
67 struct SN
68 {
69 public:
70 PN* mpPN;
71
72 bool operator<(const SN& rComp) const
73 {
74 if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
75 {
76 if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
77 {
78 return (mpPN->mnI < rComp.mpPN->mnI);
79 }
80 else
81 {
82 return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
83 }
84 }
85 else
86 {
87 return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX());
88 }
89 }
90 };
91
92 typedef std::vector< PN > PNV;
93 typedef std::vector< VN > VNV;
94 typedef std::vector< SN > SNV;
95 typedef std::pair< basegfx::B2DPoint /*orig*/, basegfx::B2DPoint /*repl*/ > CorrectionPair;
96
97 class solver
98 {
99 private:
100 const B2DPolyPolygon maOriginal;
101 PNV maPNV;
102 VNV maVNV;
103 SNV maSNV;
104 std::vector< CorrectionPair >
105 maCorrectionTable;
106
107 bool mbIsCurve : 1;
108 bool mbChanged : 1;
109
110 void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
111 {
112 const sal_uInt32 nCount(rGeometry.count());
113 PN aNewPN;
114 VN aNewVN;
115 SN aNewSN;
116
117 for(sal_uInt32 a(0); a < nCount; a++)
118 {
119 const B2DPoint aPoint(rGeometry.getB2DPoint(a));
120 aNewPN.maPoint = aPoint;
121 aNewPN.mnI = aPos + a;
122 aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
123 aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
124 maPNV.push_back(aNewPN);
125
126 if(mbIsCurve)
127 {
128 aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
129 aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
130 aNewVN.maOriginalNext = aNewVN.maNext;
131 maVNV.push_back(aNewVN);
132 }
133
134 aNewSN.mpPN = &maPNV[maPNV.size() - 1];
135 maSNV.push_back(aNewSN);
136 }
137 }
138
139 static bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest)
140 {
141 // tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is
142 // with border.
143 if(rVecA.cross(rVecB) > 0.0)
144 {
145 // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
146 const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
147 const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
148
149 return (bBoolA && bBoolB);
150 }
151 else
152 {
153 // b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside)
154 const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
155 const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
156
157 return (!(bBoolA && bBoolB));
158 }
159 }
160
161 void impSwitchNext(PN& rPNa, PN& rPNb)
162 {
163 std::swap(rPNa.mnIN, rPNb.mnIN);
164
165 if(mbIsCurve)
166 {
167 VN& rVNa = maVNV[rPNa.mnI];
168 VN& rVNb = maVNV[rPNb.mnI];
169
170 std::swap(rVNa.maNext, rVNb.maNext);
171 }
172
173 if(!mbChanged)
174 {
175 mbChanged = true;
176 }
177 }
178
179 B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
180 {
181 const B2DPoint& rStart(rPN.maPoint);
182 const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
183 const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext);
184 // Use maOriginalNext, not maNext to create the original (yet unchanged)
185 // curve segment. Otherwise, this segment would NOT ne correct.
186 const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);
187
188 return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
189 }
190
191 void impHandleCommon(PN& rPNa, PN& rPNb)
192 {
193 if(mbIsCurve)
194 {
195 const B2DCubicBezier aNextA(createSegment(rPNa, false));
196 const B2DCubicBezier aPrevA(createSegment(rPNa, true));
197
198 if(aNextA.equal(aPrevA))
199 {
200 // deadend on A (identical edge)
201 return;
202 }
203
204 const B2DCubicBezier aNextB(createSegment(rPNb, false));
205 const B2DCubicBezier aPrevB(createSegment(rPNb, true));
206
207 if(aNextB.equal(aPrevB))
208 {
209 // deadend on B (identical edge)
210 return;
211 }
212
213 if(aPrevA.equal(aPrevB))
214 {
215 // common edge in same direction
216 return;
217 }
218 else if(aPrevA.equal(aNextB))
219 {
220 // common edge in opposite direction
221 if(aNextA.equal(aPrevB))
222 {
223 // common edge in opposite direction continues
224 return;
225 }
226 else
227 {
228 // common edge in opposite direction leave
229 impSwitchNext(rPNa, rPNb);
230 }
231 }
232 else if(aNextA.equal(aNextB))
233 {
234 // common edge in same direction enter
235 // search leave edge
236 PN* pPNa2 = &maPNV[rPNa.mnIN];
237 PN* pPNb2 = &maPNV[rPNb.mnIN];
238 bool bOnEdge(true);
239
240 do
241 {
242 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
243 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
244
245 if(aNextA2.equal(aNextB2))
246 {
247 pPNa2 = &maPNV[pPNa2->mnIN];
248 pPNb2 = &maPNV[pPNb2->mnIN];
249 }
250 else
251 {
252 bOnEdge = false;
253 }
254 }
255 while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
256
257 if(bOnEdge)
258 {
259 // loop over two identical polygon paths
260 return;
261 }
262 else
263 {
264 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
265 // at enter/leave. Check for crossover.
266 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
267 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
268 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
269 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
270
271 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
272 const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true));
273 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
274 const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint());
275 const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint());
276 const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint());
277 const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2));
278
279 if(bEnter != bLeave)
280 {
281 // crossover
282 impSwitchNext(rPNa, rPNb);
283 }
284 }
285 }
286 else if(aNextA.equal(aPrevB))
287 {
288 // common edge in opposite direction enter
289 impSwitchNext(rPNa, rPNb);
290 }
291 else
292 {
293 // no common edges, check for crossover
294 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
295 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
296 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
297 const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());
298
299 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
300 const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
301
302 if(bEnter != bLeave)
303 {
304 // crossover
305 impSwitchNext(rPNa, rPNb);
306 }
307 }
308 }
309 else
310 {
311 const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
312 const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);
313
314 if(rNextA.equal(rPrevA))
315 {
316 // deadend on A
317 return;
318 }
319
320 const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
321 const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);
322
323 if(rNextB.equal(rPrevB))
324 {
325 // deadend on B
326 return;
327 }
328
329 if(rPrevA.equal(rPrevB))
330 {
331 // common edge in same direction
332 return;
333 }
334 else if(rPrevA.equal(rNextB))
335 {
336 // common edge in opposite direction
337 if(rNextA.equal(rPrevB))
338 {
339 // common edge in opposite direction continues
340 return;
341 }
342 else
343 {
344 // common edge in opposite direction leave
345 impSwitchNext(rPNa, rPNb);
346 }
347 }
348 else if(rNextA.equal(rNextB))
349 {
350 // common edge in same direction enter
351 // search leave edge
352 PN* pPNa2 = &maPNV[rPNa.mnIN];
353 PN* pPNb2 = &maPNV[rPNb.mnIN];
354 bool bOnEdge(true);
355
356 do
357 {
358 const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
359 const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);
360
361 if(rNextA2.equal(rNextB2))
362 {
363 pPNa2 = &maPNV[pPNa2->mnIN];
364 pPNb2 = &maPNV[pPNb2->mnIN];
365 }
366 else
367 {
368 bOnEdge = false;
369 }
370 }
371 while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
372
373 if(bOnEdge)
374 {
375 // loop over two identical polygon paths
376 return;
377 }
378 else
379 {
380 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
381 // at enter/leave. Check for crossover.
382 const B2DPoint& aPointE(rPNa.maPoint);
383 const B2DVector aPrevAE(rPrevA - aPointE);
384 const B2DVector aNextAE(rNextA - aPointE);
385 const B2DVector aPrevBE(rPrevB - aPointE);
386
387 const B2DPoint& aPointL(pPNa2->maPoint);
388 const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
389 const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
390 const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);
391
392 const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
393 const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
394
395 if(bEnter != bLeave)
396 {
397 // crossover; switch start or end
398 impSwitchNext(rPNa, rPNb);
399 }
400 }
401 }
402 else if(rNextA.equal(rPrevB))
403 {
404 // common edge in opposite direction enter
405 impSwitchNext(rPNa, rPNb);
406 }
407 else
408 {
409 // no common edges, check for crossover
410 const B2DPoint& aPoint(rPNa.maPoint);
411 const B2DVector aPrevA(rPrevA - aPoint);
412 const B2DVector aNextA(rNextA - aPoint);
413 const B2DVector aPrevB(rPrevB - aPoint);
414 const B2DVector aNextB(rNextB - aPoint);
415
416 const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
417 const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
418
419 if(bEnter != bLeave)
420 {
421 // crossover
422 impSwitchNext(rPNa, rPNb);
423 }
424 }
425 }
426 }
427
428 void impSolve()
429 {
430 // sort by point to identify common nodes easier
431 std::sort(maSNV.begin(), maSNV.end());
432
433 // handle common nodes
434 const sal_uInt32 nNodeCount(maSNV.size());
435 sal_uInt32 a(0);
436
437 // snap unsharp-equal points
438 if(nNodeCount)
439 {
440 basegfx::B2DPoint* pLast(&maSNV[0].mpPN->maPoint);
441
442 for(a = 1; a < nNodeCount; a++)
443 {
444 basegfx::B2DPoint* pCurrent(&maSNV[a].mpPN->maPoint);
445
446 if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
447 {
448 const basegfx::B2DPoint aMiddle((*pLast + *pCurrent) * 0.5);
449
450 if(pLast->getX() != aMiddle.getX() || pLast->getY() != aMiddle.getY())
451 {
452 maCorrectionTable.emplace_back(*pLast, aMiddle);
453 *pLast = aMiddle;
454 }
455
456 if(pCurrent->getX() != aMiddle.getX() || pCurrent->getY() != aMiddle.getY())
457 {
458 maCorrectionTable.emplace_back(*pCurrent, aMiddle);
459 *pCurrent = aMiddle;
460 }
461 }
462
463 pLast = pCurrent;
464 }
465 }
466
467 for(a = 0; a < nNodeCount - 1; a++)
468 {
469 // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
470 PN& rPNb = *(maSNV[a].mpPN);
471
472 for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
473 {
474 impHandleCommon(rPNb, *maSNV[b].mpPN);
475 }
476 }
477 }
478
479 public:
480 explicit solver(const B2DPolygon& rOriginal)
481 : maOriginal(B2DPolyPolygon(rOriginal)),
482 mbIsCurve(false),
483 mbChanged(false)
484 {
485 const sal_uInt32 nOriginalCount(rOriginal.count());
486
487 if(nOriginalCount)
488 {
489 B2DPolygon aGeometry(utils::addPointsAtCutsAndTouches(rOriginal));
490 aGeometry.removeDoublePoints();
491 aGeometry = utils::simplifyCurveSegments(aGeometry);
492 mbIsCurve = aGeometry.areControlPointsUsed();
493
494 const sal_uInt32 nPointCount(aGeometry.count());
495
496 // If it's not a bezier polygon, at least four points are needed to create
497 // a self-intersection. If it's a bezier polygon, the minimum point number
498 // is two, since with a single point You get a curve, but no self-intersection
499 if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
500 {
501 // reserve space in point, control and sort vector.
502 maSNV.reserve(nPointCount);
503 maPNV.reserve(nPointCount);
504 maVNV.reserve(mbIsCurve ? nPointCount : 0);
505
506 // fill data
507 impAddPolygon(0, aGeometry);
508
509 // solve common nodes
510 impSolve();
511 }
512 }
513 }
514
515 explicit solver(const B2DPolyPolygon& rOriginal)
516 : maOriginal(rOriginal),
517 mbIsCurve(false),
518 mbChanged(false)
519 {
520 sal_uInt32 nOriginalCount(maOriginal.count());
521
522 if(nOriginalCount)
523 {
524 B2DPolyPolygon aGeometry(utils::addPointsAtCutsAndTouches(maOriginal));
525 aGeometry.removeDoublePoints();
526 aGeometry = utils::simplifyCurveSegments(aGeometry);
527 mbIsCurve = aGeometry.areControlPointsUsed();
528 nOriginalCount = aGeometry.count();
529
530 if(nOriginalCount)
531 {
532 sal_uInt32 nPointCount(0);
533 sal_uInt32 a(0);
534
535 // count points
536 for(a = 0; a < nOriginalCount; a++)
537 {
538 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
539 const sal_uInt32 nCandCount(aCandidate.count());
540
541 // If it's not a bezier curve, at least three points would be needed to have a
542 // topological relevant (not empty) polygon. Since it's not known here if trivial
543 // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
544 // more than one point.
545 // For bezier curves, the minimum for defining an area is also one.
546 if(nCandCount)
547 {
548 nPointCount += nCandCount;
549 }
550 }
551
552 if(nPointCount)
553 {
554 // reserve space in point, control and sort vector.
555 maSNV.reserve(nPointCount);
556 maPNV.reserve(nPointCount);
557 maVNV.reserve(mbIsCurve ? nPointCount : 0);
558
559 // fill data
560 sal_uInt32 nInsertIndex(0);
561
562 for(a = 0; a < nOriginalCount; a++)
563 {
564 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
565 const sal_uInt32 nCandCount(aCandidate.count());
566
567 // use same condition as above, the data vector is
568 // pre-allocated
569 if(nCandCount)
570 {
571 impAddPolygon(nInsertIndex, aCandidate);
572 nInsertIndex += nCandCount;
573 }
574 }
575
576 // solve common nodes
577 impSolve();
578 }
579 }
580 }
581 }
582
583 B2DPolyPolygon getB2DPolyPolygon()
584 {
585 if(mbChanged)
586 {
587 B2DPolyPolygon aRetval;
588 const sal_uInt32 nCount(maPNV.size());
589 sal_uInt32 nCountdown(nCount);
590
591 for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
592 {
593 PN& rPN = maPNV[a];
594
595 if(rPN.mnI != SAL_MAX_UINT32)
596 {
597 // unused node, start new part polygon
598 B2DPolygon aNewPart;
599 PN* pPNCurr = &rPN;
600
601 do
602 {
603 const B2DPoint& rPoint = pPNCurr->maPoint;
604 aNewPart.append(rPoint);
605
606 if(mbIsCurve)
607 {
608 const VN& rVNCurr = maVNV[pPNCurr->mnI];
609
610 if(!rVNCurr.maPrev.equalZero())
611 {
612 aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
613 }
614
615 if(!rVNCurr.maNext.equalZero())
616 {
617 aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
618 }
619 }
620
621 pPNCurr->mnI = SAL_MAX_UINT32;
622 nCountdown--;
623 pPNCurr = &(maPNV[pPNCurr->mnIN]);
624 }
625 while(pPNCurr != &rPN && pPNCurr->mnI != SAL_MAX_UINT32);
626
627 // close and add
628 aNewPart.setClosed(true);
629 aRetval.append(aNewPart);
630 }
631 }
632
633 return aRetval;
634 }
635 else
636 {
637 const sal_uInt32 nCorrectionSize(maCorrectionTable.size());
638
639 // no change, return original
640 if(!nCorrectionSize)
641 {
642 return maOriginal;
643 }
644
645 // apply coordinate corrections to ensure inside/outside correctness after solving
646 const sal_uInt32 nPolygonCount(maOriginal.count());
647 basegfx::B2DPolyPolygon aRetval(maOriginal);
648
649 for(sal_uInt32 a(0); a < nPolygonCount; a++)
650 {
651 basegfx::B2DPolygon aTemp(aRetval.getB2DPolygon(a));
652 const sal_uInt32 nPointCount(aTemp.count());
653 bool bChanged(false);
654
655 for(sal_uInt32 b(0); b < nPointCount; b++)
656 {
657 const basegfx::B2DPoint aCandidate(aTemp.getB2DPoint(b));
658
659 for(sal_uInt32 c(0); c < nCorrectionSize; c++)
660 {
661 if(maCorrectionTable[c].first.getX() == aCandidate.getX() && maCorrectionTable[c].first.getY() == aCandidate.getY())
662 {
663 aTemp.setB2DPoint(b, maCorrectionTable[c].second);
664 bChanged = true;
665 }
666 }
667 }
668
669 if(bChanged)
670 {
671 aRetval.setB2DPolygon(a, aTemp);
672 }
673 }
674
675 return aRetval;
676 }
677 }
678 };
679
680 } // end of anonymous namespace
681 } // end of namespace basegfx
682
683 namespace basegfx
684 {
685 namespace utils
686 {
687
688 B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
689 {
690 if(rCandidate.count() > 0)
691 {
692 solver aSolver(rCandidate);
693 return aSolver.getB2DPolyPolygon();
694 }
695 else
696 {
697 return rCandidate;
698 }
699 }
700
701 B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate)
702 {
703 solver aSolver(rCandidate);
704 return aSolver.getB2DPolyPolygon();
705 }
706
707 B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
708 {
709 B2DPolyPolygon aRetval;
710
711 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
712 {
713 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
714
715 if(utils::getOrientation(aCandidate) != B2VectorOrientation::Neutral)
716 {
717 aRetval.append(aCandidate);
718 }
719 }
720
721 return aRetval;
722 }
723
724 B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon& rCandidate)
725 {
726 B2DPolyPolygon aCandidate;
727
728 // remove all self-intersections and intersections
729 if(rCandidate.count() == 1)
730 {
731 aCandidate = basegfx::utils::solveCrossovers(rCandidate.getB2DPolygon(0));
732 }
733 else
734 {
735 aCandidate = basegfx::utils::solveCrossovers(rCandidate);
736 }
737
738 // cleanup evtl. neutral polygons
739 aCandidate = basegfx::utils::stripNeutralPolygons(aCandidate);
740
741 // remove all polygons which have the same orientation as the polygon they are directly contained in
742 const sal_uInt32 nCount(aCandidate.count());
743
744 if(nCount > 1)
745 {
746 sal_uInt32 a, b;
747 std::vector< StripHelper > aHelpers;
748 aHelpers.resize(nCount);
749
750 for(a = 0; a < nCount; a++)
751 {
752 const B2DPolygon aCand(aCandidate.getB2DPolygon(a));
753 StripHelper* pNewHelper = &(aHelpers[a]);
754 pNewHelper->maRange = utils::getRange(aCand);
755 pNewHelper->meOrinetation = utils::getOrientation(aCand);
756
757 // initialize with own orientation
758 pNewHelper->mnDepth = (pNewHelper->meOrinetation == B2VectorOrientation::Negative ? -1 : 1);
759 }
760
761 for(a = 0; a < nCount - 1; a++)
762 {
763 const B2DPolygon aCandA(aCandidate.getB2DPolygon(a));
764 StripHelper& rHelperA = aHelpers[a];
765
766 for(b = a + 1; b < nCount; b++)
767 {
768 const B2DPolygon aCandB(aCandidate.getB2DPolygon(b));
769 StripHelper& rHelperB = aHelpers[b];
770 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && utils::isInside(aCandB, aCandA, true));
771
772 if(bAInB)
773 {
774 // A is inside B, add orientation of B to A
775 rHelperA.mnDepth += (rHelperB.meOrinetation == B2VectorOrientation::Negative ? -1 : 1);
776 }
777
778 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && utils::isInside(aCandA, aCandB, true));
779
780 if(bBInA)
781 {
782 // B is inside A, add orientation of A to B
783 rHelperB.mnDepth += (rHelperA.meOrinetation == B2VectorOrientation::Negative ? -1 : 1);
784 }
785 }
786 }
787
788 const B2DPolyPolygon aSource(aCandidate);
789 aCandidate.clear();
790
791 for(a = 0; a < nCount; a++)
792 {
793 const StripHelper& rHelper = aHelpers[a];
794 // for contained unequal oriented polygons sum will be 0
795 // for contained equal it will be >=2 or <=-2
796 // for free polygons (not contained) it will be 1 or -1
797 // -> accept all which are >=-1 && <= 1
798 bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1);
799
800 if(bAcceptEntry)
801 {
802 aCandidate.append(aSource.getB2DPolygon(a));
803 }
804 }
805 }
806
807 return aCandidate;
808 }
809
810 B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
811 {
812 const sal_uInt32 nCount(rCandidate.count());
813 B2DPolyPolygon aRetval;
814
815 if(nCount)
816 {
817 if(nCount == 1)
818 {
819 if(!bKeepAboveZero && utils::getOrientation(rCandidate.getB2DPolygon(0)) == B2VectorOrientation::Positive)
820 {
821 aRetval = rCandidate;
822 }
823 }
824 else
825 {
826 sal_uInt32 a, b;
827 std::vector< StripHelper > aHelpers;
828 aHelpers.resize(nCount);
829
830 for(a = 0; a < nCount; a++)
831 {
832 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
833 StripHelper* pNewHelper = &(aHelpers[a]);
834 pNewHelper->maRange = utils::getRange(aCandidate);
835 pNewHelper->meOrinetation = utils::getOrientation(aCandidate);
836 pNewHelper->mnDepth = (pNewHelper->meOrinetation == B2VectorOrientation::Negative ? -1 : 0);
837 }
838
839 for(a = 0; a < nCount - 1; a++)
840 {
841 const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
842 StripHelper& rHelperA = aHelpers[a];
843
844 for(b = a + 1; b < nCount; b++)
845 {
846 const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
847 StripHelper& rHelperB = aHelpers[b];
848 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && utils::isInside(aCandB, aCandA, true));
849 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && utils::isInside(aCandA, aCandB, true));
850
851 if(bAInB && bBInA)
852 {
853 // congruent
854 if(rHelperA.meOrinetation == rHelperB.meOrinetation)
855 {
856 // two polys or two holes. Lower one of them to get one of them out of the way.
857 // Since each will be contained in the other one, both will be increased, too.
858 // So, for lowering, increase only one of them
859 rHelperA.mnDepth++;
860 }
861 else
862 {
863 // poly and hole. They neutralize, so get rid of both. Move securely below zero.
864 rHelperA.mnDepth = - static_cast<sal_Int32>(nCount);
865 rHelperB.mnDepth = - static_cast<sal_Int32>(nCount);
866 }
867 }
868 else
869 {
870 if(bAInB)
871 {
872 if(rHelperB.meOrinetation == B2VectorOrientation::Negative)
873 {
874 rHelperA.mnDepth--;
875 }
876 else
877 {
878 rHelperA.mnDepth++;
879 }
880 }
881 else if(bBInA)
882 {
883 if(rHelperA.meOrinetation == B2VectorOrientation::Negative)
884 {
885 rHelperB.mnDepth--;
886 }
887 else
888 {
889 rHelperB.mnDepth++;
890 }
891 }
892 }
893 }
894 }
895
896 for(a = 0; a < nCount; a++)
897 {
898 const StripHelper& rHelper = aHelpers[a];
899 bool bAcceptEntry(bKeepAboveZero ? 1 <= rHelper.mnDepth : rHelper.mnDepth == 0);
900
901 if(bAcceptEntry)
902 {
903 aRetval.append(rCandidate.getB2DPolygon(a));
904 }
905 }
906 }
907 }
908
909 return aRetval;
910 }
911
912 B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
913 {
914 solver aSolver(rCandidate);
915 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
916
917 return correctOrientations(aRetval);
918 }
919
920 B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
921 {
922 solver aSolver(rCandidate);
923 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
924
925 return correctOrientations(aRetval);
926 }
927
928 B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
929 {
930 if(!rCandidateA.count())
931 {
932 return rCandidateB;
933 }
934 else if(!rCandidateB.count())
935 {
936 return rCandidateA;
937 }
938 else
939 {
940 // concatenate polygons, solve crossovers and throw away all sub-polygons
941 // which have a depth other than 0.
942 B2DPolyPolygon aRetval(rCandidateA);
943
944 aRetval.append(rCandidateB);
945 aRetval = solveCrossovers(aRetval);
946 aRetval = stripNeutralPolygons(aRetval);
947
948 return stripDispensablePolygons(aRetval);
949 }
950 }
951
952 B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
953 {
954 if(!rCandidateA.count())
955 {
956 return rCandidateB;
957 }
958 else if(!rCandidateB.count())
959 {
960 return rCandidateA;
961 }
962 else
963 {
964 // XOR is pretty simple: By definition it is the simple concatenation of
965 // the single polygons since we imply XOR fill rule. Make it intersection-free
966 // and correct orientations
967 B2DPolyPolygon aRetval(rCandidateA);
968
969 aRetval.append(rCandidateB);
970 aRetval = solveCrossovers(aRetval);
971 aRetval = stripNeutralPolygons(aRetval);
972
973 return correctOrientations(aRetval);
974 }
975 }
976
977 B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
978 {
979 if(!rCandidateA.count())
980 {
981 return B2DPolyPolygon();
982 }
983 else if(!rCandidateB.count())
984 {
985 return B2DPolyPolygon();
986 }
987 else
988 {
989 // concatenate polygons, solve crossovers and throw away all sub-polygons
990 // with a depth of < 1. This means to keep all polygons where at least two
991 // polygons do overlap.
992 B2DPolyPolygon aRetval(rCandidateA);
993
994 aRetval.append(rCandidateB);
995 aRetval = solveCrossovers(aRetval);
996 aRetval = stripNeutralPolygons(aRetval);
997
998 return stripDispensablePolygons(aRetval, true);
999 }
1000 }
1001
1002 B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
1003 {
1004 if(!rCandidateA.count())
1005 {
1006 return B2DPolyPolygon();
1007 }
1008 else if(!rCandidateB.count())
1009 {
1010 return rCandidateA;
1011 }
1012 else
1013 {
1014 // Make B topologically to holes and append to A
1015 B2DPolyPolygon aRetval(rCandidateB);
1016
1017 aRetval.flip();
1018 aRetval.append(rCandidateA);
1019
1020 // solve crossovers and throw away all sub-polygons which have a
1021 // depth other than 0.
1022 aRetval = basegfx::utils::solveCrossovers(aRetval);
1023 aRetval = basegfx::utils::stripNeutralPolygons(aRetval);
1024
1025 return basegfx::utils::stripDispensablePolygons(aRetval);
1026 }
1027 }
1028
1029 B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector& rInput)
1030 {
1031 B2DPolyPolygonVector aInput(rInput);
1032
1033 // first step: prepareForPolygonOperation and simple merge of non-overlapping
1034 // PolyPolygons for speedup; this is possible for the wanted OR-operation
1035 if(!aInput.empty())
1036 {
1037 B2DPolyPolygonVector aResult;
1038 aResult.reserve(aInput.size());
1039
1040 for(basegfx::B2DPolyPolygon & a : aInput)
1041 {
1042 const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(a));
1043
1044 if(!aResult.empty())
1045 {
1046 const B2DRange aCandidateRange(aCandidate.getB2DRange());
1047 bool bCouldMergeSimple(false);
1048
1049 for(auto & b: aResult)
1050 {
1051 basegfx::B2DPolyPolygon aTarget(b);
1052 const B2DRange aTargetRange(aTarget.getB2DRange());
1053
1054 if(!aCandidateRange.overlaps(aTargetRange))
1055 {
1056 aTarget.append(aCandidate);
1057 b = aTarget;
1058 bCouldMergeSimple = true;
1059 break;
1060 }
1061 }
1062
1063 if(!bCouldMergeSimple)
1064 {
1065 aResult.push_back(aCandidate);
1066 }
1067 }
1068 else
1069 {
1070 aResult.push_back(aCandidate);
1071 }
1072 }
1073
1074 aInput = aResult;
1075 }
1076
1077 // second step: melt pairwise to a single PolyPolygon
1078 while(aInput.size() > 1)
1079 {
1080 B2DPolyPolygonVector aResult;
1081 aResult.reserve((aInput.size() / 2) + 1);
1082
1083 for(size_t a(0); a < aInput.size(); a += 2)
1084 {
1085 if(a + 1 < aInput.size())
1086 {
1087 // a pair for processing
1088 aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
1089 }
1090 else
1091 {
1092 // last single PolyPolygon; copy to target to not lose it
1093 aResult.push_back(aInput[a]);
1094 }
1095 }
1096
1097 aInput = aResult;
1098 }
1099
1100 // third step: get result
1101 if(aInput.size() == 1)
1102 {
1103 return aInput[0];
1104 }
1105
1106 return B2DPolyPolygon();
1107 }
1108
1109 } // end of namespace utils
1110 } // end of namespace basegfx
1111
1112 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
FREE OFFICE SUITE