El día de hoy (4 de diciembre de 2017) es mi cumpleaños número 19, y me di cuenta de que no había preguntado una pregunta aquí en más de un año. Así que este es uno sobre un viejo problema: la computación en la intersección de las dos curvas de Bézier.
En mi Kinross SVG biblioteca, una curva Bézier objeto contiene dos representaciones equivalentes de sus coordinar polinomios ($x(t),y(t)$): un punto de control de formulario (Bernstein) y un polinomio de la forma (base de poder). El punto de control de formulario es utilizado para la interfaz con el formato SVG; el polinomio formulario se utiliza para los cálculos explícitos, y será el formulario a continuación.
El estándar SVG incluye segmentos de recta (lineal Béziers), cuadrática Béziers y cúbica de Béziers, que tienen dos, tres y cuatro puntos de control, respectivamente. Intersección de dos curvas de Bézier es fácil si no son tanto cúbicos:
- Si una de las curvas es lineal o ha colineales puntos de control, la alineación de la curva con el $x$-eje y de la resolución de una ecuación cúbica hará el truco.
- Si una de las curvas es de segundo grado, la misma idea puede ser utilizada para: realizar una transformación afín que los mapas que la curva de la gráfica de $y=x^2$$0\le x\le 1$, luego de resolver un sextic ecuación derivada de la (transformado) otra curva.
Esta es la curva de implicitisation, y NumPy (la biblioteca externa Kinross usa) tiene (univariante) polinomio de objetos y de un buen polinomio raíz-finder para los de alto grado de los polinomios que se plantean, por lo que estos son más bien aburridos de los casos. La parte interesante es cúbico cúbico intersección, donde esta simple implicitisation ya no funciona. Varias técnicas están disponibles, pero muchos no son adecuados para mis propósitos:
- Bézier subdivisión/recorte, en mis ojos, es un poco elegante, enfoque que también puede ser razonablemente rápido en la refinación de soluciones. Me gusta que mis respuestas a ser tan exactos como sea posible, sin perjuicio de la necesaria precisión de los compromisos.
- Homotopy solucionadores de problemas son demasiado complejos, que implican una ecuación diferencial en cada paso, y tiene una desconcertante variedad de los distintos casos de manejar.
- Yo una vez considerada la optimización (minimización $(p_x(t)-q_x(u))+(p_y(t)-q_y(u))^2$, donde los polinomios se define a continuación), pero esto también fue visto como excesivamente complicado en comparación directa de problemas.
- Una resultante del cálculo es actualmente un poco demasiado exigente para NumPy, ya que implica polinomios de matrices (que es no sólo posible). Yo podría eludir estos problemas en el futuro trabajando en un nivel inferior, aunque.
- El groebner-base tiene su propia etiqueta de aquí, y ciertos lugares como esta pregunta y esta Scholarpedia artículo describe el algoritmo de Buchberger en una buena cantidad de detalles. Es más complicado que el resultado del algoritmo, sin embargo, y mis propias pruebas indican que los números involucrados volar incluso para polinomios con pequeños coeficientes.
- Esto deja a la racional univariante representación (RUR). Su etapa final implica univariante raíz de la investigación, que a su vez es un pedazo de la torta para NumPy, pero hasta ahora no he sido capaz de entender plenamente cómo se va a partir de la inicial de polinomios a las soluciones (más sobre esto más adelante).
Así que se me ocurrió con mi propio algoritmo basado en el multivariante método de Newton. Supongamos que las dos curvas que se intersecan son $(p_x(t),p_y(t))$$(q_x(u),q_y(u))$. Una intersección se produce cuando $$p_x(t)-q_x(u)=p_y(t)-q_y(u)=0\tag1$$ La iteración de Newton (de$t,u$$t',u'$) es así $$\begin{bmatrix}t'\\u'\end{bmatrix}=\begin{bmatrix}t\\u\end{bmatrix}+\begin{bmatrix}\Delta_t\\\Delta_u\end{bmatrix}$$ donde el último término se soluciona $$\begin{bmatrix}p'_x(t)&-q'_x(u)\\p'_y(t)&-q'_y(u)\end{bmatrix}\begin{bmatrix}\Delta_t\\\Delta_u\end{bmatrix}=\begin{bmatrix}q_x(u)-p_x(t)\\q_y(u)-p_y(t)\end{bmatrix}$$ Para obtener suficientes puntos de partida para la captura de todas las raíces, aprovecho para cada curva:
- sus extremos
- sus puntos de extremal de la curvatura de la
- sus puntos de inflexión
y, a continuación, realizar un producto Cartesiano de dos conjuntos obtenidos. Con un poco de confusión para tratar casos donde el sistema lineal en la iteración de Newton no tienen una solución única, mi algoritmo ha desempeñado muy bien en contra de los casos de prueba que he considerado. (No necesito informe tangencies o de otras raíces múltiples casos, ya que las imágenes vectoriales puedo manejar en la práctica se han "lo suficientemente bueno" en las curvas.)
En contraste, hay pocos artículos sobre RUR a su alrededor. Por lo tanto mi pregunta aquí es:
¿Qué son exactamente los detalles algorítmicos de problemas a través de la RUBLOS, pasando de $(1)$ a las soluciones? Una curva de Bézier específicos de optimizaciones que pueden existir.
Estoy en busca de una explicación que puede ser implementada desde el suelo hasta el uso de NumPy. El objetivo último que tengo en mente no es sólo para ver si RUR es mejor que mi Newton-basado en el algoritmo (en el tiempo o fiabilidad), sino también para comprender algunos de los conceptos fundamentales de la geometría algebraica.
Si lo desea, puede explicar en RUBLOS en el uso de este par de curvas de Bézier he probado mi algoritmo en contra de: $$p_x(t)=2+147t-342t^2+221t^3\qquad q_x(u)=1+87u-84u^2+11u^3\\ p_y(t)=17-90t+183t^2-104t^3\qquad q_y(u)=10+42u-165u^2+124u^3$$ $A$1+147t-342t^2+221t^3-87u+84u^2-11u^3=0\\ 7-90t+183t^2-104t^3-42u+165u^2-124u^3=0$$ En Kinross estos son representados como
p = bezier(2+17j, 51-13j, -14+18j, 28+6j)
q = bezier(1+10j, 30+24j, 31-17j, 15+11j)
Se cruzan en cinco puntos ($0\le t,u\le1$) cuyos correspondiente $(t,u)$ parámetros son $$(0.053611563083829826, 0.10086541719622877)\\ (0.15646174074706343, 0.94523150924142163)\\ (0.41077722343039424, 0.88035078651205612)\\ (0.86571544618164098, 0.97134323668380174)\\ (0.96472594025254754, 0.43951554821497935)$$
