近似非参数三次Bezier

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

请问这是一个很好的解决方案呢？

只需解决立方体.

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

递归细分的方法可行,但我希望它比解决立方体慢得多.(除非您正在使用某种具有异常差的浮点容量的嵌入式处理器.)

您应该可以轻松找到解决已经过彻底测试和调试的立方体的代码.如果使用递归细分实现自己的解决方案,则不会有这种优势.

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

编辑:回复你的评论,但我需要超过300个字符.

我只处理bezier曲线,其中y(x)只有一个(实数)根.关于数值稳定性,使用http://en.wikipedia.org/wiki/Cubic_equation#Summary中的公式,如果你很小,可能会出现问题. - jtxx000

wackypedia文章是数学,没有代码.我怀疑你可以找到一些更准备好在某处使用的食谱代码.也许数字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一起研究在你的大小中引入了多少错误.当然,只有你知道你需要多少精确度.

本文给出了3个立方体根的公式.给定三个u值,您可以得到3个相应的x值.u和x的3个值都是具有虚部的复数.如果你确定的话必须只有一个真正的解决方案,然后你期望其中一个根具有零虚构成分,而另外两个成为复共轭.看起来你必须计算所有三个,然后选择真实的一个.(注意,复数u可以对应于实数x!)然而,还有另一个数值稳定性问题:浮点算法就是这样,真实解的虚部不会完全为零,而虚构的组成部分则是非实根可以任意接近于零.因此,数字舍入会导致您选择错误的根.如果从您的应用程序中获得一些可以在那里申请的健全性检查,那将会很有帮助.

如果你确实选择了正确的根,那么Newton-Raphson的一次或多次迭代可以提高它的准确性.