Include the implementation of Fritsh-Carlson
Closed this issue · 6 comments
Fritsch-Carlson splines, also known as Fritsch-Carlson monotone cubic splines, are a type of interpolation
method used to construct smooth and monotonic curves from a given set of data points. These splines were
introduced by Fritsch and Carlson in 1980 as an improvement over the traditional cubic spline interpolation.Unlike traditional cubic splines, Fritsch-Carlson splines guarantee monotonicity between adjacent data points.
This means that the resulting curve will not exhibit unwanted oscillations or overshoots, which can occur with
other interpolation methods.Fritsch-Carlson splines achieve monotonicity by modifying the interpolation algorithm based on the local
behavior of the data. The main idea is to ensure that the slopes of the spline segments preserve the
monotonicity of the data.The algorithm for constructing Fritsch-Carlson splines involves the following steps:
- Calculate the slopes at each data point using a suitable method, such as finite differences or local regression.
- Adjust the slopes to enforce monotonicity, ensuring that they do not change the direction between adjacent data points.
- Construct cubic spline segments between each pair of adjacent data points, using the adjusted slopes to determine the shape of the curve within that interval.
By incorporating monotonicity constraints, Fritsch-Carlson splines provide a reliable and smooth interpolation technique, particularly suitable for datasets that exhibit monotonic trends or require smooth monotonic curves. These splines have found applications in various fields, such as computer graphics, data visualization, and numerical analysis.
Fritsh Carlon monotonic spline type seems to be used on MaCh3, useful to be able to compare different types of splines
Thank you very much Lena!
Just added the description of the splines
@ClarkMcGrew do you know which type of monotonic splines is currently constructed in GUNDAM?
Spline types: Without taking a deep dive into the math terminologies, almost all "splines" are simply cubic polynomials (so a+bx+cx^2+dx^3) between adjacent knots, with the only difference being how a, b, c, and d, are calculated. At the moment, we include preliminary calculations for a,b,c&d using not-a-knot, natural, and catmull-rom definitions. It's pretty straight forward to add any other definition.
Monotonic: I won't quote the formula, but there an inequality that needs to be met for [a,b,c,d] to give a monotonic curve. After the parameters are calculated, [a,b,c,d] are modified by applying a "bounding" constraint to make sure so that the equality is satisfied (and the first derivative is continuous). Simplifying for "github", the bounding constraint used in GUNDAM is that the derivative at the knot has to be less than 3 times the average slope between the neighboring knots.
Aside: The current catmull-rom implementation is called Compact since it minimizes the memory foot print. C-R splines don't need to save the slopes so we can save memory. We could also add a C-R implementation that uses GeneralSpline (just like not-a-knot and natural). The MonotonicSpline just applies the monotonic constraint to the compact version of the C-R spline.
Another aside: It would be fairly easy to add different monotonic constraints.
I'm leaving this open until I can cross chech, but...
This may be the easiest issue to solve ever. I need to read the original paper to make sure, but our Monotonic splines already use Fritch-Carlson. I just didn't know that was the algorithm name.
Provisionally closing this since my understanding is that we are already applying this algorithm.