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

Question

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

this是一个好的解决方案吗？

Answer 1

刚解决立方。

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

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

您无需费力就能找到解决已经经过全面测试和调试的三次方的代码。如果使用递归分割实现自己的解决方案，那么您将没有优势。

最后，是的，可能存在数值稳定性问题，例如当您要的点在切线附近时，但是分割方法并不能解决这些问题。这只会使它们不那么明显。

编辑:回复您的评论，但我需要300个以上的字符。

I'm only dealing with bezier curves where y(x) has only one (real) root. Regarding numerical stability, using the formula from http://en.wikipedia.org/wiki/Cubic_equation#Summary, it would appear that there might be problems if u is very small. – jtxx000

这个wackypedia文章是数学的，没有代码。我怀疑您可以在某个地方找到一些更易于使用的食谱代码。也许是数字食谱或ACM收集的算法 link text。

对于您的特定问题，并使用与本文相同的表示法，当p也是零或接近零时，u仅为零或接近零。它们由以下公式关联:
u^^6 + q u^^3 == p^^3 /27接近零，您可以使用近似值:
q u^^3 == p^^3 /27或q的 p / 3u ==立方根
因此，来自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的一个或多个迭代可以大大提高其准确性。