Adding upstream version 1:7.0.4.upstream/1%7.0.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

12 files changed, 1990 insertions, 0 deletions

diff --git a/include/basegfx/range/b1drange.hxx b/include/basegfx/range/b1drange.hxx
new file mode 100644
index 000000000..0db585558
--- /dev/null
+++ b/include/basegfx/range/b1drange.hxx
@@ -0,0 +1,151 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/range/basicrange.hxx>
+
+
+namespace basegfx
+{
+
+    /** A one-dimensional interval over doubles
+
+        This is a set of real numbers, bounded by a lower and an upper
+        value. All inbetween values are included in the set (see also
+        http://en.wikipedia.org/wiki/Interval_%28mathematics%29).
+
+        The set is closed, i.e. the upper and the lower bound are
+        included (if you're used to the notation - we're talking about
+        [a,b] here, compared to half-open [a,b) or open intervals
+        (a,b)).
+
+        That means, isInside(val) will return true also for values of
+        val=a or val=b.
+     */
+    class B1DRange
+    {
+        ::basegfx::BasicRange< double, DoubleTraits >   maRange;
+
+    public:
+        B1DRange() {}
+
+        /// Create degenerate interval consisting of a single double number
+        explicit B1DRange(double fStartValue)
+        :   maRange(fStartValue)
+        {
+        }
+
+        /// Create proper interval between the two given double values
+        B1DRange(double fStartValue1, double fStartValue2)
+        :   maRange(fStartValue1)
+        {
+            expand(fStartValue2);
+        }
+
+        /** Check if the interval set is empty
+
+            @return false, if no value is in this set - having a
+            single value included will already return true.
+         */
+        bool isEmpty() const
+        {
+            return maRange.isEmpty();
+        }
+
+        bool operator==( const B1DRange& rRange ) const
+        {
+            return (maRange == rRange.maRange);
+        }
+
+        bool operator!=( const B1DRange& rRange ) const
+        {
+            return (maRange != rRange.maRange);
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        double getMinimum() const
+        {
+            return maRange.getMinimum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        double getMaximum() const
+        {
+            return maRange.getMaximum();
+        }
+
+        /// return difference between upper and lower value. returns 0 for empty sets.
+        double getRange() const
+        {
+            return maRange.getRange();
+        }
+
+        /// return middle of upper and lower value. returns 0 for empty sets.
+        double getCenter() const
+        {
+            return maRange.getCenter();
+        }
+
+        /// yields true if value is contained in set
+        bool isInside(double fValue) const
+        {
+            return maRange.isInside(fValue);
+        }
+
+        /// yields true if rRange at least partly inside set
+        bool overlaps(const B1DRange& rRange) const
+        {
+            return maRange.overlaps(rRange.maRange);
+        }
+
+        /// yields true if overlaps(rRange) does, and the overlap is larger than infinitesimal
+        bool overlapsMore(const B1DRange& rRange) const
+        {
+            return maRange.overlapsMore(rRange.maRange);
+        }
+
+        /// add fValue to the set, expanding as necessary
+        void expand(double fValue)
+        {
+            maRange.expand(fValue);
+        }
+
+        /// add rRange to the set, expanding as necessary
+        void expand(const B1DRange& rRange)
+        {
+            maRange.expand(rRange.maRange);
+        }
+
+        /// calc set intersection
+        void intersect(const B1DRange& rRange)
+        {
+            maRange.intersect(rRange.maRange);
+        }
+
+        /// clamp value on range
+        double clamp(double fValue) const
+        {
+            return maRange.clamp(fValue);
+        }
+    };
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2dconnectedranges.hxx b/include/basegfx/range/b2dconnectedranges.hxx
new file mode 100644
index 000000000..0d7a81481
--- /dev/null
+++ b/include/basegfx/range/b2dconnectedranges.hxx
@@ -0,0 +1,240 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <osl/diagnose.h>
+#include <basegfx/range/b2drange.hxx>
+#include <list>
+#include <utility>
+#include <algorithm>
+
+
+namespace basegfx
+{
+    /** Calculate connected ranges from input ranges.
+
+        This template constructs a list of connected ranges from the
+        given input ranges. That is, the output will contain a set of
+        ranges, itself containing a number of input ranges, which will
+        be mutually non-intersecting.
+
+        Example:
+        <code>
+        -------------------
+        |          -------|
+        |          |     ||
+        | ---      |     ||
+        | | |      -------|        --------
+        | | +---------    |        |      |
+        | --+        |    |        |      |
+        |   |        |    |        --------
+        |   ----------    |
+        -------------------
+        </code
+
+        Here, the outer rectangles represent the output
+        ranges. Contained are the input rectangles that comprise these
+        output ranges.
+
+        @tpl UserData
+        User data to be stored along with the range, to later identify
+        which range went into which connected component. Must be
+        assignable, default- and copy-constructible.
+     */
+    template< typename UserData > class B2DConnectedRanges
+    {
+    public:
+        /// Type of the basic entity (rect + user data)
+        typedef ::std::pair< B2DRange, UserData > ComponentType;
+        typedef ::std::list< ComponentType >      ComponentListType;
+
+        /// List of (intersecting) components, plus overall bounds
+        struct ConnectedComponents
+        {
+            ComponentListType   maComponentList;
+            B2DRange            maTotalBounds;
+        };
+
+        typedef ::std::list< ConnectedComponents > ConnectedComponentsType;
+
+
+        /// Create the range calculator
+        B2DConnectedRanges() :
+            maDisjunctAggregatesList(),
+            maTotalBounds()
+        {
+        }
+
+        /** Add an additional range.
+
+            This method integrates a new range into the connected
+            ranges lists. The method has a worst-case time complexity
+            of O(n^2), with n denoting the number of already added
+            ranges (typically, for well-behaved input, it is O(n)
+            though).
+         */
+        void addRange( const B2DRange&  rRange,
+                       const UserData&  rUserData )
+        {
+            // check whether fast path is possible: if new range is
+            // outside accumulated total range, can add it as a
+            // separate component right away.
+            const bool bNotOutsideEverything(
+                maTotalBounds.overlaps( rRange ) );
+
+            // update own global bounds range
+            maTotalBounds.expand( rRange );
+
+            // assemble anything intersecting with rRange into
+            // this new connected component
+            ConnectedComponents aNewConnectedComponent;
+
+            // as at least rRange will be a member of
+            // aNewConnectedComponent (will be added below), can
+            // preset the overall bounds here.
+            aNewConnectedComponent.maTotalBounds = rRange;
+
+
+            //  STAGE 1: Search for intersecting maDisjunctAggregatesList entries
+
+
+            // if rRange is empty, it will intersect with no
+            // maDisjunctAggregatesList member. Thus, we can safe us
+            // the check.
+            // if rRange is outside all other rectangle, skip here,
+            // too
+            if( bNotOutsideEverything &&
+                !rRange.isEmpty() )
+            {
+                typename ConnectedComponentsType::iterator aCurrAggregate;
+                typename ConnectedComponentsType::iterator aLastAggregate;
+
+                // flag, determining whether we touched one or more of
+                // the maDisjunctAggregatesList entries. _If_ we did,
+                // we have to repeat the intersection process, because
+                // these changes might have generated new
+                // intersections.
+                bool bSomeAggregatesChanged;
+
+                // loop, until bSomeAggregatesChanged stays false
+                do
+                {
+                    // only continue loop if 'intersects' branch below was hit
+                    bSomeAggregatesChanged = false;
+
+                    // iterate over all current members of maDisjunctAggregatesList
+                    for( aCurrAggregate=maDisjunctAggregatesList.begin(),
+                             aLastAggregate=maDisjunctAggregatesList.end();
+                         aCurrAggregate != aLastAggregate; )
+                    {
+                        // first check if current component's bounds
+                        // are empty. This ensures that distinct empty
+                        // components are not merged into one
+                        // aggregate. As a matter of fact, they have
+                        // no position and size.
+
+                        if( !aCurrAggregate->maTotalBounds.isEmpty() &&
+                            aCurrAggregate->maTotalBounds.overlaps(
+                                aNewConnectedComponent.maTotalBounds ) )
+                        {
+                            // union the intersecting
+                            // maDisjunctAggregatesList element into
+                            // aNewConnectedComponent
+
+                            // calc union bounding box
+                            aNewConnectedComponent.maTotalBounds.expand( aCurrAggregate->maTotalBounds );
+
+                            // extract all aCurrAggregate components
+                            // to aNewConnectedComponent
+                            aNewConnectedComponent.maComponentList.splice(
+                                aNewConnectedComponent.maComponentList.end(),
+                                aCurrAggregate->maComponentList );
+
+                            // remove and delete aCurrAggregate entry
+                            // from list (we've gutted it's content
+                            // above). list::erase() will update our
+                            // iterator with the predecessor here.
+                            aCurrAggregate = maDisjunctAggregatesList.erase( aCurrAggregate );
+
+                            // at least one aggregate changed, need to rescan everything
+                            bSomeAggregatesChanged = true;
+                        }
+                        else
+                        {
+                            ++aCurrAggregate;
+                        }
+                    }
+                }
+                while( bSomeAggregatesChanged );
+            }
+
+
+            //  STAGE 2: Add newly generated connected component list element
+
+
+            // add new component to the end of the component list
+            aNewConnectedComponent.maComponentList.push_back(
+                ComponentType( rRange, rUserData ) );
+
+            // do some consistency checks (aka post conditions)
+            OSL_ENSURE( !aNewConnectedComponent.maComponentList.empty(),
+                        "B2DConnectedRanges::addRange(): empty aggregate list" );
+            OSL_ENSURE( !aNewConnectedComponent.maTotalBounds.isEmpty() ||
+                         aNewConnectedComponent.maComponentList.size() == 1,
+                        "B2DConnectedRanges::addRange(): empty ranges must be solitary");
+
+            // add aNewConnectedComponent as a new entry to
+            // maDisjunctAggregatesList
+            maDisjunctAggregatesList.push_back( aNewConnectedComponent );
+        }
+
+        /** Apply a functor to each of the disjunct component
+            aggregates.
+
+            @param aFunctor
+            Functor to apply. Must provide an operator( const ConnectedComponents& ).
+
+            @return a copy of the functor, as applied to all aggregates.
+         */
+        template< typename UnaryFunctor > UnaryFunctor forEachAggregate( UnaryFunctor aFunctor ) const
+        {
+            return ::std::for_each( maDisjunctAggregatesList.begin(),
+                                    maDisjunctAggregatesList.end(),
+                                    aFunctor );
+        }
+
+    private:
+        B2DConnectedRanges(const B2DConnectedRanges&) = delete;
+        B2DConnectedRanges& operator=( const B2DConnectedRanges& ) = delete;
+
+        /** Current list of disjunct sets of connected components
+
+            Each entry corresponds to one of the top-level rectangles
+            in the drawing above.
+         */
+        ConnectedComponentsType maDisjunctAggregatesList;
+
+        /** Global bound rect over all added ranges.
+         */
+        B2DRange                maTotalBounds;
+    };
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2dpolyrange.hxx b/include/basegfx/range/b2dpolyrange.hxx
new file mode 100644
index 000000000..9a366956c
--- /dev/null
+++ b/include/basegfx/range/b2dpolyrange.hxx
@@ -0,0 +1,93 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <o3tl/cow_wrapper.hxx>
+#include <tuple>
+#include <basegfx/vector/b2enums.hxx>
+#include <basegfx/basegfxdllapi.h>
+
+namespace basegfx
+{
+    class B2DRange;
+    class B2DPolyPolygon;
+    class B2DHomMatrix;
+    class ImplB2DPolyRange;
+
+    /** Multiple ranges in one object.
+
+        This class combines multiple ranges in one object, providing a
+        total, enclosing range for it.
+
+        You can use this class e.g. when updating views containing
+        rectangular objects. Add each modified object to a
+        B2DMultiRange, then test each viewable object against
+        intersection with the multi range.
+
+        Similar in spirit to the poly-polygon vs. polygon relationship.
+
+        Note that comparable to polygons, a poly-range can also
+        contain 'holes' - this is encoded via polygon orientation at
+        the poly-polygon, and via explicit flags for the poly-range.
+     */
+    class BASEGFX_DLLPUBLIC B2DPolyRange
+    {
+    public:
+        typedef std::tuple<B2DRange, B2VectorOrientation> ElementType;
+
+        B2DPolyRange();
+        ~B2DPolyRange();
+
+        /** Create a multi range with exactly one containing range
+         */
+        B2DPolyRange( const B2DPolyRange& );
+        B2DPolyRange& operator=( const B2DPolyRange& );
+
+        bool operator==(const B2DPolyRange&) const;
+        bool operator!=(const B2DPolyRange&) const;
+
+        /// Number of included ranges
+        sal_uInt32 count() const;
+
+        ElementType getElement(sal_uInt32 nIndex) const;
+
+        // insert/append a single range
+        void appendElement(const B2DRange& rRange, B2VectorOrientation eOrient);
+
+        void clear();
+
+        /** Test whether given range overlaps one or more of the
+            included ranges. Does *not* use overall range, but checks
+            individually.
+         */
+        bool overlaps( const B2DRange& rRange ) const;
+
+        /** Request a poly-polygon with solved cross-overs
+         */
+        B2DPolyPolygon solveCrossovers() const;
+
+        void transform(const B2DHomMatrix& rTranslate);
+
+    private:
+        o3tl::cow_wrapper< ImplB2DPolyRange > mpImpl;
+    };
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2drange.hxx b/include/basegfx/range/b2drange.hxx
new file mode 100644
index 000000000..f6aa7f311
--- /dev/null
+++ b/include/basegfx/range/b2drange.hxx
@@ -0,0 +1,348 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <ostream>
+#include <vector>
+
+#include <basegfx/vector/b2dvector.hxx>
+#include <basegfx/point/b2dpoint.hxx>
+#include <basegfx/tuple/b2dtuple.hxx>
+#include <basegfx/range/basicrange.hxx>
+#include <basegfx/basegfxdllapi.h>
+
+namespace basegfx
+{
+    class B2IRange;
+    class B2DHomMatrix;
+
+    /** A two-dimensional interval over doubles
+
+        This is a set of real numbers, bounded by a lower and an upper
+        pair. All inbetween values are included in the set (see also
+        http://en.wikipedia.org/wiki/Interval_%28mathematics%29).
+
+        The set is closed, i.e. the upper and the lower bound are
+        included (if you're used to the notation - we're talking about
+        [a,b] here, compared to half-open [a,b) or open intervals
+        (a,b)).
+
+        That means, isInside(val) will return true also for values of
+        val=a or val=b.
+
+        @see B1DRange
+     */
+    class SAL_WARN_UNUSED B2DRange
+    {
+    public:
+        typedef double          ValueType;
+        typedef DoubleTraits    TraitsType;
+
+        B2DRange() {}
+
+        /// Create degenerate interval consisting of a single point
+        explicit B2DRange(const B2DTuple& rTuple)
+        :   maRangeX(rTuple.getX()),
+            maRangeY(rTuple.getY())
+        {
+        }
+
+        /// Create proper interval between the two given double pairs
+        B2DRange(double x1,
+                 double y1,
+                 double x2,
+                 double y2)
+        :   maRangeX(x1),
+            maRangeY(y1)
+        {
+            maRangeX.expand(x2);
+            maRangeY.expand(y2);
+        }
+
+        /// Create proper interval between the two given points
+        B2DRange(const B2DTuple& rTuple1,
+                 const B2DTuple& rTuple2)
+        :   maRangeX(rTuple1.getX()),
+            maRangeY(rTuple1.getY())
+        {
+            expand( rTuple2 );
+        }
+
+        BASEGFX_DLLPUBLIC explicit B2DRange(const B2IRange& rRange);
+
+        /** Check if the interval set is empty
+
+            @return false, if no value is in this set - having a
+            single point included will already return true.
+         */
+        bool isEmpty() const
+        {
+            return (
+                maRangeX.isEmpty()
+                || maRangeY.isEmpty()
+                );
+        }
+
+        /// reset the object to empty state again, clearing all values
+        void reset()
+        {
+            maRangeX.reset();
+            maRangeY.reset();
+        }
+
+        bool operator==( const B2DRange& rRange ) const
+        {
+            return (maRangeX == rRange.maRangeX
+                && maRangeY == rRange.maRangeY);
+        }
+
+        bool operator!=( const B2DRange& rRange ) const
+        {
+            return (maRangeX != rRange.maRangeX
+                || maRangeY != rRange.maRangeY);
+        }
+
+        bool equal(const B2DRange& rRange) const
+        {
+            return (maRangeX.equal(rRange.maRangeX)
+                    && maRangeY.equal(rRange.maRangeY));
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        double getMinX() const
+        {
+            return maRangeX.getMinimum();
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        double getMinY() const
+        {
+            return maRangeY.getMinimum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        double getMaxX() const
+        {
+            return maRangeX.getMaximum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        double getMaxY() const
+        {
+            return maRangeY.getMaximum();
+        }
+
+        /// return difference between upper and lower X value. returns 0 for empty sets.
+        double getWidth() const
+        {
+            return maRangeX.getRange();
+        }
+
+        /// return difference between upper and lower Y value. returns 0 for empty sets.
+        double getHeight() const
+        {
+            return maRangeY.getRange();
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        B2DPoint getMinimum() const
+        {
+            return B2DPoint(
+                maRangeX.getMinimum(),
+                maRangeY.getMinimum()
+                );
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        B2DPoint getMaximum() const
+        {
+            return B2DPoint(
+                maRangeX.getMaximum(),
+                maRangeY.getMaximum()
+                );
+        }
+
+        /// return difference between upper and lower point. returns (0,0) for empty sets.
+        B2DVector getRange() const
+        {
+            return B2DVector(
+                maRangeX.getRange(),
+                maRangeY.getRange()
+                );
+        }
+
+        /// return center point of set. returns (0,0) for empty sets.
+        B2DPoint getCenter() const
+        {
+            return B2DPoint(
+                maRangeX.getCenter(),
+                maRangeY.getCenter()
+                );
+        }
+
+        /// return center X value of set. returns 0 for empty sets.
+        double getCenterX() const
+        {
+            return maRangeX.getCenter();
+        }
+
+        /// return center Y value of set. returns 0 for empty sets.
+        double getCenterY() const
+        {
+            return maRangeY.getCenter();
+        }
+
+        /// yields true if given point is contained in set
+        bool isInside(const B2DTuple& rTuple) const
+        {
+            return (
+                maRangeX.isInside(rTuple.getX())
+                && maRangeY.isInside(rTuple.getY())
+                );
+        }
+
+        /// yields true if rRange is inside, or equal to set
+        bool isInside(const B2DRange& rRange) const
+        {
+            return (
+                maRangeX.isInside(rRange.maRangeX)
+                && maRangeY.isInside(rRange.maRangeY)
+                );
+        }
+
+        /// yields true if rRange at least partly inside set
+        bool overlaps(const B2DRange& rRange) const
+        {
+            return (
+                maRangeX.overlaps(rRange.maRangeX)
+                && maRangeY.overlaps(rRange.maRangeY)
+                );
+        }
+
+        /// yields true if overlaps(rRange) does, and the overlap is larger than infinitesimal
+        bool overlapsMore(const B2DRange& rRange) const
+        {
+            return (
+                maRangeX.overlapsMore(rRange.maRangeX)
+                && maRangeY.overlapsMore(rRange.maRangeY)
+                );
+        }
+
+        /// add point to the set, expanding as necessary
+        void expand(const B2DTuple& rTuple)
+        {
+            maRangeX.expand(rTuple.getX());
+            maRangeY.expand(rTuple.getY());
+        }
+
+        /// add rRange to the set, expanding as necessary
+        void expand(const B2DRange& rRange)
+        {
+            maRangeX.expand(rRange.maRangeX);
+            maRangeY.expand(rRange.maRangeY);
+        }
+
+        /// calc set intersection
+        void intersect(const B2DRange& rRange)
+        {
+            maRangeX.intersect(rRange.maRangeX);
+            maRangeY.intersect(rRange.maRangeY);
+        }
+
+        /// grow set by fValue on all sides
+        void grow(double fValue)
+        {
+            maRangeX.grow(fValue);
+            maRangeY.grow(fValue);
+        }
+
+        /// clamp value on range
+        B2DTuple clamp(const B2DTuple& rTuple) const
+        {
+            return B2DTuple(
+                maRangeX.clamp(rTuple.getX()),
+                maRangeY.clamp(rTuple.getY()));
+        }
+
+        /** Transform Range by given transformation matrix. */
+        BASEGFX_DLLPUBLIC void transform(const B2DHomMatrix& rMatrix);
+
+        /** Transform Range by given transformation matrix.
+
+            This operation transforms the Range by transforming all four possible
+            extrema points (corners) of the given range and building a new one.
+            This means that the range will grow evtl. when a shear and/or rotation
+            is part of the transformation.
+        */
+        BASEGFX_DLLPUBLIC B2DRange& operator*=( const ::basegfx::B2DHomMatrix& rMat );
+
+        /** Get a range filled with (0.0, 0.0, 1.0, 1.0) */
+        static const B2DRange& getUnitB2DRange();
+
+    private:
+        typedef ::basegfx::BasicRange< ValueType, TraitsType >  MyBasicRange;
+
+        MyBasicRange        maRangeX;
+        MyBasicRange        maRangeY;
+    };
+
+    /** Transform B2DRange by given transformation matrix (see operator*=())
+    */
+    B2DRange operator*( const B2DHomMatrix& rMat, const B2DRange& rB2DRange );
+
+    /** Round double to nearest integer for 2D range
+
+        @return the nearest integer for this range
+    */
+    BASEGFX_DLLPUBLIC B2IRange fround(const B2DRange& rRange);
+
+    /** Compute the set difference of the two given ranges
+
+        This method calculates the symmetric difference (aka XOR)
+        between the two given ranges, and returning the resulting
+        ranges. Thus, the result will contain all areas where one, but
+        not both ranges lie.
+
+        @param o_rResult
+        Result vector. The up to four difference ranges are returned
+        within this vector
+
+        @param rFirst
+        The first range
+
+        @param rSecond
+        The second range
+
+        @return the input vector
+     */
+    BASEGFX_DLLPUBLIC ::std::vector< B2DRange >& computeSetDifference( ::std::vector< B2DRange >&   o_rResult,
+                                                     const B2DRange&            rFirst,
+                                                     const B2DRange&            rSecond );
+
+    template< typename charT, typename traits >
+    inline std::basic_ostream<charT, traits> & operator <<(
+        std::basic_ostream<charT, traits> & stream, const B2DRange& range )
+    {
+        return stream << range.getWidth() << "x" << range.getHeight() << "@" << range.getMinimum();
+    }
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2drangeclipper.hxx b/include/basegfx/range/b2drangeclipper.hxx
new file mode 100644
index 000000000..63e8f05c2
--- /dev/null
+++ b/include/basegfx/range/b2drangeclipper.hxx
@@ -0,0 +1,42 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/range/b2dpolyrange.hxx>
+#include <vector>
+#include <basegfx/basegfxdllapi.h>
+
+namespace basegfx
+{
+    namespace utils
+    {
+        /** Extract poly-polygon w/o self-intersections from poly-range
+
+            Similar to the solveCrossovers(const B2DPolyPolygon&)
+            method, this one calculates a self-intersection-free
+            poly-polygon with the same topology, and encoding
+            inside/outsidedness via polygon orientation and layering.
+         */
+        BASEGFX_DLLPUBLIC B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
+                                       const std::vector<B2VectorOrientation>& rOrientations);
+    }
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2drectangle.hxx b/include/basegfx/range/b2drectangle.hxx
new file mode 100644
index 000000000..9c1ad86c0
--- /dev/null
+++ b/include/basegfx/range/b2drectangle.hxx
@@ -0,0 +1,33 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/range/b2drange.hxx>
+
+namespace basegfx
+{
+    // syntactic sugar: a B2DRange exactly models a Rectangle, thus,
+    // for interface clarity, we provide an alias name
+
+    /// Alias name for interface clarity (not everybody is aware of the identity)
+    typedef B2DRange B2DRectangle;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2ibox.hxx b/include/basegfx/range/b2ibox.hxx
new file mode 100644
index 000000000..2be733b93
--- /dev/null
+++ b/include/basegfx/range/b2ibox.hxx
@@ -0,0 +1,190 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <ostream>
+
+#include <basegfx/tuple/b2ituple.hxx>
+#include <basegfx/range/basicbox.hxx>
+
+namespace basegfx
+{
+    /** A two-dimensional interval over integers
+
+        This is most easily depicted as a set of integers, bounded by
+        a lower and an upper value - but excluding the upper
+        value. All inbetween values are included in the set (see also
+        http://en.wikipedia.org/wiki/Interval_%28mathematics%29).
+
+        The set is half-open, i.e. the lower bound is included, the
+        upper bound not (if you're used to the notation - we're
+        talking about [a,b) here, compared to closed [a,b] or fully
+        open intervals (a,b)).
+
+        If you don't need a half-open interval, check B2IRange.
+
+        That means, isInside(val) will return true also for values of
+        val=a, but not for val=b.
+
+        Alternatively, consider this a rectangle, where the rightmost
+        pixel column and the bottommost pixel row are excluded - this
+        is much like polygon filling. As a result, filling a given
+        rectangle with basebmp::BitmapDevice::fillPolyPolygon(), will
+        affect exactly the same set of pixel as isInside() would
+        return true for.
+
+        @see B2IRange
+     */
+    class B2IBox
+    {
+    public:
+        typedef sal_Int32       ValueType;
+        typedef Int32Traits     TraitsType;
+
+        B2IBox() {}
+
+        /// Create degenerate interval that's still empty
+        explicit B2IBox(const B2ITuple& rTuple)
+        :   maRangeX(rTuple.getX()),
+            maRangeY(rTuple.getY())
+        {
+        }
+
+        /// Create proper interval between the two given points
+        B2IBox(sal_Int32 x1,
+               sal_Int32 y1,
+               sal_Int32 x2,
+               sal_Int32 y2) :
+            maRangeX(x1),
+            maRangeY(y1)
+        {
+            maRangeX.expand(x2);
+            maRangeY.expand(y2);
+        }
+
+        /// Create proper interval between the two given points
+        B2IBox(const B2ITuple& rTuple1,
+               const B2ITuple& rTuple2) :
+            maRangeX(rTuple1.getX()),
+            maRangeY(rTuple1.getY())
+        {
+            expand( rTuple2 );
+        }
+
+        /** Check if the interval set is empty
+
+            @return false, if no value is in this set - having a
+            single value included will still return false.
+         */
+        bool isEmpty() const
+        {
+            return maRangeX.isEmpty() || maRangeY.isEmpty();
+        }
+
+        bool operator==( const B2IBox& rBox ) const
+        {
+            return (maRangeX == rBox.maRangeX
+                && maRangeY == rBox.maRangeY);
+        }
+
+        bool operator!=( const B2IBox& rBox ) const
+        {
+            return (maRangeX != rBox.maRangeX
+                || maRangeY != rBox.maRangeY);
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMinX() const
+        {
+            return maRangeX.getMinimum();
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMinY() const
+        {
+            return maRangeY.getMinimum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMaxX() const
+        {
+            return maRangeX.getMaximum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMaxY() const
+        {
+            return maRangeY.getMaximum();
+        }
+
+        /// return difference between upper and lower X value. returns 0 for empty sets.
+        sal_Int64 getWidth() const
+        {
+            return maRangeX.getRange();
+        }
+
+        /// return difference between upper and lower Y value. returns 0 for empty sets.
+        sal_Int64 getHeight() const
+        {
+            return maRangeY.getRange();
+        }
+
+        /// yields true if point is contained in set
+        bool isInside(const B2ITuple& rTuple) const
+        {
+            return (
+                maRangeX.isInside(rTuple.getX())
+                && maRangeY.isInside(rTuple.getY())
+                );
+        }
+
+        /// add point to the set, expanding as necessary
+        void expand(const B2ITuple& rTuple)
+        {
+            maRangeX.expand(rTuple.getX());
+            maRangeY.expand(rTuple.getY());
+        }
+
+        /// calc set intersection
+        void intersect(const B2IBox& rBox)
+        {
+            maRangeX.intersect(rBox.maRangeX);
+            maRangeY.intersect(rBox.maRangeY);
+        }
+
+    private:
+        BasicBox        maRangeX;
+        BasicBox        maRangeY;
+    };
+
+} // end of namespace basegfx
+
+template< typename charT, typename traits >
+inline std::basic_ostream<charT, traits> & operator <<(
+    std::basic_ostream<charT, traits> & stream, const basegfx::B2IBox& box )
+{
+    if (box.isEmpty())
+        return stream << "EMPTY";
+    else
+        return stream << box.getWidth() << 'x' << box.getHeight()
+                      << "@(" << box.getMinX() << "," << box.getMinY() << ")";
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2irange.hxx b/include/basegfx/range/b2irange.hxx
new file mode 100644
index 000000000..f24526880
--- /dev/null
+++ b/include/basegfx/range/b2irange.hxx
@@ -0,0 +1,259 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <ostream>
+#include <vector>
+
+#include <basegfx/point/b2ipoint.hxx>
+#include <basegfx/tuple/b2ituple.hxx>
+#include <basegfx/tuple/b2i64tuple.hxx>
+#include <basegfx/range/basicrange.hxx>
+#include <basegfx/basegfxdllapi.h>
+
+namespace basegfx
+{
+    /** A two-dimensional interval over integers
+
+        This is a set of real numbers, bounded by a lower and an upper
+        pair. All inbetween values are included in the set (see also
+        http://en.wikipedia.org/wiki/Interval_%28mathematics%29).
+
+        Probably you rather want B2IBox for integers.
+
+        The set is closed, i.e. the upper and the lower bound are
+        included (if you're used to the notation - we're talking about
+        [a,b] here, compared to half-open [a,b) or open intervals
+        (a,b)).
+
+        That means, isInside(val) will return true also for values of
+        val=a or val=b.
+
+        @see B2IBox
+     */
+    class B2IRange
+    {
+    public:
+        typedef sal_Int32       ValueType;
+        typedef Int32Traits     TraitsType;
+
+        B2IRange() {}
+
+        /// Create degenerate interval consisting of a single point
+        explicit B2IRange(const B2ITuple& rTuple)
+        :   maRangeX(rTuple.getX()),
+            maRangeY(rTuple.getY())
+        {
+        }
+
+        /// Create proper interval between the two given integer pairs
+        B2IRange(sal_Int32 x1,
+                 sal_Int32 y1,
+                 sal_Int32 x2,
+                 sal_Int32 y2)
+        :   maRangeX(x1),
+            maRangeY(y1)
+        {
+            maRangeX.expand(x2);
+            maRangeY.expand(y2);
+        }
+
+        /// Create proper interval between the two given points
+        B2IRange(const B2ITuple& rTuple1,
+                 const B2ITuple& rTuple2)
+        :   maRangeX(rTuple1.getX()),
+            maRangeY(rTuple1.getY())
+        {
+            expand( rTuple2 );
+        }
+
+        /** Check if the interval set is empty
+
+            @return false, if no value is in this set - having a
+            single point included will already return true.
+         */
+        bool isEmpty() const
+        {
+            return maRangeX.isEmpty() || maRangeY.isEmpty();
+        }
+
+        /// reset the object to empty state again, clearing all values
+        void reset()
+        {
+            maRangeX.reset();
+            maRangeY.reset();
+        }
+
+        bool operator==( const B2IRange& rRange ) const
+        {
+            return (maRangeX == rRange.maRangeX
+                && maRangeY == rRange.maRangeY);
+        }
+
+        bool operator!=( const B2IRange& rRange ) const
+        {
+            return (maRangeX != rRange.maRangeX
+                || maRangeY != rRange.maRangeY);
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMinX() const
+        {
+            return maRangeX.getMinimum();
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMinY() const
+        {
+            return maRangeY.getMinimum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMaxX() const
+        {
+            return maRangeX.getMaximum();
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        sal_Int32 getMaxY() const
+        {
+            return maRangeY.getMaximum();
+        }
+
+        /// return difference between upper and lower X value. returns 0 for empty sets.
+        sal_Int64 getWidth() const
+        {
+            return maRangeX.getRange();
+        }
+
+        /// return difference between upper and lower Y value. returns 0 for empty sets.
+        sal_Int64 getHeight() const
+        {
+            return maRangeY.getRange();
+        }
+
+        /// get lower bound of the set. returns arbitrary values for empty sets.
+        B2IPoint getMinimum() const
+        {
+            return B2IPoint(
+                maRangeX.getMinimum(),
+                maRangeY.getMinimum()
+                );
+        }
+
+        /// get upper bound of the set. returns arbitrary values for empty sets.
+        B2IPoint getMaximum() const
+        {
+            return B2IPoint(
+                maRangeX.getMaximum(),
+                maRangeY.getMaximum()
+                );
+        }
+
+        /// return difference between upper and lower point. returns (0,0) for empty sets.
+        B2I64Tuple getRange() const
+        {
+            return B2I64Tuple(
+                maRangeX.getRange(),
+                maRangeY.getRange()
+                );
+        }
+
+        /// yields true if given point is contained in set
+        bool isInside(const B2ITuple& rTuple) const
+        {
+            return (
+                maRangeX.isInside(rTuple.getX())
+                && maRangeY.isInside(rTuple.getY())
+                );
+        }
+
+        /// add point to the set, expanding as necessary
+        void expand(const B2ITuple& rTuple)
+        {
+            maRangeX.expand(rTuple.getX());
+            maRangeY.expand(rTuple.getY());
+        }
+
+        /// add rRange to the set, expanding as necessary
+        void expand(const B2IRange& rRange)
+        {
+            maRangeX.expand(rRange.maRangeX);
+            maRangeY.expand(rRange.maRangeY);
+        }
+
+        /// calc set intersection
+        void intersect(const B2IRange& rRange)
+        {
+            maRangeX.intersect(rRange.maRangeX);
+            maRangeY.intersect(rRange.maRangeY);
+        }
+
+        B2ITuple clamp(const B2ITuple& rTuple) const
+        {
+            return B2ITuple(
+                maRangeX.clamp(rTuple.getX()),
+                maRangeY.clamp(rTuple.getY()));
+        }
+
+    private:
+        typedef ::basegfx::BasicRange< ValueType, TraitsType >  MyBasicRange;
+
+        MyBasicRange        maRangeX;
+        MyBasicRange        maRangeY;
+    };
+
+    /** Compute the set difference of the two given ranges
+
+        This method calculates the symmetric difference (aka XOR)
+        between the two given ranges, and returning the resulting
+        ranges. Thus, the result will contain all areas where one, but
+        not both ranges lie.
+
+        @param o_rResult
+        Result vector. The up to four difference ranges are returned
+        within this vector
+
+        @param rFirst
+        The first range
+
+        @param rSecond
+        The second range
+
+        @return the input vector
+     */
+    BASEGFX_DLLPUBLIC ::std::vector< B2IRange >& computeSetDifference( ::std::vector< B2IRange >&   o_rResult,
+                                                     const B2IRange&            rFirst,
+                                                     const B2IRange&            rSecond );
+
+    template< typename charT, typename traits >
+    inline std::basic_ostream<charT, traits> & operator <<(
+        std::basic_ostream<charT, traits> & stream, const B2IRange& range )
+    {
+        if (range.isEmpty())
+            return stream << "EMPTY";
+        else
+            return stream << range.getWidth() << 'x' << range.getHeight()
+                          << "@(" << range.getMinX() << "," << range.getMinY() << ")";
+    }
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b2irectangle.hxx b/include/basegfx/range/b2irectangle.hxx
new file mode 100644
index 000000000..2c6a932a2
--- /dev/null
+++ b/include/basegfx/range/b2irectangle.hxx
@@ -0,0 +1,33 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/range/b2irange.hxx>
+
+namespace basegfx
+{
+    // syntactic sugar: a B2IRange exactly models a Rectangle, thus,
+    // for interface clarity, we provide an alias name
+
+    /// Alias name for interface clarity (not everybody is aware of the identity)
+    typedef B2IRange B2IRectangle;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/b3drange.hxx b/include/basegfx/range/b3drange.hxx
new file mode 100644
index 000000000..338c4f54a
--- /dev/null
+++ b/include/basegfx/range/b3drange.hxx
@@ -0,0 +1,227 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/vector/b3dvector.hxx>
+#include <basegfx/point/b3dpoint.hxx>
+#include <basegfx/tuple/b3dtuple.hxx>
+#include <basegfx/range/basicrange.hxx>
+#include <basegfx/basegfxdllapi.h>
+
+namespace basegfx
+{
+    class B3DHomMatrix;
+
+    class SAL_WARN_UNUSED B3DRange
+    {
+        typedef ::basegfx::BasicRange< double, DoubleTraits >   MyBasicRange;
+
+        MyBasicRange            maRangeX;
+        MyBasicRange            maRangeY;
+        MyBasicRange            maRangeZ;
+
+    public:
+        B3DRange() {}
+
+        explicit B3DRange(const B3DTuple& rTuple)
+        :   maRangeX(rTuple.getX()),
+            maRangeY(rTuple.getY()),
+            maRangeZ(rTuple.getZ())
+        {
+        }
+
+        B3DRange(double x1,
+                 double y1,
+                 double z1,
+                 double x2,
+                 double y2,
+                 double z2)
+        :   maRangeX(x1),
+            maRangeY(y1),
+            maRangeZ(z1)
+        {
+            maRangeX.expand(x2);
+            maRangeY.expand(y2);
+            maRangeZ.expand(z2);
+        }
+
+        B3DRange(const B3DTuple& rTuple1,
+                 const B3DTuple& rTuple2)
+        :   maRangeX(rTuple1.getX()),
+            maRangeY(rTuple1.getY()),
+            maRangeZ(rTuple1.getZ())
+        {
+            expand(rTuple2);
+        }
+
+        bool isEmpty() const
+        {
+            return (
+                maRangeX.isEmpty()
+                || maRangeY.isEmpty()
+                || maRangeZ.isEmpty()
+                );
+        }
+
+        void reset()
+        {
+            maRangeX.reset();
+            maRangeY.reset();
+            maRangeZ.reset();
+        }
+
+        bool operator==( const B3DRange& rRange ) const
+        {
+            return (maRangeX == rRange.maRangeX
+                && maRangeY == rRange.maRangeY
+                && maRangeZ == rRange.maRangeZ);
+        }
+
+        bool operator!=( const B3DRange& rRange ) const
+        {
+            return (maRangeX != rRange.maRangeX
+                || maRangeY != rRange.maRangeY
+                || maRangeZ != rRange.maRangeZ);
+        }
+
+        double getMinX() const
+        {
+            return maRangeX.getMinimum();
+        }
+
+        double getMinY() const
+        {
+            return maRangeY.getMinimum();
+        }
+
+        double getMinZ() const
+        {
+            return maRangeZ.getMinimum();
+        }
+
+        double getMaxX() const
+        {
+            return maRangeX.getMaximum();
+        }
+
+        double getMaxY() const
+        {
+            return maRangeY.getMaximum();
+        }
+
+        double getMaxZ() const
+        {
+            return maRangeZ.getMaximum();
+        }
+
+        double getWidth() const
+        {
+            return maRangeX.getRange();
+        }
+
+        double getHeight() const
+        {
+            return maRangeY.getRange();
+        }
+
+        double getDepth() const
+        {
+            return maRangeZ.getRange();
+        }
+
+        B3DVector getRange() const
+        {
+            return B3DVector(
+                maRangeX.getRange(),
+                maRangeY.getRange(),
+                maRangeZ.getRange()
+                );
+        }
+
+        B3DPoint getCenter() const
+        {
+            return B3DPoint(
+                maRangeX.getCenter(),
+                maRangeY.getCenter(),
+                maRangeZ.getCenter()
+                );
+        }
+
+        bool overlaps(const B3DRange& rRange) const
+        {
+            return (
+                maRangeX.overlaps(rRange.maRangeX)
+                && maRangeY.overlaps(rRange.maRangeY)
+                && maRangeZ.overlaps(rRange.maRangeZ)
+                );
+        }
+
+        void expand(const B3DTuple& rTuple)
+        {
+            maRangeX.expand(rTuple.getX());
+            maRangeY.expand(rTuple.getY());
+            maRangeZ.expand(rTuple.getZ());
+        }
+
+        void expand(const B3DRange& rRange)
+        {
+            maRangeX.expand(rRange.maRangeX);
+            maRangeY.expand(rRange.maRangeY);
+            maRangeZ.expand(rRange.maRangeZ);
+        }
+
+        void grow(double fValue)
+        {
+            maRangeX.grow(fValue);
+            maRangeY.grow(fValue);
+            maRangeZ.grow(fValue);
+        }
+
+        /// clamp value on range
+        B3DTuple clamp(const B3DTuple& rTuple) const
+        {
+            return B3DTuple(
+                maRangeX.clamp(rTuple.getX()),
+                maRangeY.clamp(rTuple.getY()),
+                maRangeZ.clamp(rTuple.getZ()));
+        }
+
+         BASEGFX_DLLPUBLIC void transform(const B3DHomMatrix& rMatrix);
+
+        /** Transform Range by given transformation matrix.
+
+            This operation transforms the Range by transforming all eight possible
+            extrema points (corners) of the given range and building a new one.
+            This means that the range will grow evtl. when a shear and/or rotation
+            is part of the transformation.
+        */
+        B3DRange& operator*=( const ::basegfx::B3DHomMatrix& rMat );
+
+        /** Get a range filled with (0.0, 0.0, 0.0, 1.0, 1.0, 1.0) */
+        static const B3DRange& getUnitB3DRange();
+    };
+
+    /** Transform B3DRange by given transformation matrix (see operator*=())
+    */
+    B3DRange operator*( const B3DHomMatrix& rMat, const B3DRange& rB2DRange );
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/basicbox.hxx b/include/basegfx/range/basicbox.hxx
new file mode 100644
index 000000000..123d2b1b3
--- /dev/null
+++ b/include/basegfx/range/basicbox.hxx
@@ -0,0 +1,68 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <basegfx/range/basicrange.hxx>
+
+
+namespace basegfx
+{
+    /** Explicitly different from BasicRange, handling the inside predicates
+        differently.
+
+        This is modelled after how polygon fill algorithms set pixel -
+        typically excluding rightmost and bottommost ones.
+     */
+    class BasicBox : public BasicRange< sal_Int32, Int32Traits >
+    {
+        typedef BasicRange< sal_Int32, Int32Traits > Base;
+    public:
+        BasicBox() {}
+
+        explicit BasicBox( sal_Int32 nValue ) :
+            Base( nValue )
+        {
+        }
+
+        bool isEmpty() const
+        {
+            return mnMinimum >= mnMaximum;
+        }
+
+        using Base::isInside;
+
+        bool isInside(sal_Int32 nValue) const
+        {
+            if(isEmpty())
+            {
+                return false;
+            }
+            else
+            {
+                return (nValue >= mnMinimum) && (nValue < mnMaximum);
+            }
+        }
+
+        using Base::overlaps;
+    };
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/include/basegfx/range/basicrange.hxx b/include/basegfx/range/basicrange.hxx
new file mode 100644
index 000000000..429f31957
--- /dev/null
+++ b/include/basegfx/range/basicrange.hxx
@@ -0,0 +1,306 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   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 .
+ */
+
+#pragma once
+
+#include <sal/types.h>
+#include <float.h>
+#include <basegfx/numeric/ftools.hxx>
+
+
+namespace basegfx
+{
+    template< typename T, typename Traits > class BasicRange
+    {
+    protected:
+        T       mnMinimum;
+        T       mnMaximum;
+
+    public:
+        typedef T       ValueType;
+        typedef Traits  TraitsType;
+
+        BasicRange() :
+            mnMinimum(Traits::maxVal()),
+            mnMaximum(Traits::minVal())
+        {
+        }
+
+        explicit BasicRange( T nValue ) :
+            mnMinimum(nValue),
+            mnMaximum(nValue)
+        {
+        }
+
+        void reset()
+        {
+            mnMinimum = Traits::maxVal();
+            mnMaximum = Traits::minVal();
+        }
+
+        bool isEmpty() const
+        {
+            return Traits::maxVal() == mnMinimum;
+        }
+
+        T getMinimum() const { return mnMinimum; }
+        T getMaximum() const { return mnMaximum; }
+
+        double getCenter() const
+        {
+            if(isEmpty())
+            {
+                return 0.0;
+            }
+            else
+            {
+                return ((mnMaximum + mnMinimum) / 2.0);
+            }
+        }
+
+        bool isInside(T nValue) const
+        {
+            if(isEmpty())
+            {
+                return false;
+            }
+            else
+            {
+                return (nValue >= mnMinimum) && (nValue <= mnMaximum);
+            }
+        }
+
+        bool isInside(const BasicRange& rRange) const
+        {
+            if(isEmpty())
+            {
+                return false;
+            }
+            else
+            {
+                if(rRange.isEmpty())
+                {
+                    return false;
+                }
+                else
+                {
+                    return (rRange.mnMinimum >= mnMinimum) && (rRange.mnMaximum <= mnMaximum);
+                }
+            }
+        }
+
+        bool overlaps(const BasicRange& rRange) const
+        {
+            if(isEmpty())
+            {
+                return false;
+            }
+            else
+            {
+                if(rRange.isEmpty())
+                {
+                    return false;
+                }
+                else
+                {
+                    return !((rRange.mnMaximum < mnMinimum) || (rRange.mnMinimum > mnMaximum));
+                }
+            }
+        }
+
+        bool overlapsMore(const BasicRange& rRange) const
+        {
+            if(isEmpty() || rRange.isEmpty())
+                return false;
+            // returns true if the overlap is more than just a touching at the limits
+            return ((rRange.mnMaximum > mnMinimum) && (rRange.mnMinimum < mnMaximum));
+        }
+
+        bool operator==( const BasicRange& rRange ) const
+        {
+            return (mnMinimum == rRange.mnMinimum && mnMaximum == rRange.mnMaximum);
+        }
+
+        bool operator!=( const BasicRange& rRange ) const
+        {
+            return (mnMinimum != rRange.mnMinimum || mnMaximum != rRange.mnMaximum);
+        }
+
+        bool equal(const BasicRange& rRange) const
+        {
+            return (
+                fTools::equal(mnMinimum, rRange.mnMinimum) &&
+                fTools::equal(mnMaximum, rRange.mnMaximum));
+        }
+
+        void expand(T nValue)
+        {
+            if(isEmpty())
+            {
+                mnMinimum = mnMaximum = nValue;
+            }
+            else
+            {
+// Silence over-eager warning emitted at least by GCC 4.9.2 in certain
+// instantiations:
+#if defined __GNUC__ && !defined __clang__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstrict-overflow"
+#endif
+                if(nValue < mnMinimum)
+#if defined __GNUC__ && !defined __clang__
+#pragma GCC diagnostic pop
+#endif
+                {
+                    mnMinimum = nValue;
+                }
+
+                if(nValue > mnMaximum)
+                {
+                    mnMaximum = nValue;
+                }
+            }
+        }
+
+        void expand(const BasicRange& rRange)
+        {
+            if(isEmpty())
+            {
+                mnMinimum = rRange.mnMinimum;
+                mnMaximum = rRange.mnMaximum;
+            }
+            else
+            {
+                if(!rRange.isEmpty())
+                {
+                    if(rRange.mnMinimum < mnMinimum)
+                    {
+                        mnMinimum = rRange.mnMinimum;
+                    }
+
+                    if(rRange.mnMaximum > mnMaximum)
+                    {
+                        mnMaximum = rRange.mnMaximum;
+                    }
+                }
+            }
+        }
+
+        void intersect(const BasicRange& rRange)
+        {
+            // here, overlaps also tests all isEmpty() conditions already.
+            if( !overlaps( rRange ) )
+            {
+                reset();
+            }
+            else
+            {
+                if(rRange.mnMinimum > mnMinimum)
+                {
+                    mnMinimum = rRange.mnMinimum;
+                }
+
+                if(rRange.mnMaximum < mnMaximum)
+                {
+                    mnMaximum = rRange.mnMaximum;
+                }
+            }
+        }
+
+        void grow(T nValue)
+        {
+            if(!isEmpty())
+            {
+                bool bLessThanZero(nValue < 0);
+
+                if(nValue > 0 || bLessThanZero)
+                {
+                    mnMinimum -= nValue;
+                    mnMaximum += nValue;
+
+                    if(bLessThanZero)
+                    {
+                        // test if range did collapse
+                        if(mnMinimum > mnMaximum)
+                        {
+                            // if yes, collapse to center
+                            mnMinimum = mnMaximum = (mnMinimum + mnMaximum) / 2;
+                        }
+                    }
+                }
+            }
+        }
+
+        T clamp(T nValue) const
+        {
+            if(isEmpty())
+            {
+                return nValue;
+            }
+            else
+            {
+                if(nValue < mnMinimum)
+                {
+                    return mnMinimum;
+                }
+
+                if(nValue > mnMaximum)
+                {
+                    return mnMaximum;
+                }
+
+                return nValue;
+            }
+        }
+
+        typename Traits::DifferenceType getRange() const
+        {
+            if(isEmpty())
+            {
+                return Traits::neutral();
+            }
+            else
+            {
+                return (mnMaximum - mnMinimum);
+            }
+        }
+    };
+
+    // some pre-fabricated traits
+    struct DoubleTraits
+    {
+        static double minVal() { return DBL_MIN; };
+        static double maxVal() { return DBL_MAX; };
+        static double neutral() { return 0.0; };
+
+        typedef double DifferenceType;
+    };
+
+    struct Int32Traits
+    {
+        static sal_Int32 minVal() { return SAL_MIN_INT32; };
+        static sal_Int32 maxVal() { return SAL_MAX_INT32; };
+        static sal_Int32 neutral() { return 0; };
+
+        typedef sal_Int64 DifferenceType;
+    };
+
+} // end of namespace basegfx
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */