summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/2geom/conic_section_clipper.h59
-rw-r--r--src/2geom/conic_section_clipper_cr.h65
-rw-r--r--src/2geom/conic_section_clipper_impl.cpp590
-rw-r--r--src/2geom/conic_section_clipper_impl.h356
4 files changed, 1070 insertions, 0 deletions
diff --git a/src/2geom/conic_section_clipper.h b/src/2geom/conic_section_clipper.h
new file mode 100644
index 000000000..a02cda4d3
--- /dev/null
+++ b/src/2geom/conic_section_clipper.h
@@ -0,0 +1,59 @@
+/**
+ * \file
+ * \brief Conic section clipping with respect to a rectangle
+ *
+ * Authors:
+ * Marco Cecchetti <mrcekets at gmail>
+ *
+ * Copyright 2009 authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (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.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+
+
+
+#ifndef _2GEOM_CONIC_SECTION_CLIPPER_H_
+#define _2GEOM_CONIC_SECTION_CLIPPER_H_
+
+
+#undef CLIP_WITH_CAIRO_SUPPORT
+#include <2geom/conic_section_clipper_impl.h>
+
+
+#endif // _2GEOM_CONIC_SECTION_CLIPPER_H_
+
+
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/2geom/conic_section_clipper_cr.h b/src/2geom/conic_section_clipper_cr.h
new file mode 100644
index 000000000..31f5a4269
--- /dev/null
+++ b/src/2geom/conic_section_clipper_cr.h
@@ -0,0 +1,65 @@
+/**
+ * \file
+ * \brief Conic section clipping with respect to a rectangle
+ *
+ * Authors:
+ * Marco Cecchetti <mrcekets at gmail>
+ *
+ * Copyright 2009 authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (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.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+
+
+
+////////////////////////////////////////////////////////////////////////////////
+// This header should be used for graphical debugging purpuse only. //
+////////////////////////////////////////////////////////////////////////////////
+
+
+#ifndef _2GEOM_CONIC_SECTION_CLIPPER_CR_H_
+#define _2GEOM_CONIC_SECTION_CLIPPER_CR_H_
+
+
+#define CLIP_WITH_CAIRO_SUPPORT
+#include "conic_section_clipper_impl.h"
+#include "conic_section_clipper_impl.cpp"
+
+
+#endif // _2GEOM_CONIC_SECTION_CLIPPER_CR_H_
+
+
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/2geom/conic_section_clipper_impl.cpp b/src/2geom/conic_section_clipper_impl.cpp
new file mode 100644
index 000000000..edfafb11c
--- /dev/null
+++ b/src/2geom/conic_section_clipper_impl.cpp
@@ -0,0 +1,590 @@
+/**
+ * \file
+ * \brief Conic section clipping with respect to a rectangle
+ *
+ * Authors:
+ * Marco Cecchetti <mrcekets at gmail>
+ *
+ * Copyright 2009 authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (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.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+
+
+
+#ifndef CLIP_WITH_CAIRO_SUPPORT
+ #include <2geom/conic_section_clipper.h>
+#endif
+
+
+
+
+namespace Geom
+{
+
+struct lex_lesser
+{
+ bool operator() (const Point & P, const Point & Q) const
+ {
+ if (P[X] < Q[X]) return true;
+ if (P[X] == Q[X] && P[Y] < Q[Y]) return true;
+ return false;
+ }
+};
+
+
+/*
+ * Find rectangle-conic crossing points. They are returned in the
+ * "crossing_points" parameter.
+ * The method returns true if the conic section intersects at least one
+ * of the four lines passing through rectangle edges, else it returns false.
+ */
+bool CLIPPER_CLASS::intersect (std::vector<Point> & crossing_points) const
+{
+ crossing_points.clear();
+
+ std::vector<double> rts;
+ std::vector<Point> cpts;
+ // rectangle corners
+ enum {TOP_LEFT, TOP_RIGHT, BOTTOM_RIGHT, BOTTOM_LEFT};
+
+ bool no_crossing = true;
+
+ // rigth edge
+ cs.roots (rts, R.right(), X);
+ if (rts.size() != 0)
+ {
+ no_crossing = false;
+ DBGPRINT ("CLIP: right: rts[0] = ", rts[0])
+ DBGPRINTIF ((rts.size() == 2), "CLIP: right: rts[1] = ", rts[1])
+
+ Point corner1 = R.corner(TOP_RIGHT);
+ Point corner2 = R.corner(BOTTOM_RIGHT);
+
+ for (size_t i = 0; i < rts.size(); ++i)
+ {
+ if (rts[i] < R.top() || rts[i] > R.bottom()) continue;
+ Point P (R.right(), rts[i]);
+ if (are_near (P, corner1))
+ P = corner1;
+ else if (are_near (P, corner2))
+ P = corner2;
+
+ cpts.push_back (P);
+ }
+ if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
+ {
+ cpts[0] = middle_point (cpts[0], cpts[1]);
+ cpts.pop_back();
+ }
+ }
+
+ // top edge
+ cs.roots (rts, R.top(), Y);
+ if (rts.size() != 0)
+ {
+ no_crossing = false;
+ DBGPRINT ("CLIP: top: rts[0] = ", rts[0])
+ DBGPRINTIF ((rts.size() == 2), "CLIP: top: rts[1] = ", rts[1])
+
+ Point corner1 = R.corner(TOP_RIGHT);
+ Point corner2 = R.corner(TOP_LEFT);
+
+ for (size_t i = 0; i < rts.size(); ++i)
+ {
+ if (rts[i] < R.left() || rts[i] > R.right()) continue;
+ Point P (rts[i], R.top());
+ if (are_near (P, corner1))
+ P = corner1;
+ else if (are_near (P, corner2))
+ P = corner2;
+
+ cpts.push_back (P);
+ }
+ if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
+ {
+ cpts[0] = middle_point (cpts[0], cpts[1]);
+ cpts.pop_back();
+ }
+ }
+
+ // left edge
+ cs.roots (rts, R.left(), X);
+ if (rts.size() != 0)
+ {
+ no_crossing = false;
+ DBGPRINT ("CLIP: left: rts[0] = ", rts[0])
+ DBGPRINTIF ((rts.size() == 2), "CLIP: left: rts[1] = ", rts[1])
+
+ Point corner1 = R.corner(TOP_LEFT);
+ Point corner2 = R.corner(BOTTOM_LEFT);
+
+ for (size_t i = 0; i < rts.size(); ++i)
+ {
+ if (rts[i] < R.top() || rts[i] > R.bottom()) continue;
+ Point P (R.left(), rts[i]);
+ if (are_near (P, corner1))
+ P = corner1;
+ else if (are_near (P, corner2))
+ P = corner2;
+
+ cpts.push_back (P);
+ }
+ if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
+ {
+ cpts[0] = middle_point (cpts[0], cpts[1]);
+ cpts.pop_back();
+ }
+ }
+
+ // bottom edge
+ cs.roots (rts, R.bottom(), Y);
+ if (rts.size() != 0)
+ {
+ no_crossing = false;
+ DBGPRINT ("CLIP: bottom: rts[0] = ", rts[0])
+ DBGPRINTIF ((rts.size() == 2), "CLIP: bottom: rts[1] = ", rts[1])
+
+ Point corner1 = R.corner(BOTTOM_RIGHT);
+ Point corner2 = R.corner(BOTTOM_LEFT);
+
+ for (size_t i = 0; i < rts.size(); ++i)
+ {
+ if (rts[i] < R.left() || rts[i] > R.right()) continue;
+ Point P (rts[i], R.bottom());
+ if (are_near (P, corner1))
+ P = corner1;
+ else if (are_near (P, corner2))
+ P = corner2;
+
+ cpts.push_back (P);
+ }
+ if (cpts.size() == 2 && are_near (cpts[0], cpts[1]))
+ {
+ cpts[0] = middle_point (cpts[0], cpts[1]);
+ cpts.pop_back();
+ }
+ }
+
+ DBGPRINT ("CLIP: intersect: crossing_points.size (with duplicates) = ",
+ cpts.size())
+
+ // remove duplicates
+ std::sort (cpts.begin(), cpts.end(), lex_lesser());
+ cpts.erase (std::unique (cpts.begin(), cpts.end()), cpts.end());
+
+
+ // Order crossing points on the rectangle edge clockwise, so two consecutive
+ // crossing points would be the end points of a conic arc all inside or all
+ // outside the rectangle.
+ std::map<double, size_t> cp_angles;
+ for (size_t i = 0; i < cpts.size(); ++i)
+ {
+ cp_angles.insert (std::make_pair (cs.angle_at (cpts[i]), i));
+ }
+
+ std::map<double, size_t>::const_iterator pos;
+ for (pos = cp_angles.begin(); pos != cp_angles.end(); ++pos)
+ {
+ crossing_points.push_back (cpts[pos->second]);
+ }
+
+ DBGPRINT ("CLIP: intersect: crossing_points.size = ", crossing_points.size())
+ DBGPRINTCOLL ("CLIP: intersect: crossing_points:", crossing_points)
+
+ return no_crossing;
+} // end function intersect
+
+
+
+inline
+double signed_triangle_area (Point const& p1, Point const& p2, Point const& p3)
+{
+ return (cross(p3, p2) - cross(p3, p1) + cross(p2, p1));
+}
+
+
+/*
+ * Test if two crossing points are the end points of a conic arc inner to the
+ * rectangle. In such a case the method returns true, else it returns false.
+ * Moreover by the parameter "M" it returns a point inner to the conic arc
+ * with the given end-points.
+ *
+ */
+bool CLIPPER_CLASS::are_paired (Point& M, const Point & P1, const Point & P2) const
+{
+ /*
+ * we looks for the points on the conic whose tangent is parallel to the
+ * arc chord P1P2, they will be extrema of the conic arc P1P2 wrt the
+ * direction orthogonal to the chord
+ */
+ Point dir = P2 - P1;
+ DBGPRINT ("CLIP: are_paired: first point: ", P1)
+ DBGPRINT ("CLIP: are_paired: second point: ", P2)
+
+ double grad0 = 2 * cs.coeff(0) * dir[0] + cs.coeff(1) * dir[1];
+ double grad1 = cs.coeff(1) * dir[0] + 2 * cs.coeff(2) * dir[1];
+ double grad2 = cs.coeff(3) * dir[0] + cs.coeff(4) * dir[1];
+
+
+ /*
+ * such points are found intersecating the conic section with the line
+ * orthogonal to "grad": the derivative wrt the "dir" direction
+ */
+ Line gl (grad0, grad1, grad2);
+ std::vector<double> rts;
+ rts = cs.roots (gl);
+ DBGPRINT ("CLIP: are_paired: extrema: rts.size() = ", rts.size())
+
+
+
+ std::vector<Point> extrema;
+ for (size_t i = 0; i < rts.size(); ++i)
+ {
+ extrema.push_back (gl.pointAt (rts[i]));
+ }
+
+ if (extrema.size() == 2)
+ {
+ // in case we are dealing with an hyperbola we could have two extrema
+ // on the same side wrt the line passing through P1 and P2, but
+ // only the nearer extremum is on the arc P1P2
+ double side0 = signed_triangle_area (P1, extrema[0], P2);
+ double side1 = signed_triangle_area (P1, extrema[1], P2);
+
+ if (sgn(side0) == sgn(side1))
+ {
+ if (std::fabs(side0) > std::fabs(side1))
+ {
+ std::swap (extrema[0], extrema[1]);
+ }
+ extrema.pop_back();
+ }
+ }
+
+ std::vector<Point> inner_points;
+ for (size_t i = 0; i < extrema.size(); ++i)
+ {
+ if (!R.contains (extrema[i])) continue;
+ // in case we are dealing with an ellipse tangent to two orthogonal
+ // rectangle edges we could have two extrema on opposite sides wrt the
+ // line passing through P1P2 and both inner the rectangle; anyway, since
+ // we order the crossing points clockwise we have only one extremum
+ // that follows such an ordering wrt P1 and P2;
+ // remark: the other arc will be selected when we test for the arc P2P1.
+ double P1angle = cs.angle_at (P1);
+ double P2angle = cs.angle_at (P2);
+ double Qangle = cs.angle_at (extrema[i]);
+ if (P1angle < P2angle && !(P1angle <= Qangle && Qangle <= P2angle))
+ continue;
+ if (P1angle > P2angle && !(P1angle <= Qangle || Qangle <= P2angle))
+ continue;
+
+ inner_points.push_back (extrema[i]);
+ }
+
+ if (inner_points.size() > 1)
+ {
+ THROW_LOGICALERROR ("conic section clipper: "
+ "more than one extremum found");
+ }
+ else if (inner_points.size() == 1)
+ {
+ M = inner_points.front();
+ return true;
+ }
+
+ return false;
+}
+
+
+/*
+ * Pair the points contained in the "crossing_points" vector; the paired points
+ * are put in the paired_points vector so that given a point with an even index
+ * and the next one they are the end points of a conic arc that is inner to the
+ * rectangle. In the "inner_points" are returned points that are inner to the
+ * arc, where the inner point with index k is related to the arc with end
+ * points with indexes 2k, 2k+1. In case there are unpaired points the are put
+ * in to the "single_points" vector.
+ */
+void CLIPPER_CLASS::pairing (std::vector<Point> & paired_points,
+ std::vector<Point> & inner_points,
+ const std::vector<Point> & crossing_points)
+{
+ paired_points.clear();
+ paired_points.reserve (crossing_points.size());
+
+ inner_points.clear();
+ inner_points.reserve (crossing_points.size() / 2);
+
+ single_points.clear();
+
+ // to keep trace of which crossing points have been paired
+ std::vector<bool> paired (crossing_points.size(), false);
+
+ Point M;
+
+ // by the way we have ordered crossing points we need to test one point wrt
+ // the next point only, for pairing; moreover the last point need to be
+ // tested wrt the first point; pay attention: one point can be paired both
+ // with the previous and the next one: this is not an error, think of
+ // crossing points that are tangent to the rectangle edge (and inner);
+ for (size_t i = 0; i < crossing_points.size(); ++i)
+ {
+ // we need to test the last point wrt the first one
+ size_t j = (i == 0) ? (crossing_points.size() - 1) : (i-1);
+ if (are_paired (M, crossing_points[j], crossing_points[i]))
+ {
+#ifdef CLIP_WITH_CAIRO_SUPPORT
+ cairo_set_source_rgba(cr, 0.1, 0.1, 0.8, 1.0);
+ draw_line_seg (cr, crossing_points[j], crossing_points[i]);
+ draw_handle (cr, crossing_points[j]);
+ draw_handle (cr, crossing_points[i]);
+ draw_handle (cr, M);
+ cairo_stroke (cr);
+#endif
+ paired[j] = paired[i] = true;
+ paired_points.push_back (crossing_points[j]);
+ paired_points.push_back (crossing_points[i]);
+ inner_points.push_back (M);
+ }
+ }
+
+ // some point are not paired with any point, e.g. a crossing point tangent
+ // to a rectangle edge but with the conic arc outside the rectangle
+ for (size_t i = 0; i < paired.size(); ++i)
+ {
+ if (!paired[i])
+ single_points.push_back (crossing_points[i]);
+ }
+ DBGPRINTCOLL ("single_points", single_points)
+
+}
+
+
+/*
+ * This method clip the section conic wrt the rectangle and returns the inner
+ * conic arcs as a vector of RatQuad objects by the "arcs" parameter.
+ */
+bool CLIPPER_CLASS::clip (std::vector<RatQuad> & arcs)
+{
+ arcs.clear();
+ std::vector<Point> crossing_points;
+ std::vector<Point> paired_points;
+ std::vector<Point> inner_points;
+
+ Line l1, l2;
+ if (cs.decompose (l1, l2))
+ {
+ bool inner_empty = true;
+
+ DBGINFO ("CLIP: degenerate section conic")
+
+ boost::optional<LineSegment> ls1 = Geom::clip (l1, R);
+ if (ls1)
+ {
+ if (ls1->isDegenerate())
+ {
+ single_points.push_back (ls1->initialPoint());
+ }
+ else
+ {
+ Point M = middle_point (*ls1);
+ arcs.push_back
+ (RatQuad (ls1->initialPoint(), M, ls1->finalPoint(), 1));
+ inner_empty = false;
+ }
+ }
+
+ boost::optional<LineSegment> ls2 = Geom::clip (l2, R);
+ if (ls2)
+ {
+ if (ls2->isDegenerate())
+ {
+ single_points.push_back (ls2->initialPoint());
+ }
+ else
+ {
+ Point M = middle_point (*ls2);
+ arcs.push_back
+ (RatQuad (ls2->initialPoint(), M, ls2->finalPoint(), 1));
+ inner_empty = false;
+ }
+ }
+
+ return !inner_empty;
+ }
+
+
+ bool no_crossing = intersect (crossing_points);
+
+ // if the only crossing point is a rectangle corner than the section conic
+ // is all outside the rectangle
+ if (crossing_points.size() == 1)
+ {
+ for (size_t i = 0; i < 4; ++i)
+ {
+ if (crossing_points[0] == R.corner(i))
+ {
+ single_points.push_back (R.corner(i));
+ return false;
+ }
+ }
+ }
+
+ // if the conic does not cross any line passing through a rectangle edge or
+ // it is tangent to only one edge then it is an ellipse
+ if (no_crossing
+ || (crossing_points.size() == 1 && single_points.size() == 0))
+ {
+ // if the ellipse centre is inside the rectangle
+ // then so it is the ellipse
+ boost::optional<Point> c = cs.centre();
+ if (c && R.contains (*c))
+ {
+ DBGPRINT ("CLIP: ellipse with centre", *c)
+ // we set paired and inner points by finding the ellipse
+ // intersection with its axes; this choice let us having a more
+ // accurate RatQuad parametric arc
+ paired_points.resize(4);
+ std::vector<double> rts;
+ double angle = cs.axis_angle();
+ Line axis1 (*c, angle);
+ rts = cs.roots (axis1);
+ if (rts[0] > rts[1]) std::swap (rts[0], rts[1]);
+ paired_points[0] = axis1.pointAt (rts[0]);
+ paired_points[1] = axis1.pointAt (rts[1]);
+ paired_points[2] = paired_points[1];
+ paired_points[3] = paired_points[0];
+ Line axis2 (*c, angle + M_PI/2);
+ rts = cs.roots (axis2);
+ if (rts[0] > rts[1]) std::swap (rts[0], rts[1]);
+ inner_points.push_back (axis2.pointAt (rts[0]));
+ inner_points.push_back (axis2.pointAt (rts[1]));
+ }
+ else if (crossing_points.size() == 1)
+ {
+ // so we have a tangent crossing point but the ellipse is outside
+ // the rectangle
+ single_points.push_back (crossing_points[0]);
+ }
+ }
+ else
+ {
+ // in case the conic section intersects any of the four lines passing
+ // through the rectangle edges but it does not cross any rectangle edge
+ // then the conic is all outer of the rectangle
+ if (crossing_points.size() == 0) return false;
+ // else we need to pair crossing points, and to find an arc inner point
+ // in order to generate a RatQuad object
+ pairing (paired_points, inner_points, crossing_points);
+ }
+
+
+ // we split arcs until the end-point distance is less than a given value,
+ // in this way the RatQuad parametrization is enough accurate
+ std::list<Point> points;
+ std::list<Point>::iterator sp, ip, fp;
+ for (size_t i = 0, j = 0; i < paired_points.size(); i += 2, ++j)
+ {
+ //DBGPRINT ("CLIP: clip: P = ", paired_points[i])
+ //DBGPRINT ("CLIP: clip: M = ", inner_points[j])
+ //DBGPRINT ("CLIP: clip: Q = ", paired_points[i+1])
+
+ // in case inner point and end points are near is better not split
+ // the conic arc further or we could get a degenerate RatQuad object
+ if (are_near (paired_points[i], inner_points[j], 1e-4)
+ && are_near (paired_points[i+1], inner_points[j], 1e-4))
+ {
+ arcs.push_back (cs.toRatQuad (paired_points[i],
+ inner_points[j],
+ paired_points[i+1]));
+ continue;
+ }
+
+ // populate the list
+ points.push_back(paired_points[i]);
+ points.push_back(inner_points[j]);
+ points.push_back(paired_points[i+1]);
+
+ // an initial unconditioned splitting
+ sp = points.begin();
+ ip = sp; ++ip;
+ fp = ip; ++fp;
+ rsplit (points, sp, ip, size_t(1u));
+ rsplit (points, ip, fp, size_t(1u));
+
+ // length conditioned split
+ sp = points.begin();
+ fp = sp; ++fp;
+ while (fp != points.end())
+ {
+ rsplit (points, sp, fp, 100.0);
+ sp = fp;
+ ++fp;
+ }
+
+ sp = points.begin();
+ ip = sp; ++ip;
+ fp = ip; ++fp;
+ //DBGPRINT ("CLIP: points ", j)
+ //DBGPRINT ("CLIP: points.size = ", points.size())
+ while (ip != points.end())
+ {
+#ifdef CLIP_WITH_CAIRO_SUPPORT
+ cairo_set_source_rgba(cr, 0.1, 0.1, 0.8, 1.0);
+ draw_handle (cr, *sp);
+ draw_handle (cr, *ip);
+ cairo_stroke (cr);
+#endif
+ //std::cerr << "CLIP: arc: [" << *sp << ", " << *ip << ", "
+ // << *fp << "]" << std::endl;
+ arcs.push_back (cs.toRatQuad (*sp, *ip, *fp));
+ sp = fp;
+ ip = sp; ++ip;
+ fp = ip; ++fp;
+ }
+ points.clear();
+ }
+ DBGPRINT ("CLIP: arcs.size() = ", arcs.size())
+ return (arcs.size() != 0);
+} // end method clip
+
+
+} // end namespace geom
+
+
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/2geom/conic_section_clipper_impl.h b/src/2geom/conic_section_clipper_impl.h
new file mode 100644
index 000000000..7db4fca9f
--- /dev/null
+++ b/src/2geom/conic_section_clipper_impl.h
@@ -0,0 +1,356 @@
+/**
+ * \file
+ * \brief Conic section clipping with respect to a rectangle
+ *
+ * Authors:
+ * Marco Cecchetti <mrcekets at gmail>
+ *
+ * Copyright 2009 authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (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.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+
+
+
+#ifndef _2GEOM_CONIC_SECTION_CLIPPER_IMPL_H_
+#define _2GEOM_CONIC_SECTION_CLIPPER_IMPL_H_
+
+
+#include <2geom/conicsec.h>
+#include <2geom/line.h>
+
+#include <list>
+#include <map>
+
+
+
+#ifdef CLIP_WITH_CAIRO_SUPPORT
+ #include <2geom/toys/path-cairo.h>
+ #define CLIPPER_CLASS clipper_cr
+#else
+ #define CLIPPER_CLASS clipper
+#endif
+
+//#define CLIPDBG
+
+#ifdef CLIPDBG
+#include <2geom/toys/path-cairo.h>
+#define DBGINFO(msg) \
+ std::cerr << msg << std::endl;
+#define DBGPRINT(msg, var) \
+ std::cerr << msg << var << std::endl;
+#define DBGPRINTIF(cond, msg, var) \
+ if (cond) \
+ std::cerr << msg << var << std::endl;
+
+#define DBGPRINT2(msg1, var1, msg2, var2) \
+ std::cerr << msg1 << var1 << msg2 << var2 << std::endl;
+
+#define DBGPRINTCOLL(msg, coll) \
+ if (coll.size() != 0) \
+ std::cerr << msg << ":\n"; \
+ for (size_t i = 0; i < coll.size(); ++i) \
+ { \
+ std::cerr << i << ": " << coll[i] << "\n"; \
+ }
+
+#else
+#define DBGINFO(msg)
+#define DBGPRINT(msg, var)
+#define DBGPRINTIF(cond, msg, var)
+#define DBGPRINT2(msg1, var1, msg2, var2)
+#define DBGPRINTCOLL(msg, coll)
+#endif
+
+
+
+
+namespace Geom
+{
+
+class CLIPPER_CLASS
+{
+
+ public:
+
+#ifdef CLIP_WITH_CAIRO_SUPPORT
+ clipper_cr (cairo_t* _cr, const xAx & _cs, const Rect & _R)
+ : cr(_cr), cs(_cs), R(_R)
+ {
+ DBGPRINT ("CLIP: right side: ", R.right())
+ DBGPRINT ("CLIP: top side: ", R.top())
+ DBGPRINT ("CLIP: left side: ", R.left())
+ DBGPRINT ("CLIP: bottom side: ", R.bottom())
+ }
+#else
+ clipper (const xAx & _cs, const Rect & _R)
+ : cs(_cs), R(_R)
+ {
+ }
+#endif
+
+ bool clip (std::vector<RatQuad> & arcs);
+
+ bool found_any_isolated_point() const
+ {
+ return (single_points.size() != 0);
+ }
+
+ const std::vector<Point> & isolated_points() const
+ {
+ return single_points;
+ }
+
+
+ private:
+ bool intersect (std::vector<Point> & crossing_points) const;
+
+ bool are_paired (Point & M, const Point & P1, const Point & P2) const;
+ void pairing (std::vector<Point> & paired_points,
+ std::vector<Point> & inner_points,
+ const std::vector<Point> & crossing_points);
+
+ Point find_inner_point_by_bisector_line (const Point & P,
+ const Point & Q) const;
+ Point find_inner_point (const Point & P, const Point & Q) const;
+
+ std::list<Point>::iterator split (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp) const;
+ void rsplit (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp,
+ size_t k) const;
+
+ void rsplit (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp,
+ double length) const;
+
+ private:
+#ifdef CLIP_WITH_CAIRO_SUPPORT
+ cairo_t* cr;
+#endif
+ const xAx & cs;
+ const Rect & R;
+ std::vector<Point> single_points;
+};
+
+
+
+
+/*
+ * Given two point "P", "Q" on the conic section the method computes
+ * a third point inner to the arc with end-point "P", "Q".
+ * The new point is found by intersecting the conic with the bisector line
+ * of the PQ line segment.
+ */
+inline
+Point CLIPPER_CLASS::find_inner_point_by_bisector_line (const Point & P,
+ const Point & Q) const
+{
+ DBGPRINT ("CLIP: find_inner_point_by_bisector_line: P = ", P)
+ DBGPRINT ("CLIP: find_inner_point_by_bisector_line: Q = ", Q)
+ Line bl = make_bisector_line (LineSegment (P, Q));
+ std::vector<double> rts = cs.roots (bl);
+ //DBGPRINT ("CLIP: find_inner_point: rts.size = ", rts.size())
+ double t;
+ if (rts.size() == 0)
+ {
+ THROW_LOGICALERROR ("clipper::find_inner_point_by_bisector_line: "
+ "no conic-bisector line intersection point");
+ }
+ if (rts.size() == 2)
+ {
+ // we suppose that the searched point is the nearest
+ // to the line segment PQ
+ t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
+ }
+ else
+ {
+ t = rts[0];
+ }
+ return bl.pointAt (t);
+}
+
+
+/*
+ * Given two point "P", "Q" on the conic section the method computes
+ * a third point inner to the arc with end-point "P", "Q".
+ * The new point is found by intersecting the conic with the line
+ * passing through the middle point of the PQ line segment and
+ * the intersection point of the tangent lines at points P and Q.
+ */
+inline
+Point CLIPPER_CLASS::find_inner_point (const Point & P, const Point & Q) const
+{
+
+ Line l1 = cs.tangent (P);
+ Line l2 = cs.tangent (Q);
+ Line l;
+ // in case we fail to find a crossing point we fall back to the bisector
+ // method
+ try
+ {
+ OptCrossing oc = intersection(l1, l2);
+ if (!oc)
+ {
+ return find_inner_point_by_bisector_line (P, Q);
+ }
+ l.setPoints (l1.pointAt (oc->ta), middle_point (P, Q));
+ }
+ catch (Geom::InfiniteSolutions e)
+ {
+ return find_inner_point_by_bisector_line (P, Q);
+ }
+
+ std::vector<double> rts = cs.roots (l);
+ double t;
+ if (rts.size() == 0)
+ {
+ return find_inner_point_by_bisector_line (P, Q);
+ }
+ // the line "l" origin is set to the tangent crossing point so in case
+ // we find two intersection points only the nearest belongs to the given arc
+ // pay attention: in case we are dealing with an hyperbola (remember that
+ // end points are on the same branch, because they are paired) the tangent
+ // crossing point belongs to the angle delimited by hyperbola asymptotes
+ // and containing the given hyperbola branch, so the previous statement is
+ // still true
+ if (rts.size() == 2)
+ {
+ t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
+ }
+ else
+ {
+ t = rts[0];
+ }
+ return l.pointAt (t);
+}
+
+
+/*
+ * Given a list of points on the conic section, and given two consecutive
+ * points belonging to the list and passed by two list iterators, the method
+ * finds a new point that is inner to the conic arc which has the two passed
+ * points as initial and final point. This new point is inserted into the list
+ * between the two passed points and an iterator pointing to the new point
+ * is returned.
+ */
+inline
+std::list<Point>::iterator CLIPPER_CLASS::split (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp) const
+{
+ Point new_point = find_inner_point (*sp, *fp);
+ std::list<Point>::iterator ip = points.insert (fp, new_point);
+ //std::cerr << "CLIP: split: [" << *sp << ", " << *ip << ", "
+ // << *fp << "]" << std::endl;
+ return ip;
+}
+
+
+/*
+ * Given a list of points on the conic section, and given two consecutive
+ * points belonging to the list and passed by two list iterators, the method
+ * recursively finds new points that are inner to the conic arc which has
+ * the two passed points as initial and final point. The recursion stop after
+ * "k" recursive calls. These new points are inserted into the list between
+ * the two passed points, and in the order we cross them going from
+ * the initial to the final arc point.
+ */
+inline
+void CLIPPER_CLASS::rsplit (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp,
+ size_t k) const
+{
+ if (k == 0)
+ {
+ //DBGINFO("CLIP: split: no further split")
+ return;
+ }
+
+ std::list<Point>::iterator ip = split (points, sp, fp);
+ --k;
+ rsplit (points, sp, ip, k);
+ rsplit (points, ip, fp, k);
+}
+
+
+/*
+ * Given a list of points on the conic section, and given two consecutive
+ * points belonging to the list and passed by two list iterators, the method
+ * recursively finds new points that are inner to the conic arc which has
+ * the two passed points as initial and final point. The recursion stop when
+ * the max distance between the new computed inner point and the two passed
+ * arc end-points is less then the value specified by the "length" parameter.
+ * These new points are inserted into the list between the two passed points,
+ * and in the order we cross them going from the initial to the final arc point.
+ */
+inline
+void CLIPPER_CLASS::rsplit (std::list<Point> & points,
+ std::list<Point>::iterator sp,
+ std::list<Point>::iterator fp,
+ double length) const
+{
+ std::list<Point>::iterator ip = split (points, sp, fp);
+ double d1 = distance (*sp, *ip);
+ double d2 = distance (*ip, *fp);
+ double mdist = std::max (d1, d2);
+
+ if (mdist < length)
+ {
+ //DBGINFO("CLIP: split: no further split")
+ return;
+ }
+
+ // they have to be called both to keep the number of points in the list
+ // in the form 2k+1 where k are the sub-arcs the initial arc is splitted in.
+ rsplit (points, sp, ip, length);
+ rsplit (points, ip, fp, length);
+}
+
+
+} // end namespace Geom
+
+
+
+
+#endif // _2GEOM_CONIC_SECTION_CLIPPER_IMPL_H_
+
+
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
generated by cgit v1.2.3 (git 2.25.1) at 2026-07-19 21:25:29 +0000