diff options
Diffstat (limited to 'src/2geom/path.cpp')
| -rw-r--r-- | src/2geom/path.cpp | 367 |
1 files changed, 367 insertions, 0 deletions
diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp new file mode 100644 index 000000000..91868eb7e --- /dev/null +++ b/src/2geom/path.cpp @@ -0,0 +1,367 @@ +/*
+ * Path - Series of continuous curves
+ *
+ * Copyright 2007 MenTaLguY <mental@rydia.net>
+ *
+ * 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.
+ */
+
+#include "path.h"
+
+namespace Geom {
+
+namespace {
+
+enum Cmp {
+ LESS_THAN=-1,
+ GREATER_THAN=1,
+ EQUAL_TO=0
+};
+
+template <typename T1, typename T2>
+inline Cmp cmp(T1 const &a, T2 const &b) {
+ if ( a < b ) {
+ return LESS_THAN;
+ } else if ( b < a ) {
+ return GREATER_THAN;
+ } else {
+ return EQUAL_TO;
+ }
+}
+
+}
+
+boost::optional<int> CurveHelpers::sbasis_winding(D2<SBasis> const &sb, Point p) {
+ Interval ix = bounds_fast(sb[X]);
+
+ if ( p[X] > ix.max() ) { /* ray does not intersect bbox */
+ return 0;
+ }
+
+ SBasis fy = sb[Y];
+ fy -= p[Y];
+
+ if (fy.empty()) { /* coincident horizontal segment */
+ return boost::optional<int>();
+ }
+
+ if ( p[X] < ix.min() ) { /* ray does not originate in bbox */
+ double y = p[Y];
+ /* winding determined by position of endpoints */
+ Cmp initial_to_ray = cmp(fy[0][0], y);
+ Cmp final_to_ray = cmp(fy[0][1], y);
+ switch (cmp(final_to_ray, initial_to_ray)) {
+ case GREATER_THAN:
+ /* exclude final endpoint */
+ return ( final_to_ray != EQUAL_TO );
+ case LESS_THAN:
+ /* exclude final endpoint */
+ return -( final_to_ray != EQUAL_TO );
+ default:
+ /* any intersections cancel out */
+ return 0;
+ }
+ } else { /* ray originates in bbox */
+ std::vector<double> ts = roots(fy);
+
+ static const unsigned MAX_DERIVATIVES=8;
+ boost::optional<SBasis> ds[MAX_DERIVATIVES];
+ ds[0] = derivative(fy);
+
+ /* winding determined by summing signs of derivatives at intersections */
+ int winding=0;
+ for ( std::vector<double>::iterator ti = ts.begin()
+ ; ti != ts.end()
+ ; ++ti )
+ {
+ double t = *ti;
+ if ( sb[X](t) >= p[X] ) { /* root is ray intersection */
+ for ( boost::optional<SBasis> *di = ds
+ ; di != ( ds + MAX_DERIVATIVES )
+ ; ++di )
+ {
+ if (!*di) {
+ *di = derivative(**(di-1));
+ }
+ switch (cmp((**di)(t), 0)) {
+ case GREATER_THAN:
+ if ( t < 1 ) { /* exclude final endpoint */
+ winding += 1;
+ }
+ goto next_root;
+ case LESS_THAN:
+ if ( t < 1 ) { /* exclude final endpoint */
+ winding -= 1;
+ }
+ goto next_root;
+ default: (void)0;
+ /* give up */
+ };
+ }
+ }
+next_root: (void)0;
+ }
+
+ return winding;
+ }
+}
+
+Rect BezierHelpers::bounds(unsigned degree, Point const *points) {
+ Point min=points[0];
+ Point max=points[0];
+ for ( unsigned i = 1 ; i <= degree ; ++i ) {
+ for ( unsigned axis = 0 ; axis < 2 ; ++axis ) {
+ min[axis] = std::min(min[axis], points[i][axis]);
+ max[axis] = std::max(max[axis], points[i][axis]);
+ }
+ }
+ return Rect(min, max);
+}
+
+Point BezierHelpers::point_and_derivatives_at(Coord t,
+ unsigned degree,
+ Point const *points,
+ unsigned n_derivs,
+ Point *derivs)
+{
+ return Point(0,0); // TODO
+}
+
+Geom::Point
+BezierHelpers::subdivideArr(Coord t, // Parameter value
+ unsigned degree, // Degree of bezier curve
+ Geom::Point const *V, // Control pts
+ Geom::Point *Left, // RETURN left half ctl pts
+ Geom::Point *Right) // RETURN right half ctl pts
+{
+ Geom::Point Vtemp[degree+1][degree+1];
+
+ /* Copy control points */
+ std::copy(V, V+degree+1, Vtemp[0]);
+
+ /* Triangle computation */
+ for (unsigned i = 1; i <= degree; i++) {
+ for (unsigned j = 0; j <= degree - i; j++) {
+ Vtemp[i][j] = lerp(t, Vtemp[i-1][j], Vtemp[i-1][j+1]);
+ }
+ }
+
+ for (unsigned j = 0; j <= degree; j++)
+ Left[j] = Vtemp[j][0];
+ for (unsigned j = 0; j <= degree; j++)
+ Right[j] = Vtemp[degree-j][j];
+
+ return (Vtemp[degree][0]);
+}
+
+void Path::swap(Path &other) {
+ std::swap(curves_, other.curves_);
+ std::swap(closed_, other.closed_);
+ std::swap(*final_, *other.final_);
+ curves_[curves_.size()-1] = final_;
+ other.curves_[other.curves_.size()-1] = other.final_;
+}
+
+Rect Path::bounds_fast() const {
+ Rect bounds=front().bounds_fast();
+ for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
+ bounds.unionWith(iter->bounds_fast());
+ }
+ return bounds;
+}
+
+Rect Path::bounds_exact() const {
+ Rect bounds=front().bounds_exact();
+ for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
+ bounds.unionWith(iter->bounds_exact());
+ }
+ return bounds;
+}
+
+int Path::winding(Point p) const {
+ int winding = 0;
+ boost::optional<Cmp> ignore = boost::optional<Cmp>();
+ for ( const_iterator iter = begin()
+ ; iter != end_closed()
+ ; ++iter )
+ {
+ boost::optional<int> w = iter->winding(p);
+ if (w) {
+ winding += *w;
+ ignore = boost::optional<Cmp>();
+ } else {
+ Point initial = iter->initialPoint();
+ Point final = iter->finalPoint();
+ switch (cmp(initial[X], final[X])) {
+ case GREATER_THAN:
+ if ( !ignore || *ignore != GREATER_THAN ) { /* ignore repeated */
+ winding += 1;
+ ignore = GREATER_THAN;
+ }
+ break;
+ case LESS_THAN:
+ if ( !ignore || *ignore != LESS_THAN ) { /* ignore repeated */
+ if ( p[X] < final[X] ) { /* ignore final point */
+ winding -= 1;
+ ignore = LESS_THAN;
+ }
+ }
+ break;
+ case EQUAL_TO:
+ /* always ignore null segments */
+ break;
+ }
+ }
+ }
+ return winding;
+}
+
+void Path::append(Curve const &curve) {
+ if ( curves_.front() != final_ && curve.initialPoint() != (*final_)[0] ) {
+ throw ContinuityError();
+ }
+ do_append(curve.duplicate());
+}
+
+void Path::append(D2<SBasis> const &curve) {
+ if ( curves_.front() != final_ ) {
+ for ( int i = 0 ; i < 2 ; ++i ) {
+ if ( curve[i][0][0] != (*final_)[0][i] ) {
+ throw ContinuityError();
+ }
+ }
+ }
+ do_append(new SBasisCurve(curve));
+}
+
+void Path::do_update(Sequence::iterator first_replaced,
+ Sequence::iterator last_replaced,
+ Sequence::iterator first,
+ Sequence::iterator last)
+{
+ // note: modifies the contents of [first,last)
+
+ check_continuity(first_replaced, last_replaced, first, last);
+ delete_range(first_replaced, last_replaced);
+ if ( ( last - first ) == ( last_replaced - first_replaced ) ) {
+ std::copy(first, last, first_replaced);
+ } else {
+ // this approach depends on std::vector's behavior WRT iterator stability
+ curves_.erase(first_replaced, last_replaced);
+ curves_.insert(first_replaced, first, last);
+ }
+
+ if ( curves_.front() != final_ ) {
+ (*final_)[0] = back().finalPoint();
+ (*final_)[1] = front().initialPoint();
+ }
+}
+
+void Path::do_append(Curve *curve) {
+ if ( curves_.front() == final_ ) {
+ (*final_)[1] = curve->initialPoint();
+ }
+ curves_.insert(curves_.end()-1, curve);
+ (*final_)[0] = curve->finalPoint();
+}
+
+void Path::delete_range(Sequence::iterator first, Sequence::iterator last) {
+ for ( Sequence::iterator iter=first ; iter != last ; ++iter ) {
+ delete *iter;
+ }
+}
+
+void Path::check_continuity(Sequence::iterator first_replaced,
+ Sequence::iterator last_replaced,
+ Sequence::iterator first,
+ Sequence::iterator last)
+{
+ if ( first != last ) {
+ if ( first_replaced != curves_.begin() ) {
+ if ( (*first_replaced)->initialPoint() != (*first)->initialPoint() ) {
+ throw ContinuityError();
+ }
+ }
+ if ( last_replaced != (curves_.end()-1) ) {
+ if ( (*(last_replaced-1))->finalPoint() != (*(last-1))->finalPoint() ) {
+ throw ContinuityError();
+ }
+ }
+ } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) {
+ if ( (*first_replaced)->initialPoint() !=
+ (*(last_replaced-1))->finalPoint() )
+ {
+ throw ContinuityError();
+ }
+ }
+}
+
+Rect SBasisCurve::bounds_fast() const {
+ throw NotImplemented();
+ return Rect(Point(0,0), Point(0,0));
+}
+
+Rect SBasisCurve::bounds_exact() const {
+ throw NotImplemented();
+ return Rect(Point(0,0), Point(0,0));
+}
+
+Point SBasisCurve::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const {
+ throw NotImplemented();
+ return Point(0,0);
+}
+
+Path const &SBasisCurve::subdivide(Coord t, Path &out) const {
+ throw NotImplemented();
+}
+
+Rect SVGEllipticalArc::bounds_fast() const {
+ throw NotImplemented();
+}
+Rect SVGEllipticalArc::bounds_exact() const {
+ throw NotImplemented();
+}
+
+Point SVGEllipticalArc::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const {
+ throw NotImplemented();
+}
+
+D2<SBasis> SVGEllipticalArc::sbasis() const {
+ throw NotImplemented();
+}
+
+}
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(substatement-open . 0))
+ indent-tabs-mode:nil
+ c-brace-offset:0
+ fill-column:99
+ End:
+ vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :
+*/
+
|