Aproximación del bezier cúbico no paramétrico

Question

¿Cuál es la mejor manera de aproximar una curva de Bezier cúbica? Idealmente, me gustaría una función y (x) que daría el valor y exacto para cualquier x dada, pero esto implicaría resolver una ecuación cúbica para cada valor x, que es demasiado lenta para mis necesidades, y puede haber problemas de estabilidad numérica también con este enfoque.

¿Sería this una buena solución?

Answer 1

Solo resuelve el cubo.

Si está hablando de curvas de plano de Bezier, donde x (t) e y (t) son polinomios cúbicos, entonces y (x) podría no estar definido o tener valores múltiples. Un caso degenerado extremo sería la línea x = 1.0, que puede expresarse como un Bezier cúbico (el punto de control 2 es el mismo que el punto final 1, el punto de control 3 es el mismo que el punto final 4). En ese caso, y (x) no tiene soluciones para x! = 1.0, y soluciones infinitas para x == 1.0.

Un método de subdivisión recursiva funcionará, pero esperaría que fuera mucho más lento que simplemente resolver el cubo. (A menos que esté trabajando con algún tipo de procesador integrado con una capacidad de coma flotante inusualmente pobre)

No debería tener problemas para encontrar un código que resuelva un cubo que ya se haya probado y depurado a fondo. Si implementa su propia solución usando la subdivisión recursiva, no tendrá esa ventaja.

Finalmente, sí, puede haber problemas numéricos de estabilidad, como cuando el punto que desea está cerca de una tangente, pero un método de subdivisión no hará que desaparezcan. Simplemente los hará menos obvios.

EDIT: respondiendo a tu comentario, pero necesito más de 300 caracteres.

Solo estoy tratando con curvas de bezier donde y (x) tiene solo una raíz (real). Con respecto a la estabilidad numérica, usando la fórmula de http://en.wikipedia.org/wiki/Cubic_equation#Summary, parece que podría haber problemas si usted es muy pequeño. - jtxx000

El artículo de wackypedia es matemática sin código. Sospecho que puedes encontrar algún código de libro de cocina que esté más listo para usar en alguna parte. Tal vez Recicerios Numéricos o algoritmos recopilados ACM link text.

Para su pregunta específica, y usando la misma notación que el artículo, u solo es cero o cerca de cero cuando p también es cero o cerca de cero. Están relacionados por la ecuación:
u^^6 + q u^^3 == p^^3 /27
cerca de cero, puede utilizar la aproximación:
q u^^3 == p^^3 /27
o p/3u == raíz cúbica de q
lo tanto, el cálculo de x de u debe contener algo como:

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

¿Cómo se acerca el "near" zero? Depende de la precisión que necesites. Podría pasar algún tiempo de calidad con Maple o Matlab mirando cuánto error se introduce para qué magnitud de u. Por supuesto, solo usted sabe la precisión que necesita.

El artículo proporciona 3 fórmulas para las 3 raíces del cubo. Dados los tres valores u, puede obtener los 3 valores x correspondientes. Los 3 valores para uyx son todos números complejos con un componente imaginario. Si está seguro que tiene que haber una sola solución real, entonces espera que una de las raíces tenga un componente imaginario cero, y las otras dos sean conjugados complejos. Parece que tienes que calcular los tres y luego elegir el verdadero. (Tenga en cuenta que un complejo u puede corresponder a una x real!) Sin embargo, hay otro problema de estabilidad numérica: la aritmética de punto flotante es lo que es, el componente imaginario de la solución real no será exactamente cero, y los componentes imaginarios de las raíces no reales pueden ser arbitrariamente cercanas a cero. Entonces, el redondeo numérico puede hacer que elijas la raíz incorrecta. Sería útil si hay algún control de cordura de su aplicación que pueda aplicar allí.

Si elige la raíz correcta, una o más iteraciones de Newton-Raphson pueden mejorar su precisión mucho.

Answer 2

Sí, el algoritmo de Casteljau funcionaría para usted. Sin embargo, no sé si será más rápido que resolver la ecuación cúbica por el método de Cardano.