diff options
Diffstat (limited to 'src/helper/geom.cpp')
| -rw-r--r-- | src/helper/geom.cpp | 310 |
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. |