如何简化三次贝塞尔曲线？

Question

我有一个由多个线段组成的三次贝塞尔曲线（左图）。它有一些粗糙的曲率，我需要使它更加平滑，就像右边的图片一样。这个问题有点像“去噪”，我该如何解决？

这里有一个类似的讨论（链接），但输入是一组点，并使用最小二乘法拟合贝塞尔曲线，而在我的问题中，输入已经是三次贝塞尔曲线。

注：上面的图片中我没有画线段和控制点，但我希望你能理解。

- azer89

---

左边的图像真的是贝塞尔曲线吗？如果你做了一些微不足道的事情，比如扔掉每隔一个的控制点，那就足以显著地平滑这个波浪形 S。通常来说，听起来你只需要降低这里的贝塞尔曲线的次数，而且有很多更复杂的方法可以实现这一点。 - Andon M. Coleman

是的，左边的那个有很多段。也许你提到的通过删除一些点来解决问题的方法可以解决这个问题，但我还需要将误差最小化。 - azer89

你可以随时提取曲线上的点并进行平滑处理。之后，你可以重新构建贝塞尔曲线。 - Spektre

嗨@Spektre，是的，我也一直在考虑这个问题，也许现在这是最明智的方法，尽管一开始我寻求其他“数学上正确”的解决方案。 - azer89

@azer89，使用BEZIER直接完成这个也是可能的，但由于BEZIER中混乱的点/方向数据，这要困难得多才能获得“相同”的结果。在某些情况下，只更改控制向量就足够了，但不要总是指望这种情况。 - Spektre

你可能会对这个目的的开源C库感兴趣：https://github.com/ideasman42/curve-fit-nd，还有一个Rust版本的 https://github.com/ideasman42/raster-retrace/tree/master/src/intern/curve_fit_nd - ideasman42

Answer 1

你是否希望保持相同的曲线段数？你需要保持Bezier曲线段之间的连续性吗？你是想达到一定数量的曲线段，还是只想保持在原始曲线的一定容差范围内平滑？

现在我假设您想减少Bezier曲线段的数量，需要保持G1连续性，并且您正在尝试在容差范围内平滑（根据您的图像猜测）。

对于顶层算法，您需要遍历每个相邻的曲线对，并尝试将它们组合起来。重复此过程，直到组合两个相邻曲线会超出您的容差范围为止。

如何组合两个相邻的Bezier曲线？让我们假设它们是曲线P和Q，由于它们都是三次曲线，因此它们各自有4个控制点，分别为P0、P1、P2、P3和Q0、Q1、Q2、Q3。我们还假设P3 == Q0。此外，我们将输出曲线定义为R，由R0、R1、R2、R3组成。

还有一个非常重要的步骤——您需要为要简化的较大曲线中的每个Bezier曲线段分配t值。因此，段0将从0..1进行，段1将从1..2进行，段2将从2..3进行，依此类推。

如果您想保持P与其相邻曲线的连续性，以及Q与其相邻曲线的连续性，则不能移动P0或Q3，并且由（P1-P0）和（Q2-Q3）形成的切向量必须保持相同方向。它们只能被缩放。

由于R中只有4个控制点，因此这两个比例因子是您唯一的自由度。我们将它们称为kp和kq。

R0=P0
R1=P0+kp*(P1-P0)
R2=Q3+kq*(Q2-Q3)
R3=Q3

如果两条曲线的结长度相等，则kp = 2，kq = 2。

- tfinniga

Answer 2

我之前曾经研究过这个问题：

以下是一些建议：

迭代删除结点

通过删除操作，您可以：

• 将线段折叠成新的结点，并放置在线段上的某个位置。
• 移除结点，然后测量由此移除引起的误差。

移除结点后，您需要重新计算两侧剩余结点的控制点长度，然后测量移除所引起的误差（移除成本）。 请参见 FitCurve.c，了解最小二乘切线长度计算的示例。

每次移除的成本可以放入一个小根堆中， 然后您可以从堆顶弹出成本最低的元素（重新评估相邻结点的移除成本）。

这里有一些可以实现此功能的C代码。

重新评估曲线

您可以将曲线评估为简单多边形，然后对结果点运行曲线拟合算法，并设置较低的误差阈值。

在已经具备曲线拟合功能的情况下，添加此选项会显著减少麻烦。

这可能不会给出完美的结果，但对于您的目的而言可能足够好。

由于可以使用现有的曲线拟合库（此处链接到自己的开源库），因此可以实现此选项。

- ideasman42