# Line simplification algorithm

I'm having an issue with a large amount of time stamped data for work. Each data point has a value and a time stamp.

We are going to be displaying this data on a graph, but we need a way to reduce the amount of points in the series due to the restriction on visible points on the graph.

Eg. A week time range will return approximately 5000 individual points, but the graphing component can only show up to 450 points in a series at a time (1 point per pixel).

So this means we need to simplify the amount of data in the series. We don't want to average points, but keep the raw values, just remove a certain number to get it underneath the 450 point maximum.

These series tend to be sawtooth waveforms.

We investigated the DouglasPeucker, but I wasn't sure how to apply it.

Are there any other algorithms or suggestions on how this can be accomplished?

EDIT: This is an example of a typical sawtooth waveform.

-
How much "subgrid" variation is there in the data? What I mean is, if you just draw every 11th data point -- so you end up with about 444 points -- will you lose a significant amount of information? –  Rahul Mar 2 '11 at 4:30
@Rahul Narain: I've attached a sample of the sawtooth waveform we deal with. –  Alastair Pitts Mar 2 '11 at 4:37
Is the shape important or is only the frequency of the teeth important? If only the frequency of the teeth, you can use a color gradient instead. You have 5000 points but only 450 pixels, then split the line into fixed number intervals (each with 30 points for example) and calculate how many teeth there are in each interval. Then color code with red for very few teeth and blue for very many teeth. –  Apprentice Queue Mar 2 '11 at 5:17
What is the scale of that image? It looks like one data point every one or two pixels, is that right? If so, then decimating the data will probably lead to aliasing in the high-frequency parts. –  Rahul Mar 2 '11 at 5:35
If there is no other requirement from you, you can just keep every 10-th point and drop other points. –  beroal Mar 2 '11 at 13:02

(1) Find "extreme" points -- ones with the property that $|y(i)| \ge |y(j)|$ for $j = i-10, i-9, \ldots, i-1, i, i+1, \ldots, i+10$, where I've used "10" as a guess here -- 3 or 5 might work just as well.