23

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:

enter image description here

To this:

enter image description here

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.

2
  • 6
    I don't have any algorithms for you, but we usually refer to this process as vertex decimation. Perhaps that will help in your Googling. Nov 2, 2011 at 12:54
  • A fairly fast numpy implementation can be found here: stackoverflow.com/a/69026086/9801281
    – Amit Oved
    Sep 5, 2021 at 22:36

2 Answers 2

29

Consider Douglas–Peucker_algorithm

enter image description here

4
  • Thanks, I ended up using Douglas–Peucker algorithm which works great.
    – laurent
    Nov 4, 2011 at 12:44
  • 1
    @this.lau_ Can you please share your implementation for this algorithm.
    – EmptyData
    Dec 23, 2015 at 11:26
  • How do you decide on epsilon with this algorithm for arbitrary curves though? Aug 22, 2021 at 9:31
  • Here's an implementation for C#: stackoverflow.com/a/69705346/3225391
    – ephraim
    Oct 25, 2021 at 9:06
15

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.

1
  • Thanks, but I think the first suggestion would not work for me because my data is not as clean as in the example. There can be small clutters of points very close to each others, which should be reduced to one single point regardless of the angle. Using a Bezier curve would probably make the problem more complex instead of simplifying it, and make the rendering slower.
    – laurent
    Nov 4, 2011 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.