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.cxx1542
1 files changed, 765 insertions, 777 deletions
diff --git a/basegfx/source/polygon/b2dpolypolygoncutter.cxx b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
index a86bfce3d937..17d1c476acbf 100644
--- a/basegfx/source/polygon/b2dpolypolygoncutter.cxx
+++ b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
@@ -2,9 +2,9 @@
*
* $RCSfile: b2dpolypolygoncutter.cxx,v $
*
- * $Revision: 1.3 $
+ * $Revision: 1.4 $
*
- * last change: $Author: aw $ $Date: 2003-11-26 14:40:12 $
+ * last change: $Author: aw $ $Date: 2003-11-28 11:18:06 $
*
* The Contents of this file are made available subject to the terms of
* either of the following licenses
@@ -88,231 +88,228 @@
namespace basegfx
{
- namespace polygon
+ B2DPolygonNode::B2DPolygonNode(const ::basegfx::B2DPoint& rPosition, B2DPolygonNode* pPrevious)
+ : maPosition(rPosition)
{
- B2DPolygonNode::B2DPolygonNode(const ::basegfx::point::B2DPoint& rPosition, B2DPolygonNode* pPrevious)
- : maPosition(rPosition)
- {
- mpListPrevious = this;
- mpListNext = this;
+ mpListPrevious = this;
+ mpListNext = this;
- if(pPrevious)
- {
- mpNext = pPrevious->getNext();
- mpPrevious = pPrevious;
- mpNext->mpPrevious = this;
- mpPrevious->mpNext = this;
- }
- else
- {
- mpPrevious = mpNext = this;
- }
+ if(pPrevious)
+ {
+ mpNext = pPrevious->getNext();
+ mpPrevious = pPrevious;
+ mpNext->mpPrevious = this;
+ mpPrevious->mpNext = this;
}
-
- B2DPolygonNode::~B2DPolygonNode()
+ else
{
- if(mpNext != this)
- {
- mpPrevious->mpNext = mpNext;
- mpNext->mpPrevious = mpPrevious;
- }
+ mpPrevious = mpNext = this;
}
+ }
- void B2DPolygonNode::calcMinMaxX(double& fMaxAX, double& fMinAX) const
+ B2DPolygonNode::~B2DPolygonNode()
+ {
+ if(mpNext != this)
{
- if(maPosition.getX() > mpNext->maPosition.getX())
- {
- fMaxAX = maPosition.getX();
- fMinAX = mpNext->maPosition.getX();
- }
- else
- {
- fMaxAX = mpNext->maPosition.getX();
- fMinAX = maPosition.getX();
- }
+ mpPrevious->mpNext = mpNext;
+ mpNext->mpPrevious = mpPrevious;
}
+ }
- void B2DPolygonNode::calcMinMaxY(double& fMaxAY, double& fMinAY) const
+ void B2DPolygonNode::calcMinMaxX(double& fMaxAX, double& fMinAX) const
+ {
+ if(maPosition.getX() > mpNext->maPosition.getX())
{
- if(maPosition.getY() > mpNext->maPosition.getY())
- {
- fMaxAY = maPosition.getY();
- fMinAY = mpNext->maPosition.getY();
- }
- else
- {
- fMaxAY = mpNext->maPosition.getY();
- fMinAY = maPosition.getY();
- }
+ fMaxAX = maPosition.getX();
+ fMinAX = mpNext->maPosition.getX();
+ }
+ else
+ {
+ fMaxAX = mpNext->maPosition.getX();
+ fMinAX = maPosition.getX();
}
+ }
- void B2DPolygonNode::swapNextPointers(B2DPolygonNode* pCand)
+ void B2DPolygonNode::calcMinMaxY(double& fMaxAY, double& fMinAY) const
+ {
+ if(maPosition.getY() > mpNext->maPosition.getY())
{
- B2DPolygonNode* pTemporary = mpNext;
- mpNext = pCand->mpNext;
- pCand->mpNext = pTemporary;
- mpNext->mpPrevious = this;
- pCand->mpNext->mpPrevious = pCand;
+ fMaxAY = maPosition.getY();
+ fMinAY = mpNext->maPosition.getY();
+ }
+ else
+ {
+ fMaxAY = mpNext->maPosition.getY();
+ fMinAY = maPosition.getY();
}
+ }
- void B2DPolygonNode::addToList(B2DPolygonNode*& rpList)
+ 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)
{
- if(rpList)
- {
- mpListNext = rpList->mpListNext;
- rpList->mpListNext = this;
- mpListPrevious = rpList;
- mpListNext->mpListPrevious = this;
- }
- else
- {
- rpList = this;
- }
+ mpListNext = rpList->mpListNext;
+ rpList->mpListNext = this;
+ mpListPrevious = rpList;
+ mpListNext->mpListPrevious = this;
+ }
+ else
+ {
+ rpList = this;
}
+ }
- void B2DPolygonNode::remFromList(B2DPolygonNode*& rpList)
+ void B2DPolygonNode::remFromList(B2DPolygonNode*& rpList)
+ {
+ if(mpListNext != this)
{
- if(mpListNext != this)
+ if(rpList == this)
{
- if(rpList == this)
- {
- rpList = mpListPrevious;
- }
-
- mpListPrevious->mpListNext = mpListNext;
- mpListNext->mpListPrevious = mpListPrevious;
- mpListNext = mpListPrevious = this;
+ rpList = mpListPrevious;
}
- else
+
+ mpListPrevious->mpListNext = mpListNext;
+ mpListNext->mpListPrevious = mpListPrevious;
+ mpListNext = mpListPrevious = this;
+ }
+ else
+ {
+ if(rpList == this)
{
- if(rpList == this)
- {
- rpList = 0L;
- }
+ rpList = 0L;
}
}
+ }
- sal_Bool B2DPolygonNode::getOrientation() const
- {
- const B2DPolygonNode* pOutmost = this;
- const B2DPolygonNode* pCurrent = this->getNext();
+ sal_Bool B2DPolygonNode::getOrientation() const
+ {
+ const B2DPolygonNode* pOutmost = this;
+ const B2DPolygonNode* pCurrent = this->getNext();
- while(pCurrent != this)
+ while(pCurrent != this)
+ {
+ if(::basegfx::fTools::more(pOutmost->getPosition().getX(), pCurrent->getPosition().getX()))
{
- if(::basegfx::numeric::fTools::more(pOutmost->getPosition().getX(), pCurrent->getPosition().getX()))
+ if(pCurrent->getPosition().getX() < pOutmost->getPosition().getX())
+ {
+ pOutmost = pCurrent;
+ }
+ else
{
- if(pCurrent->getPosition().getX() < pOutmost->getPosition().getX())
+ if(pCurrent->getPosition().getY() < pOutmost->getPosition().getY())
{
pOutmost = pCurrent;
}
- else
- {
- if(pCurrent->getPosition().getY() < pOutmost->getPosition().getY())
- {
- pOutmost = pCurrent;
- }
- }
}
-
- // next node
- pCurrent = pCurrent->getNext();
}
- ::basegfx::vector::B2DVector aVec1(pOutmost->getPrevious()->getPosition() - pOutmost->getPosition());
- ::basegfx::vector::B2DVector aVec2(pOutmost->getNext()->getPosition() - pOutmost->getPosition());
- return sal_Bool(::basegfx::numeric::fTools::more(aVec1.getX() * aVec2.getY(), aVec1.getY() * aVec2.getX()));
+ // next node
+ pCurrent = pCurrent->getNext();
}
- void B2DPolygonNode::swapOrientation()
- {
- B2DPolygonNode* pCurrent = this;
+ ::basegfx::B2DVector aVec1(pOutmost->getPrevious()->getPosition() - pOutmost->getPosition());
+ ::basegfx::B2DVector aVec2(pOutmost->getNext()->getPosition() - pOutmost->getPosition());
+ return sal_Bool(::basegfx::fTools::more(aVec1.getX() * aVec2.getY(), aVec1.getY() * aVec2.getX()));
+ }
- do {
- pCurrent->swapPreviousNext();
- pCurrent = pCurrent->getPrevious();
- } while(pCurrent != this);
- }
+ void B2DPolygonNode::swapOrientation()
+ {
+ B2DPolygonNode* pCurrent = this;
- ::basegfx::range::B2DRange B2DPolygonNode::getRange() const
- {
- ::basegfx::range::B2DRange aRetval;
- const B2DPolygonNode* pCurrent = this;
+ do {
+ pCurrent->swapPreviousNext();
+ pCurrent = pCurrent->getPrevious();
+ } while(pCurrent != this);
+ }
- do {
- aRetval.expand(pCurrent->getPosition());
- pCurrent = pCurrent->getPrevious();
- } while(pCurrent != this);
+ ::basegfx::B2DRange B2DPolygonNode::getRange() const
+ {
+ ::basegfx::B2DRange aRetval;
+ const B2DPolygonNode* pCurrent = this;
- return aRetval;
- }
+ do {
+ aRetval.expand(pCurrent->getPosition());
+ pCurrent = pCurrent->getPrevious();
+ } while(pCurrent != this);
- sal_Bool B2DPolygonNode::isInside(const ::basegfx::point::B2DPoint& rPoint, sal_Bool bWithBorder) const
+ return aRetval;
+ }
+
+ sal_Bool B2DPolygonNode::isInside(const ::basegfx::B2DPoint& rPoint, sal_Bool bWithBorder) const
+ {
+ sal_Bool bInside(sal_False);
+ const B2DPolygonNode* pCurrent = this;
+
+ do
{
- sal_Bool bInside(sal_False);
- const B2DPolygonNode* pCurrent = this;
+ if(bWithBorder && pCurrent->getPosition().equal(rPoint))
+ {
+ return sal_True;
+ }
+
+ B2DPolygonNode* pNext = pCurrent->getNext();
+ const sal_Bool bCompYA(::basegfx::fTools::more(pCurrent->getPosition().getY(), rPoint.getY()));
+ const sal_Bool bCompYB(::basegfx::fTools::more(pNext->getPosition().getY(), rPoint.getY()));
- do
+ if(bCompYA != bCompYB)
{
- if(bWithBorder && pCurrent->getPosition().equal(rPoint))
+ const sal_Bool bCompXA(::basegfx::fTools::more(pCurrent->getPosition().getX(), rPoint.getX()));
+ const sal_Bool bCompXB(::basegfx::fTools::more(pNext->getPosition().getX(), rPoint.getX()));
+
+ if(bCompXA == bCompXB)
{
- return sal_True;
+ if(bCompXA)
+ {
+ bInside = !bInside;
+ }
}
-
- B2DPolygonNode* pNext = pCurrent->getNext();
- const sal_Bool bCompYA(::basegfx::numeric::fTools::more(pCurrent->getPosition().getY(), rPoint.getY()));
- const sal_Bool bCompYB(::basegfx::numeric::fTools::more(pNext->getPosition().getY(), rPoint.getY()));
-
- if(bCompYA != bCompYB)
+ else
{
- const sal_Bool bCompXA(::basegfx::numeric::fTools::more(pCurrent->getPosition().getX(), rPoint.getX()));
- const sal_Bool bCompXB(::basegfx::numeric::fTools::more(pNext->getPosition().getX(), rPoint.getX()));
+ double fCmp =
+ pNext->getPosition().getX() - (pNext->getPosition().getY() - rPoint.getY()) *
+ (pCurrent->getPosition().getX() - pNext->getPosition().getX()) /
+ (pCurrent->getPosition().getY() - pNext->getPosition().getY());
- if(bCompXA == bCompXB)
+ if(bWithBorder && ::basegfx::fTools::more(fCmp, rPoint.getX()))
{
- if(bCompXA)
- {
- bInside = !bInside;
- }
+ bInside = !bInside;
}
- else
+ else if(::basegfx::fTools::moreOrEqual(fCmp, rPoint.getX()))
{
- double fCmp =
- pNext->getPosition().getX() - (pNext->getPosition().getY() - rPoint.getY()) *
- (pCurrent->getPosition().getX() - pNext->getPosition().getX()) /
- (pCurrent->getPosition().getY() - pNext->getPosition().getY());
-
- if(bWithBorder && ::basegfx::numeric::fTools::more(fCmp, rPoint.getX()))
- {
- bInside = !bInside;
- }
- else if(::basegfx::numeric::fTools::moreOrEqual(fCmp, rPoint.getX()))
- {
- bInside = !bInside;
- }
+ bInside = !bInside;
}
}
+ }
- // next edge
- pCurrent = pNext;
+ // next edge
+ pCurrent = pNext;
- } while(pCurrent != this);
+ } while(pCurrent != this);
- return bInside;
- }
+ return bInside;
+ }
- sal_Bool B2DPolygonNode::isPolygonInside(B2DPolygonNode* pPoly, sal_Bool bWithBorder) const
- {
- B2DPolygonNode* pTest = pPoly;
- sal_Bool bAllAInside(sal_True);
+ sal_Bool B2DPolygonNode::isPolygonInside(B2DPolygonNode* pPoly, sal_Bool bWithBorder) const
+ {
+ B2DPolygonNode* pTest = pPoly;
+ sal_Bool bAllAInside(sal_True);
- do {
- bAllAInside = isInside(pTest->getPosition(), bWithBorder);
- pTest = pTest->getNext();
- } while(bAllAInside && pTest != pPoly);
+ do {
+ bAllAInside = isInside(pTest->getPosition(), bWithBorder);
+ pTest = pTest->getNext();
+ } while(bAllAInside && pTest != pPoly);
- return bAllAInside;
- }
- } // end of namespace polygon
+ return bAllAInside;
+ }
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
@@ -320,26 +317,23 @@ namespace basegfx
namespace basegfx
{
- namespace polygon
+ void B2DSimpleCut::solve()
{
- void B2DSimpleCut::solve()
- {
- mpLeft->swapNextPointers(mpRight);
+ mpLeft->swapNextPointers(mpRight);
- if(mbCorrectOrientation)
+ if(mbCorrectOrientation)
+ {
+ if(mpLeft->getOrientation() != mbOrientation)
{
- if(mpLeft->getOrientation() != mbOrientation)
- {
- mpLeft->swapOrientation();
- }
+ mpLeft->swapOrientation();
+ }
- if(mpRight->getOrientation() != mbOrientation)
- {
- mpRight->swapOrientation();
- }
+ if(mpRight->getOrientation() != mbOrientation)
+ {
+ mpRight->swapOrientation();
}
}
- } // end of namespace polygon
+ }
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
@@ -347,27 +341,24 @@ namespace basegfx
namespace basegfx
{
- namespace polygon
+ void B2DClipExtraPolygonInfo::init(B2DPolygonNode* pNew)
{
- void B2DClipExtraPolygonInfo::init(B2DPolygonNode* pNew)
+ maRange = pNew->getRange();
+ mbOrientation = pNew->getOrientation();
+ mnDepth = (mbOrientation) ? 0L : -1L;
+ }
+
+ void B2DClipExtraPolygonInfo::changeDepth(sal_Bool bOrientation)
+ {
+ if(bOrientation)
{
- maRange = pNew->getRange();
- mbOrientation = pNew->getOrientation();
- mnDepth = (mbOrientation) ? 0L : -1L;
+ mnDepth++;
}
-
- void B2DClipExtraPolygonInfo::changeDepth(sal_Bool bOrientation)
+ else
{
- if(bOrientation)
- {
- mnDepth++;
- }
- else
- {
- mnDepth--;
- }
+ mnDepth--;
}
- } // end of namespace polygon
+ }
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
@@ -375,772 +366,769 @@ namespace basegfx
namespace basegfx
{
- namespace polygon
+ B2DPolyPolygonCutter::~B2DPolyPolygonCutter()
{
- B2DPolyPolygonCutter::~B2DPolyPolygonCutter()
+ for(sal_uInt32 a(0L); a < maPolygonList.size(); a++)
{
- for(sal_uInt32 a(0L); a < maPolygonList.size(); a++)
- {
- delete maPolygonList[a];
- }
-
- maPolygonList.clear();
+ delete maPolygonList[a];
}
- void B2DPolyPolygonCutter::removeIncludedPolygons(sal_Bool bUseOr)
+ maPolygonList.clear();
+ }
+
+ void B2DPolyPolygonCutter::removeIncludedPolygons(sal_Bool bUseOr)
+ {
+ const sal_uInt32 aCount(maPolygonList.size());
+ B2DClipExtraPolygonInfo* pInfos = new B2DClipExtraPolygonInfo[aCount];
+ sal_uInt32 a, b;
+
+ // fill infos
+ for(a = 0L; a < aCount; a++)
{
- const sal_uInt32 aCount(maPolygonList.size());
- B2DClipExtraPolygonInfo* pInfos = new B2DClipExtraPolygonInfo[aCount];
- sal_uInt32 a, b;
+ pInfos[a].init(maPolygonList[a]);
+ }
- // fill infos
- for(a = 0L; a < aCount; a++)
- {
- pInfos[a].init(maPolygonList[a]);
- }
+ // get all includes
+ for(a = 0L; a < aCount; a++)
+ {
+ B2DClipExtraPolygonInfo& rInfoA = pInfos[a];
- // get all includes
- for(a = 0L; a < aCount; a++)
+ for(b = 0L; b < aCount; b++)
{
- B2DClipExtraPolygonInfo& rInfoA = pInfos[a];
+ B2DClipExtraPolygonInfo& rInfoB = pInfos[b];
- for(b = 0L; b < aCount; b++)
+ if(a != b && doRangesInclude(rInfoA.getRange(), rInfoB.getRange()))
{
- B2DClipExtraPolygonInfo& rInfoB = pInfos[b];
-
- if(a != b && doRangesInclude(rInfoA.getRange(), rInfoB.getRange()))
+ // volume B in A, test pA, pB for inclusion, with border
+ if(maPolygonList[a]->isPolygonInside(maPolygonList[b], sal_True))
{
- // volume B in A, test pA, pB for inclusion, with border
- if(maPolygonList[a]->isPolygonInside(maPolygonList[b], sal_True))
- {
- // pB is inside pA
- rInfoB.changeDepth(rInfoA.getOrientation());
- }
+ // pB is inside pA
+ rInfoB.changeDepth(rInfoA.getOrientation());
}
}
}
+ }
- // delete removable
- for(a = 0L, b = 0L; a < aCount; a++)
- {
- B2DClipExtraPolygonInfo& rInfo = pInfos[a];
+ // delete removable
+ for(a = 0L, b = 0L; a < aCount; a++)
+ {
+ B2DClipExtraPolygonInfo& rInfo = pInfos[a];
- if((bUseOr && rInfo.getDepth() != 0L) || (!bUseOr && rInfo.getDepth() < 1L))
- {
- B2DPolygonNodeVector::iterator aPosition(maPolygonList.begin() + b);
- B2DPolygonNode* pCandidate = *aPosition;
- maPolygonList.erase(aPosition);
- deletePolygon(pCandidate);
- }
- else
- {
- b++;
- }
+ if((bUseOr && rInfo.getDepth() != 0L) || (!bUseOr && rInfo.getDepth() < 1L))
+ {
+ B2DPolygonNodeVector::iterator aPosition(maPolygonList.begin() + b);
+ B2DPolygonNode* pCandidate = *aPosition;
+ maPolygonList.erase(aPosition);
+ deletePolygon(pCandidate);
+ }
+ else
+ {
+ b++;
}
-
- // delete infos
- delete[] pInfos;
}
- void B2DPolyPolygonCutter::solveAllCuts(B2DSimpleCutVector& rCuts)
- {
- B2DPolygonNode* pNewList = 0L;
-
- // add all nodes of polys to list
- polysToList(pNewList);
+ // delete infos
+ delete[] pInfos;
+ }
- // solve cuts
- B2DSimpleCutVector::iterator aCandidate(rCuts.begin());
+ void B2DPolyPolygonCutter::solveAllCuts(B2DSimpleCutVector& rCuts)
+ {
+ B2DPolygonNode* pNewList = 0L;
- for(; aCandidate < rCuts.end(); aCandidate++)
- {
- B2DSimpleCut* pCut = *aCandidate;
- pCut->solve();
- delete pCut;
- }
+ // add all nodes of polys to list
+ polysToList(pNewList);
- rCuts.clear();
+ // solve cuts
+ B2DSimpleCutVector::iterator aCandidate(rCuts.begin());
- // extract polys
- listToPolys(pNewList);
+ for(; aCandidate < rCuts.end(); aCandidate++)
+ {
+ B2DSimpleCut* pCut = *aCandidate;
+ pCut->solve();
+ delete pCut;
}
- void B2DPolyPolygonCutter::polysToList(B2DPolygonNode*& rpList)
- {
- B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
+ rCuts.clear();
- for(; aCandidate != maPolygonList.end(); aCandidate++)
- {
- addAllNodes(*aCandidate, rpList);
- }
+ // extract polys
+ listToPolys(pNewList);
+ }
- maPolygonList.clear();
- }
+ void B2DPolyPolygonCutter::polysToList(B2DPolygonNode*& rpList)
+ {
+ B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
- void B2DPolyPolygonCutter::listToPolys(B2DPolygonNode*& rpList)
+ for(; aCandidate != maPolygonList.end(); aCandidate++)
{
- while(rpList)
- {
- // get one
- B2DPolygonNode* pNew = extractNextPolygon(rpList);
-
- if(pNew)
- {
- maPolygonList.push_back(pNew);
- }
- }
+ addAllNodes(*aCandidate, rpList);
}
- B2DPolygonNode* B2DPolyPolygonCutter::createNewPolygon(const B2DPolygon& rPolygon)
+ maPolygonList.clear();
+ }
+
+ void B2DPolyPolygonCutter::listToPolys(B2DPolygonNode*& rpList)
+ {
+ while(rpList)
{
- B2DPolygonNode* pRetval = NULL;
+ // get one
+ B2DPolygonNode* pNew = extractNextPolygon(rpList);
- for(sal_uInt32 a(0L); a < rPolygon.count(); a++)
+ if(pNew)
{
- ::basegfx::point::B2DPoint aPoint(rPolygon.getB2DPoint(a));
- pRetval = new B2DPolygonNode(aPoint, pRetval);
+ maPolygonList.push_back(pNew);
}
-
- return pRetval;
}
+ }
+
+ B2DPolygonNode* B2DPolyPolygonCutter::createNewPolygon(const B2DPolygon& rPolygon)
+ {
+ B2DPolygonNode* pRetval = NULL;
- void B2DPolyPolygonCutter::deletePolygon(B2DPolygonNode* pCand)
+ for(sal_uInt32 a(0L); a < rPolygon.count(); a++)
{
- B2DPolygonNode* pPoly = pCand;
+ ::basegfx::B2DPoint aPoint(rPolygon.getB2DPoint(a));
+ pRetval = new B2DPolygonNode(aPoint, pRetval);
+ }
- while(pPoly)
- {
- B2DPolygonNode* pNext = pPoly->getNext();
+ return pRetval;
+ }
- if(pNext == pPoly)
- {
- pNext = 0L;
- }
+ void B2DPolyPolygonCutter::deletePolygon(B2DPolygonNode* pCand)
+ {
+ B2DPolygonNode* pPoly = pCand;
+
+ while(pPoly)
+ {
+ B2DPolygonNode* pNext = pPoly->getNext();
- delete pPoly;
- pPoly = pNext;
+ if(pNext == pPoly)
+ {
+ pNext = 0L;
}
+
+ delete pPoly;
+ pPoly = pNext;
}
+ }
- void B2DPolyPolygonCutter::addAllNodes(B2DPolygonNode* pPolygon, B2DPolygonNode*& rpList)
- {
- B2DPolygonNode* pAct = pPolygon;
+ void B2DPolyPolygonCutter::addAllNodes(B2DPolygonNode* pPolygon, B2DPolygonNode*& rpList)
+ {
+ B2DPolygonNode* pAct = pPolygon;
- do {
- pAct->addToList(rpList);
- pAct = pAct->getNext();
- } while(pAct != pPolygon);
- }
+ do {
+ pAct->addToList(rpList);
+ pAct = pAct->getNext();
+ } while(pAct != pPolygon);
+ }
- void B2DPolyPolygonCutter::addPolyPolygon(const B2DPolyPolygon& rPolyPolygon, sal_Bool bForceOrientation)
+ void B2DPolyPolygonCutter::addPolyPolygon(const B2DPolyPolygon& rPolyPolygon, sal_Bool bForceOrientation)
+ {
+ for(sal_uInt32 a(0L); a < rPolyPolygon.count(); a++)
{
- for(sal_uInt32 a(0L); a < rPolyPolygon.count(); a++)
- {
- B2DPolygon aCandidate = rPolyPolygon.getB2DPolygon(a);
- aCandidate.removeDoublePoints();
+ B2DPolygon aCandidate = rPolyPolygon.getB2DPolygon(a);
+ aCandidate.removeDoublePoints();
- if(!aCandidate.isClosed() || aCandidate.count() < 3)
- {
- maNotClosedPolygons.append(aCandidate);
- }
- else
+ if(!aCandidate.isClosed() || aCandidate.count() < 3)
+ {
+ maNotClosedPolygons.append(aCandidate);
+ }
+ else
+ {
+ if(bForceOrientation)
{
- if(bForceOrientation)
- {
- ::basegfx::vector::B2DVectorOrientation aOrientation =
- ::basegfx::polygon::tools::getOrientation(aCandidate);
+ ::basegfx::B2DVectorOrientation aOrientation =
+ ::basegfx::tools::getOrientation(aCandidate);
- if(::basegfx::vector::ORIENTATION_POSITIVE != aOrientation)
- {
- aCandidate.flip();
- }
+ if(::basegfx::ORIENTATION_POSITIVE != aOrientation)
+ {
+ aCandidate.flip();
}
-
- B2DPolygonNode* pNew = createNewPolygon(aCandidate);
- maPolygonList.push_back(pNew);
}
+
+ B2DPolygonNode* pNew = createNewPolygon(aCandidate);
+ maPolygonList.push_back(pNew);
}
}
+ }
+
+ void B2DPolyPolygonCutter::getPolyPolygon(B2DPolyPolygon& rPolyPolygon)
+ {
+ B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
- void B2DPolyPolygonCutter::getPolyPolygon(B2DPolyPolygon& rPolyPolygon)
+ for(; aCandidate < maPolygonList.end(); aCandidate++)
{
- B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
+ B2DPolygonNode* pCand = *aCandidate;
+ B2DPolygonNode* pAct = pCand;
+ sal_uInt32 nCount(0L);
+
+ do {
+ nCount++;
+ pAct = pAct->getNext();
+ } while(pAct != pCand);
- for(; aCandidate < maPolygonList.end(); aCandidate++)
+ if(nCount > 2L)
{
- B2DPolygonNode* pCand = *aCandidate;
- B2DPolygonNode* pAct = pCand;
- sal_uInt32 nCount(0L);
+ B2DPolygon aNewPolygon;
do {
- nCount++;
+ aNewPolygon.append(pAct->getPosition());
pAct = pAct->getNext();
} while(pAct != pCand);
- if(nCount > 2L)
- {
- B2DPolygon aNewPolygon;
+ aNewPolygon.setClosed(sal_True);
+ rPolyPolygon.append(aNewPolygon);
+ }
- do {
- aNewPolygon.append(pAct->getPosition());
- pAct = pAct->getNext();
- } while(pAct != pCand);
+ deletePolygon(pCand);
+ }
- aNewPolygon.setClosed(sal_True);
- rPolyPolygon.append(aNewPolygon);
- }
+ maPolygonList.clear();
- deletePolygon(pCand);
- }
+ while(maNotClosedPolygons.count())
+ {
+ rPolyPolygon.append(maNotClosedPolygons.getB2DPolygon(0L));
+ maNotClosedPolygons.remove(0L);
+ }
+ }
- maPolygonList.clear();
+ B2DSimpleCut* B2DPolyPolygonCutter::getExistingCut(B2DSimpleCutVector& rTmpCuts, B2DPolygonNode* pA, B2DPolygonNode* pB)
+ {
+ for(sal_uInt32 a(0L); a < rTmpCuts.size(); a++)
+ {
+ B2DSimpleCut* pCand = rTmpCuts[a];
- while(maNotClosedPolygons.count())
+ if(pCand->isSameCut(pA, pB))
{
- rPolyPolygon.append(maNotClosedPolygons.getB2DPolygon(0L));
- maNotClosedPolygons.remove(0L);
+ return pCand;
}
}
- B2DSimpleCut* B2DPolyPolygonCutter::getExistingCut(B2DSimpleCutVector& rTmpCuts, B2DPolygonNode* pA, B2DPolygonNode* pB)
- {
- for(sal_uInt32 a(0L); a < rTmpCuts.size(); a++)
- {
- B2DSimpleCut* pCand = rTmpCuts[a];
+ return 0L;
+ }
- if(pCand->isSameCut(pA, pB))
- {
- return pCand;
- }
- }
+ B2DPolygonNode* B2DPolyPolygonCutter::extractNextPolygon(B2DPolygonNode*& rpList)
+ {
+ B2DPolygonNode* pStart = rpList;
+
+ // remove all nodes of this poly from list
+ B2DPolygonNode* pAct = pStart;
+ sal_uInt32 nNumNodes(0L);
+
+ do {
+ pAct->remFromList(rpList);
+ pAct = pAct->getNext();
+ nNumNodes++;
+ } while(pAct != pStart);
+ if(nNumNodes < 3L)
+ {
+ deletePolygon(pStart);
return 0L;
}
-
- B2DPolygonNode* B2DPolyPolygonCutter::extractNextPolygon(B2DPolygonNode*& rpList)
+ else
{
- B2DPolygonNode* pStart = rpList;
-
- // remove all nodes of this poly from list
- B2DPolygonNode* pAct = pStart;
- sal_uInt32 nNumNodes(0L);
-
- do {
- pAct->remFromList(rpList);
- pAct = pAct->getNext();
- nNumNodes++;
- } while(pAct != pStart);
-
- if(nNumNodes < 3L)
- {
- deletePolygon(pStart);
- return 0L;
- }
- else
- {
- return pStart;
- }
+ return pStart;
}
+ }
- void B2DPolyPolygonCutter::removeSelfIntersections()
+ 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++)
{
- 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;
+ pCand = maPolygonList[a];
+ pA = pCand;
+
+ // one run to find same start positions (so there is no need to
+ // search for existing cuts in main loop)
+ do {
+ pB = pA->getNext();
- // one run to find same start positions (so there is no need to
- // search for existing cuts in main loop)
do {
- pB = pA->getNext();
+ if(isSamePos(pA->getPosition(), pB->getPosition()))
+ {
+ aNewCuts.push_back(new B2DSimpleCut(pA, pB, sal_True, pCand->getOrientation()));
+ }
- do {
- if(isSamePos(pA->getPosition(), pB->getPosition()))
- {
- aNewCuts.push_back(new B2DSimpleCut(pA, pB, sal_True, pCand->getOrientation()));
- }
+ // next B
+ pB = pB->getNext();
+ } while(pB != pCand);
- // next B
- pB = pB->getNext();
- } while(pB != pCand);
+ // next A
+ pA = pA->getNext();
+ } while(pA->getNext() != pCand);
- // next A
- pA = pA->getNext();
- } while(pA->getNext() != pCand);
+ // second run to find real cuts
+ pA = pCand;
- // second run to find real cuts
- pA = pCand;
+ do {
+ // get bounds for this edge in poly
+ pA->calcMinMaxX(fMaxAX, fMinAX);
+ pA->calcMinMaxY(fMaxAY, fMinAY);
+ pB = pA->getNext();
do {
- // get bounds for this edge in poly
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- pB = pA->getNext();
+ pB->calcMinMaxX(fMaxBX, fMinBX);
- do {
- pB->calcMinMaxX(fMaxBX, fMinBX);
+ if(::basegfx::fTools::more(fMaxBX, fMinAX)
+ && ::basegfx::fTools::more(fMaxAX, fMinBX))
+ {
+ pB->calcMinMaxY(fMaxBY, fMinBY);
- if(::basegfx::numeric::fTools::more(fMaxBX, fMinAX)
- && ::basegfx::numeric::fTools::more(fMaxAX, fMinBX))
+ if(::basegfx::fTools::more(fMaxBY, fMinAY)
+ && ::basegfx::fTools::more(fMaxAY, fMinBY))
{
- pB->calcMinMaxY(fMaxBY, fMinBY);
-
- if(::basegfx::numeric::fTools::more(fMaxBY, fMinAY)
- && ::basegfx::numeric::fTools::more(fMaxAY, fMinBY))
+ if(!isSamePos(pA->getPosition(), pB->getPosition()))
{
- if(!isSamePos(pA->getPosition(), pB->getPosition()))
- {
- const ::basegfx::vector::B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
- const ::basegfx::vector::B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
+ const ::basegfx::B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
+ const ::basegfx::B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
- if(::basegfx::polygon::tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
+ if(::basegfx::tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
+ {
+ // crossover, two new points
+ ::basegfx::B2DPoint aNewPos(::basegfx::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, sal_True, pCand->getOrientation()));
+ pA->calcMinMaxX(fMaxAX, fMinAX);
+ pA->calcMinMaxY(fMaxAY, fMinAY);
+ }
+ else
+ {
+ if(::basegfx::tools::isPointOnEdge(pA->getPosition(), pB->getPosition(), aVectorB, &fCut))
{
- // crossover, two new points
- ::basegfx::point::B2DPoint aNewPos(::basegfx::tuple::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, sal_True, pCand->getOrientation()));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
+ // startpoint A at edge B, one new point
+ B2DPolygonNode* pCutHi = new B2DPolygonNode(pA->getPosition(), pB);
+ aNewCuts.push_back(new B2DSimpleCut(pA, pCutHi, sal_True, pCand->getOrientation()));
}
- else
+ else if(::basegfx::tools::isPointOnEdge(pB->getPosition(), pA->getPosition(), aVectorA, &fCut))
{
- if(::basegfx::polygon::tools::isPointOnEdge(pA->getPosition(), pB->getPosition(), aVectorB, &fCut))
- {
- // startpoint A at edge B, one new point
- B2DPolygonNode* pCutHi = new B2DPolygonNode(pA->getPosition(), pB);
- aNewCuts.push_back(new B2DSimpleCut(pA, pCutHi, sal_True, pCand->getOrientation()));
- }
- else if(::basegfx::polygon::tools::isPointOnEdge(pB->getPosition(), pA->getPosition(), aVectorA, &fCut))
- {
- // startpoint B at edge A, one new point
- B2DPolygonNode* pCutLo = new B2DPolygonNode(pB->getPosition(), pA);
- aNewCuts.push_back(new B2DSimpleCut(pCutLo, pB, sal_True, pCand->getOrientation()));
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- }
+ // startpoint B at edge A, one new point
+ B2DPolygonNode* pCutLo = new B2DPolygonNode(pB->getPosition(), pA);
+ aNewCuts.push_back(new B2DSimpleCut(pCutLo, pB, sal_True, pCand->getOrientation()));
+ pA->calcMinMaxX(fMaxAX, fMinAX);
+ pA->calcMinMaxY(fMaxAY, fMinAY);
}
}
}
}
+ }
- // next B
- pB = pB->getNext();
- } while(pB != pCand);
+ // next B
+ pB = pB->getNext();
+ } while(pB != pCand);
- // next A
- pA = pA->getNext();
- } while(pA->getNext() != 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();
- }
+ // copy new cuts to cuts
+ aCuts.insert(aCuts.begin(), aNewCuts.begin(), aNewCuts.end());
+ aNewCuts.clear();
+ }
- // second job: if there were cuts, split polys
- if(aCuts.size())
- {
- solveAllCuts(aCuts);
- }
+ // second job: if there were cuts, split polys
+ if(aCuts.size())
+ {
+ solveAllCuts(aCuts);
}
+ }
- sal_Bool B2DPolyPolygonCutter::isCrossover(B2DPolygonNode* pA, B2DPolygonNode* pB)
+ sal_Bool B2DPolyPolygonCutter::isCrossover(B2DPolygonNode* pA, B2DPolygonNode* pB)
+ {
+ // build entering vectors
+ ::basegfx::B2DVector aVecA(pA->getPrevious()->getPosition() - pA->getPosition());
+ ::basegfx::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)
{
- // build entering vectors
- ::basegfx::vector::B2DVector aVecA(pA->getPrevious()->getPosition() - pA->getPosition());
- ::basegfx::vector::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)
- {
- double fTemp = fDegreeA2;
- fDegreeA2 = fDegreeA1;
- fDegreeA1 = fTemp;
- }
+ double fTemp = fDegreeA2;
+ fDegreeA2 = fDegreeA1;
+ fDegreeA1 = fTemp;
+ }
- sal_Bool bB1Inside(::basegfx::numeric::fTools::more(fDegreeB1, fDegreeA1)
- && ::basegfx::numeric::fTools::more(fDegreeA2, fDegreeB1));
- sal_Bool bB2Inside(::basegfx::numeric::fTools::more(fDegreeB2, fDegreeA1)
- && ::basegfx::numeric::fTools::more(fDegreeA2, fDegreeB2));
+ sal_Bool bB1Inside(::basegfx::fTools::more(fDegreeB1, fDegreeA1)
+ && ::basegfx::fTools::more(fDegreeA2, fDegreeB1));
+ sal_Bool bB2Inside(::basegfx::fTools::more(fDegreeB2, fDegreeA1)
+ && ::basegfx::fTools::more(fDegreeA2, fDegreeB2));
- if(bB1Inside && bB2Inside)
- {
- return sal_False;
- }
+ if(bB1Inside && bB2Inside)
+ {
+ return sal_False;
+ }
+
+ sal_Bool bB1Outside(::basegfx::fTools::more(fDegreeA1, fDegreeB1)
+ || ::basegfx::fTools::more(fDegreeB1, fDegreeA2));
+ sal_Bool bB2Outside(::basegfx::fTools::more(fDegreeA1, fDegreeB2)
+ || ::basegfx::fTools::more(fDegreeB2, fDegreeA2));
- sal_Bool bB1Outside(::basegfx::numeric::fTools::more(fDegreeA1, fDegreeB1)
- || ::basegfx::numeric::fTools::more(fDegreeB1, fDegreeA2));
- sal_Bool bB2Outside(::basegfx::numeric::fTools::more(fDegreeA1, fDegreeB2)
- || ::basegfx::numeric::fTools::more(fDegreeB2, fDegreeA2));
+ return !(bB1Outside && bB2Outside);
+ }
- return !(bB1Outside && bB2Outside);
+ sal_Bool B2DPolyPolygonCutter::isCrossover(B2DSimpleCut* pEnter, B2DSimpleCut* pLeave)
+ {
+ // build entering vectors
+ ::basegfx::B2DVector aVecJ(pEnter->getLeft()->getNext()->getPosition() - pEnter->getLeft()->getPosition());
+ ::basegfx::B2DVector aVecA(pEnter->getLeft()->getPrevious()->getPosition() - pEnter->getLeft()->getPosition());
+ ::basegfx::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);
}
- sal_Bool B2DPolyPolygonCutter::isCrossover(B2DSimpleCut* pEnter, B2DSimpleCut* pLeave)
+ while(fDegreeA2 >= (2.0 * F_PI))
{
- // build entering vectors
- ::basegfx::vector::B2DVector aVecJ(pEnter->getLeft()->getNext()->getPosition() - pEnter->getLeft()->getPosition());
- ::basegfx::vector::B2DVector aVecA(pEnter->getLeft()->getPrevious()->getPosition() - pEnter->getLeft()->getPosition());
- ::basegfx::vector::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);
- }
+ fDegreeA2 -= (2.0 * F_PI);
+ }
- while(fDegreeA2 >= (2.0 * F_PI))
- {
- fDegreeA2 -= (2.0 * F_PI);
- }
+ // move to range [0..2PI[
+ while(fDegreeB2 < 0.0)
+ {
+ fDegreeB2 += (2.0 * F_PI);
+ }
- // 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);
+ }
- while(fDegreeB2 >= (2.0 * F_PI))
- {
- fDegreeB2 -= (2.0 * F_PI);
- }
+ sal_Bool bA2BiggerB2(::basegfx::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);
+ }
- sal_Bool bA2BiggerB2(::basegfx::numeric::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);
- }
+ while(fDegreeA1 >= (2.0 * F_PI))
+ {
+ fDegreeA1 -= (2.0 * F_PI);
+ }
- while(fDegreeA1 >= (2.0 * F_PI))
- {
- fDegreeA1 -= (2.0 * F_PI);
- }
+ // move to range [0..2PI[
+ while(fDegreeB1 < 0)
+ {
+ fDegreeB1 += (2.0 * F_PI);
+ }
- // move to range [0..2PI[
- while(fDegreeB1 < 0)
- {
- fDegreeB1 += (2.0 * F_PI);
- }
+ while(fDegreeB1 >= (2.0 * F_PI))
+ {
+ fDegreeB1 -= (2.0 * F_PI);
+ }
- while(fDegreeB1 >= (2.0 * F_PI))
- {
- fDegreeB1 -= (2.0 * F_PI);
- }
+ sal_Bool bA1BiggerB1(::basegfx::fTools::more(fDegreeA1, fDegreeB1));
- sal_Bool bA1BiggerB1(::basegfx::numeric::fTools::more(fDegreeA1, fDegreeB1));
+ // compare
+ return (bA1BiggerB1 == bA2BiggerB2);
+ }
- // compare
- return (bA1BiggerB1 == bA2BiggerB2);
+ 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
+ ::basegfx::B2DRange* pVolumes = new ::basegfx::B2DRange[maPolygonList.size()];
+
+ for(a = 0L; a < maPolygonList.size(); a++)
+ {
+ pVolumes[a] = maPolygonList[a]->getRange();
}
- void B2DPolyPolygonCutter::removeDoubleIntersections()
+ // register cuts (and add points for them) between pCandA and pCandB
+ for(a = 0L; a + 1L < maPolygonList.size(); a++)
{
- 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
- ::basegfx::range::B2DRange* pVolumes = new ::basegfx::range::B2DRange[maPolygonList.size()];
-
- for(a = 0L; a < maPolygonList.size(); a++)
- {
- pVolumes[a] = maPolygonList[a]->getRange();
- }
+ pCandA = maPolygonList[a];
- // register cuts (and add points for them) between pCandA and pCandB
- for(a = 0L; a + 1L < maPolygonList.size(); a++)
+ for(sal_uInt32 b = a + 1L; b < maPolygonList.size(); b++)
{
- pCandA = maPolygonList[a];
-
- for(sal_uInt32 b = a + 1L; b < maPolygonList.size(); b++)
+ if(doRangesIntersect(pVolumes[a], pVolumes[b]))
{
- if(doRangesIntersect(pVolumes[a], pVolumes[b]))
- {
- pCandB = maPolygonList[b];
- pA = pCandA;
+ 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;
- // one run to find same start positions (so there is no need to
- // search for existing cuts in main loop)
do {
- pB = pCandB;
+ if(isSamePos(pA->getPosition(), pB->getPosition()))
+ {
+ aTmpCuts.push_back(new B2DSimpleCut(pA, pB));
+ }
- do {
- if(isSamePos(pA->getPosition(), pB->getPosition()))
- {
- aTmpCuts.push_back(new B2DSimpleCut(pA, pB));
- }
+ // next B
+ pB = pB->getNext();
+ } while(pB != pCandB);
- // next B
- pB = pB->getNext();
- } while(pB != pCandB);
+ // next A
+ pA = pA->getNext();
+ } while(pA != pCandA);
- // next A
- pA = pA->getNext();
- } while(pA != pCandA);
+ // second run to find real cuts
+ 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 {
- // get bounds for this edge in poly
- pA->calcMinMaxX(fMaxAX, fMinAX);
- pA->calcMinMaxY(fMaxAY, fMinAY);
- pB = pCandB;
+ pB->calcMinMaxX(fMaxBX, fMinBX);
- do {
- pB->calcMinMaxX(fMaxBX, fMinBX);
+ if(::basegfx::fTools::more(fMaxBX, fMinAX)
+ && ::basegfx::fTools::more(fMaxAX, fMinBX))
+ {
+ pB->calcMinMaxY(fMaxBY, fMinBY);
- if(::basegfx::numeric::fTools::more(fMaxBX, fMinAX)
- && ::basegfx::numeric::fTools::more(fMaxAX, fMinBX))
+ if(::basegfx::fTools::more(fMaxBY, fMinAY)
+ && ::basegfx::fTools::more(fMaxAY, fMinBY))
{
- pB->calcMinMaxY(fMaxBY, fMinBY);
-
- if(::basegfx::numeric::fTools::more(fMaxBY, fMinAY)
- && ::basegfx::numeric::fTools::more(fMaxAY, fMinBY))
+ if(!isSamePos(pA->getPosition(), pB->getPosition()))
{
- if(!isSamePos(pA->getPosition(), pB->getPosition()))
- {
- const ::basegfx::vector::B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
- const ::basegfx::vector::B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
+ const ::basegfx::B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
+ const ::basegfx::B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
- if(::basegfx::polygon::tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
+ if(::basegfx::tools::findCut(pA->getPosition(), aVectorA, pB->getPosition(), aVectorB, CUTFLAG_LINE, &fCut))
+ {
+ // crossover, two new points, use as cutpoint
+ ::basegfx::B2DPoint aNewPos(::basegfx::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(::basegfx::tools::isPointOnEdge(pA->getPosition(), pB->getPosition(), aVectorB, &fCut))
{
- // crossover, two new points, use as cutpoint
- ::basegfx::point::B2DPoint aNewPos(::basegfx::tuple::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);
+ // 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
+ else if(::basegfx::tools::isPointOnEdge(pB->getPosition(), pA->getPosition(), aVectorA, &fCut))
{
- if(::basegfx::polygon::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(::basegfx::polygon::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);
- }
+ // 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);
+ // next B
+ pB = pB->getNext();
+ } while(pB != pCandB);
- // test all temporary cuts for simple criteria
- for(sal_uInt32 c(0L); c < aTmpCuts.size();)
- {
- B2DSimpleCut* pCand = aTmpCuts[c];
- sal_Bool bPrevSamePos(isPrevSamePos(pCand->getLeft(), pCand->getRight()));
- sal_Bool bNextSamePos(isNextSamePos(pCand->getLeft(), pCand->getRight()));
- sal_Bool bDelete(sal_False);
- sal_Bool bIncC(sal_True);
+ // next A
+ pA = pA->getNext();
+ } while(pA != pCandA);
- if(bPrevSamePos && bNextSamePos)
- {
- // single point inside continued same direction section
- bDelete = sal_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 = sal_False;
- }
- else
- {
- // no cut, just a touch in one point
- bDelete = sal_True;
- }
- }
+ // test all temporary cuts for simple criteria
+ for(sal_uInt32 c(0L); c < aTmpCuts.size();)
+ {
+ B2DSimpleCut* pCand = aTmpCuts[c];
+ sal_Bool bPrevSamePos(isPrevSamePos(pCand->getLeft(), pCand->getRight()));
+ sal_Bool bNextSamePos(isNextSamePos(pCand->getLeft(), pCand->getRight()));
+ sal_Bool bDelete(sal_False);
+ sal_Bool bIncC(sal_True);
- // delete if wanted
- if(bDelete)
+ if(bPrevSamePos && bNextSamePos)
+ {
+ // single point inside continued same direction section
+ bDelete = sal_True;
+ }
+ else if(!bPrevSamePos && !bNextSamePos)
+ {
+ // this is no same direction section, test for real cut
+ if(isCrossover(pCand->getLeft(), pCand->getRight()))
{
- delete pCand;
+ // real cut, move to real cutlist
+ aNewCuts.push_back(pCand);
aTmpCuts.erase(aTmpCuts.begin() + c);
bIncC = sal_False;
}
+ else
+ {
+ // no cut, just a touch in one point
+ bDelete = sal_True;
+ }
+ }
- // next candidate
- if(bIncC)
- c++;
+ // delete if wanted
+ if(bDelete)
+ {
+ delete pCand;
+ aTmpCuts.erase(aTmpCuts.begin() + c);
+ bIncC = sal_False;
}
- // are there entering/leaving same direction sections?
- while(aTmpCuts.size())
+ // next candidate
+ if(bIncC)
+ c++;
+ }
+
+ // are there entering/leaving same direction sections?
+ while(aTmpCuts.size())
+ {
+ // 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();
+ sal_Bool bPrevSamePos(isPrevSamePos(pActA, pActB));
+ sal_Bool bNextSamePos(isNextSamePos(pActA, pActB));
+
+ if(aTmpCuts.size())
{
- // 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();
- sal_Bool bPrevSamePos(isPrevSamePos(pActA, pActB));
- sal_Bool bNextSamePos(isNextSamePos(pActA, pActB));
-
- if(aTmpCuts.size())
+ B2DSimpleCut* pCutB = 0L;
+
+ if(isNextSamePos(pCutA->getLeft(), pCutA->getRight()))
{
- B2DSimpleCut* pCutB = 0L;
+ // this is a start node
+ B2DPolygonNode* pActA = pCutA->getLeft()->getNext();
+ B2DPolygonNode* pActB = pCutA->getRight()->getNext();
- if(isNextSamePos(pCutA->getLeft(), pCutA->getRight()))
+ while(!pCutB && pActA != pCutA->getLeft())
{
- // this is a start node
- B2DPolygonNode* pActA = pCutA->getLeft()->getNext();
- B2DPolygonNode* pActB = pCutA->getRight()->getNext();
-
- while(!pCutB && pActA != pCutA->getLeft())
+ if(!isNextSamePos(pActA, pActB))
{
- if(!isNextSamePos(pActA, pActB))
- {
- pCutB = getExistingCut(aTmpCuts, pActA, pActB);
- }
-
- pActA = pActA->getNext();
- pActB = pActB->getNext();
+ pCutB = getExistingCut(aTmpCuts, pActA, pActB);
}
- if(pCutB)
+ pActA = pActA->getNext();
+ pActB = pActB->getNext();
+ }
+
+ if(pCutB)
+ {
+ const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
+ aTmpCuts.erase(aFindResult);
+
+ if(isCrossover(pCutA, pCutB))
+ {
+ aNewCuts.push_back(pCutB);
+ }
+ else
{
- const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
- aTmpCuts.erase(aFindResult);
+ delete pCutB;
+ }
+ }
+ }
+ else
+ {
+ // this is a end node
+ B2DPolygonNode* pActA = pCutA->getLeft()->getPrevious();
+ B2DPolygonNode* pActB = pCutA->getRight()->getPrevious();
- if(isCrossover(pCutA, pCutB))
- {
- aNewCuts.push_back(pCutB);
- }
- else
- {
- delete pCutB;
- }
+ while(!pCutB && pActA != pCutA->getLeft())
+ {
+ if(!isPrevSamePos(pActA, pActB))
+ {
+ pCutB = getExistingCut(aTmpCuts, pActA, pActB);
}
+
+ pActA = pActA->getPrevious();
+ pActB = pActB->getPrevious();
}
- else
+
+ if(pCutB)
{
- // this is a end node
- B2DPolygonNode* pActA = pCutA->getLeft()->getPrevious();
- B2DPolygonNode* pActB = pCutA->getRight()->getPrevious();
+ const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
+ aTmpCuts.erase(aFindResult);
- while(!pCutB && pActA != pCutA->getLeft())
+ if(isCrossover(pCutB, pCutA))
{
- if(!isPrevSamePos(pActA, pActB))
- {
- pCutB = getExistingCut(aTmpCuts, pActA, pActB);
- }
-
- pActA = pActA->getPrevious();
- pActB = pActB->getPrevious();
+ aNewCuts.push_back(pCutB);
}
-
- if(pCutB)
+ else
{
- const B2DSimpleCutVector::iterator aFindResult = ::std::find(aTmpCuts.begin(), aTmpCuts.end(), pCutB);
- aTmpCuts.erase(aFindResult);
-
- if(isCrossover(pCutB, pCutA))
- {
- aNewCuts.push_back(pCutB);
- }
- else
- {
- delete pCutB;
- }
+ delete pCutB;
}
}
}
-
- // delete cut in EVERY case
- delete pCutA;
}
- // copy new cuts to all cuts
- aCuts.insert(aCuts.begin(), aNewCuts.begin(), aNewCuts.end());
- aNewCuts.clear();
+ // delete cut in EVERY case
+ delete pCutA;
}
+
+ // copy new cuts to all cuts
+ aCuts.insert(aCuts.begin(), aNewCuts.begin(), aNewCuts.end());
+ aNewCuts.clear();
}
}
+ }
- // delete volume list again
- delete[] pVolumes;
+ // delete volume list again
+ delete[] pVolumes;
- // are there cuts to solve? Solve them all in one run
- if(aCuts.size())
- {
- solveAllCuts(aCuts);
- }
+ // are there cuts to solve? Solve them all in one run
+ if(aCuts.size())
+ {
+ solveAllCuts(aCuts);
}
- } // end of namespace polygon
+ }
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-19 06:54:25 +0000