plotters_iced/sample/
lttb.rs

1// plotters-iced
2//
3// Iced backend for Plotters
4// Copyright: 2022, Joylei <leingliu@gmail.com>
5// License: MIT
6//
7
8//! Largest-Triangle-Three-Buckets algorithm (LTTB)
9//!
10//! ## Known limitations
11//! - X-values must be in a strictly increasing order
12
13// original version: https://github.com/sveinn-steinarsson/flot-downsample
14// modified based on https://github.com/jeromefroe/lttb-rs
15
16/// data point for [`LttbSource`]
17pub trait DataPoint {
18    /// x value for sampling, must be in a strictly increasing order
19    fn x(&self) -> f64;
20    /// y value for sampling
21    fn y(&self) -> f64;
22}
23
24impl<D: DataPoint> DataPoint for &D {
25    #[inline]
26    fn x(&self) -> f64 {
27        (*self).x()
28    }
29    #[inline]
30    fn y(&self) -> f64 {
31        (*self).y()
32    }
33}
34
35/// data source for lttb sampling
36///
37/// ## Known limitations
38/// - X-values must be in a strictly increasing order
39pub trait LttbSource {
40    /// data item of [`LttbSource`]
41    type Item;
42
43    /// length of [`LttbSource`]
44    fn len(&self) -> usize;
45
46    /// is [`LttbSource`] empty
47    #[inline]
48    fn is_empty(&self) -> bool {
49        self.len() == 0
50    }
51
52    /// data item at  index `i`
53    fn item_at(&self, i: usize) -> Self::Item;
54
55    /// map data item to another type.
56    /// - if the data item type of [`LttbSource`] is not [`DataPoint`], lttb sampling can be used after casting
57    fn cast<T, F>(self, f: F) -> Cast<Self, T, F>
58    where
59        Self: Sized,
60        T: DataPoint,
61        F: Fn(Self::Item) -> T,
62    {
63        Cast { s: self, f }
64    }
65
66    /// lttb sampling
67    fn lttb(self, threshold: usize) -> LttbIterator<Self>
68    where
69        Self: Sized,
70        Self::Item: DataPoint,
71    {
72        let is_sample = !(threshold >= self.len() || threshold < 3);
73        let every = if is_sample {
74            ((self.len() - 2) as f64) / ((threshold - 2) as f64)
75        } else {
76            0_f64
77        };
78        LttbIterator {
79            source: self,
80            is_sample,
81            idx: 0,
82            a: 0,
83            threshold,
84            every,
85        }
86    }
87}
88
89/// map data item to another type
90pub struct Cast<S, T, F>
91where
92    S: LttbSource,
93    T: DataPoint,
94    F: Fn(S::Item) -> T,
95{
96    s: S,
97    f: F,
98}
99
100impl<S, T, F> LttbSource for Cast<S, T, F>
101where
102    S: LttbSource,
103    T: DataPoint,
104    F: Fn(S::Item) -> T,
105{
106    type Item = T;
107    #[inline]
108    fn len(&self) -> usize {
109        self.s.len()
110    }
111
112    #[inline]
113    fn item_at(&self, i: usize) -> Self::Item {
114        let item = self.s.item_at(i);
115        (self.f)(item)
116    }
117}
118
119impl<'a, S: LttbSource> LttbSource for &'a S {
120    type Item = S::Item;
121    #[inline]
122    fn len(&self) -> usize {
123        (*self).len()
124    }
125
126    #[inline]
127    fn item_at(&self, i: usize) -> Self::Item {
128        (*self).item_at(i)
129    }
130}
131
132/// iterator for [`LttbSource`]
133pub struct LttbIterator<S: LttbSource> {
134    source: S,
135    is_sample: bool,
136    idx: usize,
137    threshold: usize,
138    every: f64,
139    a: usize,
140}
141
142impl<S: LttbSource> LttbIterator<S>
143where
144    S::Item: DataPoint,
145{
146    fn next_no_sample(&mut self) -> Option<S::Item> {
147        if self.idx < self.source.len() {
148            let item = self.source.item_at(self.idx);
149            self.idx += 1;
150            Some(item)
151        } else {
152            None
153        }
154    }
155
156    fn next_sample(&mut self) -> Option<S::Item> {
157        if self.idx < self.threshold {
158            if self.idx == 0 {
159                self.idx += 1;
160                Some(self.source.item_at(0))
161            } else if self.idx + 1 == self.threshold {
162                self.idx += 1;
163                Some(self.source.item_at(self.source.len() - 1))
164            } else {
165                let every = self.every;
166                let i = self.idx - 1;
167                // Calculate point average for next bucket (containing c).
168                let mut avg_x = 0f64;
169                let mut avg_y = 0f64;
170
171                let avg_range_start = (((i + 1) as f64) * every) as usize + 1;
172
173                let mut end = (((i + 2) as f64) * every) as usize + 1;
174                if end >= self.source.len() {
175                    end = self.source.len();
176                }
177                let avg_range_end = end;
178
179                let avg_range_length = (avg_range_end - avg_range_start) as f64;
180
181                for i in 0..(avg_range_end - avg_range_start) {
182                    let idx = avg_range_start + i;
183                    let item = self.source.item_at(idx);
184                    avg_x += item.x();
185                    avg_y += item.y();
186                }
187                avg_x /= avg_range_length;
188                avg_y /= avg_range_length;
189
190                // Get the range for this bucket.
191                let range_offs = ((i as f64) * every) as usize + 1;
192                let range_to = (((i + 1) as f64) * every) as usize + 1;
193
194                // Point a.
195                let item = self.source.item_at(self.a);
196                let point_a_x = item.x();
197                let point_a_y = item.y();
198
199                let mut max_area = -1f64;
200                let mut next_a = range_offs;
201                for i in 0..(range_to - range_offs) {
202                    let idx = range_offs + i;
203
204                    // Calculate triangle area over three buckets.
205                    let item = self.source.item_at(idx);
206                    let area = ((point_a_x - avg_x) * (item.y() - point_a_y)
207                        - (point_a_x - item.x()) * (avg_y - point_a_y))
208                        .abs()
209                        * 0.5;
210                    if area > max_area {
211                        max_area = area;
212                        next_a = idx; // Next a is this b.
213                    }
214                }
215
216                let item = self.source.item_at(next_a); // Pick this point from the bucket.
217                self.a = next_a; // This a is the next a (chosen b).
218                self.idx += 1;
219                Some(item)
220            }
221        } else {
222            None
223        }
224    }
225
226    #[inline]
227    fn remaining(&self) -> usize {
228        if self.is_sample {
229            self.threshold - self.idx
230        } else {
231            self.source.len() - self.idx
232        }
233    }
234}
235
236impl<S: LttbSource> Iterator for LttbIterator<S>
237where
238    S::Item: DataPoint,
239{
240    type Item = S::Item;
241    fn next(&mut self) -> Option<Self::Item> {
242        if self.is_sample {
243            self.next_sample()
244        } else {
245            self.next_no_sample()
246        }
247    }
248
249    #[inline]
250    fn size_hint(&self) -> (usize, Option<usize>) {
251        let size = self.remaining();
252        (size, Some(size))
253    }
254}
255
256impl<S: LttbSource> ExactSizeIterator for LttbIterator<S>
257where
258    S::Item: DataPoint,
259{
260    #[inline]
261    fn len(&self) -> usize {
262        self.remaining()
263    }
264}
265
266impl<'a, T> LttbSource for &'a [T] {
267    type Item = &'a T;
268    #[inline]
269    fn len(&self) -> usize {
270        (*self).len()
271    }
272
273    #[inline]
274    fn item_at(&self, i: usize) -> Self::Item {
275        &self[i]
276    }
277}
278
279impl<T: Clone> LttbSource for [T] {
280    type Item = T;
281    #[inline]
282    fn len(&self) -> usize {
283        (*self).len()
284    }
285
286    #[inline]
287    fn item_at(&self, i: usize) -> Self::Item {
288        self[i].clone()
289    }
290}
291
292#[cfg(test)]
293mod tests {
294    use super::*;
295
296    #[derive(Debug, PartialEq, Clone)]
297    pub struct DataPoint {
298        pub x: f64,
299        pub y: f64,
300    }
301
302    impl DataPoint {
303        pub fn new(x: f64, y: f64) -> Self {
304            DataPoint { x, y }
305        }
306    }
307
308    impl super::DataPoint for DataPoint {
309        fn x(&self) -> f64 {
310            self.x
311        }
312
313        fn y(&self) -> f64 {
314            self.y
315        }
316    }
317
318    #[test]
319    fn lttb_test() {
320        let mut dps = vec![];
321        dps.push(DataPoint::new(0.0, 10.0));
322        dps.push(DataPoint::new(1.0, 12.0));
323        dps.push(DataPoint::new(2.0, 8.0));
324        dps.push(DataPoint::new(3.0, 10.0));
325        dps.push(DataPoint::new(4.0, 12.0));
326
327        let mut expected = vec![];
328        expected.push(DataPoint::new(0.0, 10.0));
329        expected.push(DataPoint::new(2.0, 8.0));
330        expected.push(DataPoint::new(4.0, 12.0));
331
332        let result: Vec<DataPoint> = dps.as_slice().lttb(3).cloned().collect();
333
334        assert_eq!(expected, result);
335    }
336}
plotters_iced/sample/lttb.rs

plotters_iced/sample/
lttb.rs
