summaryrefslogtreecommitdiff
path: root/basegfx/source/polygon/b2dpolypolygoncutter.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'basegfx/source/polygon/b2dpolypolygoncutter.cxx')
-rw-r--r--basegfx/source/polygon/b2dpolypolygoncutter.cxx144
1 files changed, 67 insertions, 77 deletions
diff --git a/basegfx/source/polygon/b2dpolypolygoncutter.cxx b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
index e5094c7dd30d..4ad6eb5b219d 100644
--- a/basegfx/source/polygon/b2dpolypolygoncutter.cxx
+++ b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
@@ -27,8 +27,11 @@
#include <basegfx/range/b2drange.hxx>
#include <basegfx/polygon/b2dpolypolygontools.hxx>
#include <basegfx/curve/b2dcubicbezier.hxx>
+#include <sal/log.hxx>
+#include <utility>
#include <vector>
#include <algorithm>
+#include <numeric>
namespace basegfx
{
@@ -143,16 +146,16 @@ namespace basegfx
if(rVecA.cross(rVecB) > 0.0)
{
// b is left turn seen from a, test if Test is left of both and so inside (left is seen as inside)
- const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
- const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
+ const bool bBoolA(rVecA.cross(rTest) >= 0.0);
+ const bool bBoolB(rVecB.cross(rTest) <= 0.0);
return (bBoolA && bBoolB);
}
else
{
// b is right turn seen from a, test if Test is right of both and so outside (left is seen as inside)
- const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
- const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
+ const bool bBoolA(rVecA.cross(rTest) <= 0.0);
+ const bool bBoolB(rVecB.cross(rTest) >= 0.0);
return (!(bBoolA && bBoolB));
}
@@ -439,9 +442,9 @@ namespace basegfx
{
basegfx::B2DPoint* pLast(&maSNV[0].mpPN->maPoint);
- for(a = 1; a < nNodeCount; a++)
+ for(const auto& rSN : maSNV)
{
- basegfx::B2DPoint* pCurrent(&maSNV[a].mpPN->maPoint);
+ basegfx::B2DPoint* pCurrent(&rSN.mpPN->maPoint);
if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
{
@@ -512,8 +515,8 @@ namespace basegfx
impSolve();
}
- explicit solver(const B2DPolyPolygon& rOriginal)
- : maOriginal(rOriginal),
+ explicit solver(B2DPolyPolygon aOriginal, size_t* pPointLimit = nullptr)
+ : maOriginal(std::move(aOriginal)),
mbIsCurve(false),
mbChanged(false)
{
@@ -522,7 +525,7 @@ namespace basegfx
if(!nOriginalCount)
return;
- B2DPolyPolygon aGeometry(utils::addPointsAtCutsAndTouches(maOriginal));
+ B2DPolyPolygon aGeometry(utils::addPointsAtCutsAndTouches(maOriginal, pPointLimit));
aGeometry.removeDoublePoints();
aGeometry = utils::simplifyCurveSegments(aGeometry);
mbIsCurve = aGeometry.areControlPointsUsed();
@@ -531,25 +534,13 @@ namespace basegfx
if(!nOriginalCount)
return;
- sal_uInt32 nPointCount(0);
- sal_uInt32 a(0);
-
- // count points
- for(a = 0; a < nOriginalCount; a++)
- {
- const B2DPolygon& aCandidate(aGeometry.getB2DPolygon(a));
- const sal_uInt32 nCandCount(aCandidate.count());
-
- // If it's not a bezier curve, at least three points would be needed to have a
- // topological relevant (not empty) polygon. Since it's not known here if trivial
- // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
- // more than one point.
- // For bezier curves, the minimum for defining an area is also one.
- if(nCandCount)
- {
- nPointCount += nCandCount;
- }
- }
+ // If it's not a bezier curve, at least three points would be needed to have a
+ // topological relevant (not empty) polygon. Since it's not known here if trivial
+ // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
+ // more than one point.
+ // For bezier curves, the minimum for defining an area is also one.
+ sal_uInt32 nPointCount = std::accumulate( aGeometry.begin(), aGeometry.end(), sal_uInt32(0),
+ [](sal_uInt32 a, const basegfx::B2DPolygon& b){return a + b.count();});
if(!nPointCount)
return;
@@ -562,16 +553,15 @@ namespace basegfx
// fill data
sal_uInt32 nInsertIndex(0);
- for(a = 0; a < nOriginalCount; a++)
+ for(const auto& rCandidate : aGeometry )
{
- const B2DPolygon& aCandidate(aGeometry.getB2DPolygon(a));
- const sal_uInt32 nCandCount(aCandidate.count());
+ const sal_uInt32 nCandCount(rCandidate.count());
// use same condition as above, the data vector is
// pre-allocated
if(nCandCount)
{
- impAddPolygon(nInsertIndex, aCandidate);
+ impAddPolygon(nInsertIndex, rCandidate);
nInsertIndex += nCandCount;
}
}
@@ -683,11 +673,11 @@ namespace basegfx
namespace basegfx::utils
{
- B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
+ B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate, size_t* pPointLimit)
{
if(rCandidate.count() > 0)
{
- solver aSolver(rCandidate);
+ solver aSolver(rCandidate, pPointLimit);
return aSolver.getB2DPolyPolygon();
}
else
@@ -706,13 +696,11 @@ namespace basegfx::utils
{
B2DPolyPolygon aRetval;
- for(sal_uInt32 a(0); a < rCandidate.count(); a++)
+ for(const auto& rPolygon : rCandidate)
{
- const B2DPolygon& aCandidate(rCandidate.getB2DPolygon(a));
-
- if(utils::getOrientation(aCandidate) != B2VectorOrientation::Neutral)
+ if(utils::getOrientation(rPolygon) != B2VectorOrientation::Neutral)
{
- aRetval.append(aCandidate);
+ aRetval.append(rPolygon);
}
}
@@ -721,6 +709,12 @@ namespace basegfx::utils
B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon& rCandidate)
{
+ if (rCandidate.count() > 1000)
+ {
+ 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");
+ return rCandidate;
+ }
+
B2DPolyPolygon aCandidate;
// remove all self-intersections and intersections
@@ -1062,79 +1056,75 @@ namespace basegfx::utils
B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector& rInput)
{
- B2DPolyPolygonVector aInput(rInput);
+ if(rInput.empty())
+ return B2DPolyPolygon();
// first step: prepareForPolygonOperation and simple merge of non-overlapping
// PolyPolygons for speedup; this is possible for the wanted OR-operation
- if(!aInput.empty())
+ B2DPolyPolygonVector aResult;
+ aResult.reserve(rInput.size());
+
+ for(const basegfx::B2DPolyPolygon & a : rInput)
{
- B2DPolyPolygonVector aResult;
- aResult.reserve(aInput.size());
+ const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(a));
- for(const basegfx::B2DPolyPolygon & a : aInput)
+ if(!aResult.empty())
{
- const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(a));
+ const B2DRange aCandidateRange(aCandidate.getB2DRange());
+ bool bCouldMergeSimple(false);
- if(!aResult.empty())
+ for(auto & b: aResult)
{
- const B2DRange aCandidateRange(aCandidate.getB2DRange());
- bool bCouldMergeSimple(false);
-
- for(auto & b: aResult)
- {
- basegfx::B2DPolyPolygon aTarget(b);
- const B2DRange aTargetRange(aTarget.getB2DRange());
-
- if(!aCandidateRange.overlaps(aTargetRange))
- {
- aTarget.append(aCandidate);
- b = aTarget;
- bCouldMergeSimple = true;
- break;
- }
- }
+ basegfx::B2DPolyPolygon aTarget(b);
+ const B2DRange aTargetRange(aTarget.getB2DRange());
- if(!bCouldMergeSimple)
+ if(!aCandidateRange.overlaps(aTargetRange))
{
- aResult.push_back(aCandidate);
+ aTarget.append(aCandidate);
+ b = aTarget;
+ bCouldMergeSimple = true;
+ break;
}
}
- else
+
+ if(!bCouldMergeSimple)
{
aResult.push_back(aCandidate);
}
}
-
- aInput = aResult;
+ else
+ {
+ aResult.push_back(aCandidate);
+ }
}
// second step: melt pairwise to a single PolyPolygon
- while(aInput.size() > 1)
+ while(aResult.size() > 1)
{
- B2DPolyPolygonVector aResult;
- aResult.reserve((aInput.size() / 2) + 1);
+ B2DPolyPolygonVector aResult2;
+ aResult2.reserve((aResult.size() / 2) + 1);
- for(size_t a(0); a < aInput.size(); a += 2)
+ for(size_t a(0); a < aResult.size(); a += 2)
{
- if(a + 1 < aInput.size())
+ if(a + 1 < aResult.size())
{
// a pair for processing
- aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
+ aResult2.push_back(solvePolygonOperationOr(aResult[a], aResult[a + 1]));
}
else
{
// last single PolyPolygon; copy to target to not lose it
- aResult.push_back(aInput[a]);
+ aResult2.push_back(aResult[a]);
}
}
- aInput = aResult;
+ aResult = aResult2;
}
// third step: get result
- if(aInput.size() == 1)
+ if(aResult.size() == 1)
{
- return aInput[0];
+ return aResult[0];
}
return B2DPolyPolygon();
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-27 01:34:49 +0000