#i105939# Adds special box clipping support to basegfx

6 files changed, 1436 insertions, 308 deletions

diff --git a/basegfx/source/polygon/b2dpolygon.cxx b/basegfx/source/polygon/b2dpolygon.cxx
index 467a4b90f516..ccf45d31cbbc 100644
--- a/basegfx/source/polygon/b2dpolygon.cxx
+++ b/basegfx/source/polygon/b2dpolygon.cxx
@@ -44,38 +44,24 @@
 
 //////////////////////////////////////////////////////////////////////////////
 
-class CoordinateData2D
+struct CoordinateData2D : public basegfx::B2DPoint
 {
-    basegfx::B2DPoint                               maPoint;
-
 public:
-    CoordinateData2D()
-    :   maPoint()
-    {}
+    CoordinateData2D() {}
 
     explicit CoordinateData2D(const basegfx::B2DPoint& rData)
-    :   maPoint(rData)
+    :   B2DPoint(rData)
     {}
 
-    const basegfx::B2DPoint& getCoordinate() const
-    {
-        return maPoint;
-    }
-
-    void setCoordinate(const basegfx::B2DPoint& rValue)
-    {
-        if(rValue != maPoint)
-            maPoint = rValue;
-    }
-
-    bool operator==(const CoordinateData2D& rData ) const
+    CoordinateData2D& operator=(const basegfx::B2DPoint& rData)
     {
-        return (maPoint == rData.getCoordinate());
+        B2DPoint::operator=(rData);
+        return *this;
     }
 
     void transform(const basegfx::B2DHomMatrix& rMatrix)
     {
-        maPoint *= rMatrix;
+        *this *= rMatrix;
     }
 };
 
@@ -115,12 +101,12 @@ public:
 
     const basegfx::B2DPoint& getCoordinate(sal_uInt32 nIndex) const
     {
-        return maVector[nIndex].getCoordinate();
+        return maVector[nIndex];
     }
 
     void setCoordinate(sal_uInt32 nIndex, const basegfx::B2DPoint& rValue)
     {
-        maVector[nIndex].setCoordinate(rValue);
+        maVector[nIndex] = rValue;
     }
 
     void insert(sal_uInt32 nIndex, const CoordinateData2D& rValue, sal_uInt32 nCount)
@@ -221,6 +207,26 @@ public:
             aStart->transform(rMatrix);
         }
     }
+
+    const basegfx::B2DPoint* begin() const
+    {
+        return &maVector.front();
+    }
+
+    const basegfx::B2DPoint* end() const
+    {
+        return &maVector[maVector.size()];
+    }
+
+    basegfx::B2DPoint* begin()
+    {
+        return &maVector.front();
+    }
+
+    basegfx::B2DPoint* end()
+    {
+        return &maVector[maVector.size()];
+    }
 };
 
 //////////////////////////////////////////////////////////////////////////////
@@ -1113,6 +1119,28 @@ public:
             maPoints.transform(rMatrix);
         }
     }
+
+    const basegfx::B2DPoint* begin() const
+    {
+        return maPoints.begin();
+    }
+
+    const basegfx::B2DPoint* end() const
+    {
+        return maPoints.end();
+    }
+
+    basegfx::B2DPoint* begin()
+    {
+       mpBufferedData.reset();
+       return maPoints.begin();
+    }
+
+    basegfx::B2DPoint* end()
+    {
+        mpBufferedData.reset();
+        return maPoints.end();
+    }
 };
 
 //////////////////////////////////////////////////////////////////////////////
@@ -1173,7 +1201,7 @@ namespace basegfx
         return mpPolygon->count();
     }
 
-    B2DPoint B2DPolygon::getB2DPoint(sal_uInt32 nIndex) const
+    const B2DPoint& B2DPolygon::getB2DPoint(sal_uInt32 nIndex) const
     {
         OSL_ENSURE(nIndex < mpPolygon->count(), "B2DPolygon access outside range (!)");
 
@@ -1432,7 +1460,7 @@ namespace basegfx
         return mpPolygon->getDefaultAdaptiveSubdivision(*this);
     }
 
-    B2DRange B2DPolygon::getB2DRange() const
+    const B2DRange& B2DPolygon::getB2DRange() const
     {
         return mpPolygon->getB2DRange(*this);
     }
@@ -1540,6 +1568,26 @@ namespace basegfx
             mpPolygon->transform(rMatrix);
         }
     }
+
+    const B2DPoint* B2DPolygon::begin() const
+    {
+        return mpPolygon->begin();
+    }
+
+    const B2DPoint* B2DPolygon::end() const
+    {
+        return mpPolygon->end();
+    }
+
+    B2DPoint* B2DPolygon::begin()
+    {
+        return mpPolygon->begin();
+    }
+
+    B2DPoint* B2DPolygon::end()
+    {
+        return mpPolygon->end();
+    }
 } // end of namespace basegfx
 
 //////////////////////////////////////////////////////////////////////////////
diff --git a/basegfx/source/polygon/b2dpolypolygon.cxx b/basegfx/source/polygon/b2dpolypolygon.cxx
index 6467e7120c03..af63bbccf8d4 100644
--- a/basegfx/source/polygon/b2dpolypolygon.cxx
+++ b/basegfx/source/polygon/b2dpolypolygon.cxx
@@ -166,6 +166,26 @@ public:
                        maPolygons.end(),
                        std::mem_fun_ref( &basegfx::B2DPolygon::makeUnique ));
     }
+
+    const basegfx::B2DPolygon* begin() const
+    {
+        return &maPolygons.front();
+    }
+
+    const basegfx::B2DPolygon* end() const
+    {
+        return &maPolygons[maPolygons.size()];
+    }
+
+    basegfx::B2DPolygon* begin()
+    {
+        return &maPolygons.front();
+    }
+
+    basegfx::B2DPolygon* end()
+    {
+        return &maPolygons[maPolygons.size()];
+    }
 };
 
 //////////////////////////////////////////////////////////////////////////////
@@ -378,6 +398,26 @@ namespace basegfx
             mpPolyPolygon->transform(rMatrix);
         }
     }
+
+    const B2DPolygon* B2DPolyPolygon::begin() const
+    {
+        return mpPolyPolygon->begin();
+    }
+
+    const B2DPolygon* B2DPolyPolygon::end() const
+    {
+        return mpPolyPolygon->end();
+    }
+
+    B2DPolygon* B2DPolyPolygon::begin()
+    {
+        return mpPolyPolygon->begin();
+    }
+
+    B2DPolygon* B2DPolyPolygon::end()
+    {
+        return mpPolyPolygon->end();
+    }
 } // end of namespace basegfx
 
 // eof
diff --git a/basegfx/source/range/b2dmultirange.cxx b/basegfx/source/range/b2dmultirange.cxx
deleted file mode 100644
index 64c3cf5ab813..000000000000
--- a/basegfx/source/range/b2dmultirange.cxx
+++ /dev/null
@@ -1,282 +0,0 @@
-/*************************************************************************
- *
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * Copyright 2008 by Sun Microsystems, Inc.
- *
- * OpenOffice.org - a multi-platform office productivity suite
- *
- * $RCSfile: b2dmultirange.cxx,v $
- * $Revision: 1.8 $
- *
- * This file is part of OpenOffice.org.
- *
- * OpenOffice.org is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Lesser General Public License version 3
- * only, as published by the Free Software Foundation.
- *
- * OpenOffice.org 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 version 3 for more details
- * (a copy is included in the LICENSE file that accompanied this code).
- *
- * You should have received a copy of the GNU Lesser General Public License
- * version 3 along with OpenOffice.org.  If not, see
- * <http://www.openoffice.org/license.html>
- * for a copy of the LGPLv3 License.
- *
- ************************************************************************/
-
-// MARKER(update_precomp.py): autogen include statement, do not remove
-#include "precompiled_basegfx.hxx"
-#include <basegfx/range/b2drange.hxx>
-#include <basegfx/tuple/b2dtuple.hxx>
-#include <basegfx/polygon/b2dpolypolygon.hxx>
-#include <basegfx/range/b2dmultirange.hxx>
-#include <basegfx/polygon/b2dpolygontools.hxx>
-#include <basegfx/polygon/b2dpolypolygontools.hxx>
-#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
-#include <boost/bind.hpp>
-#include <boost/mem_fn.hpp>
-#include <algorithm>
-#include <vector>
-
-
-namespace basegfx
-{
-    class ImplB2DMultiRange
-    {
-    public:
-        ImplB2DMultiRange() :
-            maBounds(),
-            maRanges()
-        {
-        }
-
-        explicit ImplB2DMultiRange( const B2DRange& rRange ) :
-            maBounds(),
-            maRanges( 1, rRange )
-        {
-        }
-
-        bool isEmpty() const
-        {
-            // no ranges at all, or all ranges empty
-            return maRanges.empty() ||
-                ::std::count_if( maRanges.begin(),
-                                 maRanges.end(),
-                                 ::boost::mem_fn( &B2DRange::isEmpty ) )
-                == static_cast<VectorOfRanges::difference_type>(maRanges.size());
-        }
-
-        void reset()
-        {
-            // swap in empty vector
-            VectorOfRanges aTmp;
-            maRanges.swap( aTmp );
-
-            maBounds.reset();
-        }
-
-        template< typename ValueType > bool isInside( const ValueType& rValue ) const
-        {
-            if( !maBounds.isInside( rValue ) )
-                return false;
-
-            // cannot use ::boost::bind here, since isInside is overloaded.
-            // It is currently not possible to resolve the overload
-            // by considering one of the other template arguments.
-            VectorOfRanges::const_iterator       aCurr( maRanges.begin() );
-            const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
-            while( aCurr != aEnd )
-                if( aCurr->isInside( rValue ) )
-                    return true;
-
-            return false;
-        }
-
-        bool overlaps( const B2DRange& rRange ) const
-        {
-            if( !maBounds.overlaps( rRange ) )
-                return false;
-
-            const VectorOfRanges::const_iterator aEnd( maRanges.end() );
-            return ::std::find_if( maRanges.begin(),
-                                   aEnd,
-                                   ::boost::bind<bool>( ::boost::mem_fn( &B2DRange::overlaps ),
-                                                        _1,
-                                                        rRange ) ) != aEnd;
-        }
-
-        void addRange( const B2DRange& rRange )
-        {
-            maRanges.push_back( rRange );
-            maBounds.expand( rRange );
-        }
-
-        B2DRange getBounds() const
-        {
-            return maBounds;
-        }
-
-        B2DPolyPolygon getPolyPolygon() const
-        {
-            B2DPolyPolygon aRes;
-
-            // Make range vector unique ( have to avoid duplicate
-            // rectangles. The polygon clipper will return an empty
-            // result in this case).
-            VectorOfRanges  aUniqueRanges;
-            aUniqueRanges.reserve( maRanges.size() );
-
-            VectorOfRanges::const_iterator       aCurr( maRanges.begin() );
-            const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
-            while( aCurr != aEnd )
-            {
-                // TODO(F3): It's plain wasted resources to apply a
-                // general clipping algorithm to the problem at
-                // hand. Go for a dedicated, scan-line-based approach.
-                VectorOfRanges::const_iterator aCurrScan( aCurr+1 );
-                VectorOfRanges::const_iterator aFound( aEnd );
-                while( aCurrScan != aEnd )
-                {
-                    if( aCurrScan->equal( *aCurr ) ||
-                        aCurrScan->isInside( *aCurr ) )
-                    {
-                        // current probe is equal to aCurr, or
-                        // completely contains aCurr. Thus, stop
-                        // searching, because aCurr is definitely not
-                        // a member of the unique rect list
-                        aFound = aCurrScan;
-                        break;
-                    }
-
-                    ++aCurrScan;
-                }
-
-                if( aFound == aEnd )
-                {
-                    // check whether aCurr is fully contained in one
-                    // of the already added rects. If yes, we can skip
-                    // it.
-                    bool bUnique( true );
-                    VectorOfRanges::const_iterator aCurrUnique( aUniqueRanges.begin() );
-                    VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
-                    while( aCurrUnique != aEndUnique )
-                    {
-                        if( aCurrUnique->isInside( *aCurr ) )
-                        {
-                            // fully contained, no need to add
-                            bUnique = false;
-                            break;
-                        }
-
-                        ++aCurrUnique;
-                    }
-
-                    if( bUnique )
-                        aUniqueRanges.push_back( *aCurr );
-                }
-
-                ++aCurr;
-            }
-
-            VectorOfRanges::const_iterator       aCurrUnique( aUniqueRanges.begin() );
-            const VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
-            while( aCurrUnique != aEndUnique )
-            {
-                // simply merge all unique parts (OR)
-                aRes.append( tools::createPolygonFromRect( *aCurrUnique++ ) );
-            }
-
-            // remove redundant intersections. Note: since all added
-            // rectangles are positively oriented, this method cannot
-            // generate any holes.
-            aRes = basegfx::tools::solveCrossovers(aRes);
-            aRes = basegfx::tools::stripNeutralPolygons(aRes);
-            aRes = basegfx::tools::stripDispensablePolygons(aRes, false);
-
-            return aRes;
-        }
-
-    private:
-        typedef ::std::vector< B2DRange >   VectorOfRanges;
-
-        B2DRange        maBounds;
-        VectorOfRanges  maRanges;
-    };
-
-
-    // ====================================================================
-
-
-    B2DMultiRange::B2DMultiRange() :
-        mpImpl()
-    {
-    }
-
-    B2DMultiRange::B2DMultiRange( const B2DRange& rRange ) :
-        mpImpl( ImplB2DMultiRange( rRange ) )
-    {
-    }
-
-    B2DMultiRange::~B2DMultiRange()
-    {
-        // otherwise, ImplB2DMultiRange would be an incomplete type
-    }
-
-    B2DMultiRange::B2DMultiRange( const B2DMultiRange& rSrc ) :
-        mpImpl( rSrc.mpImpl )
-    {
-    }
-
-    B2DMultiRange& B2DMultiRange::operator=( const B2DMultiRange& rSrc )
-    {
-        mpImpl = rSrc.mpImpl;
-        return *this;
-    }
-
-    bool B2DMultiRange::isEmpty() const
-    {
-        return mpImpl->isEmpty();
-    }
-
-    void B2DMultiRange::reset()
-    {
-        mpImpl->reset();
-    }
-
-    bool B2DMultiRange::isInside( const B2DTuple& rTuple ) const
-    {
-        return mpImpl->isInside( rTuple );
-    }
-
-    bool B2DMultiRange::isInside( const B2DRange& rRange ) const
-    {
-        return mpImpl->isInside( rRange );
-    }
-
-    bool B2DMultiRange::overlaps( const B2DRange& rRange ) const
-    {
-        return mpImpl->overlaps( rRange );
-    }
-
-    void B2DMultiRange::addRange( const B2DRange& rRange )
-    {
-        mpImpl->addRange( rRange );
-    }
-
-    B2DRange B2DMultiRange::getBounds() const
-    {
-        return mpImpl->getBounds();
-    }
-
-    B2DPolyPolygon B2DMultiRange::getPolyPolygon() const
-    {
-        return mpImpl->getPolyPolygon();
-    }
-
-} // end of namespace basegfx
-
-// eof
diff --git a/basegfx/source/range/b2dpolyrange.cxx b/basegfx/source/range/b2dpolyrange.cxx
new file mode 100644
index 000000000000..c4969b38712c
--- /dev/null
+++ b/basegfx/source/range/b2dpolyrange.cxx
@@ -0,0 +1,371 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: b2dmultirange.cxx,v $
+ * $Revision: 1.8 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_basegfx.hxx"
+#include <basegfx/range/b2dpolyrange.hxx>
+
+#include <basegfx/range/b2drange.hxx>
+#include <basegfx/range/b2drangeclipper.hxx>
+#include <basegfx/tuple/b2dtuple.hxx>
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+
+#include <boost/bind.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <algorithm>
+#include <vector>
+
+static basegfx::B2VectorOrientation flipOrientation(
+    basegfx::B2VectorOrientation eOrient)
+{
+    return eOrient == basegfx::ORIENTATION_POSITIVE ?
+        basegfx::ORIENTATION_NEGATIVE : basegfx::ORIENTATION_POSITIVE;
+}
+
+namespace basegfx
+{
+    class ImplB2DPolyRange
+    {
+        void updateBounds()
+        {
+            maBounds.reset();
+            std::for_each(maRanges.begin(),
+                          maRanges.end(),
+                          boost::bind(
+                              (void (B2DRange::*)(const B2DRange&))(
+                 &B2DRange::expand),
+                              boost::ref(maBounds),
+                              _1));
+        }
+
+    public:
+        ImplB2DPolyRange() :
+            maBounds(),
+            maRanges(),
+            maOrient()
+        {}
+
+        explicit ImplB2DPolyRange( const B2DPolyRange::ElementType& rElem ) :
+            maBounds( boost::get<0>(rElem) ),
+            maRanges( 1, boost::get<0>(rElem) ),
+            maOrient( 1, boost::get<1>(rElem) )
+        {}
+
+        explicit ImplB2DPolyRange( const B2DRange& rRange, B2VectorOrientation eOrient ) :
+            maBounds( rRange ),
+            maRanges( 1, rRange ),
+            maOrient( 1, eOrient )
+        {}
+
+        bool operator==(const ImplB2DPolyRange& rRHS) const
+        {
+            return maRanges == rRHS.maRanges && maOrient == rRHS.maOrient;
+        }
+
+        sal_uInt32 count() const
+        {
+            return maRanges.size();
+        }
+
+        B2DPolyRange::ElementType getElement(sal_uInt32 nIndex) const
+        {
+            return boost::make_tuple(maRanges[nIndex],
+                                     maOrient[nIndex]);
+        }
+
+        void setElement(sal_uInt32 nIndex, const B2DPolyRange::ElementType& rElement )
+        {
+            maRanges[nIndex] = boost::get<0>(rElement);
+            maOrient[nIndex] = boost::get<1>(rElement);
+            updateBounds();
+        }
+
+        void setElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient )
+        {
+            maRanges[nIndex] = rRange;
+            maOrient[nIndex] = eOrient;
+            updateBounds();
+        }
+
+        void insertElement(sal_uInt32 nIndex, const B2DPolyRange::ElementType& rElement, sal_uInt32 nCount)
+        {
+            maRanges.insert(maRanges.begin()+nIndex, nCount, boost::get<0>(rElement));
+            maOrient.insert(maOrient.begin()+nIndex, nCount, boost::get<1>(rElement));
+            maBounds.expand(boost::get<0>(rElement));
+        }
+
+        void insertElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+        {
+            maRanges.insert(maRanges.begin()+nIndex, nCount, rRange);
+            maOrient.insert(maOrient.begin()+nIndex, nCount, eOrient);
+            maBounds.expand(rRange);
+        }
+
+        void appendElement(const B2DPolyRange::ElementType& rElement, sal_uInt32 nCount)
+        {
+            maRanges.insert(maRanges.end(), nCount, boost::get<0>(rElement));
+            maOrient.insert(maOrient.end(), nCount, boost::get<1>(rElement));
+            maBounds.expand(boost::get<0>(rElement));
+        }
+
+        void appendElement(const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+        {
+            maRanges.insert(maRanges.end(), nCount, rRange);
+            maOrient.insert(maOrient.end(), nCount, eOrient);
+            maBounds.expand(rRange);
+        }
+
+        void insertPolyRange(sal_uInt32 nIndex, const ImplB2DPolyRange& rPolyRange)
+        {
+            maRanges.insert(maRanges.begin()+nIndex, rPolyRange.maRanges.begin(), rPolyRange.maRanges.end());
+            maOrient.insert(maOrient.begin()+nIndex, rPolyRange.maOrient.begin(), rPolyRange.maOrient.end());
+            updateBounds();
+        }
+
+        void appendPolyRange(const ImplB2DPolyRange& rPolyRange)
+        {
+            maRanges.insert(maRanges.end(),
+                            rPolyRange.maRanges.begin(),
+                            rPolyRange.maRanges.end());
+            maOrient.insert(maOrient.end(),
+                            rPolyRange.maOrient.begin(),
+                            rPolyRange.maOrient.end());
+            updateBounds();
+        }
+
+        void remove(sal_uInt32 nIndex, sal_uInt32 nCount)
+        {
+            maRanges.erase(maRanges.begin()+nIndex,maRanges.begin()+nIndex+nCount);
+            maOrient.erase(maOrient.begin()+nIndex,maOrient.begin()+nIndex+nCount);
+            updateBounds();
+        }
+
+        void clear()
+        {
+            std::vector<B2DRange> aTmpRanges;
+            std::vector<B2VectorOrientation> aTmpOrient;
+
+            maRanges.swap(aTmpRanges);
+            maOrient.swap(aTmpOrient);
+
+            maBounds.reset();
+        }
+
+        void flip()
+        {
+            std::for_each(maOrient.begin(),
+                          maOrient.end(),
+                          boost::bind(
+                              &flipOrientation,
+                              _1));
+        }
+
+        B2DRange getBounds() const
+        {
+            return maBounds;
+        }
+
+        template< typename ValueType > bool isInside( const ValueType& rValue ) const
+        {
+            if( !maBounds.isInside( rValue ) )
+                return false;
+
+            // cannot use boost::bind here, since isInside is overloaded.
+            // It is currently not possible to resolve the overload
+            // by considering one of the other template arguments.
+            std::vector<B2DRange>::const_iterator       aCurr( maRanges.begin() );
+            const std::vector<B2DRange>::const_iterator aEnd ( maRanges.end() );
+            while( aCurr != aEnd )
+                if( aCurr->isInside( rValue ) )
+                    return true;
+
+            return false;
+        }
+
+        bool overlaps( const B2DRange& rRange ) const
+        {
+            if( !maBounds.overlaps( rRange ) )
+                return false;
+
+            const std::vector<B2DRange>::const_iterator aEnd( maRanges.end() );
+            return std::find_if( maRanges.begin(),
+                                 aEnd,
+                                 boost::bind<bool>( boost::mem_fn( &B2DRange::overlaps ),
+                                                    _1,
+                                                    boost::cref(rRange) ) ) != aEnd;
+        }
+
+        B2DPolyPolygon solveCrossovers() const
+        {
+            return tools::solveCrossovers(maRanges,maOrient);
+        }
+
+    private:
+        B2DRange                         maBounds;
+        std::vector<B2DRange>            maRanges;
+        std::vector<B2VectorOrientation> maOrient;
+    };
+
+    B2DPolyRange::B2DPolyRange() :
+        mpImpl()
+    {}
+
+    B2DPolyRange::~B2DPolyRange()
+    {}
+
+    B2DPolyRange::B2DPolyRange( const ElementType& rElem ) :
+        mpImpl( ImplB2DPolyRange( rElem ) )
+    {}
+
+    B2DPolyRange::B2DPolyRange( const B2DRange& rRange, B2VectorOrientation eOrient ) :
+        mpImpl( ImplB2DPolyRange( rRange, eOrient ) )
+    {}
+
+    B2DPolyRange::B2DPolyRange( const B2DPolyRange& rRange ) :
+        mpImpl( rRange.mpImpl )
+    {}
+
+    B2DPolyRange& B2DPolyRange::operator=( const B2DPolyRange& rRange )
+    {
+        mpImpl = rRange.mpImpl;
+        return *this;
+    }
+
+    void B2DPolyRange::makeUnique()
+    {
+        mpImpl.make_unique();
+    }
+
+    bool B2DPolyRange::operator==(const B2DPolyRange& rRange) const
+    {
+        if(mpImpl.same_object(rRange.mpImpl))
+            return true;
+
+        return ((*mpImpl) == (*rRange.mpImpl));
+    }
+
+    bool B2DPolyRange::operator!=(const B2DPolyRange& rRange) const
+    {
+        return !(*this == rRange);
+    }
+
+    sal_uInt32 B2DPolyRange::count() const
+    {
+        return mpImpl->count();
+    }
+
+    B2DPolyRange::ElementType B2DPolyRange::getElement(sal_uInt32 nIndex) const
+    {
+        return mpImpl->getElement(nIndex);
+    }
+
+    void B2DPolyRange::setElement(sal_uInt32 nIndex, const ElementType& rElement )
+    {
+        mpImpl->setElement(nIndex, rElement);
+    }
+
+    void B2DPolyRange::setElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient )
+    {
+        mpImpl->setElement(nIndex, rRange, eOrient );
+    }
+
+    void B2DPolyRange::insertElement(sal_uInt32 nIndex, const ElementType& rElement, sal_uInt32 nCount)
+    {
+        mpImpl->insertElement(nIndex, rElement, nCount );
+    }
+
+    void B2DPolyRange::insertElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+    {
+        mpImpl->insertElement(nIndex, rRange, eOrient, nCount );
+    }
+
+    void B2DPolyRange::appendElement(const ElementType& rElement, sal_uInt32 nCount)
+    {
+        mpImpl->appendElement(rElement, nCount);
+    }
+
+    void B2DPolyRange::appendElement(const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+    {
+        mpImpl->appendElement(rRange, eOrient, nCount );
+    }
+
+    void B2DPolyRange::insertPolyRange(sal_uInt32 nIndex, const B2DPolyRange& rRange)
+    {
+        mpImpl->insertPolyRange(nIndex, *rRange.mpImpl);
+    }
+
+    void B2DPolyRange::appendPolyRange(const B2DPolyRange& rRange)
+    {
+        mpImpl->appendPolyRange(*rRange.mpImpl);
+    }
+
+    void B2DPolyRange::remove(sal_uInt32 nIndex, sal_uInt32 nCount)
+    {
+        mpImpl->remove(nIndex, nCount);
+    }
+
+    void B2DPolyRange::clear()
+    {
+        mpImpl->clear();
+    }
+
+    void B2DPolyRange::flip()
+    {
+        mpImpl->flip();
+    }
+
+    B2DRange B2DPolyRange::getBounds() const
+    {
+        return mpImpl->getBounds();
+    }
+
+    bool B2DPolyRange::isInside( const B2DTuple& rTuple ) const
+    {
+        return mpImpl->isInside(rTuple);
+    }
+
+    bool B2DPolyRange::isInside( const B2DRange& rRange ) const
+    {
+        return mpImpl->isInside(rRange);
+    }
+
+    bool B2DPolyRange::overlaps( const B2DRange& rRange ) const
+    {
+        return mpImpl->overlaps(rRange);
+    }
+
+    B2DPolyPolygon B2DPolyRange::solveCrossovers() const
+    {
+        return mpImpl->solveCrossovers();
+    }
+
+} // end of namespace basegfx
+
+// eof
diff --git a/basegfx/source/range/b2drangeclipper.cxx b/basegfx/source/range/b2drangeclipper.cxx
new file mode 100644
index 000000000000..524479b4fde0
--- /dev/null
+++ b/basegfx/source/range/b2drangeclipper.cxx
@@ -0,0 +1,950 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: b2dmultirange.cxx,v $
+ * $Revision: 1.8 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org 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 version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_basegfx.hxx"
+
+#include <rtl/math.hxx>
+
+#include <basegfx/tuple/b2dtuple.hxx>
+#include <basegfx/range/b2drange.hxx>
+#include <basegfx/range/b2dpolyrange.hxx>
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+#include <basegfx/polygon/b2dpolygontools.hxx>
+#include <basegfx/polygon/b2dpolypolygontools.hxx>
+
+#include <o3tl/vector_pool.hxx>
+#include <boost/bind.hpp>
+#include <boost/utility.hpp>
+
+#include <algorithm>
+#include <deque>
+#include <list>
+
+
+namespace basegfx
+{
+    namespace
+    {
+        // Generating a poly-polygon from a bunch of rectangles
+        //
+        // Helper functionality for sweep-line algorithm
+        // ====================================================
+
+        typedef std::vector<B2DRange> VectorOfRanges;
+
+        class ImplPolygon;
+        typedef o3tl::vector_pool<ImplPolygon> VectorOfPolygons;
+
+
+        /** This class represents an active edge
+
+            As the sweep line traverses across the overall area,
+            rectangle edges parallel to it generate events, and
+            rectangle edges orthogonal to it generate active
+            edges. This class represents the latter.
+         */
+        class ActiveEdge
+        {
+        public:
+            /** The two possible active rectangle edges differ by one
+                coordinate value - the upper edge has the lower, the
+                lower edge the higher value.
+             */
+            enum EdgeType {
+                /// edge with lower coordinate value
+                UPPER=0,
+                /// edge with higher coordinate value
+                LOWER=1
+            };
+
+            enum EdgeDirection {
+                /// edge proceeds to the left
+                PROCEED_LEFT=0,
+                /// edge proceeds to the right
+                PROCEED_RIGHT=1
+            };
+
+            /** Create active edge
+
+                @param rRect
+                Rectangle this edge is part of
+
+                @param fInvariantCoord
+                The invariant ccordinate value of this edge
+
+                @param eEdgeType
+                Is fInvariantCoord the lower or the higher value, for
+                this rect?
+             */
+            ActiveEdge( const B2DRectangle& rRect,
+                        const double&       fInvariantCoord,
+                        std::ptrdiff_t      nPolyIdx,
+                        EdgeType            eEdgeType,
+                        EdgeDirection       eEdgeDirection ) :
+                mfInvariantCoord(fInvariantCoord),
+                mpAssociatedRect( &rRect ),
+                mnPolygonIdx( nPolyIdx ),
+                meEdgeType( eEdgeType ),
+                meEdgeDirection( eEdgeDirection )
+            {}
+
+            double              getInvariantCoord() const { return mfInvariantCoord; }
+            const B2DRectangle& getRect() const { return *mpAssociatedRect; }
+            std::ptrdiff_t      getTargetPolygonIndex() const { return mnPolygonIdx; }
+            void                setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; }
+            EdgeType            getEdgeType() const { return meEdgeType; }
+            EdgeDirection       getEdgeDirection() const { return meEdgeDirection; }
+
+            /// For STL sort
+            bool operator<( const ActiveEdge& rRHS ) const { return mfInvariantCoord < rRHS.mfInvariantCoord; }
+
+        private:
+            /** The invariant coordinate value of this edge (e.g. the
+                common y value, for a horizontal edge)
+             */
+            double              mfInvariantCoord;
+
+            /** Associated rectangle
+
+                This on the one hand saves some storage space (the
+                vector of rectangles is persistent, anyway), and on
+                the other hand provides an identifier to match active
+                edges and x events (see below)
+
+                Ptr because class needs to be assignable
+             */
+            const B2DRectangle* mpAssociatedRect;
+
+            /** Index of the polygon this edge is currently involved
+                with.
+
+                Note that this can change for some kinds of edge
+                intersection, as the algorithm tends to swap
+                associated polygons there.
+
+                -1 denotes no assigned polygon
+             */
+            std::ptrdiff_t      mnPolygonIdx;
+
+            /// 'upper' or 'lower' edge of original rectangle.
+            EdgeType            meEdgeType;
+
+            /// 'left' or 'right'
+            EdgeDirection       meEdgeDirection;
+        };
+
+        // Needs to be list - various places hold ptrs to elements
+        typedef std::list< ActiveEdge > ListOfEdges;
+
+
+        /** Element of the sweep line event list
+
+            As the sweep line traverses across the overall area,
+            rectangle edges parallel to it generate events, and
+            rectangle edges orthogonal to it generate active
+            edges. This class represents the former.
+
+            The class defines an element of the sweep line list. The
+            sweep line's position jumps in steps defined by the
+            coordinates of the sorted SweepLineEvent entries.
+         */
+        class SweepLineEvent
+        {
+        public:
+            /** The two possible sweep line rectangle edges differ by
+                one coordinate value - the starting edge has the
+                lower, the finishing edge the higher value.
+             */
+            enum EdgeType {
+                /// edge with lower coordinate value
+                STARTING_EDGE=0,
+                /// edge with higher coordinate value
+                FINISHING_EDGE=1
+            };
+
+            /** The two possible sweep line directions
+             */
+            enum EdgeDirection {
+                PROCEED_UP=0,
+                PROCEED_DOWN=1
+            };
+
+            /** Create sweep line event
+
+                @param fPos
+                Coordinate position of the event
+
+                @param rRect
+                Rectangle this event is generated for.
+
+                @param eEdgeType
+                Is fPos the lower or the higher value, for the
+                rectangle this event is generated for?
+             */
+            SweepLineEvent( double              fPos,
+                            const B2DRectangle& rRect,
+                            EdgeType            eEdgeType,
+                            EdgeDirection       eDirection) :
+                mfPos( fPos ),
+                mpAssociatedRect( &rRect ),
+                meEdgeType( eEdgeType ),
+                meEdgeDirection( eDirection )
+            {}
+
+            double              getPos() const { return mfPos; }
+            const B2DRectangle& getRect() const { return *mpAssociatedRect; }
+            EdgeType            getEdgeType() const { return meEdgeType; }
+            EdgeDirection       getEdgeDirection() const { return meEdgeDirection; }
+
+            /// For STL sort
+            bool operator<( const SweepLineEvent& rRHS ) const { return mfPos < rRHS.mfPos; }
+
+        private:
+            /// position of the event, in the direction of the line sweep
+            double                mfPos;
+
+            /** Rectangle this event is generated for
+
+                This on the one hand saves some storage space (the
+                vector of rectangles is persistent, anyway), and on
+                the other hand provides an identifier to match active
+                edges and events (see below)
+
+                Ptr because class needs to be assignable
+             */
+            const B2DRectangle*   mpAssociatedRect;
+
+            /// 'upper' or 'lower' edge of original rectangle.
+            EdgeType              meEdgeType;
+
+            /// 'up' or 'down'
+            EdgeDirection         meEdgeDirection;
+        };
+
+        typedef std::vector< SweepLineEvent > VectorOfEvents;
+
+
+        /** Smart point container for B2DMultiRange::getPolyPolygon()
+
+            This class provides methods needed only here, and is used
+            as a place to store some additional information per
+            polygon. Also, most of the intersection logic is
+            implemented here.
+         */
+        class ImplPolygon
+        {
+        public:
+            /** Create polygon
+             */
+            ImplPolygon() :
+                mpLeadingRightEdge(NULL),
+                mnIdx(-1),
+                maPoints(),
+                mbIsFinished(false)
+            {
+                // completely ad-hoc. but what the hell.
+                maPoints.reserve(11);
+            }
+
+            void setPolygonPoolIndex( std::ptrdiff_t nIdx ) { mnIdx = nIdx; }
+            bool isFinished() const { return mbIsFinished; }
+
+            /// Add point to the end of the existing points
+            void append( const B2DPoint& rPoint )
+            {
+                OSL_PRECOND( maPoints.empty() ||
+                             maPoints.back().getX() == rPoint.getX() ||
+                             maPoints.back().getY() == rPoint.getY(),
+                             "ImplPolygon::append(): added point violates 90 degree line angle constraint!" );
+
+                if( maPoints.empty() ||
+                    maPoints.back() != rPoint )
+                {
+                    // avoid duplicate points
+                    maPoints.push_back( rPoint );
+                }
+            }
+
+            /** Perform the intersection of this polygon with an
+                active edge.
+
+                @param rEvent
+                The vertical line event that generated the
+                intersection
+
+                @param rActiveEdge
+                The active edge that generated the intersection
+
+                @param rPolygonPool
+                Polygon pool, we sometimes need to allocate a new one
+
+                @param bIsFinishingEdge
+                True, when this is hitting the last edge of the
+                vertical sweep - every vertical sweep starts and ends
+                with upper and lower edge of the _same_ rectangle.
+
+                @return the new current polygon (that's the one
+                processing must proceed with, when going through the
+                list of upcoming active edges).
+             */
+            std::ptrdiff_t intersect( SweepLineEvent&   rEvent,
+                                      ActiveEdge&       rActiveEdge,
+                                      VectorOfPolygons& rPolygonPool,
+                                      B2DPolyPolygon&   rRes,
+                                      bool              isFinishingEdge )
+            {
+                OSL_PRECOND( !isFinished(),
+                             "ImplPolygon::intersect(): called on already finished polygon!" );
+                OSL_PRECOND( !isFinishingEdge
+                             || (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()),
+                             "ImplPolygon::intersect(): inconsistent ending!" );
+
+                const B2DPoint aIntersectionPoint( rEvent.getPos(),
+                                                   rActiveEdge.getInvariantCoord() );
+
+                // intersection point, goes to our polygon
+                // unconditionally
+                append(aIntersectionPoint);
+
+                const bool isSweepLineEnteringRect(
+                    rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
+                if( isFinishingEdge )
+                {
+                    if( isSweepLineEnteringRect )
+                        handleFinalOwnRightEdge(rActiveEdge);
+                    else
+                        handleFinalOwnLeftEdge(rActiveEdge,
+                                               rPolygonPool,
+                                               rRes);
+
+                    // we're done with this rect & sweep line
+                    return -1;
+                }
+                else if( metOwnEdge(rEvent,rActiveEdge) )
+                {
+                    handleInitialOwnEdge(rEvent, rActiveEdge);
+
+                    // point already added, all init done, continue
+                    // with same poly
+                    return mnIdx;
+                }
+                else
+                {
+                    OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1,
+                                "ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" );
+
+                    const bool isHittingLeftEdge(
+                        rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
+
+                    if( isHittingLeftEdge )
+                        return handleComplexLeftEdge(rActiveEdge,
+                                                     aIntersectionPoint,
+                                                     rPolygonPool,
+                                                     rRes);
+                    else
+                        return handleComplexRightEdge(rActiveEdge,
+                                                      aIntersectionPoint,
+                                                      rPolygonPool);
+                }
+            }
+
+        private:
+            std::ptrdiff_t getPolygonPoolIndex() const { return mnIdx; }
+
+            void handleInitialOwnEdge(SweepLineEvent& rEvent,
+                                      ActiveEdge&     rActiveEdge)
+            {
+                const bool isActiveEdgeProceedLeft(
+                    rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
+                const bool isSweepLineEnteringRect(
+                    rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
+                (void)isActiveEdgeProceedLeft;
+                (void)isSweepLineEnteringRect;
+
+                OSL_ENSURE( isSweepLineEnteringRect == isActiveEdgeProceedLeft,
+                            "ImplPolygon::intersect(): sweep initial own edge hit: wrong polygon order" );
+
+                OSL_ENSURE( isSweepLineEnteringRect ||
+                            mpLeadingRightEdge == &rActiveEdge,
+                            "ImplPolygon::intersect(): sweep initial own edge hit: wrong leading edge" );
+            }
+
+            void handleFinalOwnRightEdge(ActiveEdge& rActiveEdge)
+            {
+                OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT,
+                            "ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" );
+
+                rActiveEdge.setTargetPolygonIndex(mnIdx);
+                mpLeadingRightEdge = &rActiveEdge;
+            }
+
+            void handleFinalOwnLeftEdge(ActiveEdge&       rActiveEdge,
+                                        VectorOfPolygons& rPolygonPool,
+                                        B2DPolyPolygon&   rRes)
+            {
+                OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT,
+                            "ImplPolygon::handleFinalOwnLeftEdge(): end edge wrong polygon order" );
+
+                const bool isHittingOurTail(
+                    rActiveEdge.getTargetPolygonIndex() == mnIdx);
+
+                if( isHittingOurTail )
+                    finish(rRes); // just finish. no fuss.
+                else
+                {
+                    // temp poly hits final left edge
+                    const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+                    ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+                    // active edge's polygon has points
+                    // already. ours need to go in front of them.
+                    maPoints.insert(maPoints.end(),
+                                    rTmp.maPoints.begin(),
+                                    rTmp.maPoints.end());
+
+                    // adjust leading edges, we're switching the polygon
+                    ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
+
+                    mpLeadingRightEdge = pFarEdge;
+                    pFarEdge->setTargetPolygonIndex(mnIdx);
+
+                    // nTmpIdx is an empty shell, get rid of it
+                    rPolygonPool.free(nTmpIdx);
+                }
+            }
+
+            std::ptrdiff_t handleComplexLeftEdge(ActiveEdge&       rActiveEdge,
+                                                 const B2DPoint&   rIntersectionPoint,
+                                                 VectorOfPolygons& rPolygonPool,
+                                                 B2DPolyPolygon&   rRes)
+            {
+                const bool isHittingOurTail(
+                    rActiveEdge.getTargetPolygonIndex() == mnIdx);
+                if( isHittingOurTail )
+                {
+                    finish(rRes);
+
+                    // so "this" is done - need new polygon to collect
+                    // further points
+                    const std::ptrdiff_t nIdxNewPolygon=rPolygonPool.alloc();
+                    rPolygonPool.get(nIdxNewPolygon).setPolygonPoolIndex(nIdxNewPolygon);
+                    rPolygonPool.get(nIdxNewPolygon).append(rIntersectionPoint);
+
+                    rActiveEdge.setTargetPolygonIndex(nIdxNewPolygon);
+
+                    return nIdxNewPolygon;
+                }
+                else
+                {
+                    const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+                    ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+                    // active edge's polygon has points
+                    // already. ours need to go in front of them.
+                    maPoints.insert(maPoints.end(),
+                                    rTmp.maPoints.begin(),
+                                    rTmp.maPoints.end());
+
+                    rTmp.maPoints.clear();
+                    rTmp.append(rIntersectionPoint);
+
+                    // adjust leading edges, we're switching the polygon
+                    ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
+                    ActiveEdge* const pNearEdge=&rActiveEdge;
+
+                    rTmp.mpLeadingRightEdge = NULL;
+                    pNearEdge->setTargetPolygonIndex(nTmpIdx);
+
+                    mpLeadingRightEdge = pFarEdge;
+                    pFarEdge->setTargetPolygonIndex(mnIdx);
+
+                    return nTmpIdx;
+                }
+            }
+
+            std::ptrdiff_t handleComplexRightEdge(ActiveEdge&       rActiveEdge,
+                                                  const B2DPoint&   rIntersectionPoint,
+                                                  VectorOfPolygons& rPolygonPool)
+            {
+                const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+                ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+                rTmp.append(rIntersectionPoint);
+
+                rActiveEdge.setTargetPolygonIndex(mnIdx);
+                mpLeadingRightEdge = &rActiveEdge;
+
+                rTmp.mpLeadingRightEdge = NULL;
+
+                return nTmpIdx;
+            }
+
+            /// True when sweep line hits our own active edge
+            bool metOwnEdge(const SweepLineEvent& rEvent,
+                            ActiveEdge&           rActiveEdge)
+            {
+                const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect();
+                return bHitOwnEdge;
+            }
+
+            /// Retrieve B2DPolygon from this object
+            B2DPolygon getPolygon() const
+            {
+                B2DPolygon aRes;
+                std::for_each( maPoints.begin(),
+                               maPoints.end(),
+                               boost::bind(
+                     &B2DPolygon::append,
+                                   boost::ref(aRes),
+                                   _1,
+                                   1 ) );
+                aRes.setClosed( true );
+                return aRes;
+            }
+
+            /** Finish this polygon, push to result set.
+             */
+            void finish(B2DPolyPolygon& rRes)
+            {
+                OSL_PRECOND( maPoints.empty() ||
+                             maPoints.front().getX() == maPoints.back().getX() ||
+                             maPoints.front().getY() == maPoints.back().getY(),
+                             "ImplPolygon::finish(): first and last point violate 90 degree line angle constraint!" );
+
+                mbIsFinished = true;
+                mpLeadingRightEdge = NULL;
+
+                rRes.append(getPolygon());
+            }
+
+            /** Refers to the current leading edge element of this
+                polygon, or NULL. The leading edge denotes the 'front'
+                of the polygon vertex sequence, i.e. the coordinates
+                at the polygon's leading edge are returned from
+                maPoints.front()
+             */
+            ActiveEdge*           mpLeadingRightEdge;
+
+            /// current index into vector pool
+            std::ptrdiff_t        mnIdx;
+
+            /// Container for the actual polygon points
+            std::vector<B2DPoint> maPoints;
+
+            /// When true, this polygon is 'done', i.e. nothing must be added anymore.
+            bool                  mbIsFinished;
+        };
+
+        /** Init sweep line event list
+
+            This method fills the event list with the sweep line
+            events generated from the input rectangles, and sorts them
+            with increasing x.
+         */
+        void setupSweepLineEventListFromRanges( VectorOfEvents& o_rEventVector,
+                                                const std::vector<B2DRange>& rRanges,
+                                                const std::vector<B2VectorOrientation>& rOrientations )
+        {
+            // we need exactly 2*rectVec.size() events: one for the
+            // left, and one for the right edge of each rectangle
+            o_rEventVector.clear();
+            o_rEventVector.reserve( 2*rRanges.size() );
+
+            // generate events
+            // ===============
+
+            // first pass: add all left edges in increasing order
+            std::vector<B2DRange>::const_iterator aCurrRect=rRanges.begin();
+            std::vector<B2VectorOrientation>::const_iterator aCurrOrientation=rOrientations.begin();
+            const std::vector<B2DRange>::const_iterator aEnd=rRanges.end();
+            const std::vector<B2VectorOrientation>::const_iterator aEndOrientation=rOrientations.end();
+            while( aCurrRect != aEnd && aCurrOrientation != aEndOrientation )
+            {
+                const B2DRectangle& rCurrRect( *aCurrRect++ );
+
+                o_rEventVector.push_back(
+                    SweepLineEvent( rCurrRect.getMinX(),
+                                    rCurrRect,
+                                    SweepLineEvent::STARTING_EDGE,
+                                    (*aCurrOrientation++) == ORIENTATION_POSITIVE ?
+                                    SweepLineEvent::PROCEED_UP : SweepLineEvent::PROCEED_DOWN) );
+            }
+
+            // second pass: add all right edges in reversed order
+            std::vector<B2DRange>::const_reverse_iterator aCurrRectR=rRanges.rbegin();
+            std::vector<B2VectorOrientation>::const_reverse_iterator aCurrOrientationR=rOrientations.rbegin();
+            const std::vector<B2DRange>::const_reverse_iterator aEndR=rRanges.rend();
+            const std::vector<B2VectorOrientation>::const_reverse_iterator aEndOrientationR=rOrientations.rend();
+            while( aCurrRectR != aEndR )
+            {
+                const B2DRectangle& rCurrRect( *aCurrRectR++ );
+
+                o_rEventVector.push_back(
+                    SweepLineEvent( rCurrRect.getMaxX(),
+                                    rCurrRect,
+                                    SweepLineEvent::FINISHING_EDGE,
+                                    (*aCurrOrientationR++) == ORIENTATION_POSITIVE ?
+                                    SweepLineEvent::PROCEED_DOWN : SweepLineEvent::PROCEED_UP ) );
+            }
+
+            // sort events
+            // ===========
+
+            // since we use stable_sort, the order of events with the
+            // same x value will not change. The elaborate two-pass
+            // add above thus ensures, that for each two rectangles
+            // with similar left and right x coordinates, the
+            // rectangle whose left event comes first will have its
+            // right event come last. This is advantageous for the
+            // clip algorithm below, see handleRightEdgeCrossing().
+
+            // TODO(P3): Use radix sort (from
+            // b2dpolypolygonrasterconverter, or have your own
+            // templatized version).
+            std::stable_sort( o_rEventVector.begin(),
+                              o_rEventVector.end() );
+        }
+
+        /** Insert two active edge segments for the given rectangle.
+
+            This method creates two active edge segments from the
+            given rect, and inserts them into the active edge list,
+            such that this stays sorted (if it was before).
+
+            @param io_rEdgeList
+            Active edge list to insert into
+
+            @param io_rPolygons
+            Vector of polygons. Each rectangle added creates one
+            tentative result polygon in this vector, and the edge list
+            entries holds a reference to that polygon (this _requires_
+            that the polygon vector does not reallocate, i.e. it must
+            have at least the maximal number of rectangles reserved)
+
+            @param o_CurrentPolygon
+            The then-current polygon when processing this sweep line
+            event
+
+            @param rCurrEvent
+            The actual event that caused this call
+         */
+        void createActiveEdgesFromStartEvent( ListOfEdges&      io_rEdgeList,
+                                              VectorOfPolygons& io_rPolygonPool,
+                                              SweepLineEvent&   rCurrEvent )
+        {
+            ListOfEdges         aNewEdges;
+            const B2DRectangle& rRect=rCurrEvent.getRect();
+            const bool          bGoesDown=rCurrEvent.getEdgeDirection() == SweepLineEvent::PROCEED_DOWN;
+
+            // start event - new rect starts here, needs polygon to
+            // collect points into
+            const std::ptrdiff_t nIdxPolygon=io_rPolygonPool.alloc();
+            io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon);
+
+            // upper edge
+            aNewEdges.push_back(
+                ActiveEdge(
+                    rRect,
+                    rRect.getMinY(),
+                    bGoesDown ? nIdxPolygon : -1,
+                    ActiveEdge::UPPER,
+                    bGoesDown ? ActiveEdge::PROCEED_LEFT : ActiveEdge::PROCEED_RIGHT) );
+            // lower edge
+            aNewEdges.push_back(
+                ActiveEdge(
+                    rRect,
+                    rRect.getMaxY(),
+                    bGoesDown ? -1 : nIdxPolygon,
+                    ActiveEdge::LOWER,
+                    bGoesDown ? ActiveEdge::PROCEED_RIGHT : ActiveEdge::PROCEED_LEFT ) );
+
+            // furthermore, have to respect a special tie-breaking
+            // rule here, for edges which share the same y value:
+            // newly added upper edges must be inserted _before_ any
+            // other edge with the same y value, and newly added lower
+            // edges must be _after_ all other edges with the same
+            // y. This ensures that the left vertical edge processing
+            // below encounters the upper edge of the current rect
+            // first, and the lower edge last, which automatically
+            // starts and finishes this rect correctly (as only then,
+            // the polygon will have their associated active edges
+            // set).
+            const double                nMinY( rRect.getMinY() );
+            const double                nMaxY( rRect.getMaxY() );
+            ListOfEdges::iterator       aCurr( io_rEdgeList.begin() );
+            const ListOfEdges::iterator aEnd ( io_rEdgeList.end() );
+            while( aCurr != aEnd )
+            {
+                const double nCurrY( aCurr->getInvariantCoord() );
+
+                if( nCurrY >= nMinY &&
+                    aNewEdges.size() == 2 ) // only add, if not yet done.
+                {
+                    // insert upper edge _before_ aCurr. Thus, it will
+                    // be the first entry for a range of equal y
+                    // values. Using splice here, since we hold
+                    // references to the moved list element!
+                    io_rEdgeList.splice( aCurr,
+                                         aNewEdges,
+                                         aNewEdges.begin() );
+                }
+
+                if( nCurrY > nMaxY )
+                {
+                    // insert lower edge _before_ aCurr. Thus, it will
+                    // be the last entry for a range of equal y values
+                    // (aCurr is the first entry strictly larger than
+                    // nMaxY). Using splice here, since we hold
+                    // references to the moved list element!
+                    io_rEdgeList.splice( aCurr,
+                                         aNewEdges,
+                                         aNewEdges.begin() );
+                    // done with insertion, can early-exit here.
+                    return;
+                }
+
+                ++aCurr;
+            }
+
+            // append remainder of aNewList (might still contain 2 or
+            // 1 elements, depending of the contents of io_rEdgeList).
+            io_rEdgeList.splice( aCurr,
+                                 aNewEdges );
+        }
+
+        inline bool isSameRect(ActiveEdge&              rEdge,
+                               const basegfx::B2DRange& rRect)
+        {
+            return &rEdge.getRect() == &rRect;
+        }
+
+        // wow what a hack. necessary because stl's list::erase does
+        // not eat reverse_iterator
+        template<typename Cont, typename Iter> Iter eraseFromList(Cont&, Iter);
+        template<> inline ListOfEdges::iterator eraseFromList(
+            ListOfEdges& rList, ListOfEdges::iterator aIter)
+        {
+            return rList.erase(aIter);
+        }
+        template<> inline ListOfEdges::reverse_iterator eraseFromList(
+            ListOfEdges& rList, ListOfEdges::reverse_iterator aIter)
+        {
+            return ListOfEdges::reverse_iterator(
+                    rList.erase(boost::prior(aIter.base())));
+        }
+
+        template<int bPerformErase,
+                 typename Iterator> inline void processActiveEdges(
+            Iterator          first,
+            Iterator          last,
+            ListOfEdges&      rActiveEdgeList,
+            SweepLineEvent&   rCurrEvent,
+            VectorOfPolygons& rPolygonPool,
+            B2DPolyPolygon&   rRes )
+        {
+            const basegfx::B2DRange& rCurrRect=rCurrEvent.getRect();
+
+            // fast-forward to rCurrEvent's first active edge (holds
+            // for both starting and finishing sweep line events, a
+            // rect is regarded _outside_ any rects whose events have
+            // started earlier
+            first = std::find_if(first, last,
+                                 boost::bind(
+                         &isSameRect,
+                                     _1,
+                                     boost::cref(rCurrRect)));
+
+            if(first == last)
+                return;
+
+            int nCount=0;
+            std::ptrdiff_t nCurrPolyIdx=-1;
+            while(first != last)
+            {
+                if( nCurrPolyIdx == -1 )
+                    nCurrPolyIdx=first->getTargetPolygonIndex();
+
+                OSL_ASSERT(nCurrPolyIdx != -1);
+
+                // second encounter of my rect -> second edge
+                // encountered, done
+                const bool bExit=
+                    nCount &&
+                    isSameRect(*first,
+                               rCurrRect);
+
+                // deal with current active edge
+                nCurrPolyIdx =
+                    rPolygonPool.get(nCurrPolyIdx).intersect(
+                        rCurrEvent,
+                        *first,
+                        rPolygonPool,
+                        rRes,
+                        bExit);
+
+                // prune upper & lower active edges, if requested
+                if( bPerformErase && (bExit || !nCount) )
+                    first = eraseFromList(rActiveEdgeList,first);
+                else
+                    ++first;
+
+                // delayed exit, had to prune first
+                if( bExit )
+                    return;
+
+                ++nCount;
+            }
+        }
+
+        template<int bPerformErase> inline void processActiveEdgesTopDown(
+            SweepLineEvent&   rCurrEvent,
+            ListOfEdges&      rActiveEdgeList,
+            VectorOfPolygons& rPolygonPool,
+            B2DPolyPolygon&   rRes )
+        {
+            processActiveEdges<bPerformErase>(
+                rActiveEdgeList. begin(),
+                rActiveEdgeList. end(),
+                rActiveEdgeList,
+                rCurrEvent,
+                rPolygonPool,
+                rRes);
+        }
+
+        template<int bPerformErase> inline void processActiveEdgesBottomUp(
+            SweepLineEvent&   rCurrEvent,
+            ListOfEdges&      rActiveEdgeList,
+            VectorOfPolygons& rPolygonPool,
+            B2DPolyPolygon&   rRes )
+        {
+            processActiveEdges<bPerformErase>(
+                rActiveEdgeList. rbegin(),
+                rActiveEdgeList. rend(),
+                rActiveEdgeList,
+                rCurrEvent,
+                rPolygonPool,
+                rRes);
+        }
+
+        enum{ NoErase=0, PerformErase=1 };
+
+        void handleStartingEdge( SweepLineEvent&   rCurrEvent,
+                                 ListOfEdges&      rActiveEdgeList,
+                                 VectorOfPolygons& rPolygonPool,
+                                 B2DPolyPolygon&   rRes)
+        {
+            // inject two new active edges for rect
+            createActiveEdgesFromStartEvent( rActiveEdgeList,
+                                             rPolygonPool,
+                                             rCurrEvent );
+
+            if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
+                processActiveEdgesTopDown<NoErase>(
+                    rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+            else
+                processActiveEdgesBottomUp<NoErase>(
+                    rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+        }
+
+        void handleFinishingEdge( SweepLineEvent&   rCurrEvent,
+                                  ListOfEdges&      rActiveEdgeList,
+                                  VectorOfPolygons& rPolygonPool,
+                                  B2DPolyPolygon&   rRes)
+        {
+            if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
+                processActiveEdgesTopDown<PerformErase>(
+                    rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+            else
+                processActiveEdgesBottomUp<PerformErase>(
+                    rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+        }
+
+        inline void handleSweepLineEvent( SweepLineEvent&   rCurrEvent,
+                                          ListOfEdges&      rActiveEdgeList,
+                                          VectorOfPolygons& rPolygonPool,
+                                          B2DPolyPolygon&   rRes)
+        {
+            if( SweepLineEvent::STARTING_EDGE == rCurrEvent.getEdgeType() )
+                handleStartingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
+            else
+                handleFinishingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
+        }
+    }
+
+    namespace tools
+    {
+        B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
+                                       const std::vector<B2VectorOrientation>& rOrientations)
+        {
+            // sweep-line algorithm to generate a poly-polygon
+            // from a bunch of rectangles
+            // ===============================================
+            //
+            // This algorithm uses the well-known sweep line
+            // concept, explained in every good text book about
+            // computational geometry.
+            //
+            // We start with creating two structures for every
+            // rectangle, one representing the left x coordinate,
+            // one representing the right x coordinate (and both
+            // referencing the original rect). These structs are
+            // sorted with increasing x coordinates.
+            //
+            // Then, we start processing the resulting list from
+            // the beginning. Every entry in the list defines a
+            // point in time of the line sweeping from left to
+            // right across all rectangles.
+            VectorOfEvents aSweepLineEvents;
+            setupSweepLineEventListFromRanges( aSweepLineEvents,
+                                               rRanges,
+                                               rOrientations );
+
+            B2DPolyPolygon   aRes;
+            VectorOfPolygons aPolygonPool;
+            ListOfEdges      aActiveEdgeList;
+
+            // sometimes not enough, but a usable compromise
+            aPolygonPool.reserve( rRanges.size() );
+
+            std::for_each( aSweepLineEvents.begin(),
+                           aSweepLineEvents.end(),
+                           boost::bind(
+                               &handleSweepLineEvent,
+                               _1,
+                               boost::ref(aActiveEdgeList),
+                               boost::ref(aPolygonPool),
+                               boost::ref(aRes)) );
+
+            return aRes;
+        }
+    }
+}
+
diff --git a/basegfx/source/range/makefile.mk b/basegfx/source/range/makefile.mk
index 678bb16a9312..3dcf552fc420 100644
--- a/basegfx/source/range/makefile.mk
+++ b/basegfx/source/range/makefile.mk
@@ -47,7 +47,8 @@ SLOFILES= \
                 $(SLO)$/b1drange.obj		\
                 $(SLO)$/b2drange.obj		\
                 $(SLO)$/b2xrange.obj		\
-                $(SLO)$/b2dmultirange.obj		\
+                $(SLO)$/b2dpolyrange.obj	\
+                $(SLO)$/b2drangeclipper.obj	\
                 $(SLO)$/b3drange.obj
 
 # --- Targets ----------------------------------