A spline is an approximation to a single valued function of one variable. The function is approximated by first defining a specific set of sample values. Other data points of the function are interpolated given the defined set. That is, you can approximate data points that don't really exist using one the interpolate_* methods or the function call operator. See below. More...
#include <spline.h>
Classes | |
struct | info |
info stored for each x value in the sample data set More... | |
Public Types | |
typedef samples_t::const_iterator | const_iterator |
const_iterator | |
typedef D | Dt |
alias for template parm | |
typedef Y(spline::* | interpolator_t )(X const &) const |
typedef samples_t::iterator | iterator |
iterator | |
typedef samples_t::value_type | sample_t |
Elements stored. | |
typedef std::multimap< X, info > | samples_t |
Primary storage. | |
typedef spline< X, Y, D > | self |
interpolator_t lets you pass the interpolator function as a pointer. | |
typedef X | Xt |
alias for template parm | |
typedef Y | Yt |
alias for template parm | |
Public Member Functions | |
void | add_sample (sample_t const &p) |
Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced. | |
void | add_sample (X const &x, Y const &y) |
Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced. This overload lets you specify the without first constructing a sample_t. | |
template<class Operation > | |
void | apply (Operation const &) |
Modifies the extant samples by visiting each one and replacing the the Y in the sample with the return value from the operation. The operation must take a sample_t as a parameter. | |
sample_t | back () const |
Returns the last sample or an undefined value if there are none. | |
const_iterator | begin () const |
const_iterator | ceil (X const &x) const |
template<class Other , class Operation > | |
void | combine (spline< X, Y, D > &output, Other const &rhs, Operation const &op) |
Produce output by combining this with rhs according to op on a point by point basis. All sampled data points in both splines are considered. The operation is applied to each pair of points existing in either spline. Points missing in one are interpolated so as to be able to combine them with the other to produce the output. | |
template<class Other , class Operation > | |
void | combine (self &output, Other const &rhs, Operation const &op) |
void | compute_coefficients () |
Compute the second derivative of the interpolation functions and store them in the s_ member of the info associated with every x/y pair. | |
void | domain (std::set< X > *target) const |
get all interesting Xs | |
const_iterator | end () const |
template<class OutputIterator > | |
void | evaluate (X start_x, X delta_x, OutputIterator begin, OutputIterator end) const |
Create a collection of interpolated values. Output those values through an iterator that points to a pair<X,Y> where X, and Y are assignment compatible with double. The begin,end variables define the standard output iterator range logic. The first value output will be (start_x, f(start_x)), the second will be (start_x+delta_x, f(start_x+delta_x)), and so forth. | |
const_iterator | floor (X const &x) const |
Returns the iterator to the sample whose X component is as high as possible but <= x. Returns end() if no such sample exists. Consider the sequence: | |
sample_t | front () const |
Returns the first sample or an undefined value if there are none. | |
template<class SF > | |
void | include (SF const &rhs) |
Ensures that all samples in rhs also appear in this sampled function. Samples in rhs superceed samples already in the spline. rhs can be of a different type of data structure but the structure's iterator must point to pairs whose First and Second types are compatible with X and Y. | |
template<class Iterator > | |
void | include (Iterator, Iterator) |
Ensures that all samples in iterator range also appear in this sampled function. Samples in the range l-g replace samples already spline. | |
Y | interpolate_cubic (X const &) const |
Y | interpolate_line (X const &) const |
This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a piecewise linear function, like this: | |
Y | interpolate_step (X const &) const |
This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a step wise constant function that looks like this: | |
interpolator_t | interpolator () const |
gets the current interpolator | |
Y | operator() (X location) const |
template<class T > | |
self & | operator*= (T const &rhs) |
Add another spline to this one. Make sure that all samples in both splines are addressed. | |
template<class T > | |
self & | operator+= (T const &rhs) |
Add another spline to this one. Make sure that all samples in both splines are addressed. | |
template<class T > | |
self & | operator-= (T const &rhs) |
Add another spline to this one. Make sure that all samples in both splines are addressed. | |
template<class T > | |
self & | operator/= (T const &rhs) |
Add another spline to this one. Make sure that all samples in both splines are addressed. | |
self & | operator= (self const &rhs) |
void | set_interpolator (interpolator_t t) |
size_t | size () const |
template<class OtherKind > | |
spline (OtherKind const &rhs, typename spline< X, Y, D >::interpolator_t terp) | |
template<class SampleIterator > | |
spline (SampleIterator first, SampleIterator last, typename spline< X, Y, D >::interpolator_t t) | |
template<class OtherKind > | |
spline (OtherKind const &rhs, interpolator_t terp) | |
template<class SampleIterator > | |
spline (SampleIterator first, SampleIterator last, interpolator_t t) | |
spline (self const &rhs) | |
spline (interpolator_t a) | |
spline () | |
void | swap (self &rhs) |
Quickly swap the contents of this spline with that of another. This occaisionally useful when writing algorithms that construct objects and then destruct them. You can arrange to have an empty object destructed quickly while your constructed object gets filled without a copy. This of course requires thought. | |
Private Attributes | |
bool | dirty_ |
cubic spline s's need recalculation | |
interpolator_t | interpolator_ |
Current interpolator. | |
samples_t | samples_ |
Map of actual data. |
A spline is an approximation to a single valued function of one variable. The function is approximated by first defining a specific set of sample values. Other data points of the function are interpolated given the defined set. That is, you can approximate data points that don't really exist using one the interpolate_* methods or the function call operator. See below.
The following interpolators exist:
You can select which one this is using the constructor or using the set_interpolator() method. You can also call any desired interpolator directly without using set_interpolator().
A 'sample' is a pair<X,Y>. For a given X, only one Y can be used. X means 'independent variable' and Y means 'dependent variable'. That is, X is the domain of a two dimensional graph point. Y is the range.
The template parameter, D, lets you specify the data type to use when doing multiplications and divisions and repeated operations. Normally, your X and Y will be one of: int, float, double, short, etc. Using double as the default high resolution numeric data type works fine for them. It isn't used much anyway. However, if you supply your own user defined classes for X or Y, you may need to supply your own D class as well. Of course, you may not need to, but the feature is there if you need it.
Interpolation is the act of guessing at values of the Y for values of the X for which no specific data points are provided. The following interpolation schemes are provided:
Numerical Computing by Shampine and Allen. Copyright 1973. ISBN 0-7216-8150-6.
The function all operator is provided so that you can easily use the spline to access dependent variable values:
spline<int,int> s; s.add_sample(99, 13); s.add_sample(101, 20); X x = 100; Y y = s(x);
y is now somewhere between 13 and twenty, given the current interpolator.
Only one sample with a given X value will be kept. If you add a new sample at an old location, the old one will be replaced.
Samples are stored in order, sorted by X.
Use method 'domain()' to get a list of all Xs found in samples in this function.
You can use the apply method to apply an operation to all the actual sample data points. This lets you change them if you like.
Note that the primary sampled storage class allows multiple samples of the same X but the add_sample method won't. The multimap class is used instead of map because multimap supports the upperbound method which can be used to quick find a location with the multimap NEAR a given value of the X. This avoids costly linear searches when interpolating
The 'include' method lets add multiple samples in one operation -- there a couple of variations.
The operators, +=, -=, *=, and /= let you include combine two splines by interpolating this spline and another spline over all datapoints of interest to either spline, and producing a new spline. The interpolation involved in these operator functions is the 'current' interpolator set using set_interpolator() or as a parameter to the constructor.
Comments about the spline members can be found in the bodies thereof which begin immediately after the class definition.
Definition at line 55 of file spline.h.
typedef Y(spline::* interpolator_t)(X const &) const |
typedef samples_t::iterator iterator |
spline | ( | ) |
Default constructor gives you the default interpolator (stepwise). Creates an empty spline. Use add_sample to fill it. You can of course use any interpolator by calling it directly, or you can use set_interpolator to select a different one as the current interpolator.
spline | ( | interpolator_t | a | ) |
spline | ( | SampleIterator | first, | |
SampleIterator | last, | |||
interpolator_t | t | |||
) |
spline | ( | OtherKind const & | rhs, | |
interpolator_t | terp | |||
) |
spline | ( | SampleIterator | first, | |
SampleIterator | last, | |||
typename spline< X, Y, D >::interpolator_t | t | |||
) |
spline | ( | OtherKind const & | rhs, | |
typename spline< X, Y, D >::interpolator_t | terp | |||
) |
void add_sample | ( | sample_t const & | p | ) |
void add_sample | ( | X const & | x, | |
Y const & | y | |||
) |
void apply | ( | Operation const & | op | ) |
spline< X, Y, D >::const_iterator begin | ( | ) | const |
const_iterator ceil | ( | X const & | x | ) | const |
void combine | ( | spline< X, Y, D > & | output, | |
Other const & | rhs, | |||
Operation const & | op | |||
) |
Produce output by combining this with rhs according to op on a point by point basis. All sampled data points in both splines are considered. The operation is applied to each pair of points existing in either spline. Points missing in one are interpolated so as to be able to combine them with the other to produce the output.
Definition at line 491 of file spline.h.
void combine | ( | self & | output, | |
Other const & | rhs, | |||
Operation const & | op | |||
) |
void compute_coefficients | ( | ) |
void domain | ( | std::set< X > * | target | ) | const |
spline< X, Y, D >::const_iterator end | ( | ) | const |
void evaluate | ( | X | start_x, | |
X | delta_x, | |||
OutputIterator | begin, | |||
OutputIterator | end | |||
) | const |
Create a collection of interpolated values. Output those values through an iterator that points to a pair<X,Y> where X, and Y are assignment compatible with double. The begin,end variables define the standard output iterator range logic. The first value output will be (start_x, f(start_x)), the second will be (start_x+delta_x, f(start_x+delta_x)), and so forth.
Definition at line 944 of file spline.h.
spline< X, Y, D >::const_iterator floor | ( | X const & | x | ) | const |
Returns the iterator to the sample whose X component is as high as possible but <= x. Returns end() if no such sample exists. Consider the sequence:
10, 11, 12
If you ask for 9, you will get end() returned. If you ask for 13, you will get an iterator to 12. If you ask for 11.5, you will get an iterator to 11.
Definition at line 629 of file spline.h.
void include | ( | SF const & | rhs | ) |
Ensures that all samples in rhs also appear in this sampled function. Samples in rhs superceed samples already in the spline. rhs can be of a different type of data structure but the structure's iterator must point to pairs whose First and Second types are compatible with X and Y.
Definition at line 557 of file spline.h.
void include | ( | Iterator | l, | |
Iterator | g | |||
) |
Ensures that all samples in iterator range also appear in this sampled function. Samples in the range l-g replace samples already spline.
The iterators must point to pairs of some kind but those types do not have to be exactly X and Y. On the other hand, it must be possible to convert them to X and Y respectively.
Definition at line 526 of file spline.h.
Y interpolate_cubic | ( | X const & | x | ) | const |
Y interpolate_line | ( | X const & | x | ) | const |
This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a piecewise linear function, like this:
D| + ; | / \ ; C| / \ +--> ; | / \ / ; | / \ / ; | / \ / ; B| <-+ \ / ; A| +---+ ; +------------------------------------------- ; x0 x1 x2 x3 x4 ; u v ;
In this diagram, the samples are (x0,B), (x1,D), (x2,A), (x3,A), (x4,C). This is the second fastest interpolator and is usuable to represent the manufacturing of objects. Usually, an object takes a certain manufacturing time -- the more time, the more objects are made. Sales estimates generally work like this. Slowly changing real world physical phenomena can also be modeled this way. If you need more accuracy, use more samples.
The return value is calculated like this: If there are no samples, the return value is undefined. If the requested 'x' value to be interpolated is less than the lowest sampled x value, x0, then you get x0's value functional value (B). If the requested x value is greater than the highest sample's X value (x4), then you will get the Y of the highest sample. This approach allows you set your value for the 'out of range' situations. You just jam in extra samples to represent the too low and too high situations. Otherwise, if you request a location between two extant samples, you will get a linearly approximated value. Consider point 'u' in the above picture. u likes between x1 and x2. The Y associated with us is calculated like this:
slope = (B - D) / (x2 - x1) // negative value of course
deltax = x(u) - x1
y(u) = B + slope * deltax
If there are no samples at all, you get an undefined result.
Definition at line 716 of file spline.h.
Y interpolate_step | ( | X const & | x | ) | const |
This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a step wise constant function that looks like this:
D| +-------------> | | C| +-----------+ | B| <-+-----+ | | A| +---+ +------------------------------------------- x0 x1 x2 x3 u v
In this diagram, the samples are (x0,B), (x1,C), (x2,A), (x3,D). A step wise interpolator makes sense when tracking inventory and the time to load and unload trucks is insignificant. It is the fastest interpolator.
The return value is calculated like this: If there are no samples, the return value is undefined. If the requested 'x' value to be interpolated is less than the lowest sampled x value, x0, then you get x0's value functional value (B). Otherwise you get the value of the actual sample data, Y component, of the sample on or to the immediate left. So at point u, you would get C, and at v you would get D.
If there are no samples at all, you get an undefined result.
Definition at line 663 of file spline.h.
spline< X, Y, D >::interpolator_t interpolator | ( | ) | const |
Y operator() | ( | X | location | ) | const |
spline< X, Y, D > & operator*= | ( | T const & | rhs | ) |
spline< X, Y, D > & operator+= | ( | T const & | rhs | ) |
spline< X, Y, D > & operator-= | ( | T const & | rhs | ) |
spline< X, Y, D > & operator/= | ( | T const & | rhs | ) |
void set_interpolator | ( | interpolator_t | t | ) |
void swap | ( | self & | rhs | ) |
Quickly swap the contents of this spline with that of another. This occaisionally useful when writing algorithms that construct objects and then destruct them. You can arrange to have an empty object destructed quickly while your constructed object gets filled without a copy. This of course requires thought.
Definition at line 394 of file spline.h.
interpolator_t interpolator_ [private] |