summaryrefslogtreecommitdiffstats
path: root/src/2geom/path.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/2geom/path.cpp')
-rw-r--r--src/2geom/path.cpp188
1 files changed, 183 insertions, 5 deletions
diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp
index 01c1f2b8e..fdfa77c79 100644
--- a/src/2geom/path.cpp
+++ b/src/2geom/path.cpp
@@ -33,6 +33,7 @@
namespace Geom {
+
int CurveHelpers::root_winding(Curve const &c, Point p) {
std::vector<double> ts = c.roots(p[Y], Y);
@@ -74,6 +75,22 @@ int CurveHelpers::root_winding(Curve const &c, Point p) {
return wind;
}
+
+template<>
+inline
+double LineSegment::nearestPoint(Point const& p, double from, double to) const
+{
+ 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_);
@@ -106,6 +123,167 @@ iter inc(iter const &x, unsigned n) {
return ret;
}
+std::vector<double>
+Path::allNearestPoints(Point const& _point, double from, double to) const
+{
+ if ( from > to ) std::swap(from, to);
+ const Path& _path = *this;
+ unsigned int sz = _path.size();
+ if ( _path.closed() ) ++sz;
+ if ( from < 0 || to > sz )
+ {
+ THROW_RANGEERROR("[from,to] interval out of bounds");
+ }
+ double sif, st = modf(from, &sif);
+ double eif, et = modf(to, &eif);
+ unsigned int si = static_cast<unsigned int>(sif);
+ unsigned int ei = static_cast<unsigned int>(eif);
+ if ( si == sz )
+ {
+ --si;
+ st = 1;
+ }
+ if ( ei == sz )
+ {
+ --ei;
+ et = 1;
+ }
+ if ( si == ei )
+ {
+ std::vector<double> all_nearest =
+ _path[si].allNearestPoints(_point, st, et);
+ for ( unsigned int i = 0; i < all_nearest.size(); ++i )
+ {
+ all_nearest[i] = si + all_nearest[i];
+ }
+ return all_nearest;
+ }
+ std::vector<double> all_t;
+ std::vector< std::vector<double> > all_np;
+ all_np.push_back( _path[si].allNearestPoints(_point, st) );
+ std::vector<unsigned int> ni;
+ ni.push_back(si);
+ double dsq;
+ double mindistsq
+ = distanceSq( _point, _path[si].pointAt( all_np.front().front() ) );
+ Rect bb;
+ for ( unsigned int i = si + 1; i < ei; ++i )
+ {
+ bb = _path[i].boundsFast();
+ dsq = distanceSq(_point, bb);
+ if ( mindistsq < dsq ) continue;
+ all_t = _path[i].allNearestPoints(_point);
+ dsq = distanceSq( _point, _path[i].pointAt( all_t.front() ) );
+ if ( mindistsq > dsq )
+ {
+ all_np.clear();
+ all_np.push_back(all_t);
+ ni.clear();
+ ni.push_back(i);
+ mindistsq = dsq;
+ }
+ else if ( mindistsq == dsq )
+ {
+ all_np.push_back(all_t);
+ ni.push_back(i);
+ }
+ }
+ bb = _path[ei].boundsFast();
+ dsq = distanceSq(_point, bb);
+ if ( mindistsq >= dsq )
+ {
+ all_t = _path[ei].allNearestPoints(_point, 0, et);
+ dsq = distanceSq( _point, _path[ei].pointAt( all_t.front() ) );
+ if ( mindistsq > dsq )
+ {
+ for ( unsigned int i = 0; i < all_t.size(); ++i )
+ {
+ all_t[i] = ei + all_t[i];
+ }
+ return all_t;
+ }
+ else if ( mindistsq == dsq )
+ {
+ all_np.push_back(all_t);
+ ni.push_back(ei);
+ }
+ }
+ std::vector<double> all_nearest;
+ for ( unsigned int i = 0; i < all_np.size(); ++i )
+ {
+ for ( unsigned int j = 0; j < all_np[i].size(); ++j )
+ {
+ all_nearest.push_back( ni[i] + all_np[i][j] );
+ }
+ }
+ return all_nearest;
+}
+
+double Path::nearestPoint(Point const& _point, double from, double to) const
+{
+ if ( from > to ) std::swap(from, to);
+ const Path& _path = *this;
+ unsigned int sz = _path.size();
+ if ( _path.closed() ) ++sz;
+ if ( from < 0 || to > sz )
+ {
+ THROW_RANGEERROR("[from,to] interval out of bounds");
+ }
+ double sif, st = modf(from, &sif);
+ double eif, et = modf(to, &eif);
+ unsigned int si = static_cast<unsigned int>(sif);
+ unsigned int ei = static_cast<unsigned int>(eif);
+ if ( si == sz )
+ {
+ --si;
+ st = 1;
+ }
+ if ( ei == sz )
+ {
+ --ei;
+ et = 1;
+ }
+ if ( si == ei )
+ {
+ double nearest =
+ _path[si].nearestPoint(_point, st, et);
+ 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;
+ for ( unsigned int i = si + 1; i < ei; ++i )
+ {
+ bb = _path[i].boundsFast();
+ dsq = distanceSq(_point, bb);
+ if ( mindistsq <= dsq ) continue;
+ t = _path[i].nearestPoint(_point);
+ dsq = distanceSq(_point, _path[i].pointAt(t));
+ if ( mindistsq > dsq )
+ {
+ nearest = t;
+ ni = i;
+ mindistsq = dsq;
+ }
+ }
+ bb = _path[ei].boundsFast();
+ dsq = distanceSq(_point, bb);
+ if ( mindistsq > dsq )
+ {
+ t = _path[ei].nearestPoint(_point, 0, et);
+ dsq = distanceSq(_point, _path[ei].pointAt(t));
+ if ( mindistsq > dsq )
+ {
+ nearest = t;
+ ni = ei;
+ }
+ }
+ 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);
@@ -145,7 +323,7 @@ const double eps = .1;
void Path::append(Curve const &curve) {
if ( curves_.front() != final_ && !are_near(curve.initialPoint(), (*final_)[0], eps) ) {
- throwContinuityError();
+ THROW_CONTINUITYERROR();
}
do_append(curve.duplicate());
}
@@ -154,7 +332,7 @@ 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) ) {
- throwContinuityError();
+ THROW_CONTINUITYERROR();
}
}
}
@@ -206,17 +384,17 @@ void Path::check_continuity(Sequence::iterator first_replaced,
if ( first != last ) {
if ( first_replaced != curves_.begin() ) {
if ( !are_near( (*first_replaced)->initialPoint(), (*first)->initialPoint(), eps ) ) {
- throwContinuityError();
+ THROW_CONTINUITYERROR();
}
}
if ( last_replaced != (curves_.end()-1) ) {
if ( !are_near( (*(last_replaced-1))->finalPoint(), (*(last-1))->finalPoint(), eps ) ) {
- throwContinuityError();
+ 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 ) ) {
- throwContinuityError();
+ THROW_CONTINUITYERROR();
}
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 11:11:55 +0000