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.cxx1464
1 files changed, 688 insertions, 776 deletions
diff --git a/basegfx/source/polygon/b2dpolypolygoncutter.cxx b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
index f6d85f017d10..b7c74475fb92 100644
--- a/basegfx/source/polygon/b2dpolypolygoncutter.cxx
+++ b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
@@ -4,9 +4,9 @@
*
* $RCSfile: b2dpolypolygoncutter.cxx,v $
*
- * $Revision: 1.9 $
+ * $Revision: 1.10 $
*
- * last change: $Author: rt $ $Date: 2005-09-07 20:47:08 $
+ * last change: $Author: kz $ $Date: 2005-11-02 13:58:32 $
*
* The Contents of this file are made available subject to
* the terms of GNU Lesser General Public License Version 2.1.
@@ -45,8 +45,12 @@
#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
#endif
-#ifndef _BGFX_NUMERIC_FTOOLS_HXX
-#include <basegfx/numeric/ftools.hxx>
+#ifndef _BGFX_POINT_B2DPOINT_HXX
+#include <basegfx/point/b2dpoint.hxx>
+#endif
+
+#ifndef _BGFX_VECTOR_B2DVECTOR_HXX
+#include <basegfx/vector/b2dvector.hxx>
#endif
#ifndef _BGFX_POLYGON_B2DPOLYGON_HXX
@@ -57,955 +61,863 @@
#include <basegfx/polygon/b2dpolygontools.hxx>
#endif
+#ifndef _BGFX_POLYGON_CUTANDTOUCH_HXX
+#include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
+#endif
+
+#ifndef _BGFX_RANGE_B2DRANGE_HXX
+#include <basegfx/range/b2drange.hxx>
+#endif
+
+#include <vector>
#include <algorithm>
//////////////////////////////////////////////////////////////////////////////
-// B2DPolygonNode
namespace basegfx
{
- class B2DPolygonNode
+ namespace
{
- B2DPoint maPosition;
- B2DPolygonNode* mpPrevious;
- B2DPolygonNode* mpNext;
-
- B2DPolygonNode* mpListPrevious;
- B2DPolygonNode* mpListNext;
+ //////////////////////////////////////////////////////////////////////////////
- public:
- B2DPolygonNode(const B2DPoint& rPosition, B2DPolygonNode* pPrevious);
- ~B2DPolygonNode();
-
- B2DPolygonNode* getPrevious() const { return mpPrevious; }
- B2DPolygonNode* getNext() const { return mpNext; }
- const B2DPoint& getPosition() const { return maPosition; }
+ bool impLeftOfEdges(const B2DPoint& rPrev, const B2DPoint& rCurr, const B2DPoint& rNext, const B2DPoint& rTest)
+ {
+ // tests if rTest is left of both directed line segments along the line rPrev, rCurr, rNext. Test is
+ // with border, so for rTest on border or rTest == rCtrr, true is returned, too.
+ const B2DVector aVecA(rCurr - rPrev); // A is edge vector from prev to curr
+ const B2DVector aVecB(rNext - rCurr); // B is edge vector from curr to next
+ const B2DVector aVecTest(rTest - rCurr); // testpoint seen as vector, too
- void calcMinMaxX(double& fMaxAX, double& fMinAX) const;
- void calcMinMaxY(double& fMaxAY, double& fMinAY) const;
+ if(aVecA.cross(aVecB) < 0.0)
+ {
+ // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
+ const bool bBoolA(fTools::lessOrEqual(aVecA.cross(aVecTest), 0.0));
+ const bool bBoolB(fTools::lessOrEqual(aVecB.cross(aVecTest), 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 seeen as inside)
+ const bool bBoolA(fTools::more(aVecA.cross(aVecTest), 0.0));
+ const bool bBoolB(fTools::more(aVecB.cross(aVecTest), 0.0));
+ return (!(bBoolA && bBoolB));
+ }
+ }
- void swapPreviousNext() { B2DPolygonNode* pZwi = mpPrevious; mpPrevious = mpNext; mpNext = pZwi; }
- void swapNextPointers(B2DPolygonNode* pCand);
+ //////////////////////////////////////////////////////////////////////////////
- void addToList(B2DPolygonNode*& rpList);
- void remFromList(B2DPolygonNode*& rpList);
+ struct impSortNode
+ {
+ B2DPoint maPoint;
+ sal_uInt32 mnIndex;
- B2DRange getRange() const;
- };
+ // sort operator to be able to sort on coordinates to later see common points
+ bool operator<(const impSortNode& rComp) const
+ {
+ if(fTools::equal(maPoint.getX(), rComp.maPoint.getX()))
+ {
+ if(fTools::equal(maPoint.getY(), rComp.maPoint.getY()))
+ {
+ return (mnIndex < rComp.mnIndex);
+ }
+ else
+ {
+ return fTools::less(maPoint.getY(), rComp.maPoint.getY());
+ }
+ }
+ else
+ {
+ return fTools::less(maPoint.getX(), rComp.maPoint.getX());
+ }
+ }
+ };
- B2DPolygonNode::B2DPolygonNode(const B2DPoint& rPosition, B2DPolygonNode* pPrevious)
- : maPosition(rPosition)
- {
- mpListPrevious = this;
- mpListNext = this;
+ //////////////////////////////////////////////////////////////////////////////
- if(pPrevious)
- {
- mpNext = pPrevious->getNext();
- mpPrevious = pPrevious;
- mpNext->mpPrevious = this;
- mpPrevious->mpNext = this;
- }
- else
+ enum CommonPointType
{
- mpPrevious = mpNext = this;
- }
- }
+ COMMON_IS_PARALLEL, // C0: parallel in one direction
+ COMMON_IS_PARALLEL_OPPOSITE, // C2: parallel opposite directions
+ COMMON_IS_LEAVE, // C1: A leaving B
+ COMMON_IS_LEAVE_OPPOSITE, // C3: A leaving B in opposite direction
+ COMMON_IS_ENTER, // C4: A entering B
+ COMMON_IS_ENTER_OPPOSITE, // C5: A entering B in opposite direction
+ COMMON_IS_TOUCH, // C6: A touching B
+ COMMON_IS_CROSS, // C7: A crossing B
+ COMMON_IS_DEADEND // C8: one or both are a deadend, so it's only a touch
+ };
- B2DPolygonNode::~B2DPolygonNode()
- {
- if(mpNext != this)
+ CommonPointType impGetCommonPointType(const B2DPoint& rPoint, const B2DPoint& rPrevA, const B2DPoint& rNextA, const B2DPoint& rPrevB, const B2DPoint& rNextB)
{
- mpPrevious->mpNext = mpNext;
- mpNext->mpPrevious = mpPrevious;
- }
- }
+ if(rPrevA.equal(rNextA) || rPrevB.equal(rNextB))
+ {
+ return COMMON_IS_DEADEND;
+ }
+ else if(rPrevA.equal(rPrevB))
+ {
+ if(rNextA.equal(rNextB))
+ {
+ return COMMON_IS_PARALLEL;
+ }
+ else
+ {
+ return COMMON_IS_LEAVE;
+ }
+ }
+ else if(rPrevA.equal(rNextB))
+ {
+ if(rNextA.equal(rPrevB))
+ {
+ return COMMON_IS_PARALLEL_OPPOSITE;
+ }
+ else
+ {
+ return COMMON_IS_LEAVE_OPPOSITE;
+ }
+ }
+ else if(rNextA.equal(rNextB))
+ {
+ return COMMON_IS_ENTER;
+ }
+ else if(rNextA.equal(rPrevB))
+ {
+ return COMMON_IS_ENTER_OPPOSITE;
+ }
+ else
+ {
+ // C7, C8: check for crossover
+ const bool bSideOfPrevB(impLeftOfEdges(rPrevA, rPoint, rNextA, rPrevB));
+ const bool bSideOfNextB(impLeftOfEdges(rPrevA, rPoint, rNextA, rNextB));
- void B2DPolygonNode::calcMinMaxX(double& fMaxAX, double& fMinAX) const
- {
- if(maPosition.getX() > mpNext->maPosition.getX())
- {
- fMaxAX = maPosition.getX();
- fMinAX = mpNext->maPosition.getX();
- }
- else
- {
- fMaxAX = mpNext->maPosition.getX();
- fMinAX = maPosition.getX();
+ if(bSideOfPrevB == bSideOfNextB)
+ {
+ return COMMON_IS_TOUCH;
+ }
+ else
+ {
+ return COMMON_IS_CROSS;
+ }
+ }
}
- }
- void B2DPolygonNode::calcMinMaxY(double& fMaxAY, double& fMinAY) const
- {
- if(maPosition.getY() > mpNext->maPosition.getY())
- {
- fMaxAY = maPosition.getY();
- fMinAY = mpNext->maPosition.getY();
- }
- else
- {
- fMaxAY = mpNext->maPosition.getY();
- fMinAY = maPosition.getY();
- }
- }
+ //////////////////////////////////////////////////////////////////////////////
- void B2DPolygonNode::swapNextPointers(B2DPolygonNode* pCand)
- {
- B2DPolygonNode* pTemporary = mpNext;
- mpNext = pCand->mpNext;
- pCand->mpNext = pTemporary;
- mpNext->mpPrevious = this;
- pCand->mpNext->mpPrevious = pCand;
- }
-
- void B2DPolygonNode::addToList(B2DPolygonNode*& rpList)
- {
- if(rpList)
+ struct impPolyPolygonPointNode
{
- mpListNext = rpList->mpListNext;
- rpList->mpListNext = this;
- mpListPrevious = rpList;
- mpListNext->mpListPrevious = this;
- }
- else
- {
- rpList = this;
- }
- }
+ sal_uInt32 mnSelf; // my own index in whole point array
+ sal_uInt32 mnPoint; // index of point in polygon
+ sal_uInt32 mnPoly; // index of polygon in polyPolygon
+ sal_uInt32 mnPrev; // index to prev in whole point array
+ sal_uInt32 mnNext; // index to next in whole point array
- void B2DPolygonNode::remFromList(B2DPolygonNode*& rpList)
- {
- if(mpListNext != this)
- {
- if(rpList == this)
- {
- rpList = mpListPrevious;
- }
+ // bitfield
+ unsigned mbUsed : 1; // used flag for later extraction
+ unsigned mbControl : 1; // hint flag if the edge of this node is a bezier segment
+ };
- mpListPrevious->mpListNext = mpListNext;
- mpListNext->mpListPrevious = mpListPrevious;
- mpListNext = mpListPrevious = this;
- }
- else
+ //////////////////////////////////////////////////////////////////////////////
+
+ void impSwitchNext(impPolyPolygonPointNode& rCandA, impPolyPolygonPointNode& rCandB, ::std::vector< impPolyPolygonPointNode >& rPointNodes)
{
- if(rpList == this)
+ // switch prev/next indices
+ impPolyPolygonPointNode& rNextA = rPointNodes[rCandA.mnNext];
+ impPolyPolygonPointNode& rNextB = rPointNodes[rCandB.mnNext];
+ rCandA.mnNext = rNextB.mnSelf;
+ rNextB.mnPrev = rCandA.mnSelf;
+ rCandB.mnNext = rNextA.mnSelf;
+ rNextA.mnPrev = rCandB.mnSelf;
+
+ if(rCandA.mbControl || rCandB.mbControl)
{
- rpList = 0L;
+ // also switch poly, point and Control to follow the correct control vectors
+ const sal_uInt32 nPoint(rCandA.mnPoint); rCandA.mnPoint = rCandB.mnPoint; rCandB.mnPoint = nPoint;
+ const sal_uInt32 nPoly(rCandA.mnPoly); rCandA.mnPoly = rCandB.mnPoly; rCandB.mnPoly = nPoly;
+ const bool bControl(rCandA.mbControl); rCandA.mbControl = rCandB.mbControl; rCandB.mbControl = bControl;
}
}
- }
-
- B2DRange B2DPolygonNode::getRange() const
- {
- B2DRange aRetval;
- const B2DPolygonNode* pCurrent = this;
- do {
- aRetval.expand(pCurrent->getPosition());
- pCurrent = pCurrent->getPrevious();
- } while(pCurrent != this);
+ //////////////////////////////////////////////////////////////////////////////
- return aRetval;
- }
-} // end of namespace basegfx
-
-//////////////////////////////////////////////////////////////////////////////
-// B2DSimpleCut
-
-namespace basegfx
-{
- class B2DSimpleCut
- {
- B2DPolygonNode* mpLeft;
- B2DPolygonNode* mpRight;
-
- public:
- B2DSimpleCut(B2DPolygonNode* pL, B2DPolygonNode* pR)
- : mpLeft(pL),
- mpRight(pR)
+ B2DPoint impGetB2DPoint(const impPolyPolygonPointNode& rNode, const B2DPolyPolygon& rPolyPolygon)
{
+ return rPolyPolygon.getB2DPolygon(rNode.mnPoly).getB2DPoint(rNode.mnPoint);
}
- void solve()
+ //////////////////////////////////////////////////////////////////////////////
+
+ B2DPoint impGetControlPointA(const impPolyPolygonPointNode& rNode, const B2DPolyPolygon& rPolyPolygon)
{
- mpLeft->swapNextPointers(mpRight);
+ return rPolyPolygon.getB2DPolygon(rNode.mnPoly).getControlPointA(rNode.mnPoint);
}
- B2DPolygonNode* getLeft() const { return mpLeft; }
- B2DPolygonNode* getRight() const { return mpRight; }
+ //////////////////////////////////////////////////////////////////////////////
- bool isSameCut(B2DPolygonNode* pA, B2DPolygonNode* pB) const
+ B2DPoint impGetControlPointB(const impPolyPolygonPointNode& rNode, const B2DPolyPolygon& rPolyPolygon)
{
- return ((pA == mpLeft && pB == mpRight) || (pB == mpLeft && pA == mpRight));
+ return rPolyPolygon.getB2DPolygon(rNode.mnPoly).getControlPointB(rNode.mnPoint);
}
- };
+
+ //////////////////////////////////////////////////////////////////////////////
+
+ } // end of anonymous namespace
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
-// implementation B2DPolyPolygonCutter
namespace basegfx
{
- B2DPolyPolygonCutter::~B2DPolyPolygonCutter()
+ namespace
{
- for(sal_uInt32 a(0L); a < maPolygonList.size(); a++)
- {
- delete maPolygonList[a];
- }
-
- maPolygonList.clear();
- }
-
-//BFS08 void B2DPolyPolygonCutter::removeIncludedPolygons(bool bUseOr)
-//BFS08 {
-//BFS08 const sal_uInt32 aCount(maPolygonList.size());
-//BFS08 B2DClipExtraPolygonInfo* pInfos = new B2DClipExtraPolygonInfo[aCount];
-//BFS08 sal_uInt32 a, b;
-//BFS08
-//BFS08 // fill infos
-//BFS08 for(a = 0L; a < aCount; a++)
-//BFS08 {
-//BFS08 pInfos[a].init(maPolygonList[a]);
-//BFS08 }
-//BFS08
-//BFS08 // get all includes
-//BFS08 for(a = 0L; a < aCount; a++)
-//BFS08 {
-//BFS08 B2DClipExtraPolygonInfo& rInfoA = pInfos[a];
-//BFS08
-//BFS08 for(b = 0L; b < aCount; b++)
-//BFS08 {
-//BFS08 B2DClipExtraPolygonInfo& rInfoB = pInfos[b];
-//BFS08
-//BFS08 if(a != b && doRangesInclude(rInfoA.getRange(), rInfoB.getRange()))
-//BFS08 {
-//BFS08 // volume B in A, test pA, pB for inclusion, with border
-//BFS08 if(maPolygonList[a]->isPolygonInside(maPolygonList[b], true))
-//BFS08 {
-//BFS08 // pB is inside pA
-//BFS08 rInfoB.changeDepth(rInfoA.getOrientation());
-//BFS08 }
-//BFS08 }
-//BFS08 }
-//BFS08 }
-//BFS08
-//BFS08 // delete removable
-//BFS08 for(a = 0L, b = 0L; a < aCount; a++)
-//BFS08 {
-//BFS08 B2DClipExtraPolygonInfo& rInfo = pInfos[a];
-//BFS08
-//BFS08 if((bUseOr && rInfo.getDepth() != 0L) || (!bUseOr && rInfo.getDepth() < 1L))
-//BFS08 {
-//BFS08 B2DPolygonNodeVector::iterator aPosition(maPolygonList.begin() + b);
-//BFS08 B2DPolygonNode* pCandidate = *aPosition;
-//BFS08 maPolygonList.erase(aPosition);
-//BFS08 deletePolygon(pCandidate);
-//BFS08 }
-//BFS08 else
-//BFS08 {
-//BFS08 b++;
-//BFS08 }
-//BFS08 }
-//BFS08
-//BFS08 // delete infos
-//BFS08 delete[] pInfos;
-//BFS08 }
-
- void B2DPolyPolygonCutter::solveAllCuts(B2DSimpleCutVector& rCuts)
- {
- B2DPolygonNode* pNewList = 0L;
-
- // add all nodes of polys to list
- polysToList(pNewList);
-
- // solve cuts
- B2DSimpleCutVector::iterator aCandidate(rCuts.begin());
+ //////////////////////////////////////////////////////////////////////////////
- for(; aCandidate < rCuts.end(); aCandidate++)
+ class impPolygonCrossoverSolver
{
- B2DSimpleCut* pCut = *aCandidate;
- pCut->solve();
- delete pCut;
- }
-
- rCuts.clear();
+ const B2DPolygon& maOriginal;
+ B2DPolygon maGeometry;
+ ::std::vector< impPolyPolygonPointNode > maPointNodes;
- // extract polys
- listToPolys(pNewList);
- }
+ // bitfield
+ unsigned mbChanged : 1;
- void B2DPolyPolygonCutter::polysToList(B2DPolygonNode*& rpList)
- {
- B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
+ void impHandleCommon(impPolyPolygonPointNode& rCandA, impPolyPolygonPointNode& rCandB)
+ {
+ const B2DPoint aPoint(maGeometry.getB2DPoint(rCandA.mnSelf));
+ const B2DPoint aPrevA(maGeometry.getB2DPoint(rCandA.mnPrev));
+ const B2DPoint aNextA(maGeometry.getB2DPoint(rCandA.mnNext));
+ const B2DPoint aPrevB(maGeometry.getB2DPoint(rCandB.mnPrev));
+ const B2DPoint aNextB(maGeometry.getB2DPoint(rCandB.mnNext));
+ const CommonPointType aType(impGetCommonPointType(aPoint, aPrevA, aNextA, aPrevB, aNextB));
+
+ switch(aType)
+ {
+ case COMMON_IS_LEAVE : // A leaving B
+ case COMMON_IS_LEAVE_OPPOSITE : // A leaving B in opposite direction
+ case COMMON_IS_ENTER : // A entering B
+ case COMMON_IS_ENTER_OPPOSITE : // A entering B in opposite direction
+ case COMMON_IS_CROSS : // A crossing B
+ {
+ impSwitchNext(rCandA, rCandB, maPointNodes);
+ mbChanged = true;
+ break;
+ }
+ }
+ }
- for(; aCandidate != maPolygonList.end(); aCandidate++)
- {
- addAllNodes(*aCandidate, rpList);
- }
+ void impBuildGraph()
+ {
+ sal_uInt32 a;
+
+ // prepare input: create all selfcuts and touches. After
+ // this step, there will be no cut or touch inside edges, only at points.
+ // Also remove double points to always have a edge length and direction.
+ maGeometry = tools::addPointsAtCutsAndTouches(maOriginal);
+ maGeometry.removeDoublePoints();
+ const bool bControl(maGeometry.areControlPointsUsed());
+
+ // create space in point and sort vector.
+ const sal_uInt32 nCount(maGeometry.count());
+ ::std::vector< impSortNode > aSortNodes;
+ maPointNodes.resize(nCount);
+ aSortNodes.resize(nCount);
+
+ // fill data to points and sort vector
+ for(a = 0L; a < nCount; a++)
+ {
+ impPolyPolygonPointNode& rNewPointNode = maPointNodes[a];
+ rNewPointNode.mnSelf = a;
+ rNewPointNode.mnPoint = a;
+ rNewPointNode.mnPoly = 0L;
+ rNewPointNode.mnPrev = (a != 0L) ? a - 1L : nCount - 1L;
+ rNewPointNode.mnNext = (a + 1L == nCount) ? 0L : a + 1L;
+ rNewPointNode.mbUsed = false;
+ rNewPointNode.mbControl = (bControl ? !(maGeometry.getControlVectorA(a).equalZero() && maGeometry.getControlVectorB(a).equalZero()) : false);
+
+ impSortNode& rNewSortNode = aSortNodes[a];
+ rNewSortNode.maPoint = maGeometry.getB2DPoint(a);
+ rNewSortNode.mnIndex = a;
+ }
- maPolygonList.clear();
- }
+ // sort by point to identify common nodes
+ ::std::sort(aSortNodes.begin(), aSortNodes.end());
- void B2DPolyPolygonCutter::listToPolys(B2DPolygonNode*& rpList)
- {
- while(rpList)
- {
- // get one
- B2DPolygonNode* pNew = extractNextPolygon(rpList);
+ // handle common nodes
+ for(a = 0L; a < aSortNodes.size() - 1L; a++)
+ {
+ for(sal_uInt32 b(a + 1L); aSortNodes[a].maPoint.equal(aSortNodes[b].maPoint) && b < aSortNodes.size(); b++)
+ {
+ impHandleCommon(maPointNodes[aSortNodes[a].mnIndex], maPointNodes[aSortNodes[b].mnIndex]);
+ }
+ }
+ }
- if(pNew)
+ public:
+ impPolygonCrossoverSolver(const B2DPolygon& rPolygon)
+ : maOriginal(rPolygon),
+ mbChanged(false)
{
- maPolygonList.push_back(pNew);
+ if(maOriginal.count())
+ {
+ impBuildGraph();
+ }
}
- }
- }
- B2DPolygonNode* B2DPolyPolygonCutter::createNewPolygon(const B2DPolygon& rPolygon)
- {
- B2DPolygonNode* pRetval = NULL;
+ B2DPolyPolygon getB2DPolyPolygon()
+ {
+ if(mbChanged)
+ {
+ B2DPolyPolygon aRetval;
+ sal_uInt32 nPointsUsed(0L);
- for(sal_uInt32 a(0L); a < rPolygon.count(); a++)
- {
- B2DPoint aPoint(rPolygon.getB2DPoint(a));
- pRetval = new B2DPolygonNode(aPoint, pRetval);
- }
+ for(sal_uInt32 a(0L); nPointsUsed != maGeometry.count() && a < maPointNodes.size(); a++)
+ {
+ impPolyPolygonPointNode& rNode = maPointNodes[a];
- return pRetval;
- }
+ if(!rNode.mbUsed)
+ {
+ B2DPolygon aNew;
+ sal_uInt32 nCurr(rNode.mnSelf);
+ bool bCurveUsed(false);
- void B2DPolyPolygonCutter::deletePolygon(B2DPolygonNode* pCand)
- {
- B2DPolygonNode* pPoly = pCand;
+ do
+ {
+ impPolyPolygonPointNode& rCandidate = maPointNodes[nCurr];
+ const B2DPoint aNewPoint(maGeometry.getB2DPoint(rCandidate.mnPoint));
- while(pPoly)
- {
- B2DPolygonNode* pNext = pPoly->getNext();
+ if(aNew.count() > 1L && !rCandidate.mbControl && aNew.getB2DPoint(aNew.count() - 2L).equal(aNewPoint))
+ {
+ // previous last and to be added point are the same, this would create a deadend
+ // neutral polygon. Instead of adding, remove last point to achieve the same but without
+ // creating deadends.
+ aNew.remove(aNew.count() - 1L);
+ }
+ else
+ {
+ aNew.append(aNewPoint);
- if(pNext == pPoly)
- {
- pNext = 0L;
- }
+ if(rCandidate.mbControl)
+ {
+ const sal_uInt32 nNewIndex(aNew.count() - 1L);
+ aNew.setControlVectorA(nNewIndex, maGeometry.getControlVectorA(rCandidate.mnPoint));
+ aNew.setControlVectorB(nNewIndex, maGeometry.getControlVectorB(rCandidate.mnPoint));
+ bCurveUsed = true;
+ }
+ }
- delete pPoly;
- pPoly = pNext;
- }
- }
+ // mark as used and go to next
+ nPointsUsed++;
+ rCandidate.mbUsed = true;
+ nCurr = rCandidate.mnNext;
+ }
+ while(nCurr != rNode.mnSelf);
- void B2DPolyPolygonCutter::addAllNodes(B2DPolygonNode* pPolygon, B2DPolygonNode*& rpList)
- {
- B2DPolygonNode* pAct = pPolygon;
+ if(aNew.count() > 2L || bCurveUsed)
+ {
+ aNew.setClosed(true);
+ aRetval.append(aNew);
+ }
+ }
+ }
- do {
- pAct->addToList(rpList);
- pAct = pAct->getNext();
- } while(pAct != pPolygon);
- }
+ return aRetval;
+ }
+ else
+ {
+ return B2DPolyPolygon(maOriginal);
+ }
+ }
+ };
- void B2DPolyPolygonCutter::addPolygon(const B2DPolygon& rPolygon)
- {
- if(rPolygon.isClosed() && rPolygon.count() > 2)
- {
- B2DPolygonNode* pNew = createNewPolygon(rPolygon);
- maPolygonList.push_back(pNew);
- }
- }
+ //////////////////////////////////////////////////////////////////////////////
- void B2DPolyPolygonCutter::addPolyPolygon(const B2DPolyPolygon& rPolyPolygon)
- {
- for(sal_uInt32 a(0L); a < rPolyPolygon.count(); a++)
- {
- B2DPolygon aCandidate = rPolyPolygon.getB2DPolygon(a);
- addPolygon(aCandidate);
- }
- }
+ } // end of anonymous namespace
+} // end of namespace basegfx
- B2DPolyPolygon B2DPolyPolygonCutter::getPolyPolygon()
+//////////////////////////////////////////////////////////////////////////////
+
+namespace basegfx
+{
+ namespace
{
- B2DPolyPolygon aRetval;
- B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
+ //////////////////////////////////////////////////////////////////////////////
- for(; aCandidate < maPolygonList.end(); aCandidate++)
+ class impPolyPolygonCrossoverSolver
{
- B2DPolygonNode* pCand = *aCandidate;
- B2DPolygonNode* pAct = pCand;
- sal_uInt32 nCount(0L);
+ const B2DPolyPolygon& maOriginal;
+ B2DPolyPolygon maGeometry;
+ sal_uInt32 mnPointCount;
+ ::std::vector< impPolyPolygonPointNode > maPointNodes;
- do {
- nCount++;
- pAct = pAct->getNext();
- } while(pAct != pCand);
+ // bitfield
+ unsigned mbChanged : 1;
- if(nCount > 2L)
+ void impHandleLeaving(impPolyPolygonPointNode& rCandA, impPolyPolygonPointNode& rCandB, bool bOpposite, bool bSideOfLeave)
{
- B2DPolygon aNewPolygon;
+ // go back on A and look for node entering B
+ sal_uInt32 nIndexA(rCandA.mnSelf);
+ sal_uInt32 nIndexB(rCandB.mnSelf);
+ bool bOnCommonEdge(true);
+
+ // go along common edge as long as we are on common edge, backward on
+ // A and depending on bOpposite along B. Since we are on a leave, there must
+ // exist an entering node, so the loop will end.
+ while(bOnCommonEdge)
+ {
+ const sal_uInt32 nCandA(maPointNodes[nIndexA].mnPrev);
+ const sal_uInt32 nCandB((bOpposite) ? maPointNodes[nIndexB].mnNext : maPointNodes[nIndexB].mnPrev);
+ const impPolyPolygonPointNode& rCandA = maPointNodes[nCandA];
+ const impPolyPolygonPointNode& rCandB = maPointNodes[nCandB];
+ const B2DPoint aPointA(impGetB2DPoint(rCandA, maGeometry));
+ const B2DPoint aPointB(impGetB2DPoint(rCandB, maGeometry));
+
+ if(aPointA.equal(aPointB))
+ {
+ // continue going along common edge
+ nIndexA = nCandA;
+ nIndexB = nCandB;
+ }
+ else
+ {
+ // done
+ bOnCommonEdge = false;
+ }
+ }
- do {
- aNewPolygon.append(pAct->getPosition());
- pAct = pAct->getNext();
- } while(pAct != pCand);
+ // now we have the last common edge in (nIndexA, nIndexB) which must be the
+ // entering edge. Get the point values from there for the crossover test
+ impPolyPolygonPointNode& rEnterCandA = maPointNodes[nIndexA];
+ impPolyPolygonPointNode& rEnterCandB = maPointNodes[nIndexB];
+ const B2DPoint aPoint(impGetB2DPoint(rEnterCandA, maGeometry));
+ const B2DPoint aPrevA(impGetB2DPoint(maPointNodes[rEnterCandA.mnPrev], maGeometry));
+ const B2DPoint aNextA(impGetB2DPoint(maPointNodes[rEnterCandA.mnNext], maGeometry));
+ bool bSideOfEnter;
- aNewPolygon.setClosed(true);
- aRetval.append(aNewPolygon);
- }
+ if(bOpposite)
+ {
+ const B2DPoint aNextB(impGetB2DPoint(maPointNodes[rEnterCandB.mnNext], maGeometry));
+ bSideOfEnter = impLeftOfEdges(aPrevA, aPoint, aNextA, aNextB);
+ }
+ else
+ {
+ const B2DPoint aPrevB(impGetB2DPoint(maPointNodes[rEnterCandB.mnPrev], maGeometry));
+ bSideOfEnter = impLeftOfEdges(aPrevA, aPoint, aNextA, aPrevB);
+ }
- deletePolygon(pCand);
- }
+ if(bSideOfLeave != bSideOfEnter)
+ {
+ // crossover, needs to be solved
+ if(bOpposite)
+ {
+ // switch at enter and leave, make the common edge(s) an own neutral
+ // polygon
+ impSwitchNext(rEnterCandA, rEnterCandB, maPointNodes);
+ impSwitchNext(rCandA, rCandB, maPointNodes);
+ }
+ else
+ {
+ // switch at leave
+ impSwitchNext(rCandA, rCandB, maPointNodes);
+ }
+
+ // set changed flag
+ mbChanged = true;
+ }
+ }
- maPolygonList.clear();
+ void impHandleCommon(impPolyPolygonPointNode& rCandA, impPolyPolygonPointNode& rCandB)
+ {
+ const B2DPoint aPoint(impGetB2DPoint(rCandA, maGeometry));
+ const impPolyPolygonPointNode& rNodePrevA = maPointNodes[rCandA.mnPrev];
+ const impPolyPolygonPointNode& rNodePrevB = maPointNodes[rCandB.mnPrev];
- return aRetval;
- }
+ B2DPoint aPrevA(impGetB2DPoint(rNodePrevA, maGeometry));
+ B2DPoint aNextA(impGetB2DPoint(maPointNodes[rCandA.mnNext], maGeometry));
+ B2DPoint aPrevB(impGetB2DPoint(rNodePrevB, maGeometry));
+ B2DPoint aNextB(impGetB2DPoint(maPointNodes[rCandB.mnNext], maGeometry));
- B2DSimpleCut* B2DPolyPolygonCutter::getExistingCut(B2DSimpleCutVector& rTmpCuts, B2DPolygonNode* pA, B2DPolygonNode* pB)
- {
- for(sal_uInt32 a(0L); a < rTmpCuts.size(); a++)
- {
- B2DSimpleCut* pCand = rTmpCuts[a];
+ if(rNodePrevA.mbControl)
+ {
+ const B2DPoint aCandidate(impGetControlPointB(rNodePrevA, maGeometry));
- if(pCand->isSameCut(pA, pB))
- {
- return pCand;
- }
- }
+ if(!aCandidate.equal(aPoint))
+ {
+ aPrevA = aCandidate;
+ }
+ }
- return 0L;
- }
+ if(rNodePrevB.mbControl)
+ {
+ const B2DPoint aCandidate(impGetControlPointB(rNodePrevB, maGeometry));
- B2DPolygonNode* B2DPolyPolygonCutter::extractNextPolygon(B2DPolygonNode*& rpList)
- {
- B2DPolygonNode* pStart = rpList;
+ if(!aCandidate.equal(aPoint))
+ {
+ aPrevB = aCandidate;
+ }
+ }
- // remove all nodes of this poly from list
- B2DPolygonNode* pAct = pStart;
- sal_uInt32 nNumNodes(0L);
+ if(rCandA.mbControl)
+ {
+ const B2DPoint aCandidate(impGetControlPointA(rCandA, maGeometry));
- do {
- pAct->remFromList(rpList);
- pAct = pAct->getNext();
- nNumNodes++;
- } while(pAct != pStart);
+ if(!aCandidate.equal(aPoint))
+ {
+ aNextA = aCandidate;
+ }
+ }
- if(nNumNodes < 3L)
- {
- deletePolygon(pStart);
- return 0L;
- }
- else
- {
- return pStart;
- }
- }
+ if(rCandB.mbControl)
+ {
+ const B2DPoint aCandidate(impGetControlPointA(rCandB, maGeometry));
- void B2DPolyPolygonCutter::removeSelfIntersections()
- {
- B2DSimpleCutVector aCuts;
- B2DSimpleCutVector aNewCuts;
- B2DPolygonNode* pCand;
- B2DPolygonNode* pA;
- B2DPolygonNode* pB;
- double fMaxAX, fMinAX, fMaxAY, fMinAY;
- double fMaxBX, fMinBX, fMaxBY, fMinBY;
- double fCut;
-
- // first job: Find all cuts and add points there
- for(sal_uInt32 a(0L); a < maPolygonList.size(); a++)
- {
- pCand = maPolygonList[a];
- pA = pCand;
+ if(!aCandidate.equal(aPoint))
+ {
+ aNextB = aCandidate;
+ }
+ }
- // one run to find same start positions (so there is no need to
- // search for existing cuts in main loop)
- do {
- pB = pA->getNext();
+ const CommonPointType aType(impGetCommonPointType(aPoint, aPrevA, aNextA, aPrevB, aNextB));
- do {
- if(pA->getPosition().equal(pB->getPosition()))
+ switch(aType)
+ {
+ case COMMON_IS_LEAVE : // A leaving B
+ {
+ impHandleLeaving(rCandA, rCandB, false, impLeftOfEdges(aPrevA, aPoint, aNextA, aNextB));
+ break;
+ }
+ case COMMON_IS_LEAVE_OPPOSITE : // A leaving B in opposite direction
+ {
+ impHandleLeaving(rCandA, rCandB, true, impLeftOfEdges(aPrevA, aPoint, aNextA, aPrevB));
+ break;
+ }
+ case COMMON_IS_CROSS : // A crossing B
{
-//BFS08 aNewCuts.push_back(new B2DSimpleCut(pA, pB, true, pCand->getOrientation()));
- aNewCuts.push_back(new B2DSimpleCut(pA, pB));
+ impSwitchNext(rCandA, rCandB, maPointNodes);
+ mbChanged = true;
+ break;
}
+ }
+ }
- // next B
- pB = pB->getNext();
- } while(pB != pCand);
+ void impBuildGraph()
+ {
+ sal_uInt32 a, b, c;
+
+ // prepare input: create all selfcuts and touches. After
+ // this step, there will be no cut or touch inside edges, only at points.
+ // Self-intersections are not handled, should have been done outside this
+ // helper already.
+ // Also remove double points to always have a edge length and direction.
+ maGeometry = tools::addPointsAtCutsAndTouches(maOriginal, false);
+ maGeometry.removeDoublePoints();
+
+ // get mnPointCount
+ for(a = 0L; a < maGeometry.count(); a++)
+ {
+ mnPointCount += maGeometry.getB2DPolygon(a).count();
+ }
- // next A
- pA = pA->getNext();
- } while(pA->getNext() != pCand);
+ // create space in point and sort vector.
+ ::std::vector< impSortNode > aSortNodes;
+ maPointNodes.resize(mnPointCount);
+ aSortNodes.resize(mnPointCount);
- // second run to find real cuts
- pA = pCand;
+ // fill data to points and sort vector
+ for(a = c = 0L; a < maGeometry.count(); a++)
+ {
+ const B2DPolygon aPartGeometry(maGeometry.getB2DPolygon(a));
+ const bool bControl(aPartGeometry.areControlPointsUsed());
+ const sal_uInt32 nPartCount(aPartGeometry.count());
+ const sal_uInt32 nNewPolyStart(c);
- do {
- // get bounds for this edge in poly
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- pB = pA->getNext();
+ for(b = 0L; b < nPartCount; b++, c++)
+ {
+ impPolyPolygonPointNode& rNewPointNode = maPointNodes[c];
+ rNewPointNode.mnSelf = c;
+ rNewPointNode.mnPoint = b;
+ rNewPointNode.mnPoly = a;
+ rNewPointNode.mnNext = nNewPolyStart + ((b + 1L == nPartCount) ? 0L : b + 1L);
+ rNewPointNode.mnPrev = nNewPolyStart + ((b != 0L) ? b - 1L : nPartCount - 1L);
+ rNewPointNode.mbUsed = false;
+ rNewPointNode.mbControl = (bControl ? !(aPartGeometry.getControlVectorA(b).equalZero() && aPartGeometry.getControlVectorB(b).equalZero()) : false);
+
+ impSortNode& rNewSortNode = aSortNodes[c];
+ rNewSortNode.maPoint = aPartGeometry.getB2DPoint(b);
+ rNewSortNode.mnIndex = c;
+ }
+ }
- do {
- pB->calcMinMaxX(fMaxBX, fMinBX);
+ // sort by point to identify common nodes
+ ::std::sort(aSortNodes.begin(), aSortNodes.end());
- if(fTools::moreOrEqual(fMaxBX, fMinAX) // #116732#
- && fTools::moreOrEqual(fMaxAX, fMinBX)) // #116732#
+ // handle common nodes
+ for(a = 0L; a < aSortNodes.size() - 1L; a++)
+ {
+ for(b = a + 1L; aSortNodes[a].maPoint.equal(aSortNodes[b].maPoint) && b < aSortNodes.size(); b++)
{
- pB->calcMinMaxY(fMaxBY, fMinBY);
+ impHandleCommon(maPointNodes[aSortNodes[a].mnIndex], maPointNodes[aSortNodes[b].mnIndex]);
+ }
+ }
+ }
+
+ public:
+ impPolyPolygonCrossoverSolver(const B2DPolyPolygon& rPolyPolygon)
+ : maOriginal(rPolyPolygon),
+ mnPointCount(0L),
+ mbChanged(false)
+ {
+ if(maOriginal.count())
+ {
+ impBuildGraph();
+ }
+ }
+
+ B2DPolyPolygon getB2DPolyPolygon()
+ {
+ if(mbChanged)
+ {
+ B2DPolyPolygon aRetval;
+ sal_uInt32 nPointsUsed(0L);
+
+ for(sal_uInt32 a(0L); nPointsUsed != mnPointCount && a < maPointNodes.size(); a++)
+ {
+ impPolyPolygonPointNode& rNode = maPointNodes[a];
- if(fTools::moreOrEqual(fMaxBY, fMinAY) // #116732#
- && fTools::moreOrEqual(fMaxAY, fMinBY)) // #116732#
+ if(!rNode.mbUsed)
{
- if(!pA->getPosition().equal(pB->getPosition()))
+ B2DPolygon aNew;
+ sal_uInt32 nCurr(rNode.mnSelf);
+ bool bCurveUsed(false);
+
+ do
{
- const B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
- const B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
+ impPolyPolygonPointNode& rCandidate = maPointNodes[nCurr];
+ const B2DPoint aNewPoint(impGetB2DPoint(rCandidate, maGeometry));
- if(tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
+ if(aNew.count() > 1L && !rCandidate.mbControl && aNew.getB2DPoint(aNew.count() - 2L).equal(aNewPoint))
{
- // crossover, two new points
- B2DPoint aNewPos(interpolate(pA->getPosition(), pA->getNext()->getPosition(), fCut));
- B2DPolygonNode* pCutLo = new B2DPolygonNode(aNewPos, pA);
- B2DPolygonNode* pCutHi = new B2DPolygonNode(aNewPos, pB);
-//BFS08 aNewCuts.push_back(new B2DSimpleCut(pCutLo, pCutHi, true, pCand->getOrientation()));
- aNewCuts.push_back(new B2DSimpleCut(pCutLo, pCutHi));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
+ // previous last and to be added point are the same, this would create a deadend
+ // neutral polygon. Instead of adding, remove last point to achieve the same but without
+ // creating deadends.
+ aNew.remove(aNew.count() - 1L);
}
else
{
- if(tools::isPointOnEdge(pA->getPosition(), pB->getPosition(), aVectorB, &fCut))
- {
- // startpoint A at edge B, one new point
- B2DPolygonNode* pCutHi = new B2DPolygonNode(pA->getPosition(), pB);
-//BFS08 aNewCuts.push_back(new B2DSimpleCut(pA, pCutHi, true, pCand->getOrientation()));
- aNewCuts.push_back(new B2DSimpleCut(pA, pCutHi));
- }
- else if(tools::isPointOnEdge(pB->getPosition(), pA->getPosition(), aVectorA, &fCut))
+ aNew.append(aNewPoint);
+
+ if(rCandidate.mbControl)
{
- // startpoint B at edge A, one new point
- B2DPolygonNode* pCutLo = new B2DPolygonNode(pB->getPosition(), pA);
-//BFS08 aNewCuts.push_back(new B2DSimpleCut(pCutLo, pB, true, pCand->getOrientation()));
- aNewCuts.push_back(new B2DSimpleCut(pCutLo, pB));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
+ const sal_uInt32 nNewIndex(aNew.count() - 1L);
+ const B2DPolygon aTempPolygon(maGeometry.getB2DPolygon(rCandidate.mnPoly));
+ aNew.setControlVectorA(nNewIndex, aTempPolygon.getControlVectorA(rCandidate.mnPoint));
+ aNew.setControlVectorB(nNewIndex, aTempPolygon.getControlVectorB(rCandidate.mnPoint));
+ bCurveUsed = true;
}
}
+
+ // mark as used and go to next
+ rCandidate.mbUsed = true;
+ nCurr = rCandidate.mnNext;
+ }
+ while(nCurr != rNode.mnSelf);
+
+ if(aNew.count() > 2L || bCurveUsed)
+ {
+ aNew.setClosed(true);
+ aRetval.append(aNew);
}
}
}
- // next B
- pB = pB->getNext();
- } while(pB != pCand);
-
- // next A
- pA = pA->getNext();
- } while(pA->getNext() != pCand);
-
- // copy new cuts to cuts
- aCuts.insert(aCuts.begin(), aNewCuts.begin(), aNewCuts.end());
- aNewCuts.clear();
- }
+ return aRetval;
+ }
+ else
+ {
+ return B2DPolyPolygon(maOriginal);
+ }
+ }
+ };
- // second job: if there were cuts, split polys
- if(aCuts.size())
- {
- solveAllCuts(aCuts);
- }
- }
+ //////////////////////////////////////////////////////////////////////////////
- bool B2DPolyPolygonCutter::isCrossover(B2DPolygonNode* pA, B2DPolygonNode* pB)
- {
- // build entering vectors
- B2DVector aVecA(pA->getPrevious()->getPosition() - pA->getPosition());
- B2DVector aVecB(pB->getPrevious()->getPosition() - pA->getPosition());
- aVecA.normalize();
- aVecB.normalize();
- double fDegreeA2 = atan2(aVecA.getY(), aVecA.getX());
- double fDegreeB2 = atan2(aVecB.getY(), aVecB.getX());
-
- // build leaving vectors
- aVecA = pA->getNext()->getPosition() - pA->getPosition();
- aVecB = pB->getNext()->getPosition() - pA->getPosition();
- aVecA.normalize();
- aVecB.normalize();
- double fDegreeA1 = atan2(aVecA.getY(), aVecA.getX());
- double fDegreeB1 = atan2(aVecB.getY(), aVecB.getX());
-
- // compare
- if(fDegreeA1 > fDegreeA2)
+ struct impStripHelper
{
- double fTemp = fDegreeA2;
- fDegreeA2 = fDegreeA1;
- fDegreeA1 = fTemp;
- }
-
- bool bB1Inside(fTools::more(fDegreeB1, fDegreeA1)
- && fTools::more(fDegreeA2, fDegreeB1));
- bool bB2Inside(fTools::more(fDegreeB2, fDegreeA1)
- && fTools::more(fDegreeA2, fDegreeB2));
+ B2DRange maRange;
+ sal_Int32 mnDepth;
+ B2VectorOrientation meOrinetation;
+ };
- if(bB1Inside && bB2Inside)
- {
- return false;
- }
+ //////////////////////////////////////////////////////////////////////////////
- bool bB1Outside(fTools::more(fDegreeA1, fDegreeB1)
- || fTools::more(fDegreeB1, fDegreeA2));
- bool bB2Outside(fTools::more(fDegreeA1, fDegreeB2)
- || fTools::more(fDegreeB2, fDegreeA2));
+ } // end of anonymous namespace
+} // end of namespace basegfx
- return !(bB1Outside && bB2Outside);
- }
+//////////////////////////////////////////////////////////////////////////////
- bool B2DPolyPolygonCutter::isCrossover(B2DSimpleCut* pEnter, B2DSimpleCut* pLeave)
+namespace basegfx
+{
+ namespace tools
{
- // build entering vectors
- B2DVector aVecJ(pEnter->getLeft()->getNext()->getPosition() - pEnter->getLeft()->getPosition());
- B2DVector aVecA(pEnter->getLeft()->getPrevious()->getPosition() - pEnter->getLeft()->getPosition());
- B2DVector aVecB(pEnter->getRight()->getPrevious()->getPosition() - pEnter->getLeft()->getPosition());
- aVecJ.normalize();
- aVecA.normalize();
- aVecB.normalize();
- double fDegreeJo = atan2(aVecJ.getY(), aVecJ.getX());
- double fDegreeA2 = atan2(aVecA.getY(), aVecA.getX()) - fDegreeJo;
- double fDegreeB2 = atan2(aVecB.getY(), aVecB.getX()) - fDegreeJo;
-
- // move to range [0..2PI[
- while(fDegreeA2 < 0.0)
- {
- fDegreeA2 += (2.0 * F_PI);
- }
+ //////////////////////////////////////////////////////////////////////////////
- while(fDegreeA2 >= (2.0 * F_PI))
+ B2DPolyPolygon SolveCrossovers(const B2DPolyPolygon& rCandidate, bool bSelfCrossovers)
{
- fDegreeA2 -= (2.0 * F_PI);
- }
+ B2DPolyPolygon aCandidate;
- // move to range [0..2PI[
- while(fDegreeB2 < 0.0)
- {
- fDegreeB2 += (2.0 * F_PI);
- }
-
- while(fDegreeB2 >= (2.0 * F_PI))
- {
- fDegreeB2 -= (2.0 * F_PI);
- }
+ if(bSelfCrossovers)
+ {
+ for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
+ {
+ aCandidate.append(SolveCrossovers(rCandidate.getB2DPolygon(a)));
+ }
+ }
+ else
+ {
+ aCandidate = rCandidate;
+ }
- bool bA2BiggerB2(fTools::more(fDegreeA2, fDegreeB2));
-
- // build leaving vectors
- aVecJ = pLeave->getLeft()->getPrevious()->getPosition() - pLeave->getLeft()->getPosition();
- aVecA = pLeave->getLeft()->getNext()->getPosition() - pLeave->getLeft()->getPosition();
- aVecB = pLeave->getRight()->getNext()->getPosition() - pLeave->getLeft()->getPosition();
- aVecJ.normalize();
- aVecA.normalize();
- aVecB.normalize();
- fDegreeJo = atan2(aVecJ.getY(), aVecJ.getX());
- double fDegreeA1 = atan2(aVecA.getY(), aVecA.getX()) - fDegreeJo;
- double fDegreeB1 = atan2(aVecB.getY(), aVecB.getX()) - fDegreeJo;
-
- // move to range [0..2PI[
- while(fDegreeA1 < 0.0)
- {
- fDegreeA1 += (2.0 * F_PI);
- }
+ if(aCandidate.count() > 1L)
+ {
+ impPolyPolygonCrossoverSolver aSolver(aCandidate);
+ aCandidate = aSolver.getB2DPolyPolygon();
+ }
- while(fDegreeA1 >= (2.0 * F_PI))
- {
- fDegreeA1 -= (2.0 * F_PI);
+ return aCandidate;
}
- // move to range [0..2PI[
- while(fDegreeB1 < 0)
- {
- fDegreeB1 += (2.0 * F_PI);
- }
+ //////////////////////////////////////////////////////////////////////////////
- while(fDegreeB1 >= (2.0 * F_PI))
+ B2DPolyPolygon SolveCrossovers(const B2DPolygon& rCandidate)
{
- fDegreeB1 -= (2.0 * F_PI);
+ impPolygonCrossoverSolver aSolver(rCandidate);
+ return aSolver.getB2DPolyPolygon();
}
- bool bA1BiggerB1(fTools::more(fDegreeA1, fDegreeB1));
+ //////////////////////////////////////////////////////////////////////////////
- // compare
- return (bA1BiggerB1 == bA2BiggerB2);
- }
+ B2DPolyPolygon StripNeutralPolygons(const B2DPolyPolygon& rCandidate)
+ {
+ B2DPolyPolygon aRetval;
- bool B2DPolyPolygonCutter::isNextSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
- {
- return pA->getNext()->getPosition().equal(pB->getNext()->getPosition());
- }
+ for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
+ {
+ const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
- bool B2DPolyPolygonCutter::isPrevSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
- {
- return pA->getPrevious()->getPosition().equal(pB->getPrevious()->getPosition());
- }
+ if(ORIENTATION_NEUTRAL != tools::getOrientation(aCandidate))
+ {
+ aRetval.append(aCandidate);
+ }
+ }
- void B2DPolyPolygonCutter::removeDoubleIntersections()
- {
- double fMaxAX, fMinAX, fMaxAY, fMinAY;
- double fMaxBX, fMinBX, fMaxBY, fMinBY;
- double fCut;
- B2DSimpleCutVector aCuts;
- B2DSimpleCutVector aTmpCuts;
- B2DSimpleCutVector aNewCuts;
- B2DPolygonNode* pCandA;
- B2DPolygonNode* pCandB;
- B2DPolygonNode* pA;
- B2DPolygonNode* pB;
- sal_uInt32 a;
-
- // create volume list for all polys for faster compares
- B2DRange* pVolumes = new B2DRange[maPolygonList.size()];
-
- for(a = 0L; a < maPolygonList.size(); a++)
- {
- pVolumes[a] = maPolygonList[a]->getRange();
+ return aRetval;
}
- // register cuts (and add points for them) between pCandA and pCandB
- for(a = 0L; a + 1L < maPolygonList.size(); a++)
+ //////////////////////////////////////////////////////////////////////////////
+
+ B2DPolyPolygon StripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
{
- pCandA = maPolygonList[a];
+ const sal_uInt32 nCount(rCandidate.count());
+ B2DPolyPolygon aRetval;
- for(sal_uInt32 b = a + 1L; b < maPolygonList.size(); b++)
+ if(nCount)
{
- if(pVolumes[a].overlaps(pVolumes[b]))
+ if(nCount == 1L)
{
- pCandB = maPolygonList[b];
- pA = pCandA;
-
- // one run to find same start positions (so there is no need to
- // search for existing cuts in main loop)
- do {
- pB = pCandB;
-
- do {
- if(pA->getPosition().equal(pB->getPosition()))
- {
- aTmpCuts.push_back(new B2DSimpleCut(pA, pB));
- }
-
- // next B
- pB = pB->getNext();
- } while(pB != pCandB);
-
- // next A
- pA = pA->getNext();
- } while(pA != pCandA);
-
- // second run to find real cuts
- pA = pCandA;
-
- do {
- // get bounds for this edge in poly
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- pB = pCandB;
-
- do {
- pB->calcMinMaxX(fMaxBX, fMinBX);
-
- if(fTools::moreOrEqual(fMaxBX, fMinAX) // #116732#
- && fTools::moreOrEqual(fMaxAX, fMinBX)) // #116732#
- {
- pB->calcMinMaxY(fMaxBY, fMinBY);
-
- if(fTools::moreOrEqual(fMaxBY, fMinAY) // #116732#
- && fTools::moreOrEqual(fMaxAY, fMinBY)) // #116732#
- {
- if(!pA->getPosition().equal(pB->getPosition()))
- {
- const B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
- const B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
-
- if(tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
- {
- // crossover, two new points, use as cutpoint
- B2DPoint aNewPos(interpolate(pA->getPosition(), pA->getNext()->getPosition(), fCut));
- B2DPolygonNode* pCutLo = new B2DPolygonNode(aNewPos, pA);
- B2DPolygonNode* pCutHi = new B2DPolygonNode(aNewPos, pB);
- aNewCuts.push_back(new B2DSimpleCut(pCutLo, pCutHi));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- }
- else
- {
- if(tools::isPointOnEdge(pA->getPosition(), pB->getPosition(), aVectorB, &fCut))
- {
- // startpoint A at edge B, one new point
- // leaves or enters common section
- B2DPolygonNode* pCutHi = new B2DPolygonNode(pA->getPosition(), pB);
- aTmpCuts.push_back(new B2DSimpleCut(pA, pCutHi));
- }
- else if(tools::isPointOnEdge(pB->getPosition(), pA->getPosition(), aVectorA, &fCut))
- {
- // startpoint B at edge A, one new point
- // leaves or enters common section
- B2DPolygonNode* pCutLo = new B2DPolygonNode(pB->getPosition(), pA);
- aTmpCuts.push_back(new B2DSimpleCut(pCutLo, pB));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- }
- }
- }
- }
- }
-
- // next B
- pB = pB->getNext();
- } while(pB != pCandB);
-
- // next A
- pA = pA->getNext();
- } while(pA != pCandA);
-
- // test all temporary cuts for simple criteria
- for(sal_uInt32 c(0L); c < aTmpCuts.size();)
+ if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
{
- B2DSimpleCut* pCand = aTmpCuts[c];
- bool bPrevSamePos(isPrevSamePos(pCand->getLeft(), pCand->getRight()));
- bool bNextSamePos(isNextSamePos(pCand->getLeft(), pCand->getRight()));
- bool bDelete(false);
- bool bIncC(true);
-
- if(bPrevSamePos && bNextSamePos)
- {
- // single point inside continued same direction section
- bDelete = true;
- }
- else if(!bPrevSamePos && !bNextSamePos)
- {
- // this is no same direction section, test for real cut
- if(isCrossover(pCand->getLeft(), pCand->getRight()))
- {
- // real cut, move to real cutlist
- aNewCuts.push_back(pCand);
- aTmpCuts.erase(aTmpCuts.begin() + c);
- bIncC = false;
- }
- else
- {
- // no cut, just a touch in one point
- bDelete = true;
- }
- }
-
- // delete if wanted
- if(bDelete)
- {
- delete pCand;
- aTmpCuts.erase(aTmpCuts.begin() + c);
- bIncC = false;
- }
+ aRetval = rCandidate;
+ }
+ }
+ else
+ {
+ sal_uInt32 a, b;
+ ::std::vector< impStripHelper > aHelpers;
+ aHelpers.resize(nCount);
- // next candidate
- if(bIncC)
- c++;
+ for(a = 0L; a < nCount; a++)
+ {
+ const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
+ impStripHelper* pNewHelper = &(aHelpers[a]);
+ pNewHelper->maRange = tools::getRange(aCandidate);
+ pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
+ pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L);
}
- // are there entering/leaving same direction sections?
- while(aTmpCuts.size())
+ for(a = 0L; a < nCount - 1L; a++)
{
- // this cuts enter/leave a common same-direction section between
- // polygons pCandA, pCandB. If it is a real crossover, a cutpoint
- // for it is needed, else it can be ignored.
- B2DSimpleCut* pCutA = aTmpCuts[0L];
- aTmpCuts.erase(aTmpCuts.begin());
- B2DPolygonNode* pActA = pCutA->getLeft();
- B2DPolygonNode* pActB = pCutA->getRight();
-
- if(aTmpCuts.size())
+ const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
+ impStripHelper& rHelperA = aHelpers[a];
+
+ for(b = a + 1L; b < nCount; b++)
{
- B2DSimpleCut* pCutB = 0L;
+ const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
+ impStripHelper& rHelperB = aHelpers[b];
+ const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
+ const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
+ bool bForceDelete(false);
- if(isNextSamePos(pCutA->getLeft(), pCutA->getRight()))
+ if(bAInB && bBInA)
{
- // this is a start node
- B2DPolygonNode* pActA = pCutA->getLeft()->getNext();
- B2DPolygonNode* pActB = pCutA->getRight()->getNext();
-
- while(!pCutB && pActA != pCutA->getLeft())
+ // congruent
+ if(rHelperA.meOrinetation == rHelperB.meOrinetation)
{
- if(!isNextSamePos(pActA, pActB))
- {
- pCutB = getExistingCut(aTmpCuts, pActA, pActB);
- }
-
- pActA = pActA->getNext();
- pActB = pActB->getNext();
+ // two polys or two holes. Lower one of them to get one of them out of the way.
+ // Since each will be contained in the other one, both will be increased, too.
+ // So, for lowering, increase only one of them
+ rHelperA.mnDepth++;
}
-
- if(pCutB)
+ else
{
- const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
- aTmpCuts.erase(aFindResult);
-
- if(isCrossover(pCutA, pCutB))
- {
- aNewCuts.push_back(pCutB);
- }
- else
- {
- delete pCutB;
- }
+ // poly and hole. They neutralize, so get rid of both. Move securely below zero.
+ rHelperA.mnDepth = -((sal_Int32)nCount);
+ rHelperB.mnDepth = -((sal_Int32)nCount);
}
}
else
{
- // this is a end node
- B2DPolygonNode* pActA = pCutA->getLeft()->getPrevious();
- B2DPolygonNode* pActB = pCutA->getRight()->getPrevious();
-
- while(!pCutB && pActA != pCutA->getLeft())
+ if(bAInB)
{
- if(!isPrevSamePos(pActA, pActB))
+ if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation)
{
- pCutB = getExistingCut(aTmpCuts, pActA, pActB);
+ rHelperA.mnDepth--;
+ }
+ else
+ {
+ rHelperA.mnDepth++;
}
-
- pActA = pActA->getPrevious();
- pActB = pActB->getPrevious();
}
-
- if(pCutB)
+ else if(bBInA)
{
- const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
- aTmpCuts.erase(aFindResult);
-
- if(isCrossover(pCutB, pCutA))
+ if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation)
{
- aNewCuts.push_back(pCutB);
+ rHelperB.mnDepth--;
}
else
{
- delete pCutB;
+ rHelperB.mnDepth++;
}
}
}
}
-
- // delete cut in EVERY case
- delete pCutA;
}
- // copy new cuts to all cuts
- aCuts.insert(aCuts.begin(), aNewCuts.begin(), aNewCuts.end());
- aNewCuts.clear();
+ for(a = 0L; a < nCount; a++)
+ {
+ const impStripHelper& rHelper = aHelpers[a];
+ bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);
+
+ if(bAcceptEntry)
+ {
+ aRetval.append(rCandidate.getB2DPolygon(a));
+ }
+ }
}
}
+
+ return aRetval;
}
- // delete volume list again
- delete[] pVolumes;
+ //////////////////////////////////////////////////////////////////////////////
- // are there cuts to solve? Solve them all in one run
- if(aCuts.size())
- {
- solveAllCuts(aCuts);
- }
- }
+ } // end of namespace tools
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////