Informática geek, matemáticas, pensamiento crítico y alguna otra cosa de vez en cuando.

2009-12-07

Aproximando el círculo

Las curvas de Bézier son una construcción geométrica muy útil usada en multitud de ámbitos, especialmente en los relacionados con el dibujo. Fueron desarrolladas por el físico y matemático francés Paul de Faget de Casteljau mientras trabajaba para Citroën, y popularizadas y patentadas por el ingeniero francés Pierre Étienne Bézier durante su trabajo en Renault. Son segmentos de ciertas curvas paramétricas, cuyo parámetro se halla entre 0 y 1. Las más comunes son las cuadráticas (usadas sobre todo en fuentes TTF) y las cúbicas (usadas en casi todos los programas de dibujo vectorial y en lenguajes gráficos como el PostScript). Las cuadráticas requieren un punto extra, además del punto origen y el destino, y las cúbicas dos puntos extra. Tienen muchas propiedades atractivas para el dibujo; por ejemplo, que en los extremos son tangentes a las líneas que van desde los mismos hasta los puntos de control inmediatos, lo cual permite encadenarlas para formar curvas más largas sin aparentes ángulos, o que es sencillo subdividir un segmento dado en un punto arbitrario del mismo para obtener dos segmentos.

Existe una interpretación geométrica sencilla para la curva de Bézier de grado n. Phil Tregoning creó las siguientes imágenes casi autoexplicativas sobre la interpretación geométrica de las curvas de Bézier, en este caso la cuadrática y la cúbica:

Animación de una curva de Bézier de grado 2

Animación de una curva de Bézier de grado 3

(Fuente: Wikpedia).

Para la cuadrática, por ejemplo, primero se hace una interpolación lineal del segmento P0P1 entre 0 y 1 según el parámetro t, y luego se hace lo mismo con el segmento P1P2. Los dos puntos hallados determinan un tercer segmento, que al interpolarlo entre 0 y 1 según t, da un punto de la curva. La cúbica requiere seis interpolaciones lineales: los tres segmentos P0P1, P1P2 y P2P3, los dos segmentos intermedios obtenidos con las interpolaciones anteriores, y el segmento final.

Las ecuaciones paramétricas de la curva cuadrática y de la cúbica son relativamente sencillas:

B²(t) = P0 (1-t)² + 2 P1 t (1-t) + P2
B³(t) = P0 (1-t)³ + 3 P1 t (1-t)² + 3 P2 t² (1-t) + P3

Es posible convertir una curva cuadrática en cúbica. Para hacerlo, hemos de tomar puntos P1 y P2 estratégicamente; concretamente, si Q0, Q1 y Q2 son los puntos que definen la curva cuadrática, hay que escoger P1 de forma que esté a 2/3 del camino entre Q0 y Q1, y P2 de forma que esté a 2/3 del camino entre Q2 y Q1, y, por supuesto, P0 = Q0 y P3 = Q2. La curva cúbica resultante coincide en todos sus puntos con la cuadrática.

Como es de esperar, lo contrario no es posible en general: no se puede obtener una curva cuadrática que coincida con una cúbica. Lo que sí se puede hacer es aproximarla, usando más de un segmento de curva cuadrática.

Y es que las curvas de Bézier son en realidad muy útiles para aproximar figuras. Un caso particular donde se usan curvas de Bézier para aproximar una figura es el de los círculos. Con la cantidad suficiente de segmentos de curva de Bézier cúbica, es posible hallar una aproximación más que decente a una circunferencia.

Tres segmentos son definitivamente insuficientes; el resultado es demasiado deforme. Sin embargo, con cuatro segmentos basta para obtener una excelente aproximación; tan buena, de hecho, que muchos programas de dibujo vectoriales implementan sus círculos internamente mediante curvas de Bézier, en lugar de usar genuinos círculos. Entre los que lo hacen están Inkscape, Skencil (antes Sketch) y Sodipodi (del que salió Inkscape), tres conocidos programas libres de dibujo vectorial.

Si aplicamos una transformación afín a los puntos de control (P0...Pn) de una curva de Bézier, el resultado que obtenemos es equivalente a transformar cada punto de la curva. Esta deseable propiedad nos permite usarlas para obtener la aproximación de una elipse en lugar de la de una circunferencia.

Para obtener la aproximación de un cuarto de circunferencia, hay que colocar los cuatro puntos de la forma que sigue. Supondremos que se trata de aproximar un círculo de radio unidad centrado en el origen; los demás se pueden obtener fácilmente escalando y desplazando puntos.

El primer punto, P0, hay que situarlo en (0, 1); el segundo punto, P1, en (k, 1) para cierto valor de k; el tercero, P2, en (1, k) y el cuarto, P3, en (1, 0). Con esto se aproxima un cuarto de circunferencia. Los demás segmentos se obtienen fácilmente por simetría y traslación.

¿Qué valor de k es apropiado? Hay quien sugiere usar k=4/3 (2½-1) ~= 0,552284749...; este valor está calculado para que cuando t = 1/2, el punto de la curva resultante esté a distancia 1 del centro, de modo que coincida con el que se le supone a una circunferencia.

Sin embargo, ese valor tiene sus desventajas: en casi todos los puntos, el círculo aproximado resultante es ligeramente más grande que el real, lo que determina que su área sea también más grande. En concreto, el área excede la teórica del círculo en aproximadamente un 0,028%. No es mucha la diferencia, pero si se es un perfeccionista como algunos de nosotros, molesta. ;)

El área de nuestro segmento de Bézier (véase por ejemplo Paul's Online Math Notes - Area with Parametric Equations sobre cómo obtenerla) es A = 1/2 + 3/5 k - 3/20 k². Si la igualamos a π/4 y resolvemos k, obtendremos el valor de k que hace que el área coincida con la del círculo. El valor resulta ser k = 2 - (22/3 - 5/3 π)½ ~= 0,551778477... (la otra solución da k > 1, que no nos interesa).

Este último valor de k da una curva que cruza varias veces el círculo, por lo que la distancia es menor dando al mismo tiempo una distancia ligeramente más pequeña, y en general es una aproximación mejor.

No es que se vaya a notar mucho la diferencia, todo sea dicho. Por ejemplo, el Inkscape usa k = 0,552 y no me había percatado de ello hasta que he mirado el código para escribir este texto. Pero, vaya, al menos quien use el valor de k sugerido aquí podrá tener la conciencia tranquila de que sus círculos son la mejor aproximación posible a un círculo real.

Actualización a 11 de diciembre

Ese valor de k que iguala las áreas tiene un pequeño problema. Aunque el área sea correcta, la distancia a una circunferencia real es casi la misma que con el valor de 4/3(2½-1), sólo ligeramente menor. En particular, con el valor que iguala áreas es de 0,0002684... mientras que con el que iguala el punto medio es de 0,0002753...

El hecho de que cruce la circunferencia, por tanto, no constituye garantía por sí mismo de que la distancia sea menor, aunque esta vez haya habido suerte y haya sido así. He corregido esa parte de la entrada.

Y es posible reducir aún más esa distancia. Esta gráfica representa la distancia entre cada punto de la curva y la circunferencia de radio unidad, con t en el eje de abscisas, para tres valores de k (hemos ampliado la escala del eje de ordenadas para verla mejor):

Gráfica de la distancia de cada punto de una curva de Bézier que aproxima una circunferencia según un valor de tensión k, y la circunferencia misma, para tres valores de k

El del centro es el que está usando Inkscape. Con k = 0,552 la distancia máxima resulta de sólo 0,000212..., que está más cerca de la circunferencia ideal. El valor de k que minimiza la distancia se obtiene de una ecuación polinómica de 6º grado que no voy a reproducir por ser bastante larga, que resulta en un valor de k ~= 0,55191502449...; la distancia máxima a la circunferencia ideal que se obtiene con dicho valor es 0,000196076...

Así que sólo nos queda decidir qué objetivo perseguimos. Si se trata de igualar el área, el valor de k que lo consigue es el de 0,551778...; si se trata de minimizar la distancia a la circunferencia verdadera, el valor es en cambio el de 0,551915... Elija veneno.

9 comments:

Julio said...

Cuando comparamos una serie de datos experimentales a una fórmula teórica dada, para medir la "distancia" o "diferencia" o "cómo de bien se ajusta", lo que se mide es el sumatorio de la diferencia al cuadrado entre el punto experimental (xi)y el punto teórico (xj) (Χ^2)=Sum(xi-xj)^2, siendo que cuanto menor es el valor, mejor es el ajuste. Idealmente, cuando "Chi cuadrado" (Χ^2) es 0, el ajuste es perfecto.

Se puede aplicar lo mismo a las curvas Bezier respecto del círculo, siendo la curva los puntos "experimentales" y la circunferencia los datos teóricos. Si en la última gráfica elevas al cuadrado cada una de las curvas, y las integras entre 0 y 1, deberías obtener "como de bien" se ajusta cada curva a un círculo, cual es la más parecida, y así a ojo, posiblemente será la verde (k=0.522) la que mejor ajuste dé (i.e.,Χ^2 mínimo, la más parecida a una circunferencia).

También se puede hacer una rutina que calcule k para que el valor de esa integral sea el mínimo posible.Esto es básicamente lo que se hace en un ajuste de datos con parámetros variables: calcular su valor tal que Χ^2 sea mínimo.

Julio said...

sumatorio de la diferencia al cuadrado entre el punto experimental (xi) y el punto teórico (xj) (Χ^2)=Sum(xi-xj)^2

Para que no haya dudas:

Si tienes una colección de puntos (x0, x1, ...xi...xN), y quieres compararlos con una función f(x), se realiza un sumatorio en el índice i, desde 0 hasta N:

Χ^2=Σ[(xi-f(xi))^2 ]

Si la colección de puntos xi son una función g(x), el sumatorio pasa a ser una integral, y
Χ^2=\int[ (g(x)-f(x))^2 dx ]

Julio said...

Hechos unos calculines un tanto a lo bruto (calular la integral de la diferencia al cuadrado, para varios valores de k, representar los valores obtenidos en función de k, y ajustar los datos a un parábola), me sale que el valor de k tal que hace mínima la diferencia punto a punto entre circunferencia y "círculo bezier", sería de k=0.55198±0.00013

El valor de 0.552 que usa Inkscape sale de redondear ese valor a 3 cifras significativas.

pgimeno said...

Gracias por las puntualizaciones. Aquí en realidad se está evaluando la distancia visual, donde la diferencia es la que el ojo ve. Si hubiera cogido el Χ², el resultado podría tener puntualmente una distancia al círculo real mayor en valor absoluto, lo cual no interesa.

Además, ya he tenido bastantes problemas con la longitud de las fórmulas al desarrollar. No quiero imaginarme el monstruo que saldría de la integral que calcula el Χ². ;)

Copio aquí la ecuación de 6º grado mencionada en el texto, para que veas de qué te hablo. Como estos comentarios tienen problemas para escribir ciertas notaciones matemáticas, llamemos Q = raíz cuadrada de 2:

135 k^6 + (3888 Q + 1728) k^5 - (5184 Q + 6408) k^4 + (17824 - 3456 Q) k^3 + (9216 Q - 21648) k^2 + (11136 - 5376 Q) k + 1024 Q - 2048 = 0

Está claro que no hay más remedio que resolverla numéricamente, pues no existe una expresión algebraica para ella por ser de grado mayor que 4. Como fan de los números exactos, me llevé un chasco al encontrármelo.

Tal vez me anime y calcule numéricamente el Χ², por curiosidad.

pgimeno said...

Oops, me has pillado escribiendo. Bueno, se aplica la misma idea que antes. El valor que yo saqué (0,551915...) está dentro del intervalo de error que has dado. Es de esperar que la diferencia, si la hay, sea mínima.

pgimeno said...

Vaya, el Mathematica me ha insultado cuando le he pedido que me calcule la integral. Creo que me quedaré sin saber el valor.

Davidmh said...

Haciendo trabajar a Mathematica, los primeros mil decimales de la solución a tu expresión de sexto grado es:

0.5519150244935105707435627227925666423361803947243088973369805374675870988527781759268533834535800161430081525746309514854740346650879994193884891094481219849513671372812801491120034776072373329231447725994499480374338851523262875232516550220603914179600716265038260349282257748102759120140260808065654993144968506620011721330445313981828563610721437535099100964201063517577499344681696282124419126517224821466926397761987320744304356688489894189913493561018548871041745518270211426607143303360101356685129080457736657755345531553741998536069262203096309897862368245815267027765519795442085419375326787386311207759605907689130352982346609371543825687746862963141484415183332522285903583287220627990105723421548662167080719213835517167198303808371003873251245954590464222175419105897703476407312951264484855707267860439625569280454271790828050422493415885085166043333648921425207338563636666417501181635485109047509900333377504223115510244596789678846825609452635500917752125288192674149867075558048525

Dentro del intervalo indicado por Julio.

Este mismo número ha sido obtenido por dos métodos diferentes, así que es numéricamente robusta.

pgimeno said...

Pues ahí la tienen quienes quieran una solución más precisa ;)

No sé si hay herramientas libres en Linux que permitan ese tipo de cálculos. Para CAS (álgebra asistida por ordenador) he usado el Yacas, pero creo que no tiene métodos de aproximación numérica. Algún día me leeré las instrucciones O:)

Republico aquí el número de David, con espacios intercalados, para que se vea completo:

0.551915 02449351 05707435 62722792 56664233 61803947 24308897 33698053 74675870 98852778 17592685 33834535 80016143 00815257 46309514 85474034 66508799 94193884 89109448 12198495 13671372 81280149 11200347 76072373 32923144 77259944 99480374 33885152 32628752 32516550 22060391 41796007 16265038 26034928 22577481 02759120 14026080 80656549 93144968 50662001 17213304 45313981 82856361 07214375 35099100 96420106 35175774 99344681 69628212 44191265 17224821 46692639 77619873 20744304 35668848 98941899 13493561 01854887 10417455 18270211 42660714 33033601 01356685 12908045 77366577 55345531 55374199 85360692 62203096 30989786 23682458 15267027 76551979 54420854 19375326 78738631 12077596 05907689 13035298 23466093 71543825 68774686 29631414 84415183 33252228 59035832 87220627 99010572 34215486 62167080 71921383 55171671 98303808 37100387 32512459 54590464 22217541 91058977 03476407 31295126 44848557 07267860 43962556 92804542 71790828 05042249 34158850 85166043 33364892 14252073 38563636 66641750 11816354 85109047 50990033 33775042 23115510 24459678 96788468 25609452 63550091 77521252 88192674 14986707 55580485 25

Davidmh said...

En la página de comentarios no se ve entero, pero en la de la entrada sí.