diff --git a/src/2geom/piecewise.h b/src/2geom/piecewise.h
index 28d95edd5e07a23d842888bd33460067985561a8..62185b472267259fd49041805961b1c593ded703 100644 (file)
--- a/src/2geom/piecewise.h
+++ b/src/2geom/piecewise.h
-/*
- * piecewise.h - Piecewise function class
+/**
+ * \file
+ * \brief Piecewise function class
*
* Copyright 2007 Michael Sloan <mgsloan@gmail.com>
*
#ifndef SEEN_GEOM_PW_SB_H
#define SEEN_GEOM_PW_SB_H
-#include "sbasis.h"
-//#include "sbasis-2d.h"
+#include <2geom/sbasis.h>
#include <vector>
#include <map>
-#include "concepts.h"
-#include "isnan.h"
+#include <2geom/concepts.h>
+#include <2geom/isnan.h>
#include <boost/concept_check.hpp>
namespace Geom {
-
+/**
+ * %Piecewise function class.
+ * The Piecewise class manages a sequence of elements of a type as segments and
+ * the ’cuts’ between them. These cuts are time values which separate the pieces.
+ * This function representation allows for more interesting functions, as it provides
+ * a viable output for operations such as inversion, which may require multiple
+ * SBasis to properly invert the original.
+ * As for technical details, while the actual SBasis segments begin on the first
+ * cut and end on the last, the function is defined throughout all inputs by ex-
+ * tending the first and last segments. The exact switching between segments is
+ * arbitrarily such that beginnings (t=0) have preference over endings (t=1). This
+ * only matters if it is discontinuous at the location.
+ * \f[
+ * f(t) \rightarrow \left\{
+ * \begin{array}{cc}
+ * s_1,& t <= c_2 \\
+ * s_2,& c_2 <= t <= c_3\\
+ * \ldots \\
+ * s_n,& c_n <= t
+ * \end{array}\right.
+ * \f]
+ */
template <typename T>
class Piecewise {
BOOST_CLASS_REQUIRE(T, Geom, FragmentConcept);
push_cut(1.);
}
+ unsigned input_dim(){return 1;}
+
typedef typename T::output_type output_type;
explicit Piecewise(const output_type & v) {
push_cut(1.);
}
+ inline void reserve(unsigned i) { segs.reserve(i); cuts.reserve(i + 1); }
+
inline T operator[](unsigned i) const { return segs[i]; }
inline T &operator[](unsigned i) { return segs[i]; }
inline output_type operator()(double t) const { return valueAt(t); }
inline output_type lastValue() const {
return valueAt(cuts.back());
}
- std::vector<output_type> valueAndDerivatives(double t, unsigned cnt) const {
+
+ /**
+ * The size of the returned vector equals n_derivs+1.
+ */
+ std::vector<output_type> valueAndDerivatives(double t, unsigned n_derivs) const {
unsigned n = segN(t);
- std::vector<output_type> ret, val = segs[n].valueAndDerivatives(segT(t, n), cnt);
+ std::vector<output_type> ret, val = segs[n].valueAndDerivatives(segT(t, n), n_derivs);
double mult = 1;
for(unsigned i = 0; i < val.size(); i++) {
ret.push_back(val[i] * mult);
}
return ret;
}
+
//TODO: maybe it is not a good idea to have this?
Piecewise<T> operator()(SBasis f);
Piecewise<T> operator()(Piecewise<SBasis>f);
//Transforms the domain into another interval
inline void setDomain(Interval dom) {
if(empty()) return;
+ /* dom can not be empty
if(dom.isEmpty()) {
cuts.clear(); segs.clear();
return;
- }
+ }*/
double cf = cuts.front();
double o = dom.min() - cf, s = dom.extent() / (cuts.back() - cf);
for(unsigned i = 0; i <= size(); i++)
cuts[i] = (cuts[i] - cf) * s + o;
+ //fix floating point precision errors.
+ cuts[0] = dom.min();
+ cuts[size()] = dom.max();
}
//Concatenates this Piecewise function with another, offseting time of the other to match the end.
segs.insert(segs.end(), other.segs.begin(), other.segs.end());
double t = cuts.back() - other.cuts.front();
+ cuts.reserve(cuts.size() + other.size());
for(unsigned i = 0; i < other.size(); i++)
push_cut(other.cuts[i + 1] + t);
}
inline void continuousConcat(const Piecewise<T> &other) {
boost::function_requires<AddableConcept<typename T::output_type> >();
if(other.empty()) return;
- typename T::output_type y = segs.back().at1() - other.segs.front().at0();
- if(empty()) {
- for(unsigned i = 0; i < other.size(); i++)
- push_seg(other[i] + y);
- cuts = other.cuts;
- return;
- }
+ if(empty()) { segs = other.segs; cuts = other.cuts; return; }
+ typename T::output_type y = segs.back().at1() - other.segs.front().at0();
double t = cuts.back() - other.cuts.front();
+ reserve(size() + other.size());
for(unsigned i = 0; i < other.size(); i++)
push(other[i] + y, other.cuts[i + 1] + t);
}
@@ -257,11 +288,12 @@ inline typename FragmentConcept<T>::BoundsType bounds_exact(const Piecewise<T> &
}
template<typename T>
-inline typename FragmentConcept<T>::BoundsType bounds_local(const Piecewise<T> &f, const Interval &m) {
+inline typename FragmentConcept<T>::BoundsType bounds_local(const Piecewise<T> &f, const OptInterval &_m) {
boost::function_requires<FragmentConcept<T> >();
- if(f.empty()) return typename FragmentConcept<T>::BoundsType();
- if(m.isEmpty()) return typename FragmentConcept<T>::BoundsType(f(m.min()));
+ if(f.empty() || !_m) return typename FragmentConcept<T>::BoundsType();
+ Interval const &m = *_m;
+ if(m.isSingular()) return typename FragmentConcept<T>::BoundsType(f(m.min()));
unsigned fi = f.segN(m.min()), ti = f.segN(m.max());
double ft = f.segT(m.min(), fi), tt = f.segT(m.max(), ti);
if(c.empty()) return Piecewise<T>(pw);
Piecewise<T> ret = Piecewise<T>();
- ret.cuts.reserve(c.size() + pw.cuts.size());
- ret.segs.reserve(c.size() + pw.cuts.size() - 1);
+ ret.reserve(c.size() + pw.cuts.size() - 1);
if(pw.empty()) {
ret.cuts = c;
unsigned i = pw.segN(from);
ret.push_cut(from);
- if(i == pw.size() - 1 || to < pw.cuts[i + 1]) { //to/from inhabit the same segment
+ if(i == pw.size() - 1 || to <= pw.cuts[i + 1]) { //to/from inhabit the same segment
ret.push(elem_portion(pw, i, from, to), to);
return ret;
}
ret.push_seg(portion( pw[i], pw.segT(from, i), 1.0 ));
i++;
unsigned fi = pw.segN(to, i);
+ ret.reserve(fi - i + 1);
+ if (to == pw.cuts[fi]) fi-=1;
ret.segs.insert(ret.segs.end(), pw.segs.begin() + i, pw.segs.begin() + fi); //copy segs
ret.cuts.insert(ret.cuts.end(), pw.cuts.begin() + i, pw.cuts.begin() + fi + 1); //and their cuts
return ret;
}
+//TODO: seems like these should be mutating
template<typename T>
Piecewise<T> remove_short_cuts(Piecewise<T> const &f, double tol) {
if(f.empty()) return f;
Piecewise<T> ret;
+ ret.reserve(f.size());
ret.push_cut(f.cuts[0]);
for(unsigned i=0; i<f.size(); i++){
if (f.cuts[i+1]-f.cuts[i] >= tol || i==f.size()-1) {
return ret;
}
+//TODO: seems like these should be mutating
template<typename T>
Piecewise<T> remove_short_cuts_extending(Piecewise<T> const &f, double tol) {
if(f.empty()) return f;
Piecewise<T> ret;
+ ret.reserve(f.size());
ret.push_cut(f.cuts[0]);
double last = f.cuts[0]; // last cut included
for(unsigned i=0; i<f.size(); i++){
Piecewise<T> operator+(Piecewise<T> const &a, typename T::output_type b) {
boost::function_requires<OffsetableConcept<T> >();
//TODO:empty
- Piecewise<T> ret = Piecewise<T>();
+ Piecewise<T> ret;
+ ret.segs.reserve(a.size());
ret.cuts = a.cuts;
for(unsigned i = 0; i < a.size();i++)
ret.push_seg(a[i] + b);
Piecewise<T> operator-(Piecewise<T> const &a, typename T::output_type b) {
boost::function_requires<OffsetableConcept<T> >();
//TODO: empty
- Piecewise<T> ret = Piecewise<T>();
+ Piecewise<T> ret;
+ ret.segs.reserve(a.size());
ret.cuts = a.cuts;
for(unsigned i = 0; i < a.size();i++)
ret.push_seg(a[i] - b);
return ret;
}
template<typename T>
-Piecewise<T> operator+=(Piecewise<T>& a, typename T::output_type b) {
+Piecewise<T>& operator+=(Piecewise<T>& a, typename T::output_type b) {
boost::function_requires<OffsetableConcept<T> >();
if(a.empty()) { a.push_cut(0.); a.push(T(b), 1.); return a; }
return a;
}
template<typename T>
-Piecewise<T> operator-=(Piecewise<T>& a, typename T::output_type b) {
+Piecewise<T>& operator-=(Piecewise<T>& a, typename T::output_type b) {
boost::function_requires<OffsetableConcept<T> >();
- if(a.empty()) { a.push_cut(0.); a.push(T(b), 1.); return a; }
+ if(a.empty()) { a.push_cut(0.); a.push(T(-b), 1.); return a; }
for(unsigned i = 0;i < a.size();i++)
a[i] -= b;
boost::function_requires<ScalableConcept<T> >();
Piecewise<T> ret;
+ ret.segs.reserve(a.size());
ret.cuts = a.cuts;
for(unsigned i = 0; i < a.size();i++)
ret.push_seg(- a[i]);
if(a.empty()) return Piecewise<T>();
Piecewise<T> ret;
+ ret.segs.reserve(a.size());
+ ret.cuts = a.cuts;
+ for(unsigned i = 0; i < a.size();i++)
+ ret.push_seg(a[i] * b);
+ return ret;
+}
+template<typename T>
+Piecewise<T> operator*(Piecewise<T> const &a, T b) {
+ boost::function_requires<ScalableConcept<T> >();
+
+ if(a.empty()) return Piecewise<T>();
+
+ Piecewise<T> ret;
+ ret.segs.reserve(a.size());
ret.cuts = a.cuts;
for(unsigned i = 0; i < a.size();i++)
ret.push_seg(a[i] * b);
if(a.empty()) return Piecewise<T>();
Piecewise<T> ret;
+ ret.segs.reserve(a.size());
ret.cuts = a.cuts;
for(unsigned i = 0; i < a.size();i++)
ret.push_seg(a[i] / b);
return ret;
}
template<typename T>
-Piecewise<T> operator*=(Piecewise<T>& a, double b) {
+Piecewise<T>& operator*=(Piecewise<T>& a, double b) {
boost::function_requires<ScalableConcept<T> >();
- if(a.empty()) return Piecewise<T>();
-
for(unsigned i = 0; i < a.size();i++)
a[i] *= b;
return a;
}
template<typename T>
-Piecewise<T> operator/=(Piecewise<T>& a, double b) {
+Piecewise<T>& operator/=(Piecewise<T>& a, double b) {
boost::function_requires<ScalableConcept<T> >();
//FIXME: b == 0?
- if(a.empty()) return Piecewise<T>();
for(unsigned i = 0; i < a.size();i++)
a[i] /= b;
boost::function_requires<AddableConcept<T> >();
Piecewise<T> pa = partition(a, b.cuts), pb = partition(b, a.cuts);
- Piecewise<T> ret = Piecewise<T>();
+ Piecewise<T> ret;
assert(pa.size() == pb.size());
+ ret.segs.reserve(pa.size());
ret.cuts = pa.cuts;
for (unsigned i = 0; i < pa.size(); i++)
ret.push_seg(pa[i] + pb[i]);
Piecewise<T> pa = partition(a, b.cuts), pb = partition(b, a.cuts);
Piecewise<T> ret = Piecewise<T>();
assert(pa.size() == pb.size());
+ ret.segs.reserve(pa.size());
ret.cuts = pa.cuts;
for (unsigned i = 0; i < pa.size(); i++)
ret.push_seg(pa[i] - pb[i]);
return ret;
}
template<typename T>
-inline Piecewise<T> operator+=(Piecewise<T> &a, Piecewise<T> const &b) {
+inline Piecewise<T>& operator+=(Piecewise<T> &a, Piecewise<T> const &b) {
a = a+b;
return a;
}
template<typename T>
-inline Piecewise<T> operator-=(Piecewise<T> &a, Piecewise<T> const &b) {
+inline Piecewise<T>& operator-=(Piecewise<T> &a, Piecewise<T> const &b) {
a = a-b;
return a;
}
Piecewise<T2> pb = partition(b, a.cuts);
Piecewise<T2> ret = Piecewise<T2>();
assert(pa.size() == pb.size());
+ ret.segs.reserve(pa.size());
ret.cuts = pa.cuts;
for (unsigned i = 0; i < pa.size(); i++)
ret.push_seg(pa[i] * pb[i]);
}
template<typename T>
-inline Piecewise<T> operator*=(Piecewise<T> &a, Piecewise<T> const &b) {
+inline Piecewise<T>& operator*=(Piecewise<T> &a, Piecewise<T> const &b) {
a = a * b;
return a;
}
}
//first check bounds...
- Interval bs = bounds_fast(g);
+ Interval bs = *bounds_fast(g);
if (f.cuts.front() > bs.max() || bs.min() > f.cuts.back()){
int idx = (bs.max() < f.cuts[1]) ? 0 : f.cuts.size()-2;
double t0 = f.cuts[idx], width = f.cuts[idx+1] - t0;
std::vector<double> roots(Piecewise<SBasis> const &f);
+std::vector<std::vector<double> >multi_roots(Piecewise<SBasis> const &f, std::vector<double> const &values);
+
+template<typename T>
+Piecewise<T> reverse(Piecewise<T> const &f) {
+ Piecewise<T> ret = Piecewise<T>();
+ ret.reserve(f.size());
+ double start = f.cuts[0];
+ double end = f.cuts.back();
+ for (unsigned i = 0; i < f.cuts.size(); i++) {
+ double x = f.cuts[f.cuts.size() - 1 - i];
+ ret.push_cut(end - (x - start));
+ }
+ for (unsigned i = 0; i < f.segs.size(); i++)
+ ret.push_seg(reverse(f[f.segs.size() - i - 1]));
+ return ret;
}
+/**
+ * Interpolates between a and b.
+ * \return a if t = 0, b if t = 1, or an interpolation between a and b for t in [0,1]
+ * \relates Piecewise
+ */
+template<typename T>
+Piecewise<T> lerp(double t, Piecewise<T> const &a, Piecewise<T> b) {
+ // Make sure both paths have the same number of segments and cuts at the same locations
+ b.setDomain(a.domain());
+ Piecewise<T> pA = partition(a, b.cuts);
+ Piecewise<T> pB = partition(b, a.cuts);
+
+ return (pA*(1-t) + pB*t);
+}
+
+}
#endif //SEEN_GEOM_PW_SB_H
/*
Local Variables:
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 :