math - 逼近非参数三次贝塞尔曲线

Question

近似三次贝塞尔曲线的最佳方法是什么？理想情况下，我想要一个函数 y(x)，它可以为任何给定的 x 提供精确的 y 值，但这将涉及为每个 x 值求解一个三次方程，这对我的需要来说太慢了，并且可能存在数值稳定性问题以及这种方法。

这会是一个很好的解决方案吗？

Answer 1

只需解决立方。

如果您谈论的是贝塞尔平面曲线，其中 x(t) 和 y(t) 是三次多项式，那么 y(x) 可能未定义或具有多个值。极端退化的情况是线 x= 1.0，可以表示为三次贝塞尔曲线（控制点 2 与端点 1 相同；控制点 3 与端点 4 相同）。在这种情况下，y(x) 对于 x != 1.0 没有解，对于 x == 1.0 没有无限解。

递归细分的方法会起作用，但我希望它比仅仅求解三次要慢得多。（除非您正在使用某种浮点容量异常差的嵌入式处理器。）

您应该可以毫不费力地找到解决已经过彻底测试和调试的三次方的代码。如果您使用递归细分实现自己的解决方案，您将不会拥有该优势。

最后，是的，可能存在数值稳定性问题，例如当您想要的点靠近切线时，但细分方法不会使这些问题消失。它只会让它们变得不那么明显。

编辑：回复您的评论，但我需要 300 多个字符。

我只处理 y(x) 只有一个（实）根的贝塞尔曲线。关于数值稳定性，使用http://en.wikipedia.org/wiki/Cubic_equation#Summary中的公式，如果 u 非常小，可能会出现问题。– jtxx000

古怪的文章是没有代码的数学。我怀疑您可以在某处找到一些更易于使用的食谱代码。也许 Numerical Recipies 或 ACM 收集的算法链接文本。

对于您的具体问题，并使用与文章相同的符号，当 p 也为零或接近零时，u 仅为零或接近零。它们通过以下等式相关：
u^^6 + q u^^3 == p^^3 /27
接近零，您可以使用近似值：
q u^^3 == p^^3 /27
或 p / 3u ==q 的立方根
所以从 u 计算 x 应该包含以下内容：

(fabs(u) >= somesmallvalue) ?  (p / u / 3.0) : cuberoot (q)

离零有多“近”？取决于你需要多少准确度。您可以花一些时间在 Maple 或 Matlab 上查看对于 u 的大小引入了多少误差。当然，只有你知道你需要多少精度。

这篇文章为三次方的 3 个根给出了 u 的 3 个公式。给定三个 u 值，您可以获得 3 个对应的 x 值。u 和 x 的 3 个值都是具有虚部的复数。如果你确定必须只有一个真正的解决方案，然后您期望一个根的虚部为零，而另外两个是复共轭。看起来你必须计算所有三个，然后选择真正的一个。（请注意，复数 u 可以对应于实数 x！）但是，还有另一个数值稳定性问题：浮点运算就是这样，实数解的虚部不会完全为零，而虚部非实根可以任意接近零。因此，数字四舍五入可能会导致您选择错误的根。如果您的应用程序中有一些您可以在那里应用的健全性检查，那将会很有帮助。

如果您确实选择了正确的根，Newton-Raphson 的一个或多个迭代可以大大提高它的准确性。

Answer 2

是的，de Casteljau 算法会为您工作。但是，我不知道它是否会比通过卡尔达诺方法求解三次方程更快。