Merge from trunk.

(bzr r12475.1.16)

1 files changed, 310 insertions, 0 deletions

diff --git a/src/helper/geom.cpp b/src/helper/geom.cpp
index 879026521..df0e4fcf2 100644
--- a/src/helper/geom.cpp
+++ b/src/helper/geom.cpp
@@ -21,6 +21,7 @@
 #include <2geom/rect.h>
 #include <2geom/coord.h>
 #include <2geom/sbasis-to-bezier.h>
+#include <math.h> // for M_PI
 
 using Geom::X;
 using Geom::Y;
@@ -491,6 +492,315 @@ pathv_to_linear_and_cubic_beziers( Geom::PathVector const &pathv )
     return output;
 }
 
+/*
+ * Converts all segments in all paths to Geom::LineSegment.  There is an intermediate
+ * stage where some may be converted to beziers.  maxdisp is the maximum displacement from
+ * the line segment to the bezier curve.
+ *
+ * This is NOT a terribly fast method, but it should give a solution close to the one with the
+ * fewest points.
+ */
+Geom::PathVector
+pathv_to_linear( Geom::PathVector const &pathv, double maxdisp)
+{
+    Geom::PathVector output;
+    Geom::PathVector tmppath = pathv_to_linear_and_cubic_beziers(pathv);
+    
+    // Now all path segments are either already lines, or they are beziers.
+
+    for (Geom::PathVector::const_iterator pit = tmppath.begin(); pit != tmppath.end(); ++pit) {
+        output.push_back( Geom::Path() );
+        output.back().start( pit->initialPoint() );
+        output.back().close( pit->closed() );
+
+        for (Geom::Path::const_iterator cit = pit->begin(); cit != pit->end_open(); ++cit) {
+            if (is_straight_curve(*cit)) {
+                Geom::LineSegment ls(cit->initialPoint(), cit->finalPoint());
+                output.back().append(ls);
+            } 
+            else { /* all others must be Bezier curves */
+                Geom::BezierCurve const *curve = dynamic_cast<Geom::BezierCurve const *>(&*cit);
+                Geom::CubicBezier b((*curve)[0], (*curve)[1], (*curve)[2], (*curve)[3]);
+                std::vector<Geom::Point> bzrpoints = b.points();
+                Geom::Point A = bzrpoints[0];
+                Geom::Point B = bzrpoints[1];
+                Geom::Point C = bzrpoints[2];
+                Geom::Point D = bzrpoints[3];
+                std::vector<Geom::Point> pointlist;
+                pointlist.push_back(A);
+                recursive_bezier4(
+                   A[X], A[Y], 
+                   B[X], B[Y], 
+                   C[X], C[Y], 
+                   D[X], D[Y],
+                   pointlist, 
+                   0);
+                pointlist.push_back(D);
+                Geom::Point r0;
+                Geom::Point r1 = pointlist[0];
+                for (unsigned int i=1; i<pointlist.size();i++){
+                   r0 = r1;
+                   r1 = pointlist[i];
+                   Geom::LineSegment ls(r0, r1);
+                   output.back().append(ls);
+                }
+                pointlist.clear();
+           }
+        }
+    }
+    
+    return output;
+}
+
+// The next routine is modified from curv4_div::recursive_bezier from file agg_curves.cpp
+//----------------------------------------------------------------------------
+// Anti-Grain Geometry (AGG) - Version 2.5
+// A high quality rendering engine for C++
+// Copyright (C) 2002-2006 Maxim Shemanarev
+// Contact: mcseem@antigrain.com
+//          mcseemagg@yahoo.com
+//          http://antigrain.com
+// 
+// AGG is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License
+// as published by the Free Software Foundation; either version 2
+// of the License, or (at your option) any later version.
+// 
+// AGG 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 General Public License for more details.
+// 
+// You should have received a copy of the GNU General Public License
+// along with AGG; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 
+// MA 02110-1301, USA.
+//----------------------------------------------------------------------------
+void
+recursive_bezier4(const double x1, const double y1, 
+                  const double x2, const double y2, 
+                  const double x3, const double y3, 
+                  const double x4, const double y4,
+                  std::vector<Geom::Point> &m_points,
+                  int level)
+    {
+        // some of these should be parameters, but do it this way for now.
+        const double curve_collinearity_epsilon              = 1e-30;
+        const double curve_angle_tolerance_epsilon           = 0.01;
+        double       m_cusp_limit                            = 0.0;
+        double       m_angle_tolerance                       = 0.0;
+        double       m_approximation_scale                   = 1.0;
+        double       m_distance_tolerance_square = 0.5 / m_approximation_scale;
+        m_distance_tolerance_square *= m_distance_tolerance_square;
+        enum curve_recursion_limit_e { curve_recursion_limit = 32 };
+#define calc_sq_distance(A,B,C,D) ((A-C)*(A-C) + (B-D)*(B-D))
+
+        if(level > curve_recursion_limit) 
+        {
+            return;
+        }
+
+
+        // Calculate all the mid-points of the line segments
+        //----------------------
+        double x12   = (x1 + x2) / 2;
+        double y12   = (y1 + y2) / 2;
+        double x23   = (x2 + x3) / 2;
+        double y23   = (y2 + y3) / 2;
+        double x34   = (x3 + x4) / 2;
+        double y34   = (y3 + y4) / 2;
+        double x123  = (x12 + x23) / 2;
+        double y123  = (y12 + y23) / 2;
+        double x234  = (x23 + x34) / 2;
+        double y234  = (y23 + y34) / 2;
+        double x1234 = (x123 + x234) / 2;
+        double y1234 = (y123 + y234) / 2;
+
+
+        // Try to approximate the full cubic curve by a single straight line
+        //------------------
+        double dx = x4-x1;
+        double dy = y4-y1;
+
+        double d2 = fabs(((x2 - x4) * dy - (y2 - y4) * dx));
+        double d3 = fabs(((x3 - x4) * dy - (y3 - y4) * dx));
+        double da1, da2, k;
+
+        switch((int(d2 > curve_collinearity_epsilon) << 1) +
+                int(d3 > curve_collinearity_epsilon))
+        {
+        case 0:
+            // All collinear OR p1==p4
+            //----------------------
+            k = dx*dx + dy*dy;
+            if(k == 0)
+            {
+                d2 = calc_sq_distance(x1, y1, x2, y2);
+                d3 = calc_sq_distance(x4, y4, x3, y3);
+            }
+            else
+            {
+                k   = 1 / k;
+                da1 = x2 - x1;
+                da2 = y2 - y1;
+                d2  = k * (da1*dx + da2*dy);
+                da1 = x3 - x1;
+                da2 = y3 - y1;
+                d3  = k * (da1*dx + da2*dy);
+                if(d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1)
+                {
+                    // Simple collinear case, 1---2---3---4
+                    // We can leave just two endpoints
+                    return;
+                }
+                     if(d2 <= 0) d2 = calc_sq_distance(x2, y2, x1, y1);
+                else if(d2 >= 1) d2 = calc_sq_distance(x2, y2, x4, y4);
+                else             d2 = calc_sq_distance(x2, y2, x1 + d2*dx, y1 + d2*dy);
+
+                     if(d3 <= 0) d3 = calc_sq_distance(x3, y3, x1, y1);
+                else if(d3 >= 1) d3 = calc_sq_distance(x3, y3, x4, y4);
+                else             d3 = calc_sq_distance(x3, y3, x1 + d3*dx, y1 + d3*dy);
+            }
+            if(d2 > d3)
+            {
+                if(d2 < m_distance_tolerance_square)
+                {
+                    m_points.push_back(Geom::Point(x2, y2));
+                    return;
+                }
+            }
+            else
+            {
+                if(d3 < m_distance_tolerance_square)
+                {
+                    m_points.push_back(Geom::Point(x3, y3));
+                    return;
+                }
+            }
+            break;
+
+        case 1:
+            // p1,p2,p4 are collinear, p3 is significant
+            //----------------------
+            if(d3 * d3 <= m_distance_tolerance_square * (dx*dx + dy*dy))
+            {
+                if(m_angle_tolerance < curve_angle_tolerance_epsilon)
+                {
+                    m_points.push_back(Geom::Point(x23, y23));
+                    return;
+                }
+
+                // Angle Condition
+                //----------------------
+                da1 = fabs(atan2(y4 - y3, x4 - x3) - atan2(y3 - y2, x3 - x2));
+                if(da1 >= M_PI) da1 = 2*M_PI - da1;
+
+                if(da1 < m_angle_tolerance)
+                {
+                    m_points.push_back(Geom::Point(x2, y2));
+                    m_points.push_back(Geom::Point(x3, y3));
+                    return;
+                }
+
+                if(m_cusp_limit != 0.0)
+                {
+                    if(da1 > m_cusp_limit)
+                    {
+                        m_points.push_back(Geom::Point(x3, y3));
+                        return;
+                    }
+                }
+            }
+            break;
+
+        case 2:
+            // p1,p3,p4 are collinear, p2 is significant
+            //----------------------
+            if(d2 * d2 <= m_distance_tolerance_square * (dx*dx + dy*dy))
+            {
+                if(m_angle_tolerance < curve_angle_tolerance_epsilon)
+                {
+                    m_points.push_back(Geom::Point(x23, y23));
+                    return;
+                }
+
+                // Angle Condition
+                //----------------------
+                da1 = fabs(atan2(y3 - y2, x3 - x2) - atan2(y2 - y1, x2 - x1));
+                if(da1 >= M_PI) da1 = 2*M_PI - da1;
+
+                if(da1 < m_angle_tolerance)
+                {
+                    m_points.push_back(Geom::Point(x2, y2));
+                    m_points.push_back(Geom::Point(x3, y3));
+                    return;
+                }
+
+                if(m_cusp_limit != 0.0)
+                {
+                    if(da1 > m_cusp_limit)
+                    {
+                        m_points.push_back(Geom::Point(x2, y2));
+                        return;
+                    }
+                }
+            }
+            break;
+
+        case 3: 
+            // Regular case
+            //-----------------
+            if((d2 + d3)*(d2 + d3) <= m_distance_tolerance_square * (dx*dx + dy*dy))
+            {
+                // If the curvature doesn't exceed the distance_tolerance value
+                // we tend to finish subdivisions.
+                //----------------------
+                if(m_angle_tolerance < curve_angle_tolerance_epsilon)
+                {
+                    m_points.push_back(Geom::Point(x23, y23));
+                    return;
+                }
+
+                // Angle & Cusp Condition
+                //----------------------
+                k   = atan2(y3 - y2, x3 - x2);
+                da1 = fabs(k - atan2(y2 - y1, x2 - x1));
+                da2 = fabs(atan2(y4 - y3, x4 - x3) - k);
+                if(da1 >= M_PI) da1 = 2*M_PI - da1;
+                if(da2 >= M_PI) da2 = 2*M_PI - da2;
+
+                if(da1 + da2 < m_angle_tolerance)
+                {
+                    // Finally we can stop the recursion
+                    //----------------------
+                    m_points.push_back(Geom::Point(x23, y23));
+                    return;
+                }
+
+                if(m_cusp_limit != 0.0)
+                {
+                    if(da1 > m_cusp_limit)
+                    {
+                        m_points.push_back(Geom::Point(x2, y2));
+                        return;
+                    }
+
+                    if(da2 > m_cusp_limit)
+                    {
+                        m_points.push_back(Geom::Point(x3, y3));
+                        return;
+                    }
+                }
+            }
+            break;
+        }
+
+        // Continue subdivision
+        //----------------------
+        recursive_bezier4(x1, y1, x12, y12, x123, y123, x1234, y1234, m_points, level + 1); 
+        recursive_bezier4(x1234, y1234, x234, y234, x34, y34, x4, y4, m_points, level + 1); 
+}
+
 
 /**
  * rounds all corners of the rectangle 'outwards', i.e. x0 and y0 are floored, x1 and y1 are ceiled.