piecewise linear approximation

q<-c(18, 15, 24, 23, 18, 22, 19, 29, 22, 25, 20, 19, 18, 20, 26, 32,
     26, 26, 34, 29, 23, 34, 22, 19, 21, 19, 34, 23, 23, 23, 30, 21,
     15, 29, 32, 19, 21, 28, 22, 32, 29, 25, 28, 28, 23, 12, 26, 24,
     27, 14, 38, 27, 28, 25, 38, 34, 25, 37, 15, 28, 15, 23, 23, 28,
     15, 15, 19, 25, 28, 16, 19, 17, 23, 19, 16, 18, 18, 17, 20, 18,
     21, 13, 11, 12, 13, 16, 13, 16, 10, 13, 14,  6, 19, 18, 19, 15,
     17,  6, 14, 28, 15, 20, 16, 12)

# distance function
dis_f <- function(t, q, i, j){
  a <- (q[j]-q[i])/(j-i)
  abs((q[i]*j-q[j]*i)/(j-i) + a * t - q[t]) / sqrt(a^2 + 1)
}

pla <- function(q, i, j, time, eplison){
  if (i > j || j - i <= 1)
    return(sort(time))

  # find the maximum distance (Following two lines represents the Step 3~5)
  dis_t <- dis_f((i+1):(j-1), q, i, j) # calculate distance of qi~qj
  loc <- which.max(dis_t)
  # find the position
  pos <- i + loc
  # record the position
  best_so_far <- dis_t[loc]
  # print the segment
  cat(sprintf("segment: %i, %i, %.2f\n", i, j, best_so_far))
  # Step 6: find more segments
  if (best_so_far >= eplison)
  {
    # record the time
    time <- c(time, pos)
    if (pos < j)
    {
      time <- pla(q, i, pos, time, eplison)
      time <- pla(q, pos, j, time, eplison)
    }
  }
  return(sort(time))
}
# calculate eplison
eplison <- sd(dis_f(1:length(q), q, 1, length(q)))
time <- pla(q, 1, length(q), c(1, length(q)), eplison)

plot(1:length(q), q,type="o")
lines(time, q[time], col = 2)