0
$\begingroup$

I'm trying to implement Ramer-Douglas-Peucker line simplification in Mathematica, and I'm running into an issue with recursion. My implementation of the algorithm is below:

RDP[points_, ϵ_] := (
  Print[points];
  start := points[[1]];
  end := points[[-1]];
  vec := Normalize[end - start];
  dist[p_] := (
    t := Dot[(p - start), vec];
    loc := start + t*vec;
    Norm[loc - p]
    );
  distances := Map[dist, points];
  maxdist := Max[distances];
  maxelem := FirstPosition[distances, maxdist][[1]];
  res := If[maxdist < ϵ,
    {start, end},
    p0 := points[[1 ;; maxelem]];
    p1 := points[[maxelem ;;]];
    fst := RDP[p0, ϵ];
     Print["Run with p1 = ", p1];
    snd := RDP[p1, ϵ];
    Join[fst, snd];
    ];
  Print["result ", res];
  res
  )
line := {{0, -1}, {5, 5}, {5, 16}, {11, 23}}
Block[{$RecursionLimit = 25}, RDP[line, 1]]

I'm getting a very strange result. A snippet of the output:

{{0,-1},{5,5},{5,16},{11,23}}    
Run with p1 = {{5,16},{11,23}}    
{{0,-1},{5,5},{5,16}}    
Run with p1 = {{5,5},{5,16}}    
{{0,-1},{5,5}}    
result {{0,-1},{5,5}}    
{{0,-1},{5,5},{5,16}}    
Run with p1 = {{5,5},{5,16}}    
{{0,-1},{5,5}}    
result {{0,-1},{5,5}}    
{{0,-1},{5,5},{5,16}}    
Run with p1 = {{5,5},{5,16}}    
{{0,-1},{5,5}}    
result {{0,-1},{5,5}}    
{{0,-1},{5,5},{5,16}}    
Run with p1 = {{5,5},{5,16}}

It looks like p0 and p1 are set correctly after the split, and I can verify that the recursive call succeeds when it's called on p0. However, on the second recursive call, the value passed into the function is not the value that the function actually runs on; you can see that, when p1 is set to {{5,16},{11,23}}, RDP[p1, ϵ] actually runs with points set to {{0,-1},{5,5},{5,16}}.

I'm not the most experienced Mathematica user, and this is my first time implementing this sort of recursive function, so I might be missing something pretty simple. Any help or pointers welcome!

$\endgroup$
  • 1
    $\begingroup$ Why don't you localize the variables inside the function? Look up Module, and also the difference betweeen = and := (Set vs SetDelayed). $\endgroup$ – Szabolcs Aug 4 '14 at 19:10
  • 3
    $\begingroup$ You'll have to localize variables. Using globals in a recursive function just isn't going to work. $\endgroup$ – Daniel Lichtblau Aug 4 '14 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.