a5be42587c0be602eb02c28677769e14943bfed7
1 /**
2 * \file
3 * \brief Piecewise function class
4 *
5 * Copyright 2007 Michael Sloan <mgsloan@gmail.com>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it either under the terms of the GNU Lesser General Public
9 * License version 2.1 as published by the Free Software Foundation
10 * (the "LGPL") or, at your option, under the terms of the Mozilla
11 * Public License Version 1.1 (the "MPL"). If you do not alter this
12 * notice, a recipient may use your version of this file under either
13 * the MPL or the LGPL.
14 *
15 * You should have received a copy of the LGPL along with this library
16 * in the file COPYING-LGPL-2.1; if not, output to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 * You should have received a copy of the MPL along with this library
19 * in the file COPYING-MPL-1.1
20 *
21 * The contents of this file are subject to the Mozilla Public License
22 * Version 1.1 (the "License"); you may not use this file except in
23 * compliance with the License. You may obtain a copy of the License at
24 * http://www.mozilla.org/MPL/
25 *
26 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
27 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
28 * the specific language governing rights and limitations.
29 *
30 */
32 #ifndef SEEN_GEOM_PW_SB_H
33 #define SEEN_GEOM_PW_SB_H
35 #include <2geom/sbasis.h>
36 #include <vector>
37 #include <map>
39 #include <2geom/concepts.h>
40 #include <2geom/isnan.h>
41 #include <boost/concept_check.hpp>
43 namespace Geom {
44 /**
45 * %Piecewise function class.
46 * The Piecewise class manages a sequence of elements of a type as segments and
47 * the ’cuts’ between them. These cuts are time values which separate the pieces.
48 * This function representation allows for more interesting functions, as it provides
49 * a viable output for operations such as inversion, which may require multiple
50 * SBasis to properly invert the original.
51 * As for technical details, while the actual SBasis segments begin on the first
52 * cut and end on the last, the function is defined throughout all inputs by ex-
53 * tending the first and last segments. The exact switching between segments is
54 * arbitrarily such that beginnings (t=0) have preference over endings (t=1). This
55 * only matters if it is discontinuous at the location.
56 * \f[
57 * f(t) \rightarrow \left\{
58 * \begin{array}{cc}
59 * s_1,& t <= c_2 \\
60 * s_2,& c_2 <= t <= c_3\\
61 * \ldots
62 * s_n,& c_n <= t
63 * \end{array}\right.
64 * \f]
65 */
66 template <typename T>
67 class Piecewise {
68 BOOST_CLASS_REQUIRE(T, Geom, FragmentConcept);
70 public:
71 std::vector<double> cuts;
72 std::vector<T> segs;
73 //segs[i] stretches from cuts[i] to cuts[i+1].
75 Piecewise() {}
77 explicit Piecewise(const T &s) {
78 push_cut(0.);
79 push_seg(s);
80 push_cut(1.);
81 }
83 unsigned input_dim(){return 1;}
85 typedef typename T::output_type output_type;
87 explicit Piecewise(const output_type & v) {
88 push_cut(0.);
89 push_seg(T(v));
90 push_cut(1.);
91 }
93 inline void reserve(unsigned i) { segs.reserve(i); cuts.reserve(i + 1); }
95 inline T operator[](unsigned i) const { return segs[i]; }
96 inline T &operator[](unsigned i) { return segs[i]; }
97 inline output_type operator()(double t) const { return valueAt(t); }
98 inline output_type valueAt(double t) const {
99 unsigned n = segN(t);
100 return segs[n](segT(t, n));
101 }
102 inline output_type firstValue() const {
103 return valueAt(cuts.front());
104 }
105 inline output_type lastValue() const {
106 return valueAt(cuts.back());
107 }
108 std::vector<output_type> valueAndDerivatives(double t, unsigned n_derivs) const {
109 unsigned n = segN(t);
110 std::vector<output_type> ret, val = segs[n].valueAndDerivatives(segT(t, n), n_derivs);
111 double mult = 1;
112 for(unsigned i = 0; i < val.size(); i++) {
113 ret.push_back(val[i] * mult);
114 mult /= cuts[n+1] - cuts[n];
115 }
116 return ret;
117 }
118 //TODO: maybe it is not a good idea to have this?
119 Piecewise<T> operator()(SBasis f);
120 Piecewise<T> operator()(Piecewise<SBasis>f);
122 inline unsigned size() const { return segs.size(); }
123 inline bool empty() const { return segs.empty(); }
124 inline void clear() {
125 segs.clear();
126 cuts.clear();
127 }
129 /**Convenience/implementation hiding function to add segment/cut pairs.
130 * Asserts that basic size and order invariants are correct
131 */
132 inline void push(const T &s, double to) {
133 assert(cuts.size() - segs.size() == 1);
134 push_seg(s);
135 push_cut(to);
136 }
137 //Convenience/implementation hiding function to add cuts.
138 inline void push_cut(double c) {
139 ASSERT_INVARIANTS(cuts.empty() || c > cuts.back());
140 cuts.push_back(c);
141 }
142 //Convenience/implementation hiding function to add segments.
143 inline void push_seg(const T &s) { segs.push_back(s); }
145 /**Returns the segment index which corresponds to a 'global' piecewise time.
146 * Also takes optional low/high parameters to expedite the search for the segment.
147 */
148 inline unsigned segN(double t, int low = 0, int high = -1) const {
149 high = (high == -1) ? size() : high;
150 if(t < cuts[0]) return 0;
151 if(t >= cuts[size()]) return size() - 1;
152 while(low < high) {
153 int mid = (high + low) / 2; //Lets not plan on having huge (> INT_MAX / 2) cut sequences
154 double mv = cuts[mid];
155 if(mv < t) {
156 if(t < cuts[mid + 1]) return mid; else low = mid + 1;
157 } else if(t < mv) {
158 if(cuts[mid - 1] < t) return mid - 1; else high = mid - 1;
159 } else {
160 return mid;
161 }
162 }
163 return low;
164 }
166 /**Returns the time within a segment, given the 'global' piecewise time.
167 * Also takes an optional index parameter which may be used for efficiency or to find the time on a
168 * segment outside its range. If it is left to its default, -1, it will call segN to find the index.
169 */
170 inline double segT(double t, int i = -1) const {
171 if(i == -1) i = segN(t);
172 assert(i >= 0);
173 return (t - cuts[i]) / (cuts[i+1] - cuts[i]);
174 }
176 inline double mapToDomain(double t, unsigned i) const {
177 return (1-t)*cuts[i] + t*cuts[i+1]; //same as: t * (cuts[i+1] - cuts[i]) + cuts[i]
178 }
180 //Offsets the piecewise domain
181 inline void offsetDomain(double o) {
182 assert(IS_FINITE(o));
183 if(o != 0)
184 for(unsigned i = 0; i <= size(); i++)
185 cuts[i] += o;
186 }
188 //Scales the domain of the function by a value. 0 will result in an empty Piecewise.
189 inline void scaleDomain(double s) {
190 assert(s > 0);
191 if(s == 0) {
192 cuts.clear(); segs.clear();
193 return;
194 }
195 for(unsigned i = 0; i <= size(); i++)
196 cuts[i] *= s;
197 }
199 //Retrieves the domain in interval form
200 inline Interval domain() const { return Interval(cuts.front(), cuts.back()); }
202 //Transforms the domain into another interval
203 inline void setDomain(Interval dom) {
204 if(empty()) return;
205 /* dom can not be empty
206 if(dom.isEmpty()) {
207 cuts.clear(); segs.clear();
208 return;
209 }*/
210 double cf = cuts.front();
211 double o = dom.min() - cf, s = dom.extent() / (cuts.back() - cf);
212 for(unsigned i = 0; i <= size(); i++)
213 cuts[i] = (cuts[i] - cf) * s + o;
214 //fix floating point precision errors.
215 cuts[0] = dom.min();
216 cuts[size()] = dom.max();
217 }
219 //Concatenates this Piecewise function with another, offseting time of the other to match the end.
220 inline void concat(const Piecewise<T> &other) {
221 if(other.empty()) return;
223 if(empty()) {
224 cuts = other.cuts; segs = other.segs;
225 return;
226 }
228 segs.insert(segs.end(), other.segs.begin(), other.segs.end());
229 double t = cuts.back() - other.cuts.front();
230 cuts.reserve(cuts.size() + other.size());
231 for(unsigned i = 0; i < other.size(); i++)
232 push_cut(other.cuts[i + 1] + t);
233 }
235 //Like concat, but ensures continuity.
236 inline void continuousConcat(const Piecewise<T> &other) {
237 boost::function_requires<AddableConcept<typename T::output_type> >();
238 if(other.empty()) return;
240 if(empty()) { segs = other.segs; cuts = other.cuts; return; }
242 typename T::output_type y = segs.back().at1() - other.segs.front().at0();
243 double t = cuts.back() - other.cuts.front();
244 reserve(size() + other.size());
245 for(unsigned i = 0; i < other.size(); i++)
246 push(other[i] + y, other.cuts[i + 1] + t);
247 }
249 //returns true if the Piecewise<T> meets some basic invariants.
250 inline bool invariants() const {
251 // segs between cuts
252 if(!(segs.size() + 1 == cuts.size() || (segs.empty() && cuts.empty())))
253 return false;
254 // cuts in order
255 for(unsigned i = 0; i < segs.size(); i++)
256 if(cuts[i] >= cuts[i+1])
257 return false;
258 return true;
259 }
261 };
263 template<typename T>
264 inline typename FragmentConcept<T>::BoundsType bounds_fast(const Piecewise<T> &f) {
265 boost::function_requires<FragmentConcept<T> >();
267 if(f.empty()) return typename FragmentConcept<T>::BoundsType();
268 typename FragmentConcept<T>::BoundsType ret(bounds_fast(f[0]));
269 for(unsigned i = 1; i < f.size(); i++)
270 ret.unionWith(bounds_fast(f[i]));
271 return ret;
272 }
274 template<typename T>
275 inline typename FragmentConcept<T>::BoundsType bounds_exact(const Piecewise<T> &f) {
276 boost::function_requires<FragmentConcept<T> >();
278 if(f.empty()) return typename FragmentConcept<T>::BoundsType();
279 typename FragmentConcept<T>::BoundsType ret(bounds_exact(f[0]));
280 for(unsigned i = 1; i < f.size(); i++)
281 ret.unionWith(bounds_exact(f[i]));
282 return ret;
283 }
285 template<typename T>
286 inline typename FragmentConcept<T>::BoundsType bounds_local(const Piecewise<T> &f, const OptInterval &_m) {
287 boost::function_requires<FragmentConcept<T> >();
289 if(f.empty() || !_m) return typename FragmentConcept<T>::BoundsType();
290 Interval const &m = *_m;
291 if(m.isSingular()) return typename FragmentConcept<T>::BoundsType(f(m.min()));
293 unsigned fi = f.segN(m.min()), ti = f.segN(m.max());
294 double ft = f.segT(m.min(), fi), tt = f.segT(m.max(), ti);
296 if(fi == ti) return bounds_local(f[fi], Interval(ft, tt));
298 typename FragmentConcept<T>::BoundsType ret(bounds_local(f[fi], Interval(ft, 1.)));
299 for(unsigned i = fi + 1; i < ti; i++)
300 ret.unionWith(bounds_exact(f[i]));
301 if(tt != 0.) ret.unionWith(bounds_local(f[ti], Interval(0., tt)));
303 return ret;
304 }
306 //returns a portion of a piece of a Piecewise<T>, given the piece's index and a to/from time.
307 template<typename T>
308 T elem_portion(const Piecewise<T> &a, unsigned i, double from, double to) {
309 assert(i < a.size());
310 double rwidth = 1 / (a.cuts[i+1] - a.cuts[i]);
311 return portion( a[i], (from - a.cuts[i]) * rwidth, (to - a.cuts[i]) * rwidth );
312 }
314 /**Piecewise<T> partition(const Piecewise<T> &pw, std::vector<double> const &c);
315 * Further subdivides the Piecewise<T> such that there is a cut at every value in c.
316 * Precondition: c sorted lower to higher.
317 *
318 * //Given Piecewise<T> a and b:
319 * Piecewise<T> ac = a.partition(b.cuts);
320 * Piecewise<T> bc = b.partition(a.cuts);
321 * //ac.cuts should be equivalent to bc.cuts
322 */
323 template<typename T>
324 Piecewise<T> partition(const Piecewise<T> &pw, std::vector<double> const &c) {
325 assert(pw.invariants());
326 if(c.empty()) return Piecewise<T>(pw);
328 Piecewise<T> ret = Piecewise<T>();
329 ret.reserve(c.size() + pw.cuts.size() - 1);
331 if(pw.empty()) {
332 ret.cuts = c;
333 for(unsigned i = 0; i < c.size() - 1; i++)
334 ret.push_seg(T());
335 return ret;
336 }
338 unsigned si = 0, ci = 0; //Segment index, Cut index
340 //if the cuts have something earlier than the Piecewise<T>, add portions of the first segment
341 while(c[ci] < pw.cuts.front() && ci < c.size()) {
342 bool isLast = (ci == c.size()-1 || c[ci + 1] >= pw.cuts.front());
343 ret.push_cut(c[ci]);
344 ret.push_seg( elem_portion(pw, 0, c[ci], isLast ? pw.cuts.front() : c[ci + 1]) );
345 ci++;
346 }
348 ret.push_cut(pw.cuts[0]);
349 double prev = pw.cuts[0]; //previous cut
350 //Loop which handles cuts within the Piecewise<T> domain
351 //Should have the cuts = segs + 1 invariant
352 while(si < pw.size() && ci <= c.size()) {
353 if(ci == c.size() && prev <= pw.cuts[si]) { //cuts exhausted, straight copy the rest
354 ret.segs.insert(ret.segs.end(), pw.segs.begin() + si, pw.segs.end());
355 ret.cuts.insert(ret.cuts.end(), pw.cuts.begin() + si + 1, pw.cuts.end());
356 return ret;
357 }else if(ci == c.size() || c[ci] >= pw.cuts[si + 1]) { //no more cuts within this segment, finalize
358 if(prev > pw.cuts[si]) { //segment already has cuts, so portion is required
359 ret.push_seg(portion(pw[si], pw.segT(prev, si), 1.0));
360 } else { //plain copy is fine
361 ret.push_seg(pw[si]);
362 }
363 ret.push_cut(pw.cuts[si + 1]);
364 prev = pw.cuts[si + 1];
365 si++;
366 } else if(c[ci] == pw.cuts[si]){ //coincident
367 //Already finalized the seg with the code immediately above
368 ci++;
369 } else { //plain old subdivision
370 ret.push(elem_portion(pw, si, prev, c[ci]), c[ci]);
371 prev = c[ci];
372 ci++;
373 }
374 }
376 //input cuts extend further than this Piecewise<T>, extend the last segment.
377 while(ci < c.size()) {
378 if(c[ci] > prev) {
379 ret.push(elem_portion(pw, pw.size() - 1, prev, c[ci]), c[ci]);
380 prev = c[ci];
381 }
382 ci++;
383 }
384 return ret;
385 }
387 /**Piecewise<T> portion(const Piecewise<T> &pw, double from, double to);
388 * Returns a Piecewise<T> with a defined domain of [min(from, to), max(from, to)].
389 */
390 template<typename T>
391 Piecewise<T> portion(const Piecewise<T> &pw, double from, double to) {
392 if(pw.empty() || from == to) return Piecewise<T>();
394 Piecewise<T> ret;
396 double temp = from;
397 from = std::min(from, to);
398 to = std::max(temp, to);
400 unsigned i = pw.segN(from);
401 ret.push_cut(from);
402 if(i == pw.size() - 1 || to <= pw.cuts[i + 1]) { //to/from inhabit the same segment
403 ret.push(elem_portion(pw, i, from, to), to);
404 return ret;
405 }
406 ret.push_seg(portion( pw[i], pw.segT(from, i), 1.0 ));
407 i++;
408 unsigned fi = pw.segN(to, i);
409 ret.reserve(fi - i + 1);
410 if (to == pw.cuts[fi]) fi-=1;
412 ret.segs.insert(ret.segs.end(), pw.segs.begin() + i, pw.segs.begin() + fi); //copy segs
413 ret.cuts.insert(ret.cuts.end(), pw.cuts.begin() + i, pw.cuts.begin() + fi + 1); //and their cuts
415 ret.push_seg( portion(pw[fi], 0.0, pw.segT(to, fi)));
416 if(to != ret.cuts.back()) ret.push_cut(to);
417 ret.invariants();
418 return ret;
419 }
421 //TODO: seems like these should be mutating
422 template<typename T>
423 Piecewise<T> remove_short_cuts(Piecewise<T> const &f, double tol) {
424 if(f.empty()) return f;
425 Piecewise<T> ret;
426 ret.reserve(f.size());
427 ret.push_cut(f.cuts[0]);
428 for(unsigned i=0; i<f.size(); i++){
429 if (f.cuts[i+1]-f.cuts[i] >= tol || i==f.size()-1) {
430 ret.push(f[i], f.cuts[i+1]);
431 }
432 }
433 return ret;
434 }
436 //TODO: seems like these should be mutating
437 template<typename T>
438 Piecewise<T> remove_short_cuts_extending(Piecewise<T> const &f, double tol) {
439 if(f.empty()) return f;
440 Piecewise<T> ret;
441 ret.reserve(f.size());
442 ret.push_cut(f.cuts[0]);
443 double last = f.cuts[0]; // last cut included
444 for(unsigned i=0; i<f.size(); i++){
445 if (f.cuts[i+1]-f.cuts[i] >= tol) {
446 ret.push(elem_portion(f, i, last, f.cuts[i+1]), f.cuts[i+1]);
447 last = f.cuts[i+1];
448 }
449 }
450 return ret;
451 }
453 template<typename T>
454 std::vector<double> roots(const Piecewise<T> &pw) {
455 std::vector<double> ret;
456 for(unsigned i = 0; i < pw.size(); i++) {
457 std::vector<double> sr = roots(pw[i]);
458 for (unsigned j = 0; j < sr.size(); j++) ret.push_back(sr[j] * (pw.cuts[i + 1] - pw.cuts[i]) + pw.cuts[i]);
460 }
461 return ret;
462 }
464 //IMPL: OffsetableConcept
465 template<typename T>
466 Piecewise<T> operator+(Piecewise<T> const &a, typename T::output_type b) {
467 boost::function_requires<OffsetableConcept<T> >();
468 //TODO:empty
469 Piecewise<T> ret;
470 ret.segs.reserve(a.size());
471 ret.cuts = a.cuts;
472 for(unsigned i = 0; i < a.size();i++)
473 ret.push_seg(a[i] + b);
474 return ret;
475 }
476 template<typename T>
477 Piecewise<T> operator-(Piecewise<T> const &a, typename T::output_type b) {
478 boost::function_requires<OffsetableConcept<T> >();
479 //TODO: empty
480 Piecewise<T> ret;
481 ret.segs.reserve(a.size());
482 ret.cuts = a.cuts;
483 for(unsigned i = 0; i < a.size();i++)
484 ret.push_seg(a[i] - b);
485 return ret;
486 }
487 template<typename T>
488 Piecewise<T>& operator+=(Piecewise<T>& a, typename T::output_type b) {
489 boost::function_requires<OffsetableConcept<T> >();
491 if(a.empty()) { a.push_cut(0.); a.push(T(b), 1.); return a; }
493 for(unsigned i = 0; i < a.size();i++)
494 a[i] += b;
495 return a;
496 }
497 template<typename T>
498 Piecewise<T>& operator-=(Piecewise<T>& a, typename T::output_type b) {
499 boost::function_requires<OffsetableConcept<T> >();
501 if(a.empty()) { a.push_cut(0.); a.push(T(-b), 1.); return a; }
503 for(unsigned i = 0;i < a.size();i++)
504 a[i] -= b;
505 return a;
506 }
508 //IMPL: ScalableConcept
509 template<typename T>
510 Piecewise<T> operator-(Piecewise<T> const &a) {
511 boost::function_requires<ScalableConcept<T> >();
513 Piecewise<T> ret;
514 ret.segs.reserve(a.size());
515 ret.cuts = a.cuts;
516 for(unsigned i = 0; i < a.size();i++)
517 ret.push_seg(- a[i]);
518 return ret;
519 }
520 template<typename T>
521 Piecewise<T> operator*(Piecewise<T> const &a, double b) {
522 boost::function_requires<ScalableConcept<T> >();
524 if(a.empty()) return Piecewise<T>();
526 Piecewise<T> ret;
527 ret.segs.reserve(a.size());
528 ret.cuts = a.cuts;
529 for(unsigned i = 0; i < a.size();i++)
530 ret.push_seg(a[i] * b);
531 return ret;
532 }
533 template<typename T>
534 Piecewise<T> operator*(Piecewise<T> const &a, T b) {
535 boost::function_requires<ScalableConcept<T> >();
537 if(a.empty()) return Piecewise<T>();
539 Piecewise<T> ret;
540 ret.segs.reserve(a.size());
541 ret.cuts = a.cuts;
542 for(unsigned i = 0; i < a.size();i++)
543 ret.push_seg(a[i] * b);
544 return ret;
545 }
546 template<typename T>
547 Piecewise<T> operator/(Piecewise<T> const &a, double b) {
548 boost::function_requires<ScalableConcept<T> >();
550 //FIXME: b == 0?
551 if(a.empty()) return Piecewise<T>();
553 Piecewise<T> ret;
554 ret.segs.reserve(a.size());
555 ret.cuts = a.cuts;
556 for(unsigned i = 0; i < a.size();i++)
557 ret.push_seg(a[i] / b);
558 return ret;
559 }
560 template<typename T>
561 Piecewise<T>& operator*=(Piecewise<T>& a, double b) {
562 boost::function_requires<ScalableConcept<T> >();
564 for(unsigned i = 0; i < a.size();i++)
565 a[i] *= b;
566 return a;
567 }
568 template<typename T>
569 Piecewise<T>& operator/=(Piecewise<T>& a, double b) {
570 boost::function_requires<ScalableConcept<T> >();
572 //FIXME: b == 0?
574 for(unsigned i = 0; i < a.size();i++)
575 a[i] /= b;
576 return a;
577 }
579 //IMPL: AddableConcept
580 template<typename T>
581 Piecewise<T> operator+(Piecewise<T> const &a, Piecewise<T> const &b) {
582 boost::function_requires<AddableConcept<T> >();
584 Piecewise<T> pa = partition(a, b.cuts), pb = partition(b, a.cuts);
585 Piecewise<T> ret;
586 assert(pa.size() == pb.size());
587 ret.segs.reserve(pa.size());
588 ret.cuts = pa.cuts;
589 for (unsigned i = 0; i < pa.size(); i++)
590 ret.push_seg(pa[i] + pb[i]);
591 return ret;
592 }
593 template<typename T>
594 Piecewise<T> operator-(Piecewise<T> const &a, Piecewise<T> const &b) {
595 boost::function_requires<AddableConcept<T> >();
597 Piecewise<T> pa = partition(a, b.cuts), pb = partition(b, a.cuts);
598 Piecewise<T> ret = Piecewise<T>();
599 assert(pa.size() == pb.size());
600 ret.segs.reserve(pa.size());
601 ret.cuts = pa.cuts;
602 for (unsigned i = 0; i < pa.size(); i++)
603 ret.push_seg(pa[i] - pb[i]);
604 return ret;
605 }
606 template<typename T>
607 inline Piecewise<T>& operator+=(Piecewise<T> &a, Piecewise<T> const &b) {
608 a = a+b;
609 return a;
610 }
611 template<typename T>
612 inline Piecewise<T>& operator-=(Piecewise<T> &a, Piecewise<T> const &b) {
613 a = a-b;
614 return a;
615 }
617 template<typename T1,typename T2>
618 Piecewise<T2> operator*(Piecewise<T1> const &a, Piecewise<T2> const &b) {
619 //function_requires<MultiplicableConcept<T1> >();
620 //function_requires<MultiplicableConcept<T2> >();
622 Piecewise<T1> pa = partition(a, b.cuts);
623 Piecewise<T2> pb = partition(b, a.cuts);
624 Piecewise<T2> ret = Piecewise<T2>();
625 assert(pa.size() == pb.size());
626 ret.segs.reserve(pa.size());
627 ret.cuts = pa.cuts;
628 for (unsigned i = 0; i < pa.size(); i++)
629 ret.push_seg(pa[i] * pb[i]);
630 return ret;
631 }
633 template<typename T>
634 inline Piecewise<T>& operator*=(Piecewise<T> &a, Piecewise<T> const &b) {
635 a = a * b;
636 return a;
637 }
639 Piecewise<SBasis> divide(Piecewise<SBasis> const &a, Piecewise<SBasis> const &b, unsigned k);
640 //TODO: replace divide(a,b,k) by divide(a,b,tol,k)?
641 //TODO: atm, relative error is ~(tol/a)%. Find a way to make it independant of a.
642 //Nota: the result is 'truncated' where b is smaller than 'zero': ~ a/max(b,zero).
643 Piecewise<SBasis>
644 divide(Piecewise<SBasis> const &a, Piecewise<SBasis> const &b, double tol, unsigned k, double zero=1.e-3);
645 Piecewise<SBasis>
646 divide(SBasis const &a, Piecewise<SBasis> const &b, double tol, unsigned k, double zero=1.e-3);
647 Piecewise<SBasis>
648 divide(Piecewise<SBasis> const &a, SBasis const &b, double tol, unsigned k, double zero=1.e-3);
649 Piecewise<SBasis>
650 divide(SBasis const &a, SBasis const &b, double tol, unsigned k, double zero=1.e-3);
652 //Composition: functions called compose_* are pieces of compose that are factored out in pw.cpp.
653 std::map<double,unsigned> compose_pullback(std::vector<double> const &cuts, SBasis const &g);
654 int compose_findSegIdx(std::map<double,unsigned>::iterator const &cut,
655 std::map<double,unsigned>::iterator const &next,
656 std::vector<double> const &levels,
657 SBasis const &g);
659 //TODO: add concept check
660 template<typename T>
661 Piecewise<T> compose(Piecewise<T> const &f, SBasis const &g){
662 Piecewise<T> result;
663 if (f.empty()) return result;
664 if (g.isZero()) return Piecewise<T>(f(0));
665 if (f.size()==1){
666 double t0 = f.cuts[0], width = f.cuts[1] - t0;
667 return (Piecewise<T>) compose(f.segs[0],compose(Linear(-t0 / width, (1-t0) / width), g));
668 }
670 //first check bounds...
671 Interval bs = *bounds_fast(g);
672 if (f.cuts.front() > bs.max() || bs.min() > f.cuts.back()){
673 int idx = (bs.max() < f.cuts[1]) ? 0 : f.cuts.size()-2;
674 double t0 = f.cuts[idx], width = f.cuts[idx+1] - t0;
675 return (Piecewise<T>) compose(f.segs[idx],compose(Linear(-t0 / width, (1-t0) / width), g));
676 }
678 std::vector<double> levels;//we can forget first and last cuts...
679 levels.insert(levels.begin(),f.cuts.begin()+1,f.cuts.end()-1);
680 //TODO: use a std::vector<pairs<double,unsigned> > instead of a map<double,unsigned>.
681 std::map<double,unsigned> cuts_pb = compose_pullback(levels,g);
683 //-- Compose each piece of g with the relevant seg of f.
684 result.cuts.push_back(0.);
685 std::map<double,unsigned>::iterator cut=cuts_pb.begin();
686 std::map<double,unsigned>::iterator next=cut; next++;
687 while(next!=cuts_pb.end()){
688 //assert(std::abs(int((*cut).second-(*next).second))<1);
689 //TODO: find a way to recover from this error? the root finder missed some root;
690 // the levels/variations of f might be too close/fast...
691 int idx = compose_findSegIdx(cut,next,levels,g);
692 double t0=(*cut).first;
693 double t1=(*next).first;
695 SBasis sub_g=compose(g, Linear(t0,t1));
696 sub_g=compose(Linear(-f.cuts[idx]/(f.cuts[idx+1]-f.cuts[idx]),
697 (1-f.cuts[idx])/(f.cuts[idx+1]-f.cuts[idx])),sub_g);
698 result.push(compose(f[idx],sub_g),t1);
699 cut++;
700 next++;
701 }
702 return(result);
703 }
705 //TODO: add concept check for following composition functions
706 template<typename T>
707 Piecewise<T> compose(Piecewise<T> const &f, Piecewise<SBasis> const &g){
708 Piecewise<T> result;
709 for(unsigned i = 0; i < g.segs.size(); i++){
710 Piecewise<T> fgi=compose(f, g.segs[i]);
711 fgi.setDomain(Interval(g.cuts[i], g.cuts[i+1]));
712 result.concat(fgi);
713 }
714 return result;
715 }
717 /*
718 Piecewise<D2<SBasis> > compose(D2<SBasis2d> const &sb2d, Piecewise<D2<SBasis> > const &pwd2sb){
719 Piecewise<D2<SBasis> > result;
720 result.push_cut(0.);
721 for(unsigned i = 0; i < pwd2sb.size(); i++){
722 result.push(compose_each(sb2d,pwd2sb[i]),i+1);
723 }
724 return result;
725 }*/
727 template <typename T>
728 Piecewise<T> Piecewise<T>::operator()(SBasis f){return compose((*this),f);}
729 template <typename T>
730 Piecewise<T> Piecewise<T>::operator()(Piecewise<SBasis>f){return compose((*this),f);}
732 template<typename T>
733 Piecewise<T> integral(Piecewise<T> const &a) {
734 Piecewise<T> result;
735 result.segs.resize(a.segs.size());
736 result.cuts = a.cuts;
737 typename T::output_type c = a.segs[0].at0();
738 for(unsigned i = 0; i < a.segs.size(); i++){
739 result.segs[i] = integral(a.segs[i])*(a.cuts[i+1]-a.cuts[i]);
740 result.segs[i]+= c-result.segs[i].at0();
741 c = result.segs[i].at1();
742 }
743 return result;
744 }
746 template<typename T>
747 Piecewise<T> derivative(Piecewise<T> const &a) {
748 Piecewise<T> result;
749 result.segs.resize(a.segs.size());
750 result.cuts = a.cuts;
751 for(unsigned i = 0; i < a.segs.size(); i++){
752 result.segs[i] = derivative(a.segs[i])/(a.cuts[i+1]-a.cuts[i]);
753 }
754 return result;
755 }
757 std::vector<double> roots(Piecewise<SBasis> const &f);
759 std::vector<std::vector<double> >multi_roots(Piecewise<SBasis> const &f, std::vector<double> const &values);
761 template<typename T>
762 Piecewise<T> reverse(Piecewise<T> const &f) {
763 Piecewise<T> ret = Piecewise<T>();
764 ret.reserve(f.size());
765 double start = f.cuts[0];
766 double end = f.cuts.back();
767 for (unsigned i = 0; i < f.cuts.size(); i++) {
768 double x = f.cuts[f.cuts.size() - 1 - i];
769 ret.push_cut(end - (x - start));
770 }
771 for (unsigned i = 0; i < f.segs.size(); i++)
772 ret.push_seg(reverse(f[f.segs.size() - i - 1]));
773 return ret;
774 }
777 /**
778 * Interpolates between a and b.
779 * \return a if t = 0, b if t = 1, or an interpolation between a and b for t in [0,1]
780 */
781 template<typename T>
782 Piecewise<T> lerp(double t, Piecewise<T> const &a, Piecewise<T> b) {
783 // Make sure both paths have the same number of segments and cuts at the same locations
784 b.setDomain(a.domain());
785 Piecewise<T> pA = partition(a, b.cuts);
786 Piecewise<T> pB = partition(b, a.cuts);
788 return (pA*(1-t) + pB*t);
789 }
791 }
792 #endif //SEEN_GEOM_PW_SB_H
793 /*
794 Local Variables:
795 mode:c++
796 c-file-style:"stroustrup"
797 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
798 indent-tabs-mode:nil
799 fill-column:99
800 End:
801 */
802 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :