conic_section_clipper_impl.cpp revision 5738b9afc93525510fa01185f7609fd5cbb0ff1a
/**
* \file
* \brief Conic section clipping with respect to a rectangle
*
* Authors:
* Marco Cecchetti <mrcekets at gmail>
*
* Copyright 2009 authors
*
* 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
*
* 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
#endif
namespace Geom
{
struct lex_lesser
{
{
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.
*/
{
// rectangle corners
bool no_crossing = true;
// rigth edge
{
no_crossing = false;
{
P = corner1;
P = corner2;
}
{
}
}
// top edge
{
no_crossing = false;
{
P = corner1;
P = corner2;
}
{
}
}
// left edge
{
no_crossing = false;
{
P = corner1;
P = corner2;
}
{
}
}
// bottom edge
{
no_crossing = false;
{
P = corner1;
P = corner2;
}
{
}
}
DBGPRINT ("CLIP: intersect: crossing_points.size (with duplicates) = ",
// remove duplicates
// 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.
{
}
{
}
return no_crossing;
} // end function intersect
inline
{
}
/*
* 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.
*
*/
{
/*
* 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
*/
/*
* such points are found intersecating the conic section with the line
* orthogonal to "grad": the derivative wrt the "dir" direction
*/
{
}
{
// 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
{
{
}
}
}
{
// 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.
continue;
continue;
}
{
THROW_LOGICALERROR ("conic section clipper: "
"more than one extremum found");
}
{
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.
*/
{
// to keep trace of which crossing points have been paired
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);
{
// we need to test the last point wrt the first one
{
#ifdef CLIP_WITH_CAIRO_SUPPORT
draw_handle (cr, M);
cairo_stroke (cr);
#endif
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
{
if (!paired[i])
}
}
/*
* 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 inner_empty = true;
DBGINFO ("CLIP: degenerate section conic")
if (ls1)
{
if (ls1->isDegenerate())
{
}
else
{
inner_empty = false;
}
}
if (ls2)
{
if (ls2->isDegenerate())
{
}
else
{
inner_empty = false;
}
}
return !inner_empty;
}
// if the only crossing point is a rectangle corner than the section conic
// is all outside the rectangle
{
for (size_t i = 0; i < 4; ++i)
{
if (crossing_points[0] == 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
{
// if the ellipse centre is inside the rectangle
// then so it is the ellipse
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
}
{
// so we have a tangent crossing point but the ellipse is outside
// the rectangle
}
}
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
}
// we split arcs until the end-point distance is less than a given value,
// in this way the RatQuad parametrization is enough accurate
{
//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
{
inner_points[j],
paired_points[i+1]));
continue;
}
// populate the list
// an initial unconditioned splitting
// length conditioned split
{
++fp;
}
//DBGPRINT ("CLIP: points ", j)
{
#ifdef CLIP_WITH_CAIRO_SUPPORT
cairo_stroke (cr);
#endif
//std::cerr << "CLIP: arc: [" << *sp << ", " << *ip << ", "
// << *fp << "]" << std::endl;
}
}
} // 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 :