summaryrefslogtreecommitdiff
path: root/basegfx/source/polygon/b2dpolypolygoncutter.cxx
diff options
context:
space:
mode:
authorPascal Junck <pjunck@openoffice.org>2004-11-03 07:37:59 +0000
committerPascal Junck <pjunck@openoffice.org>2004-11-03 07:37:59 +0000
commitfd8fe422bb414f61aba1cfc6afe62221299cc725 (patch)
treed3ecaaf2c6cf39fbbfe932f0f7bce7b7e607dfa2 /basegfx/source/polygon/b2dpolypolygoncutter.cxx
parent8f5dc2ea9912c83240871d8b69f0614dac1594e8 (diff)
INTEGRATION: CWS aw019 (1.6.22); FILE MERGED
2004/10/19 08:55:28 aw 1.6.22.2: #i34831# 2004/10/18 10:39:56 aw 1.6.22.1: #i34831#
Diffstat (limited to 'basegfx/source/polygon/b2dpolypolygoncutter.cxx')
-rw-r--r--basegfx/source/polygon/b2dpolypolygoncutter.cxx381
1 files changed, 143 insertions, 238 deletions
diff --git a/basegfx/source/polygon/b2dpolypolygoncutter.cxx b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
index 6b738b19239d..75c459a7abff 100644
--- a/basegfx/source/polygon/b2dpolypolygoncutter.cxx
+++ b/basegfx/source/polygon/b2dpolypolygoncutter.cxx
@@ -2,9 +2,9 @@
*
* $RCSfile: b2dpolypolygoncutter.cxx,v $
*
- * $Revision: 1.6 $
+ * $Revision: 1.7 $
*
- * last change: $Author: kz $ $Date: 2004-06-10 11:40:01 $
+ * last change: $Author: pjunck $ $Date: 2004-11-03 08:37:59 $
*
* The Contents of this file are made available subject to the terms of
* either of the following licenses
@@ -83,11 +83,42 @@
#include <basegfx/polygon/b2dpolygontools.hxx>
#endif
+#include <algorithm>
+
//////////////////////////////////////////////////////////////////////////////
-// B2DPolygonNode implementation
+// B2DPolygonNode
namespace basegfx
{
+ class B2DPolygonNode
+ {
+ 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; }
+
+ void calcMinMaxX(double& fMaxAX, double& fMinAX) const;
+ void calcMinMaxY(double& fMaxAY, double& fMinAY) const;
+
+ void swapPreviousNext() { B2DPolygonNode* pZwi = mpPrevious; mpPrevious = mpNext; mpNext = pZwi; }
+ void swapNextPointers(B2DPolygonNode* pCand);
+
+ void addToList(B2DPolygonNode*& rpList);
+ void remFromList(B2DPolygonNode*& rpList);
+
+ B2DRange getRange() const;
+ };
+
B2DPolygonNode::B2DPolygonNode(const B2DPoint& rPosition, B2DPolygonNode* pPrevious)
: maPosition(rPosition)
{
@@ -190,47 +221,6 @@ namespace basegfx
}
}
- bool B2DPolygonNode::getOrientation() const
- {
- const B2DPolygonNode* pOutmost = this;
- const B2DPolygonNode* pCurrent = this->getNext();
-
- while(pCurrent != this)
- {
- if(fTools::more(pOutmost->getPosition().getX(), pCurrent->getPosition().getX()))
- {
- if(pCurrent->getPosition().getX() < pOutmost->getPosition().getX())
- {
- pOutmost = pCurrent;
- }
- else
- {
- if(pCurrent->getPosition().getY() < pOutmost->getPosition().getY())
- {
- pOutmost = pCurrent;
- }
- }
- }
-
- // next node
- pCurrent = pCurrent->getNext();
- }
-
- B2DVector aVec1(pOutmost->getPrevious()->getPosition() - pOutmost->getPosition());
- B2DVector aVec2(pOutmost->getNext()->getPosition() - pOutmost->getPosition());
- return bool(fTools::more(aVec1.getX() * aVec2.getY(), aVec1.getY() * aVec2.getX()));
- }
-
- void B2DPolygonNode::swapOrientation()
- {
- B2DPolygonNode* pCurrent = this;
-
- do {
- pCurrent->swapPreviousNext();
- pCurrent = pCurrent->getPrevious();
- } while(pCurrent != this);
- }
-
B2DRange B2DPolygonNode::getRange() const
{
B2DRange aRetval;
@@ -243,122 +233,38 @@ namespace basegfx
return aRetval;
}
-
- bool B2DPolygonNode::isInside(const B2DPoint& rPoint, bool bWithBorder) const
- {
- bool bInside(false);
- const B2DPolygonNode* pCurrent = this;
-
- do
- {
- if(bWithBorder && pCurrent->getPosition().equal(rPoint))
- {
- return true;
- }
-
- B2DPolygonNode* pNext = pCurrent->getNext();
- const bool bCompYA(fTools::more(pCurrent->getPosition().getY(), rPoint.getY()));
- const bool bCompYB(fTools::more(pNext->getPosition().getY(), rPoint.getY()));
-
- if(bCompYA != bCompYB)
- {
- const bool bCompXA(fTools::more(pCurrent->getPosition().getX(), rPoint.getX()));
- const bool bCompXB(fTools::more(pNext->getPosition().getX(), rPoint.getX()));
-
- if(bCompXA == bCompXB)
- {
- if(bCompXA)
- {
- bInside = !bInside;
- }
- }
- else
- {
- double fCmp =
- pNext->getPosition().getX() - (pNext->getPosition().getY() - rPoint.getY()) *
- (pCurrent->getPosition().getX() - pNext->getPosition().getX()) /
- (pCurrent->getPosition().getY() - pNext->getPosition().getY());
-
- if(bWithBorder && fTools::more(fCmp, rPoint.getX()))
- {
- bInside = !bInside;
- }
- else if(fTools::moreOrEqual(fCmp, rPoint.getX()))
- {
- bInside = !bInside;
- }
- }
- }
-
- // next edge
- pCurrent = pNext;
-
- } while(pCurrent != this);
-
- return bInside;
- }
-
- bool B2DPolygonNode::isPolygonInside(B2DPolygonNode* pPoly, bool bWithBorder) const
- {
- B2DPolygonNode* pTest = pPoly;
- bool bAllAInside(true);
-
- do {
- bAllAInside = isInside(pTest->getPosition(), bWithBorder);
- pTest = pTest->getNext();
- } while(bAllAInside && pTest != pPoly);
-
- return bAllAInside;
- }
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
-// B2DSimpleCut implementation
+// B2DSimpleCut
namespace basegfx
{
- void B2DSimpleCut::solve()
+ class B2DSimpleCut
{
- mpLeft->swapNextPointers(mpRight);
+ B2DPolygonNode* mpLeft;
+ B2DPolygonNode* mpRight;
- if(mbCorrectOrientation)
+ public:
+ B2DSimpleCut(B2DPolygonNode* pL, B2DPolygonNode* pR)
+ : mpLeft(pL),
+ mpRight(pR)
{
- if(mpLeft->getOrientation() != mbOrientation)
- {
- mpLeft->swapOrientation();
- }
-
- if(mpRight->getOrientation() != mbOrientation)
- {
- mpRight->swapOrientation();
- }
}
- }
-} // end of namespace basegfx
-//////////////////////////////////////////////////////////////////////////////
-// B2DClipExtraPolygonInfo implementation
-
-namespace basegfx
-{
- void B2DClipExtraPolygonInfo::init(B2DPolygonNode* pNew)
- {
- maRange = pNew->getRange();
- mbOrientation = pNew->getOrientation();
- mnDepth = (mbOrientation) ? 0L : -1L;
- }
-
- void B2DClipExtraPolygonInfo::changeDepth(bool bOrientation)
- {
- if(bOrientation)
+ void solve()
{
- mnDepth++;
+ mpLeft->swapNextPointers(mpRight);
}
- else
+
+ B2DPolygonNode* getLeft() const { return mpLeft; }
+ B2DPolygonNode* getRight() const { return mpRight; }
+
+ bool isSameCut(B2DPolygonNode* pA, B2DPolygonNode* pB) const
{
- mnDepth--;
+ return ((pA == mpLeft && pB == mpRight) || (pB == mpLeft && pA == mpRight));
}
- }
+ };
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
@@ -376,60 +282,60 @@ namespace basegfx
maPolygonList.clear();
}
- void B2DPolyPolygonCutter::removeIncludedPolygons(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++)
- {
- pInfos[a].init(maPolygonList[a]);
- }
-
- // get all includes
- for(a = 0L; a < aCount; a++)
- {
- B2DClipExtraPolygonInfo& rInfoA = pInfos[a];
-
- for(b = 0L; b < aCount; b++)
- {
- 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], true))
- {
- // pB is inside pA
- rInfoB.changeDepth(rInfoA.getOrientation());
- }
- }
- }
- }
-
- // 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++;
- }
- }
-
- // delete infos
- delete[] pInfos;
- }
+//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)
{
@@ -521,38 +427,27 @@ namespace basegfx
} while(pAct != pPolygon);
}
- void B2DPolyPolygonCutter::addPolyPolygon(const B2DPolyPolygon& rPolyPolygon, bool bForceOrientation)
+ 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);
- aCandidate.removeDoublePoints();
-
- if(!aCandidate.isClosed() || aCandidate.count() < 3)
- {
- maNotClosedPolygons.append(aCandidate);
- }
- else
- {
- if(bForceOrientation)
- {
- B2VectorOrientation aOrientation =
- tools::getOrientation(aCandidate);
-
- if(ORIENTATION_POSITIVE != aOrientation)
- {
- aCandidate.flip();
- }
- }
-
- B2DPolygonNode* pNew = createNewPolygon(aCandidate);
- maPolygonList.push_back(pNew);
- }
+ addPolygon(aCandidate);
}
}
- void B2DPolyPolygonCutter::getPolyPolygon(B2DPolyPolygon& rPolyPolygon)
+ B2DPolyPolygon B2DPolyPolygonCutter::getPolyPolygon()
{
+ B2DPolyPolygon aRetval;
B2DPolygonNodeVector::iterator aCandidate(maPolygonList.begin());
for(; aCandidate < maPolygonList.end(); aCandidate++)
@@ -576,7 +471,7 @@ namespace basegfx
} while(pAct != pCand);
aNewPolygon.setClosed(true);
- rPolyPolygon.append(aNewPolygon);
+ aRetval.append(aNewPolygon);
}
deletePolygon(pCand);
@@ -584,11 +479,7 @@ namespace basegfx
maPolygonList.clear();
- while(maNotClosedPolygons.count())
- {
- rPolyPolygon.append(maNotClosedPolygons.getB2DPolygon(0L));
- maNotClosedPolygons.remove(0L);
- }
+ return aRetval;
}
B2DSimpleCut* B2DPolyPolygonCutter::getExistingCut(B2DSimpleCutVector& rTmpCuts, B2DPolygonNode* pA, B2DPolygonNode* pB)
@@ -654,9 +545,10 @@ namespace basegfx
pB = pA->getNext();
do {
- if(isSamePos(pA->getPosition(), pB->getPosition()))
+ if(pA->getPosition().equal(pB->getPosition()))
{
- aNewCuts.push_back(new B2DSimpleCut(pA, pB, true, pCand->getOrientation()));
+//BFS08 aNewCuts.push_back(new B2DSimpleCut(pA, pB, true, pCand->getOrientation()));
+ aNewCuts.push_back(new B2DSimpleCut(pA, pB));
}
// next B
@@ -687,7 +579,7 @@ namespace basegfx
if(fTools::moreOrEqual(fMaxBY, fMinAY) // #116732#
&& fTools::moreOrEqual(fMaxAY, fMinBY)) // #116732#
{
- if(!isSamePos(pA->getPosition(), pB->getPosition()))
+ if(!pA->getPosition().equal(pB->getPosition()))
{
const B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
const B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());
@@ -698,7 +590,8 @@ namespace basegfx
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, true, pCand->getOrientation()));
+//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);
}
@@ -708,13 +601,15 @@ namespace basegfx
{
// startpoint A at edge B, one new point
B2DPolygonNode* pCutHi = new B2DPolygonNode(pA->getPosition(), pB);
- aNewCuts.push_back(new B2DSimpleCut(pA, pCutHi, true, pCand->getOrientation()));
+//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))
{
// startpoint B at edge A, one new point
B2DPolygonNode* pCutLo = new B2DPolygonNode(pB->getPosition(), pA);
- aNewCuts.push_back(new B2DSimpleCut(pCutLo, pB, true, pCand->getOrientation()));
+//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);
}
@@ -863,6 +758,16 @@ namespace basegfx
return (bA1BiggerB1 == bA2BiggerB2);
}
+ bool B2DPolyPolygonCutter::isNextSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
+ {
+ return pA->getNext()->getPosition().equal(pB->getNext()->getPosition());
+ }
+
+ bool B2DPolyPolygonCutter::isPrevSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
+ {
+ return pA->getPrevious()->getPosition().equal(pB->getPrevious()->getPosition());
+ }
+
void B2DPolyPolygonCutter::removeDoubleIntersections()
{
double fMaxAX, fMinAX, fMaxAY, fMinAY;
@@ -892,7 +797,7 @@ namespace basegfx
for(sal_uInt32 b = a + 1L; b < maPolygonList.size(); b++)
{
- if(doRangesIntersect(pVolumes[a], pVolumes[b]))
+ if(pVolumes[a].overlaps(pVolumes[b]))
{
pCandB = maPolygonList[b];
pA = pCandA;
@@ -903,7 +808,7 @@ namespace basegfx
pB = pCandB;
do {
- if(isSamePos(pA->getPosition(), pB->getPosition()))
+ if(pA->getPosition().equal(pB->getPosition()))
{
aTmpCuts.push_back(new B2DSimpleCut(pA, pB));
}
@@ -936,7 +841,7 @@ namespace basegfx
if(fTools::moreOrEqual(fMaxBY, fMinAY) // #116732#
&& fTools::moreOrEqual(fMaxAY, fMinBY)) // #116732#
{
- if(!isSamePos(pA->getPosition(), pB->getPosition()))
+ if(!pA->getPosition().equal(pB->getPosition()))
{
const B2DVector aVectorA(pA->getNext()->getPosition() - pA->getPosition());
const B2DVector aVectorB(pB->getNext()->getPosition() - pB->getPosition());