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.

Michael J. Barber
  • 24,518
  • 9
  • 68
  • 88
laurent
  • 88,262
  • 77
  • 290
  • 428
  • 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. – Jesse Stimpson Nov 02 '11 at 12:54
  • A fairly fast numpy implementation can be found here: https://stackoverflow.com/a/69026086/9801281 – Amit Oved Sep 05 '21 at 22:36

2 Answers2

29

Consider Douglas–Peucker_algorithm

enter image description here

MBo
  • 77,366
  • 5
  • 53
  • 86
16

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.

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • 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 04 '11 at 12:49