如何在保持曲线总体形状的情况下减少曲线上的点数？

Question

我有一组构成曲线的点，我想减少点的数量，但仍保持曲线的整体形状。

基本上，我想从这个：

变成这个：

因此，算法将删除冗余的点，但保留那些真正定义形状的点（例如曲线底部的点）。是否存在已知的算法来完成此操作？我认为有，但我不确定在Google上该如何搜索。任何帮助都将不胜感激。

- laurent

---

我没有任何算法可以提供给你，但我们通常将这个过程称为“顶点简化”。也许这能帮助你在谷歌上搜索相关内容。 - Jesse Stimpson

一个相当快的numpy实现可以在这里找到：https://stackoverflow.com/a/69026086/9801281 - Amit Oved

Answer 1

考虑使用道格拉斯-普克算法

- MBo

---

谢谢，我最终使用了 Douglas-Peucker 算法，效果非常好。 - laurent

@this.lau_ 你能分享一下你对这个算法的实现吗？ - EmptyData

你如何决定在任意曲线上使用该算法的 epsilon 值？ - user3700562

这是C#的一个实现：https://dev59.com/GB79s4cB2Jgan1znUg4P#69705346 - ephraim

Answer 2

这方面有几种算法。

最简单的算法可能就是不断删除相邻点之间角度最接近180度的点，直到达到某个阈值或者所需点数为止。

如果曲线像你的图片一样平滑，可以使用贝塞尔曲线来得到更好的逼近（或者更少的点，如果你需要的话）。

- aioobe

---

谢谢，但我认为第一个建议对我不起作用，因为我的数据不像示例中那样干净。可能会有非常靠近彼此的小点杂乱无章，应该将其缩减为一个单独的点，而不考虑角度。使用贝塞尔曲线可能会使问题更加复杂，而不是简化它，并使渲染变慢。 - laurent