xref: /trunk/main/basegfx/source/polygon/b2dpolypolygoncutter.cxx (revision 3ddd48ca)

/**************************************************************
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/



// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_basegfx.hxx"
#include <osl/diagnose.h>
#include <basegfx/numeric/ftools.hxx>
#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
#include <basegfx/point/b2dpoint.hxx>
#include <basegfx/vector/b2dvector.hxx>
#include <basegfx/polygon/b2dpolygon.hxx>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
#include <basegfx/range/b2drange.hxx>
#include <basegfx/polygon/b2dpolypolygontools.hxx>
#include <basegfx/curve/b2dcubicbezier.hxx>
#include <vector>
#include <algorithm>

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
	namespace
	{
		//////////////////////////////////////////////////////////////////////////////

		struct StripHelper
		{
			B2DRange								maRange;
			sal_Int32								mnDepth;
			B2VectorOrientation						meOrinetation;
		};

		//////////////////////////////////////////////////////////////////////////////

		struct PN
        {
        public:
            B2DPoint                maPoint;
            sal_uInt32              mnI;
            sal_uInt32              mnIP;
            sal_uInt32              mnIN;
        };

		//////////////////////////////////////////////////////////////////////////////

		struct VN
        {
        public:
            B2DVector               maPrev;
            B2DVector               maNext;

			// to have the correct curve segments in the crossover checks,
			// it is necessary to keep the original next vectors, too. Else,
			// it may happen to use a already switched next vector which
			// would interpolate the wrong comparison point
            B2DVector               maOriginalNext;
        };

		//////////////////////////////////////////////////////////////////////////////

		struct SN
        {
        public:
            PN*                     mpPN;

            bool operator<(const SN& rComp) const
			{
				if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
				{
					if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
					{
						return (mpPN->mnI < rComp.mpPN->mnI);
					}
					else
					{
						return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
					}
				}
				else
				{
					return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX());
				}
			}
        };

		//////////////////////////////////////////////////////////////////////////////

		typedef ::std::vector< PN > PNV;
		typedef ::std::vector< VN > VNV;
		typedef ::std::vector< SN > SNV;
        typedef ::std::pair< basegfx::B2DPoint /*orig*/, basegfx::B2DPoint /*repl*/ > CorrectionPair;
        typedef ::std::vector< CorrectionPair > CorrectionTable;

		//////////////////////////////////////////////////////////////////////////////

		class solver
        {
        private:
            const B2DPolyPolygon    maOriginal;
            PNV                     maPNV;
            VNV                     maVNV;
            SNV                     maSNV;
            CorrectionTable         maCorrectionTable;

            unsigned                mbIsCurve : 1;
            unsigned                mbChanged : 1;

            void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
            {
                const sal_uInt32 nCount(rGeometry.count());
                PN aNewPN;
                VN aNewVN;
                SN aNewSN;

                for(sal_uInt32 a(0); a < nCount; a++)
	            {
                    const B2DPoint aPoint(rGeometry.getB2DPoint(a));
                    aNewPN.maPoint = aPoint;
                    aNewPN.mnI = aPos + a;
		            aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
		            aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
                    maPNV.push_back(aNewPN);

                    if(mbIsCurve)
                    {
                        aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
                        aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
						aNewVN.maOriginalNext = aNewVN.maNext;
                        maVNV.push_back(aNewVN);
                    }

                    aNewSN.mpPN = &maPNV[maPNV.size() - 1];
                    maSNV.push_back(aNewSN);
                }
            }

			bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest)
			{
				// tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is
				// with border.
				if(rVecA.cross(rVecB) > 0.0)
				{
					// b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
					const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
					const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));

					return (bBoolA && bBoolB);
				}
				else
				{
					// b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside)
					const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
					const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));

					return (!(bBoolA && bBoolB));
				}
			}

			void impSwitchNext(PN& rPNa, PN& rPNb)
			{
				::std::swap(rPNa.mnIN, rPNb.mnIN);

				if(mbIsCurve)
				{
					VN& rVNa = maVNV[rPNa.mnI];
					VN& rVNb = maVNV[rPNb.mnI];

					::std::swap(rVNa.maNext, rVNb.maNext);
				}

				if(!mbChanged)
				{
					mbChanged = true;
				}
			}

            B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
            {
                const B2DPoint& rStart(rPN.maPoint);
                const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
                const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext);
				// Use maOriginalNext, not maNext to create the original (yet unchanged)
				// curve segment. Otherwise, this segment would NOT ne correct.
                const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);

                return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
            }

			void impHandleCommon(PN& rPNa, PN& rPNb)
            {
                if(mbIsCurve)
                {
                    const B2DCubicBezier aNextA(createSegment(rPNa, false));
                    const B2DCubicBezier aPrevA(createSegment(rPNa, true));

                    if(aNextA.equal(aPrevA))
                    {
                        // deadend on A (identical edge)
                        return;
                    }

                    const B2DCubicBezier aNextB(createSegment(rPNb, false));
                    const B2DCubicBezier aPrevB(createSegment(rPNb, true));

                    if(aNextB.equal(aPrevB))
                    {
                        // deadend on B (identical edge)
                        return;
                    }

                    if(aPrevA.equal(aPrevB))
                    {
                        // common edge in same direction
                        if(aNextA.equal(aNextB))
                        {
                            // common edge in same direction continues
                            return;
                        }
                        else
                        {
                            // common edge in same direction leave
                            // action is done on enter
                            return;
                        }
                    }
                    else if(aPrevA.equal(aNextB))
                    {
                        // common edge in opposite direction
                        if(aNextA.equal(aPrevB))
                        {
                            // common edge in opposite direction continues
                            return;
                        }
                        else
                        {
                            // common edge in opposite direction leave
                            impSwitchNext(rPNa, rPNb);
                        }
                    }
                    else if(aNextA.equal(aNextB))
                    {
                        // common edge in same direction enter
                        // search leave edge
                        PN* pPNa2 = &maPNV[rPNa.mnIN];
                        PN* pPNb2 = &maPNV[rPNb.mnIN];
                        bool bOnEdge(true);

                        do
                        {
                            const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
                            const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));

                            if(aNextA2.equal(aNextB2))
                            {
                                pPNa2 = &maPNV[pPNa2->mnIN];
                                pPNb2 = &maPNV[pPNb2->mnIN];
                            }
                            else
                            {
                                bOnEdge = false;
                            }
                        }
                        while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa);

                        if(bOnEdge)
                        {
                            // loop over two identical polygon paths
                            return;
                        }
                        else
                        {
                            // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
                            // at enter/leave. Check for crossover.
                            const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
                            const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
                            const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
                            const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));

                            const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
                            const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true));
                            const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
                            const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint());
                            const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint());
                            const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint());
                            const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2));

                            if(bEnter != bLeave)
                            {
                                // crossover
                                impSwitchNext(rPNa, rPNb);
                            }
                        }
                    }
                    else if(aNextA.equal(aPrevB))
                    {
                        // common edge in opposite direction enter
                        impSwitchNext(rPNa, rPNb);
                    }
                    else
                    {
                        // no common edges, check for crossover
                        const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
                        const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
                        const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
                        const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());

                        const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
                        const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));

                        if(bEnter != bLeave)
                        {
                            // crossover
                            impSwitchNext(rPNa, rPNb);
                        }
                    }
                }
                else
                {
                    const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
                    const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);

                    if(rNextA.equal(rPrevA))
                    {
                        // deadend on A
                        return;
                    }

                    const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
                    const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);

                    if(rNextB.equal(rPrevB))
                    {
                        // deadend on B
                        return;
                    }

                    if(rPrevA.equal(rPrevB))
                    {
                        // common edge in same direction
                        if(rNextA.equal(rNextB))
                        {
                            // common edge in same direction continues
                            return;
                        }
                        else
                        {
                            // common edge in same direction leave
                            // action is done on enter
                            return;
                        }
                    }
                    else if(rPrevA.equal(rNextB))
                    {
                        // common edge in opposite direction
                        if(rNextA.equal(rPrevB))
                        {
                            // common edge in opposite direction continues
                            return;
                        }
                        else
                        {
                            // common edge in opposite direction leave
                            impSwitchNext(rPNa, rPNb);
                        }
                    }
                    else if(rNextA.equal(rNextB))
                    {
                        // common edge in same direction enter
                        // search leave edge
                        PN* pPNa2 = &maPNV[rPNa.mnIN];
                        PN* pPNb2 = &maPNV[rPNb.mnIN];
                        bool bOnEdge(true);

                        do
                        {
                            const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
                            const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);

                            if(rNextA2.equal(rNextB2))
                            {
                                pPNa2 = &maPNV[pPNa2->mnIN];
                                pPNb2 = &maPNV[pPNb2->mnIN];
                            }
                            else
                            {
                                bOnEdge = false;
                            }
                        }
                        while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa);

                        if(bOnEdge)
                        {
                            // loop over two identical polygon paths
                            return;
                        }
                        else
                        {
                            // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
                            // at enter/leave. Check for crossover.
                            const B2DPoint& aPointE(rPNa.maPoint);
                            const B2DVector aPrevAE(rPrevA - aPointE);
                            const B2DVector aNextAE(rNextA - aPointE);
                            const B2DVector aPrevBE(rPrevB - aPointE);

                            const B2DPoint& aPointL(pPNa2->maPoint);
                            const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
                            const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
                            const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);

                            const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
                            const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));

                            if(bEnter != bLeave)
                            {
                                // crossover; switch start or end
                                impSwitchNext(rPNa, rPNb);
                            }
                        }
                    }
                    else if(rNextA.equal(rPrevB))
                    {
                        // common edge in opposite direction enter
                        impSwitchNext(rPNa, rPNb);
                    }
                    else
                    {
                        // no common edges, check for crossover
                        const B2DPoint& aPoint(rPNa.maPoint);
                        const B2DVector aPrevA(rPrevA - aPoint);
                        const B2DVector aNextA(rNextA - aPoint);
                        const B2DVector aPrevB(rPrevB - aPoint);
                        const B2DVector aNextB(rNextB - aPoint);

                        const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
                        const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));

                        if(bEnter != bLeave)
                        {
                            // crossover
                            impSwitchNext(rPNa, rPNb);
                        }
                    }
                }
            }

            void impSolve()
            {
                // sort by point to identify common nodes easier
                ::std::sort(maSNV.begin(), maSNV.end());

                // handle common nodes
                const sal_uInt32 nNodeCount(maSNV.size());
                sal_uInt32 a(0);

                // snap unsharp-equal points
                if(nNodeCount)
                {
                    basegfx::B2DPoint* pLast(&maSNV[0].mpPN->maPoint);

                    for(a = 1; a < nNodeCount; a++)
                    {
                        basegfx::B2DPoint* pCurrent(&maSNV[a].mpPN->maPoint);

                        if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
                        {
                            const basegfx::B2DPoint aMiddle((*pLast + *pCurrent) * 0.5);

                            if(pLast->getX() != aMiddle.getX() || pLast->getY() != aMiddle.getY())
                            {
                                maCorrectionTable.push_back(CorrectionPair(*pLast, aMiddle));
                                *pLast = aMiddle;
                            }

                            if(pCurrent->getX() != aMiddle.getX() || pCurrent->getY() != aMiddle.getY())
                            {
                                maCorrectionTable.push_back(CorrectionPair(*pCurrent, aMiddle));
                                *pCurrent = aMiddle;
                            }
                        }

                        pLast = pCurrent;
                    }
                }

                for(a = 0; a < nNodeCount - 1; a++)
                {
                    // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
                    PN& rPNb = *(maSNV[a].mpPN);

                    for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
                    {
                        impHandleCommon(rPNb, *maSNV[b].mpPN);
                    }
                }
            }

		public:
            solver(const B2DPolygon& rOriginal)
            :   maOriginal(B2DPolyPolygon(rOriginal)),
                mbIsCurve(false),
                mbChanged(false)
            {
                const sal_uInt32 nOriginalCount(rOriginal.count());

                if(nOriginalCount)
                {
				    B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal));
				    aGeometry.removeDoublePoints();
                    aGeometry = tools::simplifyCurveSegments(aGeometry);
                    mbIsCurve = aGeometry.areControlPointsUsed();

                    const sal_uInt32 nPointCount(aGeometry.count());

                    // If it's not a pezier polygon, at least four points are needed to create
                    // a self-intersection. If it's a bezier polygon, the minimum point number
                    // is two, since with a single point You get a curve, but no self-intersection
                    if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
                    {
				        // reserve space in point, control and sort vector.
                        maSNV.reserve(nPointCount);
				        maPNV.reserve(nPointCount);
                        maVNV.reserve(mbIsCurve ? nPointCount : 0);

				        // fill data
                        impAddPolygon(0, aGeometry);

						// solve common nodes
						impSolve();
                    }
                }
            }

			solver(const B2DPolyPolygon& rOriginal)
            :   maOriginal(rOriginal),
                mbIsCurve(false),
                mbChanged(false)
            {
                sal_uInt32 nOriginalCount(maOriginal.count());

                if(nOriginalCount)
                {
				    B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true));
					aGeometry.removeDoublePoints();
                    aGeometry = tools::simplifyCurveSegments(aGeometry);
                    mbIsCurve = aGeometry.areControlPointsUsed();
					nOriginalCount = aGeometry.count();

					if(nOriginalCount)
					{
						sal_uInt32 nPointCount(0);
						sal_uInt32 a(0);

						// count points
						for(a = 0; a < nOriginalCount; a++)
						{
							const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
							const sal_uInt32 nCandCount(aCandidate.count());

                            // If it's not a bezier curve, at least three points would be needed to have a
                            // topological relevant (not empty) polygon. Since its not known here if trivial
                            // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
                            // more than one point.
                            // For bezier curves, the minimum for defining an area is also one.
							if(nCandCount)
							{
								nPointCount += nCandCount;
							}
						}

                        if(nPointCount)
                        {
				            // reserve space in point, control and sort vector.
                            maSNV.reserve(nPointCount);
				            maPNV.reserve(nPointCount);
                            maVNV.reserve(mbIsCurve ? nPointCount : 0);

				            // fill data
	                        sal_uInt32 nInsertIndex(0);

						    for(a = 0; a < nOriginalCount; a++)
						    {
							    const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
							    const sal_uInt32 nCandCount(aCandidate.count());

                                // use same condition as above, the data vector is
                                // pre-allocated
							    if(nCandCount)
							    {
		                            impAddPolygon(nInsertIndex, aCandidate);
								    nInsertIndex += nCandCount;
							    }
						    }

						    // solve common nodes
						    impSolve();
                        }
					}
                }
            }

			B2DPolyPolygon getB2DPolyPolygon()
			{
				if(mbChanged)
				{
					B2DPolyPolygon aRetval;
					const sal_uInt32 nCount(maPNV.size());
					sal_uInt32 nCountdown(nCount);

					for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
					{
                        PN& rPN = maPNV[a];

						if(SAL_MAX_UINT32 != rPN.mnI)
						{
							// unused node, start new part polygon
							B2DPolygon aNewPart;
	                        PN* pPNCurr = &rPN;

							do
							{
								const B2DPoint& rPoint = pPNCurr->maPoint;
								aNewPart.append(rPoint);

								if(mbIsCurve)
								{
				                    const VN& rVNCurr = maVNV[pPNCurr->mnI];

									if(!rVNCurr.maPrev.equalZero())
									{
										aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
									}

									if(!rVNCurr.maNext.equalZero())
									{
										aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
									}
								}

								pPNCurr->mnI = SAL_MAX_UINT32;
								nCountdown--;
								pPNCurr = &(maPNV[pPNCurr->mnIN]);
							}
							while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI);

							// close and add
							aNewPart.setClosed(true);
							aRetval.append(aNewPart);
						}
					}

					return aRetval;
				}
                else
                {
                    const sal_uInt32 nCorrectionSize(maCorrectionTable.size());

                    // no change, return original
                    if(!nCorrectionSize)
                    {
                        return maOriginal;
                    }

                    // apply coordinate corrections to ensure inside/outside correctness after solving
                    const sal_uInt32 nPolygonCount(maOriginal.count());
                    basegfx::B2DPolyPolygon aRetval(maOriginal);

                    for(sal_uInt32 a(0); a < nPolygonCount; a++)
                    {
                        basegfx::B2DPolygon aTemp(aRetval.getB2DPolygon(a));
                        const sal_uInt32 nPointCount(aTemp.count());
                        bool bChanged(false);

                        for(sal_uInt32 b(0); b < nPointCount; b++)
                        {
                            const basegfx::B2DPoint aCandidate(aTemp.getB2DPoint(b));

                            for(sal_uInt32 c(0); c < nCorrectionSize; c++)
                            {
                                if(maCorrectionTable[c].first.getX() == aCandidate.getX() && maCorrectionTable[c].first.getY() == aCandidate.getY())
                                {
                                    aTemp.setB2DPoint(b, maCorrectionTable[c].second);
                                    bChanged = true;
                                }
                            }
                        }

                        if(bChanged)
                        {
                            aRetval.setB2DPolygon(a, aTemp);
                        }
                    }

                    return aRetval;
                }
            }
        };

		//////////////////////////////////////////////////////////////////////////////

	} // end of anonymous namespace
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
	namespace tools
	{
		//////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
		{
			if(rCandidate.count() > 1L)
			{
				solver aSolver(rCandidate);
				return aSolver.getB2DPolyPolygon();
			}
			else
			{
				return rCandidate;
			}
		}

		//////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate)
		{
			solver aSolver(rCandidate);
			return aSolver.getB2DPolyPolygon();
		}

		//////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
		{
			B2DPolyPolygon aRetval;

			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
			{
				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));

				if(ORIENTATION_NEUTRAL != tools::getOrientation(aCandidate))
				{
					aRetval.append(aCandidate);
				}
			}

			return aRetval;
		}

		//////////////////////////////////////////////////////////////////////////////

        B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon& rCandidate)
        {
            B2DPolyPolygon aCandidate;

            // remove all self-intersections and intersections
            if(rCandidate.count() == 1)
            {
                aCandidate = basegfx::tools::solveCrossovers(rCandidate.getB2DPolygon(0));
            }
            else
            {
                aCandidate = basegfx::tools::solveCrossovers(rCandidate);
            }

            // cleanup evtl. neutral polygons
            aCandidate = basegfx::tools::stripNeutralPolygons(aCandidate);

            // remove all polygons which have the same orientation as the polygon they are directly contained in
            const sal_uInt32 nCount(aCandidate.count());

            if(nCount > 1)
            {
                sal_uInt32 a, b;
                ::std::vector< StripHelper > aHelpers;
                aHelpers.resize(nCount);

                for(a = 0; a < nCount; a++)
                {
                    const B2DPolygon aCand(aCandidate.getB2DPolygon(a));
                    StripHelper* pNewHelper = &(aHelpers[a]);
                    pNewHelper->maRange = tools::getRange(aCand);
                    pNewHelper->meOrinetation = tools::getOrientation(aCand);

                    // initialize with own orientation
                    pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1 : 1);
                }

                for(a = 0; a < nCount - 1; a++)
                {
                    const B2DPolygon aCandA(aCandidate.getB2DPolygon(a));
                    StripHelper& rHelperA = aHelpers[a];

                    for(b = a + 1; b < nCount; b++)
                    {
                        const B2DPolygon aCandB(aCandidate.getB2DPolygon(b));
                        StripHelper& rHelperB = aHelpers[b];
                        const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));

                        if(bAInB)
                        {
                            // A is inside B, add orientation of B to A
                            rHelperA.mnDepth += (ORIENTATION_NEGATIVE == rHelperB.meOrinetation ? -1 : 1);
                        }

                        const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));

                        if(bBInA)
                        {
                            // B is inside A, add orientation of A to B
                            rHelperB.mnDepth += (ORIENTATION_NEGATIVE == rHelperA.meOrinetation ? -1 : 1);
                        }
                    }
                }

                const B2DPolyPolygon aSource(aCandidate);
                aCandidate.clear();

                for(a = 0L; a < nCount; a++)
                {
                    const StripHelper& rHelper = aHelpers[a];
                    // for contained unequal oriented polygons sum will be 0
                    // for contained equal it will be >=2 or <=-2
                    // for free polygons (not contained) it will be 1 or -1
                    // -> accept all which are >=-1 && <= 1
                    bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1);

                    if(bAcceptEntry)
                    {
                        aCandidate.append(aSource.getB2DPolygon(a));
                    }
                }
            }

            return aCandidate;
        }

        //////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
		{
			const sal_uInt32 nCount(rCandidate.count());
			B2DPolyPolygon aRetval;

			if(nCount)
			{
				if(nCount == 1L)
				{
					if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
					{
						aRetval = rCandidate;
					}
				}
				else
				{
					sal_uInt32 a, b;
					::std::vector< StripHelper > aHelpers;
					aHelpers.resize(nCount);

					for(a = 0L; a < nCount; a++)
					{
						const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
						StripHelper* pNewHelper = &(aHelpers[a]);
						pNewHelper->maRange = tools::getRange(aCandidate);
						pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
						pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L);
					}

					for(a = 0L; a < nCount - 1L; a++)
					{
						const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
						StripHelper& rHelperA = aHelpers[a];

						for(b = a + 1L; b < nCount; b++)
						{
							const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
							StripHelper& 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));

							if(bAInB && bBInA)
							{
								// congruent
								if(rHelperA.meOrinetation == rHelperB.meOrinetation)
								{
									// 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++;
								}
								else
								{
									// 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
							{
								if(bAInB)
								{
									if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation)
									{
										rHelperA.mnDepth--;
									}
									else
									{
										rHelperA.mnDepth++;
									}
								}
								else if(bBInA)
								{
									if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation)
									{
										rHelperB.mnDepth--;
									}
									else
									{
										rHelperB.mnDepth++;
									}
								}
							}
						}
					}

					for(a = 0L; a < nCount; a++)
					{
						const StripHelper& rHelper = aHelpers[a];
						bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);

						if(bAcceptEntry)
						{
							aRetval.append(rCandidate.getB2DPolygon(a));
						}
					}
				}
			}

			return aRetval;
		}

        //////////////////////////////////////////////////////////////////////////////

        B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
        {
			solver aSolver(rCandidate);
			B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));

            return correctOrientations(aRetval);
        }

        B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
        {
			solver aSolver(rCandidate);
			B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));

            return correctOrientations(aRetval);
        }

        B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
        {
            if(!rCandidateA.count())
            {
                return rCandidateB;
            }
            else if(!rCandidateB.count())
            {
                return rCandidateA;
            }
            else
            {
                // concatenate polygons, solve crossovers and throw away all sub-polygons
                // which have a depth other than 0.
                B2DPolyPolygon aRetval(rCandidateA);

                aRetval.append(rCandidateB);
			    aRetval = solveCrossovers(aRetval);
			    aRetval = stripNeutralPolygons(aRetval);

                return stripDispensablePolygons(aRetval, false);
            }
        }

        B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
        {
            if(!rCandidateA.count())
            {
                return rCandidateB;
            }
            else if(!rCandidateB.count())
            {
                return rCandidateA;
            }
            else
            {
                // XOR is pretty simple: By definition it is the simple concatenation of
                // the single polygons since we imply XOR fill rule. Make it intersection-free
                // and correct orientations
                B2DPolyPolygon aRetval(rCandidateA);

                aRetval.append(rCandidateB);
			    aRetval = solveCrossovers(aRetval);
			    aRetval = stripNeutralPolygons(aRetval);

                return correctOrientations(aRetval);
            }
        }

        B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
        {
            if(!rCandidateA.count())
            {
                return B2DPolyPolygon();
            }
            else if(!rCandidateB.count())
            {
                return B2DPolyPolygon();
            }
            else
            {
                // concatenate polygons, solve crossovers and throw away all sub-polygons
                // with a depth of < 1. This means to keep all polygons where at least two
                // polygons do overlap.
                B2DPolyPolygon aRetval(rCandidateA);

                aRetval.append(rCandidateB);
			    aRetval = solveCrossovers(aRetval);
			    aRetval = stripNeutralPolygons(aRetval);

                return stripDispensablePolygons(aRetval, true);
            }
        }

        B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
        {
            if(!rCandidateA.count())
            {
                return B2DPolyPolygon();
            }
            else if(!rCandidateB.count())
            {
                return rCandidateA;
            }
            else
            {
			    // Make B topologically to holes and append to A
                B2DPolyPolygon aRetval(rCandidateB);

                aRetval.flip();
                aRetval.append(rCandidateA);

                // solve crossovers and throw away all sub-polygons which have a
                // depth other than 0.
			    aRetval = basegfx::tools::solveCrossovers(aRetval);
			    aRetval = basegfx::tools::stripNeutralPolygons(aRetval);

                return basegfx::tools::stripDispensablePolygons(aRetval, false);
            }
        }

		B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector& rInput)
		{
			B2DPolyPolygonVector aInput(rInput);

			// first step: prepareForPolygonOperation and simple merge of non-overlapping
			// PolyPolygons for speedup; this is possible for the wanted OR-operation
			if(aInput.size())
			{
				B2DPolyPolygonVector aResult;
				aResult.reserve(aInput.size());

				for(sal_uInt32 a(0); a < aInput.size(); a++)
				{
					const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a]));

					if(aResult.size())
					{
				        const B2DRange aCandidateRange(aCandidate.getB2DRange());
						bool bCouldMergeSimple(false);

						for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++)
						{
							basegfx::B2DPolyPolygon aTarget(aResult[b]);
					        const B2DRange aTargetRange(aTarget.getB2DRange());

							if(!aCandidateRange.overlaps(aTargetRange))
							{
								aTarget.append(aCandidate);
								aResult[b] = aTarget;
								bCouldMergeSimple = true;
							}
						}

						if(!bCouldMergeSimple)
						{
							aResult.push_back(aCandidate);
						}
					}
					else
					{
						aResult.push_back(aCandidate);
					}
				}

				aInput = aResult;
			}

			// second step: melt pairwise to a single PolyPolygon
			while(aInput.size() > 1)
			{
				B2DPolyPolygonVector aResult;
				aResult.reserve((aInput.size() / 2) + 1);

				for(sal_uInt32 a(0); a < aInput.size(); a += 2)
				{
					if(a + 1 < aInput.size())
					{
						// a pair for processing
						aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
					}
					else
					{
						// last single PolyPolygon; copy to target to not lose it
						aResult.push_back(aInput[a]);
					}
				}

				aInput = aResult;
			}

			// third step: get result
			if(1 == aInput.size())
			{
				return aInput[0];
			}

			return B2DPolyPolygon();
		}

		//////////////////////////////////////////////////////////////////////////////

	} // end of namespace tools
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////
// eof