Return evenly-spaced samples from an array using Bresenham's line algorithm

bresenham.rs

/// Return evenly-spaced samples from an array using [Bresenham's line algorithm](https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html)
/// Adapted from https://observablehq.com/@mbostock/evenly-spaced-sampling
///
/// # Explanation
/// This works because the problem is equivalent to drawing a line on a `num_samples` x `arr` grid of
/// discrete pixels:
/// `x` coordinates are in the range `0…arr - 1` and `y` coordinates are in the range `0…num_samples - 1`
/// We then proceed as if we were drawing a line from the origin to `arr - 1, num_samples - 1`:
/// Whenever the `y` coordinate changes we choose a new element from `x`.
///
/// # Examples
///
/// ```
/// use bresenham_sampling::bresenham_sampling;
///
/// let array = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
/// assert_eq!(bresenham_sampling(&array, 3), vec![0, 5, 9]);
/// ```
pub fn bresenham_sampling<T: Clone>(arr: &[T], num_samples: u32) -> Vec<T> {
    let n = arr.len();
    if num_samples == 0 {
        vec![]
    } else if n <= num_samples as usize {
        arr.to_vec()
    } else {
        (0_..num_samples)
            .enumerate()
            .map(|(idx, _)| {
                // conversion from usize to f64 can result in precision loss
                // if the input falls outside ±9,007,199,254,740,991
                // todo: handle this in a better way than panicking?
                arr[(idx as f64 / (num_samples as f64 - 1.0) * (n as f64 - 1.0)).round() as usize]
                    .clone()
            })
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sampling() {
        // this test exercises wrapping behaviour and will fail if it's incorrectly implemented
        let array = (0_i32..1000).collect::<Vec<_>>();
        let samples = bresenham_sampling(&array, 5);
        assert_eq!(samples, vec![0, 250, 500, 749, 999]);
    }
}