INTEGRATION: CWS canvas02 (1.8.24); FILE MERGED

2005/10/08 13:20:16 thb 1.8.24.2: RESYNC: (1.8-1.9); FILE MERGED
2005/07/28 10:10:20 thb 1.8.24.1: Join from cws_src680_aw024: #i48939# and new rendering subsystem need AW's clipper changes

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
 
 //////////////////////////////////////////////////////////////////////////////