逼近非参数三次贝塞尔曲线 [英] Approximating nonparametric cubic Bezier

问题描述

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

What is the best way to approximate a cubic Bezier curve? Ideally I would want a function y(x) which would give the exact y value for any given x, but this would involve solving a cubic equation for every x value, which is too slow for my needs, and there may be numerical stability issues as well with this approach.

这是一个好的解决方案吗?

Would this be a good solution?

推荐答案

只解决三次方.

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

If you're talking about Bezier plane curves, where x(t) and y(t) are cubic polynomials, then y(x) might be undefined or have multiple values. An extreme degenerate case would be the line x= 1.0, which can be expressed as a cubic Bezier (control point 2 is the same as end point 1; control point 3 is the same as end point 4). In that case, y(x) has no solutions for x != 1.0, and infinite solutions for x == 1.0.

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

A method of recursive subdivision will work, but I would expect it to be much slower than just solving the cubic. (Unless you're working with some sort of embedded processor with unusually poor floating-point capacity.)

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

You should have no trouble finding code that solves a cubic that has already been thoroughly tested and debuged. If you implement your own solution using recursive subdivision, you won't have that advantage.

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

Finally, yes, there may be numerical stablility problems, like when the point you want is near a tangent, but a subdivision method won't make those go away. It will just make them less obvious.

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

EDIT: responding to your comment, but I need more than 300 characters.

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

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收集的算法链接文本.

The wackypedia article is math with no code. I suspect you can find some cookbook code that's more ready-to-use somewhere. Maybe Numerical Recipies or ACM collected algorithms link text.

对于您的特定问题，使用与本文相同的表示法，当p也是零或接近零时，u仅为零或接近零.它们由以下公式关联:
u^^6 + q u^^3 == p^^3 /27
接近零，您可以使用近似值:
q u^^3 == p^^3 /27
或q的p / 3u ==立方根
因此，来自u的x的计算应包含以下内容:

To your specific question, and using the same notation as the article, u is only zero or near zero when p is also zero or near zero. They're related by the equation:
u^^6 + q u^^3 == p^^3 /27
Near zero, you can use the approximation:
q u^^3 == p^^3 /27
or p / 3u == cube root of q
So the computation of x from u should contain something like:

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

零附近的附近"如何?取决于您需要多少精度.您可以在Maple或Matlab上度过一些美好的时光，看看对u的大小引入多少误差.当然，只有您知道您需要多少精度.

How "near" zero is near? Depends on how much accuracy you need. You could spend some quality time with Maple or Matlab looking at how much error is introduced for what magnitudes of u. Of course, only you know how much accuracy you need.

本文为三次方的3个根给出了u的3个公式.给定三个u值，您可以获得3个对应的x值. u和x的3个值都是带有虚部的复数.如果您确保必须只存在一个实解，那么您希望其中一个根的虚部为零，而另两个根是复共轭的.看来您必须计算所有三个，然后选择真实的三个. (请注意，复数u可以对应于实数x！)但是，这里还有另一个数值稳定性问题:浮点运算就是它的实数，实解的虚部不会完全为零，而的虚部为非实根可以任意接近零.因此，数字四舍五入可能会导致您选择错误的根.如果您的应用程序中有一些健全性检查，可以在其中进行应用，那么这将很有帮助.

The article gives 3 formulas for u for the 3 roots of the cubic. Given the three u values, you can get the 3 corresponding x values. The 3 values for u and x are all complex numbers with an imaginary component. If you're sure that there has to be only one real solution, then you expect one of the roots to have a zero imaginary component, and the other two to be complex conjugates. It looks like you have to compute all three and then pick the real one. (Note that a complex u can correspond to a real x!) However, there's another numerical stability problem there: floating-point arithmetic being what it is, the imaginary component of the real solution will not be exactly zero, and the imaginary components of the non-real roots can be arbitrarily close to zero. So numeric round-off can result in you picking the wrong root. It would be helpfull if there's some sanity check from your application that you could apply there.

如果选择正确的根，Newton-Raphson的一个或多个迭代可以大大提高其准确性.

If you do pick the right root, one or more iterations of Newton-Raphson can improve it's accuracy a lot.

这篇关于逼近非参数三次贝塞尔曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！