How can I avoid stack overflow when calling this recursive function

Question

I've implemented the Ramer–Douglas–Peucker line simplification algorithm in Rust, and it works correctly for epsilon values > 1.0. However, any value lower than that causes a stack overflow. How can I rewrite the function to avoid this?

// distance formula
pub fn distance(start: &[f64; 2], end: &[f64; 2]) -> f64 {
    ((start[0] - end[0]).powf(2.) + (start[1] - end[1]).powf(2.)).sqrt()
}

// perpendicular distance from a point to a line
pub fn point_line_distance(point: &[f64; 2], start: &[f64; 2], end: &[f64; 2]) -> f64 {
    if start == end {
        return distance(*&point, *&start);
    } else {

        let n = ((end[0] - start[0]) * (start[1] - point[1]) -
                 (start[0] - point[0]) * (end[1] - start[1]))
            .abs();
        let d = ((end[0] - start[0]).powf(2.0) + (end[1] - start[1]).powf(2.0)).sqrt();
        n / d
    }
}

// Ramer–Douglas-Peucker line simplification algorithm
pub fn rdp(points: &[[f64; 2]], epsilon: &f64) -> Vec<[f64; 2]> {
    let mut dmax = 1.0;
    let mut index: usize = 0;
    let mut distance: f64;
    for (i, _) in points.iter().enumerate().take(points.len() - 1).skip(1) {
        distance = point_line_distance(&points[i],
                                       &*points.first().unwrap(),
                                       &*points.last().unwrap());
        if distance > dmax {
            index = i;
            dmax = distance;
        }
    }
    if dmax > *epsilon {
        let mut intermediate = rdp(&points[..index + 1], &*epsilon);
        intermediate.pop();
        intermediate.extend_from_slice(&rdp(&points[index..], &*epsilon));
        intermediate
    } else {
        vec![*points.first().unwrap(), *points.last().unwrap()]
    }
}

fn main() {
    let points = vec![[0.0, 0.0], [5.0, 4.0], [11.0, 5.5], [17.3, 3.2], [27.8, 0.1]];
    // change this to &0.99 to overflow the stack
    let foo: Vec<_> = rdp(&points, &1.0);
    assert_eq!(foo, vec![[0.0, 0.0], [5.0, 4.0], [11.0, 5.5], [17.3, 3.2]]);
}

In this pseudo-code dmax starts with 0. Why do you start dmax with 1.0? — malbarbo
– malbarbo, Commented Aug 4, 2016 at 11:59
@MatthieuM. Oh, I was never in any doubt that that was the case. Unfortunately, it wasn't a more subtle error on my part… — urschrei
– urschrei, Commented Aug 4, 2016 at 12:21

Matthieu M. · Accepted Answer · 2016-08-04 12:19:37Z

4

Look at the flow of rdp. It's a recursive function that recurses on the condition that dmax > epsilon. So, let's follow those variables as we step through it:

First, we set dmax to 1.0. Then, if distance > dmax, dmax is set to distance. So, there's no way for dmax to ever be less than 1.0.

Then, if dmax > epsilon, we recurse. This will always happen if epsilon < 1.0.

If we look at the algorithm on wikipedia, you can see that dmax should start at 0.0.

As an aside, you could make your distance functions a bit nicer with the hypot function.

edited Aug 4, 2016 at 12:19

Matthieu M.

303k58 gold badges496 silver badges754 bronze badges

answered Aug 4, 2016 at 12:07

paholg

2,13819 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

urschrei Over a year ago

Well this is embarrassing.

Collectives™ on Stack Overflow

How can I avoid stack overflow when calling this recursive function

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related