この再帰関数を呼び出すときにスタックオーバーフローを避けるには

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機能を使用すると、距離機能を少し良くすることができます。