![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp
index fdfa77c791cf36d9a02d98590c53c6bdb5db14ec..c47902649654953884b54247e50e8a00ce104d23 100644 (file)
--- a/src/2geom/path.cpp
+++ b/src/2geom/path.cpp
/*
* Path - Series of continuous curves
- *
- * Copyright 2007 MenTaLguY <mental@rydia.net>
- *
- * This library is free software; you can redistribute it and/or
+ *
+ * Authors:
+ * MenTaLguY <mental@rydia.net>
+ * Marco Cecchetti <mrcekets at gmail.com>
+ *
+ * Copyright 2007-2008 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
+ * 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
+ * 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
+ * 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"
-#include "ord.h"
-namespace Geom {
+#include <2geom/path.h>
+#include <algorithm>
-int CurveHelpers::root_winding(Curve const &c, Point p) {
- std::vector<double> ts = c.roots(p[Y], Y);
- if(ts.empty()) return 0;
+using namespace Geom::PathInternal;
- double const fudge = 0.01; //fudge factor used on first and last
-
- std::sort(ts.begin(), ts.end());
-
- // winding determined by crossings at roots
- int wind=0;
- // previous time
- double pt = ts.front() - fudge;
- for ( std::vector<double>::iterator ti = ts.begin()
- ; ti != ts.end()
- ; ++ti )
- {
- double t = *ti;
- if ( t <= 0. || t >= 1. ) continue; //skip endpoint roots
- if ( c.valueAt(t, X) > p[X] ) { // root is ray intersection
- // Get t of next:
- std::vector<double>::iterator next = ti;
- next++;
- double nt;
- if(next == ts.end()) nt = t + fudge; else nt = *next;
-
- // Check before in time and after in time for positions
- // Currently we're using the average times between next and previous segs
- Cmp after_to_ray = cmp(c.valueAt((t + nt) / 2, Y), p[Y]);
- Cmp before_to_ray = cmp(c.valueAt((t + pt) / 2, Y), p[Y]);
- // if y is included, these will have opposite values, giving order.
- Cmp dt = cmp(after_to_ray, before_to_ray);
- if(dt != EQUAL_TO) //Should always be true, but yah never know..
- wind += dt;
- pt = t;
- }
- }
-
- return wind;
-}
-
-
-template<>
-inline
-double LineSegment::nearestPoint(Point const& p, double from, double to) const
+namespace Geom
{
- if ( from > to ) std::swap(from, to);
- Point ip = pointAt(from);
- Point fp = pointAt(to);
- Point v = fp - ip;
- double t = dot( p - ip, v ) / L2sq(v);
- if ( t <= 0 ) return from;
- else if ( t >= 1 ) return to;
- else return from + t*(to-from);
-}
-
-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::boundsFast() const {
- Rect bounds=front().boundsFast();
- for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
- bounds.unionWith(iter->boundsFast());
+OptRect Path::boundsFast() const {
+ OptRect bounds;
+ if (empty()) return bounds;
+ bounds=front().boundsFast();
+ const_iterator iter = begin();
+ if ( iter != end() ) {
+ for ( ++iter; iter != end() ; ++iter ) {
+ bounds.unionWith(iter->boundsFast());
+ }
}
return bounds;
}
-Rect Path::boundsExact() const {
- Rect bounds=front().boundsExact();
- for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
- bounds.unionWith(iter->boundsExact());
+OptRect Path::boundsExact() const {
+ OptRect bounds;
+ if (empty()) return bounds;
+ bounds=front().boundsExact();
+ const_iterator iter = begin();
+ if ( iter != end() ) {
+ for ( ++iter; iter != end() ; ++iter ) {
+ bounds.unionWith(iter->boundsExact());
+ }
}
return bounds;
}
return ret;
}
-std::vector<double>
+Path &Path::operator*=(Matrix const &m) {
+ unshare();
+ Sequence::iterator last = get_curves().end() - 1;
+ Sequence::iterator it;
+ Point prev;
+ for (it = get_curves().begin() ; it != last ; ++it) {
+ *it = boost::shared_ptr<Curve>((*it)->transformed(m));
+ if ( it != get_curves().begin() && (*it)->initialPoint() != prev ) {
+ THROW_CONTINUITYERROR();
+ }
+ prev = (*it)->finalPoint();
+ }
+ for ( int i = 0 ; i < 2 ; ++i ) {
+ final_->setPoint(i, (*final_)[i] * m);
+ }
+ if (get_curves().size() > 1) {
+ if ( front().initialPoint() != initialPoint() || back().finalPoint() != finalPoint() ) {
+ THROW_CONTINUITYERROR();
+ }
+ }
+ return *this;
+}
+
+std::vector<double>
Path::allNearestPoints(Point const& _point, double from, double to) const
{
if ( from > to ) std::swap(from, to);
}
if ( si == ei )
{
- std::vector<double> all_nearest =
+ std::vector<double> all_nearest =
_path[si].allNearestPoints(_point, st, et);
for ( unsigned int i = 0; i < all_nearest.size(); ++i )
{
std::vector<unsigned int> ni;
ni.push_back(si);
double dsq;
- double mindistsq
+ double mindistsq
= distanceSq( _point, _path[si].pointAt( all_np.front().front() ) );
- Rect bb;
+ Rect bb(Geom::Point(0,0),Geom::Point(0,0));
for ( unsigned int i = si + 1; i < ei; ++i )
{
- bb = _path[i].boundsFast();
+ bb = *(_path[i].boundsFast());
dsq = distanceSq(_point, bb);
if ( mindistsq < dsq ) continue;
all_t = _path[i].allNearestPoints(_point);
ni.push_back(i);
}
}
- bb = _path[ei].boundsFast();
+ bb = *(_path[ei].boundsFast());
dsq = distanceSq(_point, bb);
if ( mindistsq >= dsq )
{
all_nearest.push_back( ni[i] + all_np[i][j] );
}
}
- return all_nearest;
+ all_nearest.erase(std::unique(all_nearest.begin(), all_nearest.end()),
+ all_nearest.end());
+ return all_nearest;
}
-double Path::nearestPoint(Point const& _point, double from, double to) const
+std::vector<double>
+Path::nearestPointPerCurve(Point const& _point) const
+{
+ //return a single nearest point for each curve in this path
+ std::vector<double> np;
+ for (const_iterator it = begin() ; it != end_default(); ++it)
+ //for (std::vector<Path>::const_iterator it = _path.begin(); it != _path.end(), ++it){
+ {
+ np.push_back(it->nearestPoint(_point));
+ }
+ return np;
+}
+
+double Path::nearestPoint(Point const &_point, double from, double to, double *distance_squared) const
{
if ( from > to ) std::swap(from, to);
const Path& _path = *this;
double eif, et = modf(to, &eif);
unsigned int si = static_cast<unsigned int>(sif);
unsigned int ei = static_cast<unsigned int>(eif);
+ if(sz == 0) {// naked moveto
+ if (distance_squared != NULL)
+ *distance_squared = distanceSq(_point, _path.initialPoint());
+ return 0;
+ }
if ( si == sz )
{
--si;
}
if ( si == ei )
{
- double nearest =
- _path[si].nearestPoint(_point, st, et);
+ double nearest = _path[si].nearestPoint(_point, st, et);
+ if (distance_squared != NULL)
+ *distance_squared = distanceSq(_point, _path[si].pointAt(nearest));
return si + nearest;
}
+
double t;
double nearest = _path[si].nearestPoint(_point, st);
unsigned int ni = si;
double dsq;
double mindistsq = distanceSq(_point, _path[si].pointAt(nearest));
- Rect bb;
+ Rect bb(Geom::Point(0,0),Geom::Point(0,0));
for ( unsigned int i = si + 1; i < ei; ++i )
{
- bb = _path[i].boundsFast();
+ bb = *(_path[i].boundsFast());
dsq = distanceSq(_point, bb);
if ( mindistsq <= dsq ) continue;
t = _path[i].nearestPoint(_point);
mindistsq = dsq;
}
}
- bb = _path[ei].boundsFast();
+ bb = *(_path[ei].boundsFast());
dsq = distanceSq(_point, bb);
if ( mindistsq > dsq )
{
{
nearest = t;
ni = ei;
+ mindistsq = dsq;
}
}
+
+ if (distance_squared != NULL)
+ *distance_squared = mindistsq;
+
return ni + nearest;
}
-//This assumes that you can't be perfect in your t-vals, and as such, tweaks the start
void Path::appendPortionTo(Path &ret, double from, double to) const {
- assert(from >= 0 && to >= 0);
+ if (!(from >= 0 && to >= 0)) {
+ THROW_RANGEERROR("from and to must be >=0 in Path::appendPortionTo");
+ }
if(to == 0) to = size()+0.999999;
if(from == to) { return; }
double fi, ti;
const_iterator fromi = inc(begin(), (unsigned)fi);
if(fi == ti && from < to) {
Curve *v = fromi->portion(ff, tf);
- ret.append(*v);
+ ret.append(*v, STITCH_DISCONTINUOUS);
delete v;
return;
}
if(ff != 1.) {
Curve *fromv = fromi->portion(ff, 1.);
//fromv->setInitial(ret.finalPoint());
- ret.append(*fromv);
+ ret.append(*fromv, STITCH_DISCONTINUOUS);
delete fromv;
}
if(from >= to) {
const_iterator ender = end();
if(ender->initialPoint() == ender->finalPoint()) ender++;
- ret.insert(ret.end(), ++fromi, ender);
- ret.insert(ret.end(), begin(), toi);
+ ret.insert(ret.end(), ++fromi, ender, STITCH_DISCONTINUOUS);
+ ret.insert(ret.end(), begin(), toi, STITCH_DISCONTINUOUS);
} else {
- ret.insert(ret.end(), ++fromi, toi);
+ ret.insert(ret.end(), ++fromi, toi, STITCH_DISCONTINUOUS);
}
Curve *tov = toi->portion(0., tf);
- ret.append(*tov);
+ ret.append(*tov, STITCH_DISCONTINUOUS);
delete tov;
}
-const double eps = .1;
-
-void Path::append(Curve const &curve) {
- if ( curves_.front() != final_ && !are_near(curve.initialPoint(), (*final_)[0], eps) ) {
- 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 ( !are_near(curve[i][0][0], (*final_)[0][i], eps) ) {
- 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)
+ 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);
+ get_curves().erase(first_replaced, last_replaced);
+ get_curves().insert(first_replaced, first, last);
}
- if ( curves_.front() != final_ ) {
+ if ( get_curves().front().get() != final_ ) {
final_->setPoint(0, back().finalPoint());
final_->setPoint(1, front().initialPoint());
}
}
-void Path::do_append(Curve *curve) {
- if ( curves_.front() == final_ ) {
+void Path::do_append(Curve *c) {
+ boost::shared_ptr<Curve> curve(c);
+ if ( get_curves().front().get() == final_ ) {
final_->setPoint(1, curve->initialPoint());
+ } else {
+ if (curve->initialPoint() != finalPoint()) {
+ THROW_CONTINUITYERROR();
+ }
}
- curves_.insert(curves_.end()-1, curve);
+ get_curves().insert(get_curves().end()-1, curve);
final_->setPoint(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::stitch(Sequence::iterator first_replaced,
+ Sequence::iterator last_replaced,
+ Sequence &source)
+{
+ if (!source.empty()) {
+ if ( first_replaced != get_curves().begin() ) {
+ if ( (*first_replaced)->initialPoint() != source.front()->initialPoint() ) {
+ Curve *stitch = new StitchSegment((*first_replaced)->initialPoint(),
+ source.front()->initialPoint());
+ source.insert(source.begin(), boost::shared_ptr<Curve>(stitch));
+ }
+ }
+ if ( last_replaced != (get_curves().end()-1) ) {
+ if ( (*last_replaced)->finalPoint() != source.back()->finalPoint() ) {
+ Curve *stitch = new StitchSegment(source.back()->finalPoint(),
+ (*last_replaced)->finalPoint());
+ source.insert(source.end(), boost::shared_ptr<Curve>(stitch));
+ }
+ }
+ } else if ( first_replaced != last_replaced && first_replaced != get_curves().begin() && last_replaced != get_curves().end()-1) {
+ if ( (*first_replaced)->initialPoint() != (*(last_replaced-1))->finalPoint() ) {
+ Curve *stitch = new StitchSegment((*(last_replaced-1))->finalPoint(),
+ (*first_replaced)->initialPoint());
+ source.insert(source.begin(), boost::shared_ptr<Curve>(stitch));
+ }
}
}
Sequence::iterator last)
{
if ( first != last ) {
- if ( first_replaced != curves_.begin() ) {
- if ( !are_near( (*first_replaced)->initialPoint(), (*first)->initialPoint(), eps ) ) {
+ if ( first_replaced != get_curves().begin() ) {
+ if ( (*first_replaced)->initialPoint() != (*first)->initialPoint() ) {
THROW_CONTINUITYERROR();
}
}
- if ( last_replaced != (curves_.end()-1) ) {
- if ( !are_near( (*(last_replaced-1))->finalPoint(), (*(last-1))->finalPoint(), eps ) ) {
+ if ( last_replaced != (get_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 ( !are_near((*first_replaced)->initialPoint(), (*(last_replaced-1))->finalPoint(), eps ) ) {
+ } else if ( first_replaced != last_replaced && first_replaced != get_curves().begin() && last_replaced != get_curves().end()-1) {
+ if ( (*first_replaced)->initialPoint() != (*(last_replaced-1))->finalPoint() ) {
THROW_CONTINUITYERROR();
}
}
fill-column:99
End:
*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :