ramer_douglas_peucker 0.2.2

#![allow(clippy::range_minus_one)]
#![deny(
    deprecated_in_future,
    exported_private_dependencies,
    future_incompatible,
    missing_copy_implementations,
    missing_crate_level_docs,
    missing_debug_implementations,
    missing_docs,
    private_in_public,
    rust_2018_compatibility,
    rust_2018_idioms, // this complains about elided lifetimes.
    trivial_casts,
    trivial_numeric_casts,
    unsafe_code,
    unstable_features,
    unused_import_braces,
    unused_qualifications
)]
/*!
An implementation of the Ramer Douglas Peucker algorithm.

Given a slice of `Point2` and an epsilon, the `rdp()` function will return a Vec<usize> of which indices to keep.
*/

use std::ops::RangeInclusive;

use legasea_line::LineDistance;
use mint::Point2;

/// Given a set of points and an epsilon, returns a list of indexes to keep.
///
/// If the first and last points are the same, then the points are treated as a closed polygon
pub fn rdp<T, U>(points: &[Point2<T>], epsilon: f64) -> Vec<usize>
where
    T: Copy + std::ops::Sub<Output = U>,
    U: num_traits::cast::NumCast,
    T: num_traits::cast::NumCast,
{
    if points.len() < 3 {
        return (0..points.len()).collect();
    }

    let mut ranges = Vec::<RangeInclusive<usize>>::new();

    let mut results = Vec::new();
    results.push(0); // We always keep the starting point

    // Set of ranges to work through
    ranges.push(0..=points.len() - 1);

    while let Some(range) = ranges.pop() {
        let range_start = *range.start();
        let range_end = *range.end();

        let start = points[range_start];
        let end = points[range_end];

        // Caches a bit of the calculation to make the loop quicker
        let line = LineDistance::new(start, end);

        let (max_distance, max_index) = points[range_start + 1..range_end].iter().enumerate().fold(
            (0.0_f64, 0),
            move |(max_distance, max_index), (index, point)| {
                let distance = match line.to(point) {
                    Some(distance) => distance,
                    None => {
                        let base = (point.x - start.x).to_f64().unwrap();
                        let height = (point.y - start.y).to_f64().unwrap();
                        base.hypot(height)
                    }
                };

                if distance > max_distance {
                    // new max distance!
                    // +1 to the index because we start enumerate()ing on the 1st element
                    return (distance, index + 1);
                }

                // no new max, pass the previous through
                (max_distance, max_index)
            },
        );

        // If there is a point outside of epsilon, subdivide the range and try again
        if max_distance > epsilon {
            // We add range_start to max_index because the range needs to be in
            // the space of the whole vector and not the range
            let division_point = range_start + max_index;

            let first_section = range_start..=division_point;
            let second_section = division_point..=range_end;

            // Process the second one first to maintain the stack
            // The order of ranges and results are opposite, hence the awkwardness
            let should_keep_second_half = division_point - range_start > 2;
            if should_keep_second_half {
                ranges.push(second_section);
            }

            if division_point - range_start > 2 {
                ranges.push(first_section);
            } else {
                results.push(division_point);
            }

            if !should_keep_second_half {
                results.push(range_end);
            }
        } else {
            // Keep the end point for the results
            results.push(range_end);
        }
    }

    results
}

#[cfg(test)]
mod tests {
    use mint::Point2;

    use super::*;

    #[test]
    fn within_epsilon() {
        let points = vec![
            Point2 { x: 0.0, y: 0.0 },  //
            Point2 { x: 1.0, y: 0.5 },  //
            Point2 { x: 2.0, y: -0.9 }, //
            Point2 { x: 3.0, y: 0.3 },  //
            Point2 { x: 4.0, y: 0.0 },  //
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0, 4];

        assert_eq!(expected, actual);
    }

    #[test]
    fn within_center_out() {
        let points = vec![
            Point2 { x: 0.0, y: 0.0 },  // included
            Point2 { x: 1.0, y: 0.5 },  // excluded
            Point2 { x: 2.0, y: -1.1 }, // included
            Point2 { x: 3.0, y: 0.3 },  // excluded
            Point2 { x: 4.0, y: 0.0 },  // included
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0, 2, 4];

        assert_eq!(expected, actual);
    }

    #[test]
    fn inner_edges_out() {
        let points = vec![
            Point2 { x: 0.0, y: 0.0 }, // included
            Point2 { x: 1.0, y: 2.5 }, // included
            Point2 { x: 2.0, y: 1.1 }, // excluded
            Point2 { x: 3.0, y: 2.6 }, // included
            Point2 { x: 4.0, y: 0.0 }, // included
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0, 1, 3, 4];

        assert_eq!(expected, actual);
    }

    #[test]
    fn one_point() {
        let points = vec![
            Point2 { x: 0.0, y: 0.0 }, // included
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0];

        assert_eq!(expected, actual);
    }

    #[test]
    fn two_points() {
        let points = vec![
            Point2 { x: 0.0, y: 0.0 }, // included
            Point2 { x: 4.0, y: 0.0 }, // included
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0, 1];

        assert_eq!(expected, actual);
    }

    #[test]
    fn simplify_circle() {
        // If the first and last points are the same, it should treat the shape as a circle

        let points = vec![
            Point2 { x: 1, y: 1 }, // first
            Point2 { x: 2, y: 1 },
            Point2 { x: 3, y: 1 }, // keep
            Point2 { x: 3, y: 2 },
            Point2 { x: 3, y: 3 }, // keep
            Point2 { x: 2, y: 3 },
            Point2 { x: 1, y: 3 }, // keep
            Point2 { x: 1, y: 2 },
            Point2 { x: 1, y: 1 }, // same as first
        ];

        let actual = rdp(&points, 1.0);

        let expected = vec![0, 2, 4, 6, 8];

        assert_eq!(actual, expected);
    }
}