Added tooling for PolyPolygon cutting

1 files changed, 280 insertions, 0 deletions

diff --git a/basegfx/inc/basegfx/polygon/b2dpolypolygoncutter.hxx b/basegfx/inc/basegfx/polygon/b2dpolypolygoncutter.hxx
new file mode 100644
index 000000000000..578df5a36965
--- /dev/null
+++ b/basegfx/inc/basegfx/polygon/b2dpolypolygoncutter.hxx
@@ -0,0 +1,280 @@
+/*************************************************************************
+ *
+ *  $RCSfile: b2dpolypolygoncutter.hxx,v $
+ *
+ *  $Revision: 1.1 $
+ *
+ *  last change: $Author: aw $ $Date: 2003-11-06 16:28:48 $
+ *
+ *  The Contents of this file are made available subject to the terms of
+ *  either of the following licenses
+ *
+ *         - GNU Lesser General Public License Version 2.1
+ *         - Sun Industry Standards Source License Version 1.1
+ *
+ *  Sun Microsystems Inc., October, 2000
+ *
+ *  GNU Lesser General Public License Version 2.1
+ *  =============================================
+ *  Copyright 2000 by Sun Microsystems, Inc.
+ *  901 San Antonio Road, Palo Alto, CA 94303, USA
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License version 2.1, as published by the Free Software Foundation.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Lesser General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ *  MA  02111-1307  USA
+ *
+ *
+ *  Sun Industry Standards Source License Version 1.1
+ *  =================================================
+ *  The contents of this file are subject to the Sun Industry Standards
+ *  Source License Version 1.1 (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.openoffice.org/license.html.
+ *
+ *  Software provided under this License is provided on an "AS IS" basis,
+ *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
+ *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
+ *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
+ *  See the License for the specific provisions governing your rights and
+ *  obligations concerning the Software.
+ *
+ *  The Initial Developer of the Original Code is: Sun Microsystems, Inc.
+ *
+ *  Copyright: 2000 by Sun Microsystems, Inc.
+ *
+ *  All Rights Reserved.
+ *
+ *  Contributor(s): _______________________________________
+ *
+ *
+ ************************************************************************/
+
+#ifndef _BGFX_POLYGON_B2DPOLYPOLYGONCUTTER_HXX
+#define _BGFX_POLYGON_B2DPOLYPOLYGONCUTTER_HXX
+
+#ifndef _SAL_TYPES_H_
+#include <sal/types.h>
+#endif
+
+#ifndef _BGFX_POINT_B2DPOINT_HXX
+#include <basegfx/point/b2dpoint.hxx>
+#endif
+
+#ifndef _BGFX_VECTOR_B2DVECTOR_HXX
+#include <basegfx/vector/b2dvector.hxx>
+#endif
+
+#ifndef _BGFX_RANGE_B2DRANGE_HXX
+#include <basegfx/range/b2drange.hxx>
+#endif
+
+#ifndef _BGFX_POLYGON_B2DPOLYPOLYGON_HXX
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+#endif
+
+#include <vector>
+#include <algorithm>
+
+//////////////////////////////////////////////////////////////////////////////
+// B2DPolygonNode class
+//
+// This class is a pure tooling class used to hold a polygon in double linked
+// list form for faster manipulation. It is used from the polygon clipper.
+
+namespace basegfx
+{
+    namespace polygon
+    {
+        class B2DPolygonNode
+        {
+            ::basegfx::point::B2DPoint              maPosition;
+            B2DPolygonNode*                         mpPrevious;
+            B2DPolygonNode*                         mpNext;
+
+            B2DPolygonNode*                         mpListPrevious;
+            B2DPolygonNode*                         mpListNext;
+
+        public:
+            B2DPolygonNode(const ::basegfx::point::B2DPoint& rPosition, B2DPolygonNode* pPrevious);
+            ~B2DPolygonNode();
+
+            B2DPolygonNode* getPrevious() const { return mpPrevious; }
+            B2DPolygonNode* getNext() const { return mpNext; }
+            const ::basegfx::point::B2DPoint& getPosition() const { return maPosition; }
+
+            void calcMinMaxX(double& fMaxAX, double& fMinAX) const;
+            void calcMinMaxY(double& fMaxAY, double& fMinAY) const;
+
+            void swapPreviousNext() { B2DPolygonNode* pZwi = mpPrevious; mpPrevious = mpNext; mpNext = pZwi; }
+            void swapNextPointers(B2DPolygonNode* pCand);
+
+            void addToList(B2DPolygonNode*& rpList);
+            void remFromList(B2DPolygonNode*& rpList);
+
+            sal_Bool getOrientation() const;
+            void swapOrientation();
+            ::basegfx::range::B2DRange getRange() const;
+
+            sal_Bool isInside(const ::basegfx::point::B2DPoint& rPnt) const;
+            sal_Bool isPolygonInside(B2DPolygonNode* pPoly) const;
+        };
+
+        // a type definition to have a vector of pointers to B2DPolygonNodes
+        typedef ::std::vector< B2DPolygonNode* > B2DPolygonNodeVector;
+
+    } // end of namespace polygon
+} // end of namespace basegfx
+
+//////////////////////////////////////////////////////////////////////////////
+// B2DSimpleCut class
+
+namespace basegfx
+{
+    namespace polygon
+    {
+        class B2DSimpleCut
+        {
+            B2DPolygonNode*                         mpLeft;
+            B2DPolygonNode*                         mpRight;
+
+            // bitfield
+            unsigned                                mbCorrectOrientation : 1;
+            unsigned                                mbOrientation : 1;
+
+        public:
+            B2DSimpleCut(B2DPolygonNode* pL, B2DPolygonNode* pR, sal_Bool bCoOr = sal_False, sal_Bool bOr = sal_True)
+            :   mpLeft(pL),
+                mpRight(pR),
+                mbCorrectOrientation(bCoOr),
+                mbOrientation(bOr)
+            {
+            }
+
+            void solve();
+            B2DPolygonNode* getLeft() const { return mpLeft; }
+            B2DPolygonNode* getRight() const { return mpRight; }
+
+            sal_Bool isSameCut(B2DPolygonNode* pA, B2DPolygonNode* pB) const
+            {
+                return ((pA == mpLeft && pB == mpRight) || (pB == mpLeft && pA == mpRight));
+            }
+        };
+
+        // a type definition to have a vector of pointers to B2DSimpleCuts
+        typedef ::std::vector< B2DSimpleCut* > B2DSimpleCutVector;
+
+    } // end of namespace polygon
+} // end of namespace basegfx
+
+//////////////////////////////////////////////////////////////////////////////
+// B2DClipExtraPolygonInfo class
+
+namespace basegfx
+{
+    namespace polygon
+    {
+        class B2DClipExtraPolygonInfo
+        {
+            ::basegfx::range::B2DRange              maRange;
+            sal_Int32                               mnDepth;
+
+            // bitfield
+            unsigned                                mbOrientation : 1;
+
+        public:
+            B2DClipExtraPolygonInfo() {}
+
+            void init(B2DPolygonNode* pNew);
+            const ::basegfx::range::B2DRange& getRange() const { return maRange; }
+            sal_Bool getOrientation() const { return mbOrientation; }
+
+            sal_Int32 getDepth() const { return mnDepth; }
+            void changeDepth(sal_Bool bOrientation);
+        };
+    } // end of namespace polygon
+} // end of namespace basegfx
+
+//////////////////////////////////////////////////////////////////////////////
+// class B2DPolyPolygonCutter
+
+namespace basegfx
+{
+    namespace polygon
+    {
+        class B2DPolyPolygonCutter
+        {
+            // list of polys
+            B2DPolygonNodeVector                    maPolygonList;
+            B2DPolyPolygon                          maNotClosedPolygons;
+
+            // help routines
+            sal_Bool isSamePos(const ::basegfx::point::B2DPoint& rPntA, const ::basegfx::point::B2DPoint& rPntB)
+            {
+                return rPntA.equal(rPntB);
+            }
+
+            B2DSimpleCut* getExistingCut(B2DSimpleCutVector& rTmpCuts, B2DPolygonNode* pA, B2DPolygonNode* pB);
+            B2DPolygonNode* extractNextPolygon(B2DPolygonNode*& rpList);
+            sal_Bool isCrossover(B2DPolygonNode* pA, B2DPolygonNode* pB);
+            sal_Bool isCrossover(B2DSimpleCut* pEnter, B2DSimpleCut* pLeave);
+
+            sal_Bool isNextSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
+            {
+                return isSamePos(pA->getNext()->getPosition(), pB->getNext()->getPosition());
+            }
+
+            sal_Bool isPrevSamePos(B2DPolygonNode* pA, B2DPolygonNode* pB)
+            {
+                return isSamePos(pA->getPrevious()->getPosition(), pB->getPrevious()->getPosition());
+            }
+
+            void addAllNodes(B2DPolygonNode* pPolygon, B2DPolygonNode*& rpList);
+            B2DPolygonNode* createNewPolygon(const B2DPolygon& rPolygon);
+            void deletePolygon(B2DPolygonNode* pCand);
+            void polysToList(B2DPolygonNode*& rpList);
+            void listToPolys(B2DPolygonNode*& rpList);
+
+            sal_Bool doRangesIntersect(const ::basegfx::range::B2DRange& rRange1, const ::basegfx::range::B2DRange& rRange2) const
+            {
+                return rRange1.overlaps(rRange2);
+            }
+
+            sal_Bool doRangesInclude(const ::basegfx::range::B2DRange& rRange1, const ::basegfx::range::B2DRange& rRange2) const
+            {
+                return rRange1.isInside(rRange2);
+            }
+
+            void solveAllCuts(B2DSimpleCutVector& rCuts);
+
+        public:
+            B2DPolyPolygonCutter() {}
+            ~B2DPolyPolygonCutter();
+
+            // put/get poly
+            void addPolyPolygon(const B2DPolyPolygon& rPolyPolygon, sal_Bool bForceOrientation = sal_False);
+            void getPolyPolygon(B2DPolyPolygon& rPolyPolygon);
+
+            // transformations
+            void removeSelfIntersections();
+            void removeDoubleIntersections();
+
+            // remove included
+            void removeIncludedPolygons(sal_Bool bUseOr = sal_True);
+        };
+    } // end of namespace polygon
+} // end of namespace basegfx
+
+//////////////////////////////////////////////////////////////////////////////
+
+
+#endif //   _BGFX_POLYGON_B2DPOLYPOLYGONCUTTER_HXX