title: Efficient Perceptually Important Points (PIPs) algo. in R or Rcpp
body: <p>I try to write an algorithm which finds Perceptually Important Points (PIPs) PIPs in a time series. These are Points which &quot;shape&quot; or &quot;characterize&quot; a time series. It is quite simple. The algorithm connects the first and the last point of the time series and &quot;draws&quot; a line between them. In the next step the algorithm looks for that point in the time series which has the greatest &quot;distance&quot; (the distance can be measured simple by the vertical distance or euclidean distance) to the &quot;imaginary&quot; line. This Point is the next PIP. Now there are two lines. Connecting the first Point with the new PIP and the second line - connecting the new PIP with the last.
  The algorithm now does the same again. Checks on both lines: &quot;which point has the greatest distance&quot; -&gt; Set this point as next PIP.</p>
  <p>Here is a visualization of the algorithm followed by a pseudo code</p>
  <p><img src="https://i.stack.imgur.com/VDruO.jpg" alt="Identification of the first 5 PIPs using the vertical distancnce (Fu2008)" /></p>
  <p>Pseudo code:</p>
  <pre><code>Function findPIPs(P)
  Input: sequence p[1 ..m]
  Output: PIPList L[l..m]
  Begin
  Set L[l] = P[1], L[2] = P[2]
  Repeat until L[l ..m] all filled 
  Begin
  Select point p[j] with maximum distance to the adjacent points in PIPList(L[1] and L[2] initially)
  Append P[j] to L
  End
  Return L
  END
  </code></pre>
  <p>I tried to implement it in R. But it seems to be completely inefficient. It takes way to much time. Furthermore there is still a small &quot;bug&quot; (sometimes some Points lying exactly on the interpolated line. Hence, the distance is &quot;0&quot; - the algorithm does not account for this problem at the moment).</p>
  <p>In the end I think I need to write the code in c++ with Rcpp. Is there a way to make the R code more efficient via vectorization for example?</p>
  <p>Here is my R code:</p>
  <pre><code># PIPs
  
  # -&gt; Input
  ## Vector
  # &lt;- Output
  # PIPs Indiezes
  
  getPIPs &lt;- function(x, y, distance = &quot;EUK&quot;) {
      PIPs &lt;- vector(&quot;list&quot;, 4)
      PIPs[[1]] &lt;- c(1, length(y)) 
    
      for(i in 1:(length(y)-2)) {
          switch(distance,
              EUK = (DISTANCE.F &lt;- EUK.distance.f),
              VD  = (DISTANCE.F &lt;- VD.distance.f ),
          )
      
          PIPs &lt;- helper.f(PIPs, x, y, DISTANCE.F)
      }
    
      return(PIPs)
  }
  
  helper.f &lt;- function(PIPs, x, y, DISTANCE.F) {
      t &lt;- sort(PIPs[[1]])
      gesamt &lt;- NULL
    
      for(z in 1:(length(t)-1)) {  
          gesamt &lt;- c(gesamt,DISTANCE.F(x, y, t[z], t[z+1]))
      }
  
      if(all(gesamt == 0)) return(PIPs)
      else PIPs[[1]] &lt;- append(PIPs[[1]], which.max(gesamt))
    
      return(PIPs)
  }
  
  EUK.distance.f &lt;- function(x, y, sI, eI) {
      pointsbetween &lt;- sI:eI
  
      erg &lt;- 
      sqrt((sI - x[pointsbetween])^2 + (y[sI] - y[pointsbetween])^2) + 
      sqrt((eI - x[pointsbetween])^2 + (y[eI] - y[pointsbetween])^2)
      erg[1] &lt;- 0
      erg &lt;- erg[-length(erg)]
  
      return(erg)
  }
  
  VD.distance.f &lt;- function(x, y, sI, eI) { #Start und Endindex
      erg &lt;- 
      abs(y[sI:eI] - (y[sI] +
          (x[sI:eI] - x[sI]) *
          ((y[eI] - y[sI]) / (x[eI] - x[sI]))
          )
      )
      erg &lt;- erg[-length(erg)]
  
      return(erg)
  }
  
  #visualize
  itertivePlotPIPS.f &lt;- function(x, y, z) {
      plot(x, y)
      lines(sort(PIPs[[1]][1:length(x)]), y[sort(PIPs[[1]][1:length(x)])], col  = &quot;azure3&quot;)
      lines(sort(PIPs[[1]][1:z]), y[sort(PIPs[[1]][1:z])])
  }
  </code></pre>
  <p>Run the code with</p>
  <pre><code>x &lt;- 1:100 # &quot;Time&quot; (x)-axis
  y &lt;- sample(1:100) # &quot;Data&quot; y-axis
  getPIPs(x, y, &quot;EUK&quot;)
  </code></pre>
  <p>To visualize the data</p>
  <pre><code>itertivePlotPIPS.f(x,y,10) # the 10 at the end means &quot;take the first ten PIPs&quot;
  </code></pre>
  <p>I hope it is not too confusing. I tried to make it simple.</p>
  <blockquote>
  <p>References: Fu, Tak chung et al. (2008). &quot;Representing Financial time
  series based on data point importance&quot;. In: Engineering Applications
  of Artifcial Intelligence 21.2. F/S, PIIP, pp. 277{300. issn:
  0952-1976. doi: <a href="http://dx.doi.org/10.%201016/j.engappai.2007.04.009" rel="nofollow noreferrer">http://dx.doi.org/10.
  1016/j.engappai.2007.04.009</a>. url: <a href="http://www.sciencedirect.%20com/science/article/pii/S0952197607000577" rel="nofollow noreferrer">http://www.sciencedirect.
  com/science/article/pii/S0952197607000577</a>.</p>
  </blockquote>