2012-07-17 21 views
7

Tengo un conjunto de casos especiales de splines cúbicos, cuyos 2d puntos de control siempre darán como resultado una curva que nunca se cruzará en el eje x . Es decir, las curvas parecen que podrían ser una función polinómica simple tal que y = f (x). Quiero crear de manera eficiente una matriz de y coordenadas a lo largo de la spline que corresponden a las coordenadas equies espaciadas que se extienden a lo largo del segmento spline.Transformar la función 2d spline f (t) en f (x)

Quiero encontrar de manera eficiente las coordenadas Y a lo largo de la acanaladura que, por ejemplo, x = 0,0, x = 0,1, x = 0,2, etc., o acercado otra manera, transformar eficazmente el f x, y ( t) función de estilo en una función f ( x).

Actualmente estoy usando una matriz constante 4x4 y cuatro puntos de control 2d para describir la spline, utilizando constantes de matriz, ya sea para Hermite o Catmull-Rom splines, y conectarlos a una función cúbica de t que va de 0 a 1.

Dada la matriz y los puntos de control, ¿cuál es la mejor manera de obtener estos valores y sobre el eje x?

EDITAR: Debo añadir que una aproximación lo suficientemente buena como para dibujar es suficiente.

+1

El método más simple que he encontrado hasta ahora es simplemente tomando una muestra de puntos de la curva a intervalos regulares de t, y luego interpolando entre los que están a lo largo del eje x para recoger los valores de f (x). Esto se ve bien la mayor parte del tiempo, pero ocasionalmente pierde detalles, porque es difícil saber dónde se encuentran las esquinas agudas; aumentar la frecuencia de muestreo ayuda, pero no es exactamente eficiente ni satisfactorio. Estoy seguro de que hay una manera inteligente que es computacionalmente eficiente y no pierde los detalles. – vercellop

+0

@vervellop, con la pregunta editada, su enfoque actual podría ser la mejor respuesta, por lo que le sugiero que lo publique como respuesta, para que eventualmente pueda aceptarlo si no aparece nada mejor. Y los usuarios pueden votarlo si lo consideran una solución buena/apropiada para este problema. – MvG

+0

Puede haber una contradicción en su pregunta: la pregunta original pide coordenadas espaciadas uniformemente * x *, mientras que la edición requiere una solución adecuada para el dibujo. En presencia de cúspides pronunciadas, un muestreo uniformemente espaciado probablemente no podrá capturar estas cúspides. Por lo tanto, sugiero que deje la pregunta tal como estaba originalmente, ya que a eso se refieren las respuestas. Es posible que desee hacer una nueva pregunta sobre el problema del dibujo, preferiblemente dando detalles sobre qué es exactamente lo que intenta lograr, es decir, por qué simplemente dibujar la spline 2D no es suficiente. – MvG

Respuesta

2

Su pregunta indica que desea espacios en forma pareja x coordenadas, y las soluciones aproximadas están bien. Por eso propongo el siguiente algoritmo:

  • Decidir sobre la red señala que desee, por ejemplo, uno cada 0,1 x unidades.
  • Comience con l = 0 y r = 1.
  • Compute f x ( l) y f x ( r) y considerar el intervalo denotado por estos criterios de valoración.
    • Si el intervalo es suficientemente pequeño y contiene exactamente un punto de la cuadrícula, utilice el parámetro central de t = ( l + r)/2 como una buena aproximación para este punto de la cuadrícula, y volver que como lista de un elemento.
    • Si hay al menos un punto de la cuadrícula en ese intervalo, se dividió en dos usando ( l + r)/2 como el punto de división, y concatenar las listas resultantes de ambos cálculos.
    • Si no hay un punto de la cuadrícula en el intervalo, omita la rama actual del cálculo y devuelva una lista vacía.

Esto hará zoom sobre los puntos de la cuadrícula, que divide en dos el espacio de parámetros en cada paso, y se van a plantear con los parámetros adecuados para todos los puntos de la rejilla.

+1

Este es un método de bisección ([link] (http://en.wikipedia.org/wiki/Bisection_method)), uno de los muchos métodos de búsqueda de raíz. Consulte en Wikipedia las fortalezas y debilidades de los algoritmos que pueden funcionar mejor (o peor) para problemas similares. –

2

Bueno, usted podría resolver su f x (t ) = x para t. Eso sería una ecuación cúbica; feo, pero aún es posible resolverlo explícitamente. Si su spline es tal como la describe, entonces dos de las soluciones serán conjugadas complejas, por lo que la única que queda es la que debe tomar. Úselo para calcular y = f y ( t). Dudo que puedas lograr algo más fácil si quieres soluciones exactas.

Puede usar el general formula from Wikipedia para calcular la solución de la ecuación cúbica.

+0

Gracias, eso es útil. De hecho, miré las soluciones para t y son bastante feas. Ciertamente más feo que cualquier cosa que quisiera calcular en gran cantidad. He agregado que una aproximación (adecuada para dibujar la curva como una función f (x)) es suficiente. – vercellop

+0

@vercellop, publiqué un enlace que le da una fórmula para resolver una ecuación cúbica. – MvG