이 재귀 함수를 호출 할 때 스택 오버플로를 피하는 방법

Question

Rust에서 Ramer-Douglas-Peucker 행 단순화 알고리즘을 구현했으며 엡실론 값> 1.0에서 올바르게 작동합니다. 그러나 그보다 작은 값은 스택 오버 플로우를 발생시킵니다. 어떻게 이것을 피하기 위해 함수를 다시 작성할 수 있습니까?

// 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]]); 
} 

Answer 1

rdp의 흐름을 살펴보십시오. dmax > epsilon 조건에서 재귀하는 재귀 함수입니다. 따라서 변수를 따라 가자.

먼저 dmax을 1.0으로 설정합니다. 그런 다음 distance > dmax, dmax이 distance으로 설정됩니다. 따라서 dmax이 1.0 미만일 수는 없습니다.

그런 다음 dmax > epsilon 인 경우 재발행합니다. 일 경우 항상이 발생합니다.

알고리즘을 wikipedia에서 보면 dmax이 0.0부터 시작해야 함을 알 수 있습니다.

제쳐두고, hypot 기능으로 거리 기능을 약간 더 멋지게 만들 수 있습니다.