80 return (
mpPN->mnI < rComp.mpPN->mnI);
94 typedef std::vector< PN > PNV;
95 typedef std::vector< VN > VNV;
96 typedef std::vector< SN > SNV;
106 std::vector< CorrectionPair >
112 void impAddPolygon(
const sal_uInt32 aPos,
const B2DPolygon& rGeometry)
114 const sal_uInt32
nCount(rGeometry.count());
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);
130 aNewVN.maPrev = rGeometry.getPrevControlPoint(
a) - aPoint;
131 aNewVN.maNext = rGeometry.getNextControlPoint(
a) - aPoint;
132 aNewVN.maOriginalNext = aNewVN.maNext;
133 maVNV.push_back(aNewVN);
137 maSNV.push_back(aNewSN);
141 static bool impLeftOfEdges(
const B2DVector& rVecA,
const B2DVector& rVecB,
const B2DVector& rTest)
145 if(rVecA.cross(rVecB) > 0.0)
151 return (bBoolA && bBoolB);
159 return (!(bBoolA && bBoolB));
163 void impSwitchNext(PN& rPNa, PN& rPNb)
165 std::swap(rPNa.mnIN, rPNb.mnIN);
169 VN& rVNa =
maVNV[rPNa.mnI];
170 VN& rVNb =
maVNV[rPNb.mnI];
172 std::swap(rVNa.maNext, rVNb.maNext);
181 B2DCubicBezier createSegment(
const PN& rPN,
bool bPrev)
const
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);
188 const B2DVector& rCPB(bPrev ?
maVNV[
maPNV[rPN.mnIP].mnI].maOriginalNext :
maVNV[
maPNV[rPN.mnIN].mnI].maPrev);
190 return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
193 void impHandleCommon(PN& rPNa, PN& rPNb)
197 const B2DCubicBezier aNextA(createSegment(rPNa,
false));
198 const B2DCubicBezier aPrevA(createSegment(rPNa,
true));
200 if(aNextA.equal(aPrevA))
206 const B2DCubicBezier aNextB(createSegment(rPNb,
false));
207 const B2DCubicBezier aPrevB(createSegment(rPNb,
true));
209 if(aNextB.equal(aPrevB))
215 if(aPrevA.equal(aPrevB))
220 else if(aPrevA.equal(aNextB))
223 if(aNextA.equal(aPrevB))
231 impSwitchNext(rPNa, rPNb);
234 else if(aNextA.equal(aNextB))
244 const B2DCubicBezier aNextA2(createSegment(*pPNa2,
false));
245 const B2DCubicBezier aNextB2(createSegment(*pPNb2,
false));
247 if(aNextA2.equal(aNextB2))
249 pPNa2 = &
maPNV[pPNa2->mnIN];
250 pPNb2 = &
maPNV[pPNb2->mnIN];
257 while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
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));
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));
284 impSwitchNext(rPNa, rPNb);
288 else if(aNextA.equal(aPrevB))
291 impSwitchNext(rPNa, rPNb);
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());
301 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
302 const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
307 impSwitchNext(rPNa, rPNb);
313 const B2DPoint& rNextA(
maPNV[rPNa.mnIN].maPoint);
314 const B2DPoint& rPrevA(
maPNV[rPNa.mnIP].maPoint);
316 if(rNextA.equal(rPrevA))
322 const B2DPoint& rNextB(
maPNV[rPNb.mnIN].maPoint);
323 const B2DPoint& rPrevB(
maPNV[rPNb.mnIP].maPoint);
325 if(rNextB.equal(rPrevB))
331 if(rPrevA.equal(rPrevB))
336 else if(rPrevA.equal(rNextB))
339 if(rNextA.equal(rPrevB))
347 impSwitchNext(rPNa, rPNb);
350 else if(rNextA.equal(rNextB))
360 const B2DPoint& rNextA2(
maPNV[pPNa2->mnIN].maPoint);
361 const B2DPoint& rNextB2(
maPNV[pPNb2->mnIN].maPoint);
363 if(rNextA2.equal(rNextB2))
365 pPNa2 = &
maPNV[pPNa2->mnIN];
366 pPNb2 = &
maPNV[pPNb2->mnIN];
373 while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
384 const B2DPoint& aPointE(rPNa.maPoint);
385 const B2DVector aPrevAE(rPrevA - aPointE);
386 const B2DVector aNextAE(rNextA - aPointE);
387 const B2DVector aPrevBE(rPrevB - aPointE);
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);
394 const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
395 const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
400 impSwitchNext(rPNa, rPNb);
404 else if(rNextA.equal(rPrevB))
407 impSwitchNext(rPNa, rPNb);
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);
418 const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
419 const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
424 impSwitchNext(rPNa, rPNb);
436 const sal_uInt32 nNodeCount(
maSNV.size());
444 for(a = 1;
a < nNodeCount;
a++)
448 if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
452 if(pLast->getX() != aMiddle.getX() || pLast->getY() != aMiddle.getY())
458 if(pCurrent->getX() != aMiddle.getX() || pCurrent->getY() != aMiddle.getY())
469 for(a = 0;
a < nNodeCount - 1;
a++)
474 for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(
maSNV[b].
mpPN->maPoint); b++)
482 explicit solver(
const B2DPolygon& rOriginal)
487 const sal_uInt32 nOriginalCount(rOriginal.count());
493 aGeometry.removeDoublePoints();
495 mbIsCurve = aGeometry.areControlPointsUsed();
497 const sal_uInt32 nPointCount(aGeometry.count());
502 if(!(nPointCount > 3 || (nPointCount > 1 &&
mbIsCurve)))
506 maSNV.reserve(nPointCount);
507 maPNV.reserve(nPointCount);
511 impAddPolygon(0, aGeometry);
517 explicit solver(B2DPolyPolygon aOriginal,
size_t* pPointLimit =
nullptr)
522 sal_uInt32 nOriginalCount(
maOriginal.count());
528 aGeometry.removeDoublePoints();
530 mbIsCurve = aGeometry.areControlPointsUsed();
531 nOriginalCount = aGeometry.count();
536 sal_uInt32 nPointCount(0);
540 for(a = 0;
a < nOriginalCount;
a++)
542 const B2DPolygon& aCandidate(aGeometry.getB2DPolygon(a));
543 const sal_uInt32 nCandCount(aCandidate.count());
552 nPointCount += nCandCount;
560 maSNV.reserve(nPointCount);
561 maPNV.reserve(nPointCount);
565 sal_uInt32 nInsertIndex(0);
567 for(a = 0;
a < nOriginalCount;
a++)
569 const B2DPolygon& aCandidate(aGeometry.getB2DPolygon(a));
570 const sal_uInt32 nCandCount(aCandidate.count());
576 impAddPolygon(nInsertIndex, aCandidate);
577 nInsertIndex += nCandCount;
585 B2DPolyPolygon getB2DPolyPolygon()
589 B2DPolyPolygon aRetval;
591 sal_uInt32 nCountdown(nCount);
593 for(sal_uInt32
a(0); nCountdown &&
a <
nCount;
a++)
597 if(rPN.mnI != SAL_MAX_UINT32)
605 const B2DPoint& rPoint = pPNCurr->maPoint;
606 aNewPart.append(rPoint);
610 const VN& rVNCurr =
maVNV[pPNCurr->mnI];
612 if(!rVNCurr.maPrev.equalZero())
614 aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
617 if(!rVNCurr.maNext.equalZero())
619 aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
625 pPNCurr = &(
maPNV[pPNCurr->mnIN]);
627 while(pPNCurr != &rPN && pPNCurr->mnI != SAL_MAX_UINT32);
630 aNewPart.setClosed(
true);
631 aRetval.append(aNewPart);
648 const sal_uInt32 nPolygonCount(
maOriginal.count());
651 for(sal_uInt32
a(0);
a < nPolygonCount;
a++)
654 const sal_uInt32 nPointCount(aTemp.count());
655 bool bChanged(
false);
657 for(sal_uInt32 b(0); b < nPointCount; b++)
661 for(sal_uInt32 c(0); c < nCorrectionSize; c++)
673 aRetval.setB2DPolygon(a, aTemp);
690 if(rCandidate.
count() > 0)
692 solver aSolver(rCandidate, pPointLimit);
693 return aSolver.getB2DPolyPolygon();
703 solver aSolver(rCandidate);
704 return aSolver.getB2DPolyPolygon();
711 for(sal_uInt32
a(0);
a < rCandidate.
count();
a++)
717 aRetval.
append(aCandidate);
726 if (rCandidate.
count() > 1000)
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");
735 if(rCandidate.
count() == 1)
753 std::vector< StripHelper > aHelpers;
759 StripHelper* pNewHelper = &(aHelpers[
a]);
770 StripHelper& rHelperA = aHelpers[
a];
772 for(b =
a + 1; b <
nCount; b++)
775 StripHelper& rHelperB = aHelpers[b];
776 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) &&
utils::isInside(aCandB, aCandA,
true));
784 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) &&
utils::isInside(aCandA, aCandB,
true));
799 const StripHelper& rHelper = aHelpers[
a];
804 bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1);
827 aRetval = rCandidate;
833 std::vector< StripHelper > aHelpers;
839 StripHelper* pNewHelper = &(aHelpers[
a]);
848 StripHelper& rHelperA = aHelpers[
a];
850 for(b =
a + 1; b <
nCount; 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));
860 if(rHelperA.meOrinetation == rHelperB.meOrinetation)
870 rHelperA.mnDepth = -
static_cast<sal_Int32
>(
nCount);
871 rHelperB.mnDepth = -
static_cast<sal_Int32
>(
nCount);
904 const StripHelper& rHelper = aHelpers[
a];
905 bool bAcceptEntry(bKeepAboveZero ? 1 <= rHelper.mnDepth : rHelper.mnDepth == 0);
920 solver aSolver(rCandidate);
928 solver aSolver(rCandidate);
936 if(!rCandidateA.
count())
940 else if(!rCandidateB.
count())
950 aRetval.
append(rCandidateB);
960 if(!rCandidateA.
count())
964 else if(!rCandidateB.
count())
975 aRetval.
append(rCandidateB);
985 if(!rCandidateA.
count())
989 else if(!rCandidateB.
count())
1036 aRetval.
append(rCandidateB);
1046 if(!rCandidateA.
count())
1050 else if(!rCandidateB.
count())
1060 aRetval.
append(rCandidateA);
1079 aResult.reserve(rInput.size());
1085 if(!aResult.empty())
1088 bool bCouldMergeSimple(
false);
1090 for(
auto & b: aResult)
1095 if(!aCandidateRange.
overlaps(aTargetRange))
1097 aTarget.
append(aCandidate);
1099 bCouldMergeSimple =
true;
1104 if(!bCouldMergeSimple)
1106 aResult.push_back(aCandidate);
1111 aResult.push_back(aCandidate);
1116 while(aResult.size() > 1)
1119 aResult2.
reserve((aResult.size() / 2) + 1);
1121 for(
size_t a(0);
a < aResult.size();
a += 2)
1123 if(
a + 1 < aResult.size())
1131 aResult2.push_back(aResult[
a]);
1139 if(aResult.size() == 1)
B2VectorOrientation meOrinetation
std::vector< CorrectionPair > maCorrectionTable
const B2DPolyPolygon maOriginal
Base Point class with two double values.
B2DPolygon const & getB2DPolygon(sal_uInt32 nIndex) const
void append(const B2DPolygon &rPolygon, sal_uInt32 nCount=1)
B2DRange getB2DRange() const
Get the B2DRange (Rectangle dimensions) of this B2DPolyPolygon.
void reserve(sal_uInt32 nCount)
A two-dimensional interval over doubles.
void intersect(const Range2D &rRange)
calc set intersection
bool isInside(const Tuple2D< TYPE > &rTuple) const
yields true if given point is contained in set
bool isEmpty() const
Check if the interval set is empty.
bool overlaps(const Range2D &rRange) const
yields true if rRange at least partly inside set
#define SAL_WARN(area, stream)
B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon &rCandidate)
Emulate nonzero winding rule filling.
B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon &rCandidate)
prep for ops - solve self-intersections and intersections, remove neutral parts and check orientation...
B2DPolygon createPolygonFromRect(const B2DRectangle &rRect, double fRadiusX, double fRadiusY)
Create a polygon from a rectangle.
B2VectorOrientation getOrientation(const B2DPolygon &rCandidate)
B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon &rCandidateA, const B2DPolyPolygon &rCandidateB)
OR: Return all areas where CandidateA or CandidateB exist.
B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon &rCandidateA, const B2DPolyPolygon &rCandidateB)
AND: Return all areas where CandidateA and CandidateB exist.
bool isInside(const B2DPolygon &rCandidate, const B2DPoint &rPoint, bool bWithBorder)
B2DPolyPolygon correctOrientations(const B2DPolyPolygon &rCandidate)
B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon &rCandidateA, const B2DPolyPolygon &rCandidateB)
XOR: Return all areas where CandidateA or CandidateB exist, but not both.
B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon &rCandidate)
Strip neutral polygons from PolyPolygon.
bool isRectangle(const B2DPolygon &rPoly)
Predicate whether a given polygon is a rectangle.
B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon &rCandidate, size_t *pPointLimit)
B2DPolyPolygon solveCrossovers(const B2DPolyPolygon &rCandidate, size_t *pPointLimit)
Solve all crossovers (aka self-intersections) in a polyPolygon.
B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector &rInput)
merge all single PolyPolygons to a single, OR-ed PolyPolygon
B2DPolygon simplifyCurveSegments(const B2DPolygon &rCandidate)
B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon &rCandidate, bool bKeepAboveZero)
Remove unnecessary/non-displayed polygons.
B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon &rCandidateA, const B2DPolyPolygon &rCandidateB)
DIFF: Return all areas where CandidateA is not covered by CandidateB (cut B out of A)
B2DRange getRange(const B2DPolygon &rCandidate)
Get the range of a polygon.
B2VectorOrientation
Descriptor for the mathematical orientations of two 2D Vectors.
@ Positive
mathematically positive oriented
@ Neutral
mathematically neutral, thus parallel
@ Negative
mathematically negative oriented
::std::vector< B2DPolyPolygon > B2DPolyPolygonVector
constexpr OUStringLiteral first
bool operator<(const wwFont &r1, const wwFont &r2)