Merge rendering cache branch (GSoC 2011)

(bzr r10579)

9 files changed, 173 insertions, 36 deletions

diff --git a/src/2geom/affine.cpp b/src/2geom/affine.cpp
index 2a1f18d77..c31b9ba90 100644
--- a/src/2geom/affine.cpp
+++ b/src/2geom/affine.cpp
@@ -410,6 +410,9 @@ Affine &Affine::operator*=(Affine const &o) {
 }
 
 //TODO: What's this!?!
+/** Given a matrix m such that unit_circle = m*x, this returns the
+ * quadratic form x*A*x = 1.
+ * @relates Affine */
 Affine elliptic_quadratic_form(Affine const &m) {
     double od = m[0] * m[1]  +  m[2] * m[3];
     Affine ret (m[0]*m[0] + m[1]*m[1], od,
@@ -469,6 +472,15 @@ Eigen::Eigen(double m[2][2]) {
         vectors[i] = Point(0,0);
 }
 
+/** @brief Nearness predicate for affine transforms
+ * @returns True if all entries of matrices are within eps of each other */
+bool are_near(Affine const &a, Affine const &b, Coord eps)
+{
+    return are_near(a[0], b[0], eps) && are_near(a[1], b[1], eps) &&
+           are_near(a[2], b[2], eps) && are_near(a[3], b[3], eps) &&
+           are_near(a[4], b[4], eps) && are_near(a[5], b[5], eps);
+}
+
 }  //namespace Geom
 
 /*
diff --git a/src/2geom/affine.h b/src/2geom/affine.h
index d7a7a0692..22f8bd9f5 100644
--- a/src/2geom/affine.h
+++ b/src/2geom/affine.h
@@ -200,9 +200,8 @@ inline std::ostream &operator<< (std::ostream &out_file, const Geom::Affine &m)
     return out_file;
 }
 
-/** Given a matrix m such that unit_circle = m*x, this returns the
- * quadratic form x*A*x = 1.
- * @relates Affine */
+// Affine factories
+Affine from_basis(const Point x_basis, const Point y_basis, const Point offset=Point(0,0));
 Affine elliptic_quadratic_form(Affine const &m);
 
 /** Given a matrix (ignoring the translation) this returns the eigen
@@ -215,9 +214,6 @@ public:
     Eigen(double M[2][2]);
 };
 
-// Affine factories
-Affine from_basis(const Point x_basis, const Point y_basis, const Point offset=Point(0,0));
-
 /** @brief Create an identity matrix.
  * This is a convenience function identical to Affine::identity(). */
 inline Affine identity() {
@@ -239,6 +235,8 @@ inline Affine Affine::identity() {
     return ret; // allow NRVO
 }
 
+bool are_near(Affine const &a1, Affine const &a2, Coord eps=EPSILON);
+
 } // end namespace Geom
 
 #endif // LIB2GEOM_SEEN_AFFINE_H
diff --git a/src/2geom/coord.h b/src/2geom/coord.h
index f7bf2c5d0..90e776665 100644
--- a/src/2geom/coord.h
+++ b/src/2geom/coord.h
@@ -34,6 +34,7 @@
 
 #include <cmath>
 #include <limits>
+#include <boost/operators.hpp>
 #include <2geom/forward.h>
 
 namespace Geom {
@@ -62,6 +63,9 @@ inline bool rel_error_bound(Coord a, Coord b, double eps=EPSILON) { return a <=
 template <typename C>
 struct CoordTraits {};
 
+// NOTE: operator helpers for Rect and Interval are defined here.
+// This is to avoid increasing their size through multiple inheritance.
+
 template<>
 struct CoordTraits<IntCoord> {
     typedef IntPoint PointType;
@@ -69,6 +73,22 @@ struct CoordTraits<IntCoord> {
     typedef OptIntInterval OptIntervalType;
     typedef IntRect RectType;
     typedef OptIntRect OptRectType;
+
+    typedef
+      boost::equality_comparable< IntervalType
+    , boost::additive< IntervalType
+    , boost::additive< IntervalType, IntCoord
+    , boost::orable< IntervalType
+      > > > >
+        IntervalOps;
+
+    typedef
+      boost::equality_comparable< RectType
+    , boost::orable< RectType
+    , boost::orable< RectType, OptRectType
+    , boost::additive< RectType, PointType 
+      > > > >
+        RectOps;
 };
 
 template<>
@@ -78,6 +98,24 @@ struct CoordTraits<Coord> {
     typedef OptInterval OptIntervalType;
     typedef Rect RectType;
     typedef OptRect OptRectType;
+
+    typedef
+      boost::equality_comparable< IntervalType
+    , boost::additive< IntervalType
+    , boost::multipliable< IntervalType
+    , boost::orable< IntervalType
+    , boost::arithmetic< IntervalType, Coord
+      > > > > >
+        IntervalOps;
+
+    typedef
+      boost::equality_comparable< RectType
+    , boost::orable< RectType
+    , boost::orable< RectType, OptRectType
+    , boost::additive< RectType, PointType
+    , boost::multipliable< RectType, Affine
+      > > > > >
+        RectOps;
 };
 
 } // end namespace Geom
diff --git a/src/2geom/generic-interval.h b/src/2geom/generic-interval.h
index a32e97d4b..0212da676 100644
--- a/src/2geom/generic-interval.h
+++ b/src/2geom/generic-interval.h
@@ -34,7 +34,7 @@
 #include <cassert>
 #include <boost/none.hpp>
 #include <boost/optional.hpp>
-#include <boost/operators.hpp>
+#include <2geom/coord.h>
 
 namespace Geom {
 
@@ -47,11 +47,7 @@ class GenericOptInterval;
  */
 template <typename C>
 class GenericInterval
-    : boost::equality_comparable< GenericInterval<C>
-    , boost::additive< GenericInterval<C>
-    , boost::additive< GenericInterval<C>, C
-    , boost::orable< GenericInterval<C>
-      > > > >
+    : CoordTraits<C>::IntervalOps
 {
     typedef GenericInterval<C> Self;
 protected:
diff --git a/src/2geom/generic-rect.h b/src/2geom/generic-rect.h
index 2db30dfa9..efe499809 100644
--- a/src/2geom/generic-rect.h
+++ b/src/2geom/generic-rect.h
@@ -42,6 +42,7 @@
 
 #include <limits>
 #include <boost/optional.hpp>
+#include <2geom/coord.h>
 
 namespace Geom {
 
@@ -54,11 +55,7 @@ class GenericOptRect;
  */
 template <typename C>
 class GenericRect
-    : boost::additive< typename CoordTraits<C>::RectType, typename CoordTraits<C>::PointType
-    , boost::equality_comparable< typename CoordTraits<C>::RectType
-    , boost::orable< typename CoordTraits<C>::RectType
-    , boost::orable< typename CoordTraits<C>::RectType, typename CoordTraits<C>::OptRectType
-      > > > >
+    : CoordTraits<C>::RectOps
 {
     typedef typename CoordTraits<C>::IntervalType CInterval;
     typedef typename CoordTraits<C>::PointType CPoint;
@@ -131,15 +128,22 @@ public:
 
     /// @name Inspect dimensions.
     /// @{
-    CInterval &operator[](unsigned i)              { return f[i]; }
+    CInterval &operator[](unsigned i)             { return f[i]; }
     CInterval const &operator[](unsigned i) const { return f[i]; }
+    CInterval &operator[](Dim2 d)                 { return f[d]; }
+    CInterval const &operator[](Dim2 d) const     { return f[d]; }
 
+    /** @brief Get the corner of the rectangle with smallest coordinate values.
+     * In 2Geom standard coordinate system, this means upper left. */
     CPoint min() const { return CPoint(f[X].min(), f[Y].min()); }
+    /** @brief Get the corner of the rectangle with largest coordinate values.
+     * In 2Geom standard coordinate system, this means lower right. */
     CPoint max() const { return CPoint(f[X].max(), f[Y].max()); }
     /** @brief Return the n-th corner of the rectangle.
-     * If the Y axis grows upwards, this returns corners in clockwise order
-     * starting from the lower left. If Y grows downwards, it returns the corners
-     * in counter-clockwise order starting from the upper left. */
+     * Returns corners in the direction of growing angles, starting from
+     * the one given by min(). For the standard coordinate system used
+     * in 2Geom (+Y downwards), this means clockwise starting from
+     * the upper left. */
     CPoint corner(unsigned i) const {
         switch(i % 4) {
             case 0:  return CPoint(f[X].min(), f[Y].min());
@@ -196,10 +200,10 @@ public:
     }
 
     /** @brief Check whether the rectangles have any common points.
-     * A non-empty rectangle will not intersect empty rectangles. */
+     * Empty rectangles will not intersect with any other rectangle. */
     inline bool intersects(OptCRect const &r) const;
     /** @brief Check whether the rectangle includes all points in the given rectangle.
-     * A non-empty rectangle will contain any empty rectangle. */
+     * Empty rectangles will be contained in any non-empty rectangle. */
     inline bool contains(OptCRect const &r) const;
 
     /** @brief Check whether the given point is within the rectangle. */
@@ -224,11 +228,11 @@ public:
     void expandTo(CPoint const &p)        { 
         f[X].expandTo(p[X]);  f[Y].expandTo(p[Y]);
     }
-    /** @brief Enlarge the rectangle to contain the given rectangle. */
+    /** @brief Enlarge the rectangle to contain the argument. */
     void unionWith(CRect const &b) { 
         f[X].unionWith(b[X]); f[Y].unionWith(b[Y]);
     }
-    /** @brief Enlarge the rectangle to contain the given rectangle.
+    /** @brief Enlarge the rectangle to contain the argument.
      * Unioning with an empty rectangle results in no changes. */
     void unionWith(OptCRect const &b);
 
@@ -244,7 +248,8 @@ public:
      * This will expand the width by the X coordinate of the point in both directions
      * and the height by Y coordinate of the point. Negative coordinate values will
      * shrink the rectangle. If <code>-p[X]</code> is larger than half of the width,
-     * the X interval will contain only the X coordinate of the midpoint; same for height. */
+     * the X interval will contain only the X coordinate of the midpoint;
+     * same for height. */
     void expandBy(CPoint const &p) { 
         f[X].expandBy(p[X]);  f[Y].expandBy(p[Y]);
     }
@@ -297,30 +302,66 @@ class GenericOptRect
     typedef typename CoordTraits<C>::OptRectType OptCRect;
     typedef boost::optional<CRect> Base;
 public:
+    /// @name Create potentially empty rectangles.
+    /// @{
     GenericOptRect() : Base() {}
     GenericOptRect(GenericRect<C> const &a) : Base(CRect(a)) {}
     GenericOptRect(CPoint const &a, CPoint const &b) : Base(CRect(a, b)) {}
-    /**
-     * Creates an empty OptRect when one of the argument intervals is empty.
-     */
+    /// Creates an empty OptRect when one of the argument intervals is empty.
     GenericOptRect(OptCInterval const &x_int, OptCInterval const &y_int) {
         if (x_int && y_int) {
             *this = CRect(*x_int, *y_int);
         }
         // else, stay empty.
     }
+    /** @brief Create a rectangle from a range of points.
+     * The resulting rectangle will contain all ponts from the range.
+     * If the range contains no points, the result will be an empty rectangle.
+     * The return type of iterators must be convertible to the corresponding
+     * point type (Point or IntPoint).
+     * @param start Beginning of the range
+     * @param end   End of the range
+     * @return Rectangle that contains all points from [start, end). */
+    template <typename InputIterator>
+    static OptCRect from_range(InputIterator start, InputIterator end) {
+        OptCRect result;
+        for (; start != end; ++start) {
+            result.expandTo(*start);
+        }
+        return result;
+    }
+    /// @}
 
+    /// @name Check other rectangles and points for inclusion.
+    /// @{
     /** @brief Check for emptiness. */
     inline bool isEmpty() const { return !*this; };
-
+    /** @brief Check whether the rectangles have any common points.
+     * Empty rectangles will not intersect with any other rectangle. */
     bool intersects(CRect const &r) const { return r.intersects(*this); }
+    /** @brief Check whether the rectangle includes all points in the given rectangle.
+     * Empty rectangles will be contained in any non-empty rectangle. */
     bool contains(CRect const &r) const { return *this && (*this)->contains(r); }
 
+    /** @brief Check whether the rectangles have any common points.
+     * Empty rectangles will not intersect with any other rectangle.
+     * Two empty rectangles will not intersect each other. */
     bool intersects(OptCRect const &r) const { return *this && (*this)->intersects(r); }
+    /** @brief Check whether the rectangle includes all points in the given rectangle.
+     * Empty rectangles will be contained in any non-empty rectangle.
+     * An empty rectangle will not contain other empty rectangles. */
     bool contains(OptCRect const &r) const { return *this && (*this)->contains(r); }
 
+    /** @brief Check whether the given point is within the rectangle.
+     * An empty rectangle will not contain any points. */
     bool contains(CPoint const &p) const { return *this && (*this)->contains(p); }
+    /// @}
 
+    /// @name Modify the potentially empty rectangle.
+    /// @{
+    /** @brief Enlarge the rectangle to contain the argument.
+     * If this rectangle is empty, after callng this method it will
+     * be equal to the argument. */
     void unionWith(CRect const &b) {
         if (*this) {
             (*this)->unionWith(b);
@@ -328,9 +369,16 @@ public:
             *this = b;
         }
     }
+    /** @brief Enlarge the rectangle to contain the argument.
+     * Unioning with an empty rectangle results in no changes.
+     * If this rectangle is empty, after calling this method it will
+     * be equal to the argument. */
     void unionWith(OptCRect const &b) {
         if (b) unionWith(*b);
     }
+    /** @brief Leave only the area overlapping with the argument.
+     * If the rectangles do not have any points in common, after calling
+     * this method the rectangle will be empty. */
     void intersectWith(CRect const &b) {
         if (!*this) return;
         OptCInterval x = (**this)[X] & b[X], y = (**this)[Y] & b[Y];
@@ -340,6 +388,9 @@ public:
             *(static_cast<Base*>(this)) = boost::none;
         }
     }
+    /** @brief Leave only the area overlapping with the argument.
+     * If the argument is empty or the rectangles do not have any points
+     * in common, after calling this method the rectangle will be empty. */
     void intersectWith(OptCRect const &b) {
         if (b) {
             intersectWith(*b);
@@ -347,18 +398,36 @@ public:
             *(static_cast<Base*>(this)) = boost::none;
         }
     }
+    /** @brief Create or enlarge the rectangle to contain the given point.
+     * If the rectangle is empty, after calling this method it will be non-empty
+     * and it will contain only the given point. */
+    void expandTo(CPoint const &p) {
+        if (*this) {
+            (*this).expandTo(p);
+        } else {
+            *this = CRect(p, p);
+        }
+    }
+    /// @}
+    
+    /// @name Operators
+    /// @{
+    /** @brief Union with @a b */
     GenericOptRect<C> &operator|=(OptCRect const &b) {
         unionWith(b);
         return *this;
     }
+    /** @brief Intersect with @a b */
     GenericOptRect<C> &operator&=(CRect const &b) {
         intersectWith(b);
         return *this;
     }
+    /** @brief Intersect with @a b */
     GenericOptRect<C> &operator&=(OptCRect const &b) {
         intersectWith(b);
         return *this;
     }
+    /// @}
 };
 
 template <typename C>
diff --git a/src/2geom/interval.h b/src/2geom/interval.h
index e95da4811..711eaa5e2 100644
--- a/src/2geom/interval.h
+++ b/src/2geom/interval.h
@@ -63,9 +63,6 @@ typedef GenericOptInterval<Coord> OptInterval;
  */
 class Interval
     : public GenericInterval<Coord>
-    , boost::multipliable< Interval
-    , boost::multiplicative< Interval, Coord
-      > >
 {
     typedef GenericInterval<Coord> Base;
 public:
diff --git a/src/2geom/linear.h b/src/2geom/linear.h
index df6dd9904..448ab3bb7 100644
--- a/src/2geom/linear.h
+++ b/src/2geom/linear.h
@@ -55,7 +55,7 @@ class SBasis;
 class Linear{
 public:
     double a[2];
-    Linear() {}
+    Linear() { a[0] = 0; a[1] = 0; }
     Linear(double aa, double b) {a[0] = aa; a[1] = b;}
     Linear(double aa) {a[0] = aa; a[1] = aa;}
 
diff --git a/src/2geom/rect.h b/src/2geom/rect.h
index f7d331523..b79a0a04f 100644
--- a/src/2geom/rect.h
+++ b/src/2geom/rect.h
@@ -59,7 +59,6 @@ typedef GenericOptRect<Coord> OptRect;
  */
 class Rect
     : public GenericRect<Coord>
-    , boost::multipliable< Rect, Affine >
 {
     typedef GenericRect<Coord> Base;
 public:
diff --git a/src/2geom/transforms.h b/src/2geom/transforms.h
index 5627e8b6f..eaf869056 100644
--- a/src/2geom/transforms.h
+++ b/src/2geom/transforms.h
@@ -45,10 +45,11 @@ namespace Geom {
  * @ingroup Concepts */
 template <typename T>
 struct TransformConcept {
-    T t;
+    T t, t2;
     Affine m;
     Point p;
     bool bool_;
+    Coord epsilon;
     void constraints() {
         m = t;  //implicit conversion
         m *= t;
@@ -63,6 +64,8 @@ struct TransformConcept {
         bool_ = (t != t);
         t = T::identity();
         t = t.inverse();
+        bool_ = are_near(t, t2);
+        bool_ = are_near(t, t2, epsilon);
     }
 };
 
@@ -130,6 +133,10 @@ public:
     friend class Point;
 };
 
+inline bool are_near(Translate const &a, Translate const &b, Coord eps=EPSILON) {
+    return are_near(a[X], b[X], eps) && are_near(a[Y], b[Y], eps);
+}
+
 /** @brief Scaling from the origin.
  * During scaling, the point (0,0) will not move. To obtain a scale  with a different
  * invariant point, combine with translation to the origin and back.
@@ -164,6 +171,10 @@ public:
     friend class Point;
 };
 
+inline bool are_near(Scale const &a, Scale const &b, Coord eps=EPSILON) {
+    return are_near(a[X], b[X], eps) && are_near(a[Y], b[Y], eps);
+}
+
 /** @brief Rotation around the origin.
  * Combine with translations to the origin and back to get a rotation around a different point.
  * @ingroup Transforms */
@@ -207,6 +218,10 @@ public:
     friend class Point;
 };
 
+inline bool are_near(Rotate const &a, Rotate const &b, Coord eps=EPSILON) {
+    return are_near(a[X], b[X], eps) && are_near(a[Y], b[Y], eps);
+}
+
 /** @brief Common base for shearing transforms.
  * This class is an implementation detail and should not be used directly.
  * @ingroup Transforms */
@@ -241,6 +256,10 @@ public:
     operator Affine() const { Affine ret(1, 0, f, 1, 0, 0); return ret; }
 };
 
+inline bool are_near(HShear const &a, HShear const &b, Coord eps=EPSILON) {
+    return are_near(a.factor(), b.factor(), eps);
+}
+
 /** @brief Vertical shearing.
  * Points on the Y axis will not move. Combine with translations to get a shear
  * with a different invariant line.
@@ -253,6 +272,10 @@ public:
     operator Affine() const { Affine ret(1, f, 0, 1, 0, 0); return ret; }
 };
 
+inline bool are_near(VShear const &a, VShear const &b, Coord eps=EPSILON) {
+    return are_near(a.factor(), b.factor(), eps);
+}
+
 /** @brief Combination of a translation and uniform scale.
  * The translation part is applied first, then the result is scaled from the new origin.
  * This way when the class is used to accumulate a zoom transform, trans always points
@@ -295,6 +318,11 @@ public:
     friend class Affine;
 };
 
+inline bool are_near(Zoom const &a, Zoom const &b, Coord eps=EPSILON) {
+    return are_near(a.scale(), b.scale(), eps) &&
+           are_near(a.translation(), b.translation(), eps);
+}
+
 /** @brief Specialization of exponentiation for Scale.
  * @relates Scale */
 template<>