embedded_charts/math/
interpolation.rs

1//! Curve interpolation algorithms for smooth data visualization.
2//!
3//! This module provides various interpolation algorithms optimized for embedded systems:
4//! - Cubic spline interpolation for smooth curves
5//! - Catmull-Rom spline for balanced smoothness and control
6//! - Bezier curve interpolation for artistic control
7//! - Linear interpolation as a fallback
8//!
9//! All algorithms are designed to work with the no_std environment and use
10//! static allocation for memory efficiency.
11
12use crate::data::Point2D;
13use crate::error::{ChartError, ChartResult};
14use heapless::Vec;
15
16/// Maximum number of interpolated points that can be generated
17pub const MAX_INTERPOLATED_POINTS: usize = 512;
18
19/// Type of curve interpolation to use
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub enum InterpolationType {
22    /// Linear interpolation - straight lines between points
23    Linear,
24    /// Cubic spline interpolation - smooth curves through all points
25    CubicSpline,
26    /// Catmull-Rom spline - smooth curves with local control
27    CatmullRom,
28    /// Bezier curve approximation - artistic smooth curves
29    Bezier,
30}
31
32/// Configuration for curve interpolation
33#[derive(Debug, Clone)]
34pub struct InterpolationConfig {
35    /// Type of interpolation to use
36    pub interpolation_type: InterpolationType,
37    /// Number of points to generate between each pair of data points
38    pub subdivisions: u32,
39    /// Tension parameter for splines (0.0 = loose, 1.0 = tight)
40    pub tension: f32,
41    /// Whether to create a closed curve (connect last point to first)
42    pub closed: bool,
43}
44
45impl Default for InterpolationConfig {
46    fn default() -> Self {
47        Self {
48            interpolation_type: InterpolationType::CubicSpline,
49            subdivisions: 8,
50            tension: 0.5,
51            closed: false,
52        }
53    }
54}
55
56/// Curve interpolator that generates smooth curves from discrete data points
57pub struct CurveInterpolator;
58
59impl CurveInterpolator {
60    /// Interpolate a series of 2D points to create a smooth curve
61    ///
62    /// # Arguments
63    /// * `points` - Input data points to interpolate
64    /// * `config` - Interpolation configuration
65    ///
66    /// # Returns
67    /// A vector of interpolated points that form a smooth curve
68    pub fn interpolate(
69        points: &[Point2D],
70        config: &InterpolationConfig,
71    ) -> ChartResult<Vec<Point2D, MAX_INTERPOLATED_POINTS>> {
72        if points.len() < 2 {
73            return Err(ChartError::InsufficientData);
74        }
75
76        match config.interpolation_type {
77            InterpolationType::Linear => Self::linear_interpolation(points, config),
78            InterpolationType::CubicSpline => Self::cubic_spline_interpolation(points, config),
79            InterpolationType::CatmullRom => Self::catmull_rom_interpolation(points, config),
80            InterpolationType::Bezier => Self::bezier_interpolation(points, config),
81        }
82    }
83
84    /// Linear interpolation - simply subdivides straight lines
85    fn linear_interpolation(
86        points: &[Point2D],
87        config: &InterpolationConfig,
88    ) -> ChartResult<Vec<Point2D, MAX_INTERPOLATED_POINTS>> {
89        let mut result = Vec::new();
90
91        for i in 0..points.len() - 1 {
92            let p0 = points[i];
93            let p1 = points[i + 1];
94
95            // Add the starting point
96            result.push(p0).map_err(|_| ChartError::MemoryFull)?;
97
98            // Add subdivided points
99            for j in 1..config.subdivisions {
100                let t = j as f32 / config.subdivisions as f32;
101                let x = p0.x + t * (p1.x - p0.x);
102                let y = p0.y + t * (p1.y - p0.y);
103                result
104                    .push(Point2D::new(x, y))
105                    .map_err(|_| ChartError::MemoryFull)?;
106            }
107        }
108
109        // Add the final point
110        if let Some(last) = points.last() {
111            result.push(*last).map_err(|_| ChartError::MemoryFull)?;
112        }
113
114        Ok(result)
115    }
116
117    /// Cubic spline interpolation for smooth curves
118    fn cubic_spline_interpolation(
119        points: &[Point2D],
120        config: &InterpolationConfig,
121    ) -> ChartResult<Vec<Point2D, MAX_INTERPOLATED_POINTS>> {
122        let mut result = Vec::new();
123        let n = points.len();
124
125        if n < 3 {
126            return Self::linear_interpolation(points, config);
127        }
128
129        // Calculate derivatives for natural cubic spline
130        let mut derivatives = Vec::<f32, 256>::new();
131        for _i in 0..n {
132            derivatives.push(0.0).map_err(|_| ChartError::MemoryFull)?;
133        }
134
135        // Calculate second derivatives using simplified approach
136        for i in 1..n - 1 {
137            let h1 = points[i].x - points[i - 1].x;
138            let h2 = points[i + 1].x - points[i].x;
139            let delta1 = (points[i].y - points[i - 1].y) / h1;
140            let delta2 = (points[i + 1].y - points[i].y) / h2;
141            derivatives[i] = 2.0 * (delta2 - delta1) / (h1 + h2);
142        }
143
144        // Generate interpolated points
145        for i in 0..n - 1 {
146            let p0 = points[i];
147            let p1 = points[i + 1];
148            let d0 = derivatives[i];
149            let d1 = derivatives[i + 1];
150
151            result.push(p0).map_err(|_| ChartError::MemoryFull)?;
152
153            let h = p1.x - p0.x;
154            for j in 1..config.subdivisions {
155                let t = j as f32 / config.subdivisions as f32;
156                let t2 = t * t;
157                let t3 = t2 * t;
158
159                // Cubic Hermite interpolation
160                let h00 = 2.0 * t3 - 3.0 * t2 + 1.0;
161                let h10 = t3 - 2.0 * t2 + t;
162                let h01 = -2.0 * t3 + 3.0 * t2;
163                let h11 = t3 - t2;
164
165                let x = p0.x + t * h;
166                let y = h00 * p0.y + h10 * h * d0 + h01 * p1.y + h11 * h * d1;
167
168                result
169                    .push(Point2D::new(x, y))
170                    .map_err(|_| ChartError::MemoryFull)?;
171            }
172        }
173
174        if let Some(last) = points.last() {
175            result.push(*last).map_err(|_| ChartError::MemoryFull)?;
176        }
177
178        Ok(result)
179    }
180
181    /// Catmull-Rom spline interpolation
182    fn catmull_rom_interpolation(
183        points: &[Point2D],
184        config: &InterpolationConfig,
185    ) -> ChartResult<Vec<Point2D, MAX_INTERPOLATED_POINTS>> {
186        let mut result = Vec::new();
187        let n = points.len();
188
189        if n < 3 {
190            return Self::linear_interpolation(points, config);
191        }
192
193        // Process each segment
194        for i in 0..n - 1 {
195            // Get control points (with boundary handling)
196            let p0 = if i == 0 { points[0] } else { points[i - 1] };
197            let p1 = points[i];
198            let p2 = points[i + 1];
199            let p3 = if i + 2 < n {
200                points[i + 2]
201            } else {
202                points[n - 1]
203            };
204
205            result.push(p1).map_err(|_| ChartError::MemoryFull)?;
206
207            // Generate subdivided points
208            for j in 1..config.subdivisions {
209                let t = j as f32 / config.subdivisions as f32;
210                let t2 = t * t;
211                let t3 = t2 * t;
212
213                // Catmull-Rom basis functions
214                let x = 0.5
215                    * ((2.0 * p1.x)
216                        + (-p0.x + p2.x) * t
217                        + (2.0 * p0.x - 5.0 * p1.x + 4.0 * p2.x - p3.x) * t2
218                        + (-p0.x + 3.0 * p1.x - 3.0 * p2.x + p3.x) * t3);
219
220                let y = 0.5
221                    * ((2.0 * p1.y)
222                        + (-p0.y + p2.y) * t
223                        + (2.0 * p0.y - 5.0 * p1.y + 4.0 * p2.y - p3.y) * t2
224                        + (-p0.y + 3.0 * p1.y - 3.0 * p2.y + p3.y) * t3);
225
226                result
227                    .push(Point2D::new(x, y))
228                    .map_err(|_| ChartError::MemoryFull)?;
229            }
230        }
231
232        if let Some(last) = points.last() {
233            result.push(*last).map_err(|_| ChartError::MemoryFull)?;
234        }
235
236        Ok(result)
237    }
238
239    /// Bezier curve interpolation
240    fn bezier_interpolation(
241        points: &[Point2D],
242        config: &InterpolationConfig,
243    ) -> ChartResult<Vec<Point2D, MAX_INTERPOLATED_POINTS>> {
244        let mut result = Vec::new();
245        let n = points.len();
246
247        if n < 3 {
248            return Self::linear_interpolation(points, config);
249        }
250
251        // Generate control points for quadratic Bezier curves
252        for i in 0..n - 1 {
253            let p0 = points[i];
254            let p2 = points[i + 1];
255
256            // Simple control point calculation
257            let mid_x = (p0.x + p2.x) * 0.5;
258            let mid_y = (p0.y + p2.y) * 0.5;
259
260            // Add some curvature based on tension
261            let offset_x = (p2.y - p0.y) * config.tension * 0.2;
262            let offset_y = (p0.x - p2.x) * config.tension * 0.2;
263
264            let p1 = Point2D::new(mid_x + offset_x, mid_y + offset_y);
265
266            result.push(p0).map_err(|_| ChartError::MemoryFull)?;
267
268            // Generate quadratic Bezier curve
269            for j in 1..config.subdivisions {
270                let t = j as f32 / config.subdivisions as f32;
271                let one_minus_t = 1.0 - t;
272                let t2 = t * t;
273                let one_minus_t2 = one_minus_t * one_minus_t;
274
275                let x = one_minus_t2 * p0.x + 2.0 * one_minus_t * t * p1.x + t2 * p2.x;
276                let y = one_minus_t2 * p0.y + 2.0 * one_minus_t * t * p1.y + t2 * p2.y;
277
278                result
279                    .push(Point2D::new(x, y))
280                    .map_err(|_| ChartError::MemoryFull)?;
281            }
282        }
283
284        if let Some(last) = points.last() {
285            result.push(*last).map_err(|_| ChartError::MemoryFull)?;
286        }
287
288        Ok(result)
289    }
290
291    /// Smooth a single point using neighboring points
292    pub fn smooth_point(
293        points: &[Point2D],
294        index: usize,
295        smoothing_factor: f32,
296    ) -> ChartResult<Point2D> {
297        if index >= points.len() {
298            return Err(ChartError::InvalidRange);
299        }
300
301        let n = points.len();
302        if n < 3 || index == 0 || index == n - 1 {
303            return Ok(points[index]);
304        }
305
306        let prev = points[index - 1];
307        let curr = points[index];
308        let next = points[index + 1];
309
310        // Apply smoothing using weighted average
311        let factor = smoothing_factor.clamp(0.0, 1.0);
312        let smoothed_x = curr.x * (1.0 - factor) + (prev.x + next.x) * 0.5 * factor;
313        let smoothed_y = curr.y * (1.0 - factor) + (prev.y + next.y) * 0.5 * factor;
314
315        Ok(Point2D::new(smoothed_x, smoothed_y))
316    }
317
318    /// Apply smoothing to an entire series of points
319    pub fn smooth_series(
320        points: &[Point2D],
321        smoothing_factor: f32,
322        iterations: u32,
323    ) -> ChartResult<Vec<Point2D, 256>> {
324        let mut working_points = Vec::new();
325        for point in points {
326            working_points
327                .push(*point)
328                .map_err(|_| ChartError::MemoryFull)?;
329        }
330
331        for _ in 0..iterations {
332            let mut smoothed = Vec::new();
333            for i in 0..working_points.len() {
334                let smoothed_point = Self::smooth_point(&working_points, i, smoothing_factor)?;
335                smoothed
336                    .push(smoothed_point)
337                    .map_err(|_| ChartError::MemoryFull)?;
338            }
339            working_points = smoothed;
340        }
341
342        Ok(working_points)
343    }
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349
350    #[test]
351    fn test_linear_interpolation() {
352        let mut points = heapless::Vec::<Point2D, 16>::new();
353        points.push(Point2D::new(0.0, 0.0)).unwrap();
354        points.push(Point2D::new(1.0, 1.0)).unwrap();
355        let config = InterpolationConfig {
356            interpolation_type: InterpolationType::Linear,
357            subdivisions: 4,
358            ..Default::default()
359        };
360
361        let result = CurveInterpolator::interpolate(&points, &config).unwrap();
362        assert!(result.len() > 2);
363        assert_eq!(result[0], points[0]);
364        assert_eq!(result[result.len() - 1], points[1]);
365    }
366
367    #[test]
368    fn test_catmull_rom_interpolation() {
369        let mut points = heapless::Vec::<Point2D, 16>::new();
370        points.push(Point2D::new(0.0, 0.0)).unwrap();
371        points.push(Point2D::new(1.0, 1.0)).unwrap();
372        points.push(Point2D::new(2.0, 0.0)).unwrap();
373        let config = InterpolationConfig {
374            interpolation_type: InterpolationType::CatmullRom,
375            subdivisions: 8,
376            ..Default::default()
377        };
378
379        let result = CurveInterpolator::interpolate(&points, &config).unwrap();
380        assert!(result.len() > points.len());
381    }
382
383    #[test]
384    fn test_point_smoothing() {
385        let mut points = heapless::Vec::<Point2D, 16>::new();
386        points.push(Point2D::new(0.0, 0.0)).unwrap();
387        points.push(Point2D::new(1.0, 10.0)).unwrap(); // Spike
388        points.push(Point2D::new(2.0, 0.0)).unwrap();
389
390        let smoothed = CurveInterpolator::smooth_point(&points, 1, 0.5).unwrap();
391        assert!(smoothed.y < 10.0); // Should be smoothed down
392        assert!(smoothed.y > 0.0); // But still positive
393    }
394
395    #[test]
396    fn test_series_smoothing() {
397        let mut points = heapless::Vec::<Point2D, 16>::new();
398        points.push(Point2D::new(0.0, 0.0)).unwrap();
399        points.push(Point2D::new(1.0, 10.0)).unwrap();
400        points.push(Point2D::new(2.0, 0.0)).unwrap();
401        points.push(Point2D::new(3.0, 10.0)).unwrap();
402        points.push(Point2D::new(4.0, 0.0)).unwrap();
403
404        let smoothed = CurveInterpolator::smooth_series(&points, 0.3, 2).unwrap();
405        assert_eq!(smoothed.len(), points.len());
406
407        // Check that spikes are reduced
408        assert!(smoothed[1].y < points[1].y);
409        assert!(smoothed[3].y < points[3].y);
410    }
411}
embedded_charts/math/interpolation.rs

embedded_charts/math/
interpolation.rs
