conic_section_clipper_impl.h revision 07bda0b13ae048815f53f21ad1edbe3cc1b7e4e8
07bda0b13ae048815f53f21ad1edbe3cc1b7e4e8Johan Engelen * \brief Conic section clipping with respect to a rectangle
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Marco Cecchetti <mrcekets at gmail>
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Copyright 2009 authors
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * This library is free software; you can redistribute it and/or
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * modify it either under the terms of the GNU Lesser General Public
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * License version 2.1 as published by the Free Software Foundation
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * (the "LGPL") or, at your option, under the terms of the Mozilla
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Public License Version 1.1 (the "MPL"). If you do not alter this
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * notice, a recipient may use your version of this file under either
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the MPL or the LGPL.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * You should have received a copy of the LGPL along with this library
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * in the file COPYING-LGPL-2.1; if not, write to the Free Software
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * You should have received a copy of the MPL along with this library
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * in the file COPYING-MPL-1.1
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * The contents of this file are subject to the Mozilla Public License
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Version 1.1 (the "License"); you may not use this file except in
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * compliance with the License. You may obtain a copy of the License at
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * OF ANY KIND, either express or implied. See the LGPL or the MPL for
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the specific language governing rights and limitations.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen//#define CLIPDBG
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen std::cerr << msg1 << var1 << msg2 << var2 << std::endl;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen clipper_cr (cairo_t* _cr, const xAx & _cs, const Rect & _R)
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen const std::vector<Point> & isolated_points() const
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen bool intersect (std::vector<Point> & crossing_points) const;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen bool are_paired (Point & M, const Point & P1, const Point & P2) const;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen void pairing (std::vector<Point> & paired_points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen Point find_inner_point_by_bisector_line (const Point & P,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen const Point & Q) const;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen Point find_inner_point (const Point & P, const Point & Q) const;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen std::list<Point>::iterator split (std::list<Point> & points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen double length) const;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Given two point "P", "Q" on the conic section the method computes
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * a third point inner to the arc with end-point "P", "Q".
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * The new point is found by intersecting the conic with the bisector line
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * of the PQ line segment.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan EngelenPoint CLIPPER_CLASS::find_inner_point_by_bisector_line (const Point & P,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen const Point & Q) const
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen DBGPRINT ("CLIP: find_inner_point_by_bisector_line: P = ", P)
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen DBGPRINT ("CLIP: find_inner_point_by_bisector_line: Q = ", Q)
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen Line bl = make_bisector_line (LineSegment (P, Q));
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen //DBGPRINT ("CLIP: find_inner_point: rts.size = ", rts.size())
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen THROW_LOGICALERROR ("clipper::find_inner_point_by_bisector_line: "
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen "no conic-bisector line intersection point");
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // we suppose that the searched point is the nearest
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // to the line segment PQ
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Given two point "P", "Q" on the conic section the method computes
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * a third point inner to the arc with end-point "P", "Q".
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * The new point is found by intersecting the conic with the line
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * passing through the middle point of the PQ line segment and
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the intersection point of the tangent lines at points P and Q.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan EngelenPoint CLIPPER_CLASS::find_inner_point (const Point & P, const Point & Q) const
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // in case we fail to find a crossing point we fall back to the bisector
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen return find_inner_point_by_bisector_line (P, Q);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen l.setPoints (l1.pointAt (oc->ta), middle_point (P, Q));
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen return find_inner_point_by_bisector_line (P, Q);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen return find_inner_point_by_bisector_line (P, Q);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // the line "l" origin is set to the tangent crossing point so in case
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // we find two intersection points only the nearest belongs to the given arc
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // pay attention: in case we are dealing with an hyperbola (remember that
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // end points are on the same branch, because they are paired) the tangent
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // crossing point belongs to the angle delimited by hyperbola asymptotes
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // and containing the given hyperbola branch, so the previous statement is
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // still true
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen t = (std::fabs(rts[0]) < std::fabs(rts[1])) ? rts[0] : rts[1];
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen return l.pointAt (t);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Given a list of points on the conic section, and given two consecutive
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * points belonging to the list and passed by two list iterators, the method
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * finds a new point that is inner to the conic arc which has the two passed
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * points as initial and final point. This new point is inserted into the list
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * between the two passed points and an iterator pointing to the new point
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * is returned.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelenstd::list<Point>::iterator CLIPPER_CLASS::split (std::list<Point> & points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen Point new_point = find_inner_point (*sp, *fp);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen std::list<Point>::iterator ip = points.insert (fp, new_point);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen //std::cerr << "CLIP: split: [" << *sp << ", " << *ip << ", "
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // << *fp << "]" << std::endl;
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Given a list of points on the conic section, and given two consecutive
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * points belonging to the list and passed by two list iterators, the method
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * recursively finds new points that are inner to the conic arc which has
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the two passed points as initial and final point. The recursion stop after
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * "k" recursive calls. These new points are inserted into the list between
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the two passed points, and in the order we cross them going from
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the initial to the final arc point.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelenvoid CLIPPER_CLASS::rsplit (std::list<Point> & points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen //DBGINFO("CLIP: split: no further split")
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen std::list<Point>::iterator ip = split (points, sp, fp);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * Given a list of points on the conic section, and given two consecutive
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * points belonging to the list and passed by two list iterators, the method
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * recursively finds new points that are inner to the conic arc which has
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the two passed points as initial and final point. The recursion stop when
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * the max distance between the new computed inner point and the two passed
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * arc end-points is less then the value specified by the "length" parameter.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * These new points are inserted into the list between the two passed points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen * and in the order we cross them going from the initial to the final arc point.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelenvoid CLIPPER_CLASS::rsplit (std::list<Point> & points,
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen double length) const
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen std::list<Point>::iterator ip = split (points, sp, fp);
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen //DBGINFO("CLIP: split: no further split")
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // they have to be called both to keep the number of points in the list
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen // in the form 2k+1 where k are the sub-arcs the initial arc is splitted in.
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen} // end namespace Geom
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen#endif // _2GEOM_CONIC_SECTION_CLIPPER_IMPL_H_
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen Local Variables:
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen c-file-style:"stroustrup"
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen indent-tabs-mode:nil
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen fill-column:99
5738b9afc93525510fa01185f7609fd5cbb0ff1aJohan Engelen// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :