¿Cómo puedo encontrar una curva que pasa a través de una serie de puntos?

Question

Cuando alguien tiene los 4 puntos de control P0, P1, P2, P3 de 2D cúbica de Bézier, esa persona puede calcular una serie de cientos de puntos a lo largo de la curva que comienzan a partir de P0 en t=0 y final en P3 en t=1 (pero, en general, de los puntos nunca golpear a P1 o P2).

Si esa persona me da una serie de puntos distintos a lo largo de la curva (en orden, comenzando con X0=P0 y terminando con XN=P3), ¿cómo puedo recuperar el original de 4 puntos de control P0...P3 que se utilizó para calcular los distintos puntos?

Si yo sabía que uno de los puntos X1 estaba en t=1/4 y X2 fue en t=3/4, entonces yo podría calcular

P0 = X0
P1 = (1/9)*( -10*X0 + 24*X1 -  8*X2 +  3*X3 )
P2 = (1/9)*(   3*X0 -  8*X1 + 24*X2 - 10*X3 )
P3 = X3

Alternativamente, si yo sabía que uno de los puntos X1 estaba en t=1/3 y X2 fue en t=2/3, entonces yo podría encontrar una curva de Bézier cúbica que pasa a través de los 4 puntos utilizando Juan Burkardt del enfoque:

P0 = X0
P1 = (1/6)*( -5*X0 + 18*X1 - 9*X2 + 2*X3 )
P2 = (1/6)*(  2*X0 -  9*X1 +18*X2 - 5*X3 )
P3 = X3.

Pero aunque sé que t=0 para el primer punto, y t=1 para el último punto, No conozco los valores de t se utiliza para producir cualquiera de los otros puntos intermedios de la curva. Los 4 puntos (sin información) no es exclusiva de definir una curva de Bézier cúbica, como se puede ver arriba, si puedo usar el mismo 4 puntos X0...X3 y conéctelos a los dos diferentes enfoques de arriba, tengo 2 ligeramente diferentes de las curvas de Bézier (el estimado de P1 y P2 de los puntos de control son ligeramente diferentes), ambos de los cuales pasan a través de todos los 4 puntos dados.

Así que cuando no tengo los valores de t, necesito más de 4 puntos a lo largo de la curva de Bezier únicamente para determinar la original de 4 puntos de control.

¿Cómo puedo determinar la original de 4 puntos de control?

Decir que he tenido una serie de aproximadamente 100 puntos igualmente espaciados a lo largo de una curva que sé que vino originalmente de una curva de Bézier -- ¿hay alguna manera más fácil de determinar la original de 4 puntos de control, entonces?

(La motivación: Al imprimir algo en una RepRap, a menudo la pieza fue originalmente diseñado en algún programa de CAD con la superficie lisa splines que, cuando en rodajas, sería de esperar que para dar suaves curvas 2D que más o menos coincide con una curva de Bézier. Sin embargo, la exportación de ese modelo desde el paquete CAD siempre parece producir una facetada archivo STL compuesto en su totalidad de la plana triángulos, para la segmentación se produce en miles de pequeñas líneas rectas con los extremos que se tocan los que la curva de Bézier. Quiero tratar de convertir a los de la serie de pequeñas líneas rectas en una sola curva de Bézier cúbica. Sospecho que el Arduino se puede analizar una línea de texto ASCII que contiene los 4 puntos de control de una sola curva de Bézier cúbica mucho más rápido que se podría analizar un par de cientos de líneas de texto ASCII, cada uno que contiene los 2 extremos de una corta línea recta.)

Answer 1

Como usted dice, cuatro puntos (sin sus asociados "t" valores) no son suficientes para definir un plano de curva de Bézier cúbica.

De hecho, los 6 puntos son necesarios. Pero, por otro lado, el 6 puntos deben satisfacer ciertas condiciones, o de lo contrario la necesaria curva no existe. En su caso, usted sabe que la curva existe, porque fue utilizado para generar los puntos en el primer lugar.

La historia completa se da en este papel: J. Kozak, M. Krajnc, Geométrico interpolación por planar polinomio cúbico curvas, Comput. Ayudados Geom. Des., 24 (2007), pp 67-78. Usted puede obtener una copia de este documento en el sitio web de los autores.

Otro enfoque (en lugar de los inteligentes técnicas sugeridas en el papel) es el uso de la fuerza bruta métodos numéricos. Comience con 6 puntos de $X_1, \ldots, X_6$ y 6 los valores de parámetro de $t_1, \ldots, t_6$. Podemos suponer que $t_1 = 0$$t_6 = 1$, pero $t_2, t_3, t_4, t_5$ son desconocidos.Queremos encontrar los puntos de control $P_1, P_2, P_3, P_4$ para nuestra curva. Obviamente podemos establecer$P_1 = X_1$$P_4 = X_6$, pero $P_2$ $P_3$ son desconocidos. Podemos (numéricamente) encontrar los valores de $t_2, t_3, t_4, t_5$ $P_2$ $P_3$ que minimizar la cantidad

$$ \sum_{i=2}^{i=5}\Vert C(t_i) - X_i \Vert^2 $$

donde $C(t)$ es la curva de Bezier con los puntos de control $P_1, P_2, P_3, P_4$. Esto es bastante desagradable problema no lineal, pero un buen algoritmo numérico generalmente convergen a la solución deseada, dado un punto de partida decente.

Otro enfoque numérico: con la misma notación que hemos utilizado anteriormente, resolver las ecuaciones: $$ C(t_i) = X_i \quad (i = 2,3,4,5)$$ Puesto que el $X_i$ 2D puntos, hay 8 ecuaciones de aquí. Contamos con 8 incógnitas -- $t_2, t_3, t_4, t_5$ e las $x$ $y$ coordenadas de $P_2$$P_3$. Las ecuaciones no son lineales, pero un buen numérico raíz encontrar el paquete debe ser capaz de manejar.

Un enfoque mucho mejor es obtener las curvas de Bézier desde el programa de CAD. Si el diseño chicos no se dan las curvas, se debería cobrar más dinero por sus servicios, ya que ellas están haciendo la vida mucho más difícil. Su elección -- curvas o en efectivo :-)