use thiserror::Error;
#[derive(Debug, Clone, PartialEq, Error)]
pub enum InterpolationError {
#[error("At least {required} points required, but {provided} were provided")]
InsufficientPoints {
required: usize,
provided: usize,
},
#[error("Dimension mismatch: x has length {x_len}, y has length {y_len}")]
DimensionMismatch {
x_len: usize,
y_len: usize,
},
#[error("x-coordinates must be strictly sorted in increasing order")]
NonMonotonicX,
#[error("Value {0} is outside interpolation range [{1}, {2}]")]
ExtrapolationNotAllowed(f64, f64, f64),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Extrapolation {
#[default]
None,
Flat,
Linear,
}
#[derive(Debug, Clone)]
pub struct LinearInterpolation {
xs: Vec<f64>,
ys: Vec<f64>,
extrapolation: Extrapolation,
}
impl LinearInterpolation {
pub fn new(
xs: Vec<f64>,
ys: Vec<f64>,
extrapolation: Extrapolation,
) -> Result<Self, InterpolationError> {
if xs.len() < 2 {
return Err(InterpolationError::InsufficientPoints {
required: 2,
provided: xs.len(),
});
}
if xs.len() != ys.len() {
return Err(InterpolationError::DimensionMismatch {
x_len: xs.len(),
y_len: ys.len(),
});
}
for i in 1..xs.len() {
if xs[i] <= xs[i - 1] {
return Err(InterpolationError::NonMonotonicX);
}
}
Ok(Self {
xs,
ys,
extrapolation,
})
}
pub fn interpolate(&self, x: f64) -> Result<f64, InterpolationError> {
let n = self.xs.len();
let x_min = self.xs[0];
let x_max = self.xs[n - 1];
if x < x_min {
return match self.extrapolation {
Extrapolation::None => {
Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
}
Extrapolation::Flat => Ok(self.ys[0]),
Extrapolation::Linear => {
let dx = self.xs[1] - self.xs[0];
let dy = self.ys[1] - self.ys[0];
let slope = dy / dx;
Ok(self.ys[0] + slope * (x - x_min))
}
};
}
if x > x_max {
return match self.extrapolation {
Extrapolation::None => {
Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
}
Extrapolation::Flat => Ok(self.ys[n - 1]),
Extrapolation::Linear => {
let dx = self.xs[n - 1] - self.xs[n - 2];
let dy = self.ys[n - 1] - self.ys[n - 2];
let slope = dy / dx;
Ok(self.ys[n - 1] + slope * (x - x_max))
}
};
}
let idx = self.xs.partition_point(|&val| val <= x);
let i = if idx == 0 {
0
} else if idx >= n {
n - 2
} else {
idx - 1
};
let x0 = self.xs[i];
let x1 = self.xs[i + 1];
let y0 = self.ys[i];
let y1 = self.ys[i + 1];
let t = (x - x0) / (x1 - x0);
Ok(y0 + t * (y1 - y0))
}
}
#[derive(Debug, Clone)]
pub struct CubicSpline {
xs: Vec<f64>,
ys: Vec<f64>,
m: Vec<f64>,
extrapolation: Extrapolation,
}
impl CubicSpline {
pub fn new(
xs: Vec<f64>,
ys: Vec<f64>,
extrapolation: Extrapolation,
) -> Result<Self, InterpolationError> {
let n = xs.len();
if n < 3 {
return Err(InterpolationError::InsufficientPoints {
required: 3,
provided: n,
});
}
if n != ys.len() {
return Err(InterpolationError::DimensionMismatch {
x_len: n,
y_len: ys.len(),
});
}
for i in 1..n {
if xs[i] <= xs[i - 1] {
return Err(InterpolationError::NonMonotonicX);
}
}
let mut h = vec![0.0; n - 1];
for i in 0..n - 1 {
h[i] = xs[i + 1] - xs[i];
}
let m_size = n - 2;
let mut a = vec![0.0; m_size]; let mut b = vec![0.0; m_size]; let mut c = vec![0.0; m_size]; let mut d = vec![0.0; m_size];
for i in 0..m_size {
let knot = i + 1;
let h_prev = h[knot - 1];
let h_curr = h[knot];
b[i] = 2.0 * (h_prev + h_curr);
if i > 0 {
a[i] = h_prev;
}
if i < m_size - 1 {
c[i] = h_curr;
}
let slope_curr = (ys[knot + 1] - ys[knot]) / h_curr;
let slope_prev = (ys[knot] - ys[knot - 1]) / h_prev;
d[i] = 6.0 * (slope_curr - slope_prev);
}
let mut c_prime = vec![0.0; m_size];
let mut d_prime = vec![0.0; m_size];
c_prime[0] = c[0] / b[0];
d_prime[0] = d[0] / b[0];
for i in 1..m_size {
let denom = b[i] - a[i] * c_prime[i - 1];
c_prime[i] = if i < m_size - 1 { c[i] / denom } else { 0.0 };
d_prime[i] = (d[i] - a[i] * d_prime[i - 1]) / denom;
}
let mut m_interior = vec![0.0; m_size];
m_interior[m_size - 1] = d_prime[m_size - 1];
for i in (0..m_size - 1).rev() {
m_interior[i] = d_prime[i] - c_prime[i] * m_interior[i + 1];
}
let mut m = vec![0.0; n];
m[0] = 0.0;
m[n - 1] = 0.0;
m[1..n - 1].copy_from_slice(&m_interior);
Ok(Self {
xs,
ys,
m,
extrapolation,
})
}
pub fn interpolate(&self, x: f64) -> Result<f64, InterpolationError> {
let n = self.xs.len();
let x_min = self.xs[0];
let x_max = self.xs[n - 1];
if x < x_min {
return match self.extrapolation {
Extrapolation::None => {
Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
}
Extrapolation::Flat => Ok(self.ys[0]),
Extrapolation::Linear => {
let slope = self.derivative(x_min);
Ok(self.ys[0] + slope * (x - x_min))
}
};
}
if x > x_max {
return match self.extrapolation {
Extrapolation::None => {
Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
}
Extrapolation::Flat => Ok(self.ys[n - 1]),
Extrapolation::Linear => {
let slope = self.derivative(x_max);
Ok(self.ys[n - 1] + slope * (x - x_max))
}
};
}
let idx = self.xs.partition_point(|&val| val <= x);
let i = if idx == 0 {
0
} else if idx >= n {
n - 2
} else {
idx - 1
};
let x_i = self.xs[i];
let x_ip1 = self.xs[i + 1];
let h = x_ip1 - x_i;
let y_i = self.ys[i];
let y_ip1 = self.ys[i + 1];
let m_i = self.m[i];
let m_ip1 = self.m[i + 1];
let dx_left = x - x_i;
let dx_right = x_ip1 - x;
let term1 = (m_i * dx_right.powi(3) + m_ip1 * dx_left.powi(3)) / (6.0 * h);
let term2 = (y_i - m_i * h.powi(2) / 6.0) * dx_right / h;
let term3 = (y_ip1 - m_ip1 * h.powi(2) / 6.0) * dx_left / h;
Ok(term1 + term2 + term3)
}
pub fn derivative(&self, x: f64) -> f64 {
let n = self.xs.len();
let idx = self.xs.partition_point(|&val| val <= x);
let i = if idx == 0 {
0
} else if idx >= n {
n - 2
} else {
idx - 1
};
let x_i = self.xs[i];
let x_ip1 = self.xs[i + 1];
let h = x_ip1 - x_i;
let y_i = self.ys[i];
let y_ip1 = self.ys[i + 1];
let m_i = self.m[i];
let m_ip1 = self.m[i + 1];
let dx_left = x - x_i;
let dx_right = x_ip1 - x;
-m_i * dx_right.powi(2) / (2.0 * h)
+ m_ip1 * dx_left.powi(2) / (2.0 * h)
+ (y_ip1 - y_i) / h
- (m_ip1 - m_i) * h / 6.0
}
}