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