How to reduce the number of points in a curve whil

问题:

I have a list of points that make a curve, and I would like to reduce the number of points, but still keep the overall shape of the curve.

Basically, I want to go from this:

To this:

So the algorithm would remove the points that are redundant but preserve those that really define the shape (like the points at the bottom of the curve). Is there any known algorithm to do that? I expect there is but I'm not sure what to search for on Google. Any help would be appreciated.

回答1:

Consider Douglas–Peucker_algorithm

回答2:

There are several algorithms for this.

The simplest one is probably to just keep removing the point whose angle between neighboring points is closest to 180 degrees, until some threshold, or until you've reached a desired number of points.

If the curve is smooth as in your picture, you'll probably get better approximations (or fewer points if you so like) by using Bezier curves for instance.