I have a continuous data and i want to compress it by linearization(see picture). What algorithm can be used to minimize both number of lines and total compression error?
I have a continuous data and i want to compress it by linearization(see picture). What algorithm can be used to minimize both number of lines and total compression error?
On the face of it, this doesn't look that different from many polygon reduction algorithms, which are largely driven by picking an error tolerance. But could just as easily be done by picking a target polygon count or reduction percentage. In the simplest terms those type of algorithms take your squiggly line and compute an error function for the removal of each point, and then remove points the produce the least error while updating the error on the other points.
Depending on what this data means, you could do it in one or more passes. A simple one-pass solution (given that this is say, a line stroke from an artist's pen) is to read the line in point by point, collapsing the points as you go via comparison of the raw direction, or the tangents. This is useful for say smoothing a user input in 3d space to a much shorter list of directions from a very noisy input. But if this data has more information than just direction, Alvero is on the right track that you want to iteratively reduce your line by removing the points that contribute the least to the overall shape of the function.
Im doing some project on terrain geomorphing (with level of details), so you may consider initial data to be a values from heightmap (see picture). I need to find areas which can be approximated by line (triangles in 3D, not strictly equilateral or right-angled).Then in the same way find lines inside the parent lines (like tree). And may be in future apply this algorithm to 3D.