Polygonal Approximation of Curves

Definition: Using line segments to approximate one curve. No doubt it will compress data and simplify the shape analysis.

Methods

1) Heuristic

Search point by point, until the error boundary has been exceeded. It just gives out the line segments which does not exceed the Error Threshold.

2) Optimized

Use a shortest path theory to solve the problem. The path length will be the errors, and the path is the selected vertex, then use a optimized method to search the best path. It gives out the line segments Minimizing the total error.

Problem I met when i used it:

1) Noise

when there is noise in signal , most of the time, the algorithm can get the mean line of the noise, which can be seen as a denoising effect. But some time it just takes some big noise peaks as the true line of the signal.

some conditions to identify this: a) noise in context as reference, b) at least including one up and down shapes, c) errors is zeros, d) length is short but not so short, e) slope is high.

2) computational burden

the heuristic method is fast, but can give a -peasudo-best results, and can not give the corners good thinking.

the optimized method need too much searching loops.