Solución al problema de la cebra

Vamos con la solución al puzle de la cebra.

Recordemos las pistas:

1. 1=B5
2. 3=E3
3. A1=D2
4. A2=B1
5. A5=E1
6. B2=E4
7. B3=D1
8. B4=C5
9. C4=D3
10. D4=E5
11. A4|B5
12. C1|D5
13. C3|D2
14. A3|A5
15. A3<A5

Ponemos en un casillero los símbolos, de tal forma que en cada casilla estén todos los símbolos de una fila. Para esto se puede emplear OOCalc, que es lo que he hecho.

	1	2	3	4	5
A	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5
B	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5	E1E2E3E4E5

Aplicamos las pistas 1, 2 y 11 para hallar la posición de B5, E3 y A4.

	1	2	3	4	5
A	A1A2A3A4A5	A4	A1A2A3A4A5	A1A2A3A4A5	A1A2A3A4A5
B	B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5	B1B2B3B4B5
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E3E4E5	E1E2E3E4E5	E3	E1E2E3E4E5	E1E2E3E4E5

Cada vez que consigamos averiguar el símbolo de una casilla, lo tachamos (borramos) de todas las demás casillas de esa fila:

	1	2	3	4	5
A	A1A2A3A5	A4	A1A2A3A5	A1A2A3A5	A1A2A3A5
B	B5	B1B2B3B4	B1B2B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E4E5	E1E2E4E5	E3	E1E2E4E5	E1E2E4E5

Ahora vamos recorriendo las pistas repetidamente. Para cada igualdad, hemos de comprobar si en las columnas donde aparece cada uno de los dos miembros también está el otro; si no es así, debemos tachar el extra. Por ejemplo, aplicando la pista 3 (A1=D2), puesto que en la 2ª columna no hay A1, hemos de quitar D2 de la misma:

	1	2	3	4	5
A	A1A2A3A5	A4	A1A2A3A5	A1A2A3A5	A1A2A3A5
B	B5	B1B2B3B4	B1B2B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D1D2D3D4D5	D1D3D4D5	D1D2D3D4D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E4E5	E1E2E4E5	E3	E1E2E4E5	E1E2E4E5

Repetimos con las pistas 4, 5, 6, 7, 8 y 10:

	1	2	3	4	5
A	A1A3A5	A4	A1A2A3	A1A2A3A5	A1A2A3A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C3C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2D3D4D5	D1D3D4D5	D1D2D3D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Al examinar la pista 13, observamos que en la columna 2 no hay D2, por lo tanto en la columna 1 no puede haber C3. Al aplicar la pista 14, podemos tachar A3 y A5 de la columna 1. Como se queda solo A1 en la primera fila, lo tachamos de las demás celdas de esa fila (a partir de ahora lo haremos sin avisar). De acuerdo con la pista 15, A3 no puede estar a la derecha del todo, así que lo tachamos también. Después de todos esos cambios, queda esto:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2D3D4D5	D1D3D4D5	D1D2D3D5	D1D2D3D4D5	D1D2D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Cuando al comprobar una de las igualdades, uno de los miembros está solo, el otro debe estarlo también. Aplicando ese principio a la pista 3 en este punto, hay que dejar solo D2 en la columna 1:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2	D1D3D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E1E2E5	E2E4E5	E3	E1E2E4E5	E1E2E4E5

Aplicamos las pistas 5 y 10, quitando E1 y E5, respectivamente, de la columna 1. Ya sabemos quién bebe E2=agua:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3B4	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2C4	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5	C1C2C3C4C5
D	D2	D1D3D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E2	E4E5	E3	E1E4E5	E1E4E5

Es B5, el noruego. Aplicamos las pistas 13, 8, 9 y ya no podemos seguir por este método:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2B3	B1B3B4	B1B2B3B4	B1B2B3B4
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2C4C5
D	D2	D1D4D5	D1D3D5	D1D3D4D5	D1D3D4D5
E	E2	E4E5	E3	E1E4E5	E1E4E5

Vamos a hacer un ensayo para falsar una hipótesis. Supongamos que en la columna 2 va E5 y no E4. Entonces, por la pista 10, tiene que ir D4 ahí. Por la pista 7, no puede ir B3 en esa columna, luego tiene que ser B2; pero ahora esto se contradice con la pista 6, que dice que donde va B2 tiene que ir E4. La conclusión es que en la columna 2 no puede ir E5. Lo tachamos y continuamos, aplicando las pistas 6, 10 y 7:

	1	2	3	4	5
A	A1	A4	A2A3	A2A3A5	A2A5
B	B5	B2	B1B3B4	B1B3B4	B1B3B4
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2C4C5
D	D2	D5	D1D3	D1D3D4	D1D3D4
E	E2	E4	E3	E1E5	E1E5

Nuevo punto muerto. Este es más complicado. Vamos a ensayar primero poniendo E1 en la columna 4 y viendo si nos conduce a una contradicción. Aplicamos las pistas 5, 10, 9, 15, 4, 8 y llegamos a este resultado provisional:

	1	2	3	4	5
A	A1	A4	A3	A5	A2
B	B5	B2	B3B4	B3B4	B1
C	C1C2	C3	C1C2C4C5	C1C2C4C5	C1C2
D	D2	D5	D1D3	D1D3	D4
E	E2	E4	E3	E1	E5

Ahora, si ponemos B3 en la columna 3, por la pista 7 tiene que ir D1 en la misma columna, luego en la columna 4 tiene que ir D3, y por la pista 9 va C4 en la misma. Pero esto se contradice con la pista 8, ya que en la columna 4 sólo puede ir B4. Y si ponemos B3 en la columna 4 en vez de la 3, tenemos exactamente el mismo problema. Pongamos donde pongamos B3, llegamos a una contradicción. La única conclusión posible es que E1 no puede ir en la columna 4.

Antes de seguir, una nota. En este punto se puede recurrir a una técnica del Sudoku que consiste en lo siguiente. Las columnas 1 y 5 tienen ambas C1 y C2, aunque no sabemos en qué orden. Esto quiere decir que o la 1 tiene C1 y la 5 C2, o viceversa, no hay otra posibilidad. En cualquiera de los dos casos, podemos tachar C1 y C2 de las columnas 3 y 4. Después de hacerlo, podemos recurrir a la pista 12 para asignar C1 a la columna 1, con lo que en la columna 5 iría C2. Esta es la solución parcial errónea a la que aludía al plantear el problema: C2 está en la columna correcta, como veremos, pero B1 no es la respuesta.

Volvemos al punto muerto anterior, ponemos E5 en la columna 4 y continuamos. Aplicamos las pistas 10, 5, 14, 4, 7, 9, 8, 12 y obtenemos la solución:

	1	2	3	4	5
A	A1	A4	A2	A3	A5
B	B5	B2	B1	B4	B3
C	C1	C3	C4	C5	C2
D	D2	D5	D3	D4	D1
E	E2	E4	E3	E5	E1

O sea, el dueño de C2 (la cebra) es B3 (el japonés).

¿Quién es el dueño de la cebra?

Cuando era niño, vi en una revista un pasatiempo que me resultó muy curioso. Lo copié y lo repartí a mis compañeros y hubo cierto revuelo con el mismo. Se ha divulgado en otras formas, pero aún permanecen en mi memoria las frases del planteamiento y la solución tal y como figuraban en la revista.

Decía así (disculpas por la propaganda de tabacos, que sospecho que estaba detrás de esa publicación, pero he preferido dejar el texto original tal y como lo conocí):

1. Hay cinco casas de distinto color con individuos de diferentes nacionalidades. También hay distintos animales, cigarrillos y bebidas en cada una de ellas.
2. El inglés vive en la casa roja.
3. El español es el propietario del perro.
4. En la casa verde se bebe café.
5. El ucraniano bebe té.
6. La casa verde está contigua y a la derecha (la derecha del lector) de la casa de marfil.
7. El fumador de Winston tiene caracoles.
8. En la casa amarilla se fuma Camel.
9. En la casa del centro se bebe leche.
10. El noruego vive en la primera casa de la izquierda.
11. El hombre que fuma Chesterfield vive en la casa contigua a la del dueño del zorro.
12. En la casa contigua a aquella donde se encuentra el caballo se fuma Camel.
13. El fumador de Lucky Strike bebe naranjada.
14. El japonés fuma Philip Morris.
15. El noruego vive al lado de la casa azul.

Las preguntas eran: ¿quién bebe agua? y ¿quién es el dueño de la cebra?

La respuesta a la primera pregunta es relativamente fácil, pues surge al poco tiempo de ir aplicando pistas. La segunda requiere llegar hasta el final, lo cual requiere bastante más esfuerzo.

Se puede abstraer este problema de la siguiente manera: sea un casillero de 5 filas y 5 columnas, en el que se deben colocar los símbolos A1, A2, A3, A4, A5, B1 a B5, C1 a C5, D1 a D5 y E1 a E5, cada uno en una casilla. Las letras indican la fila en la que colocarlos, pero los dígitos NO indican la columna; en este caso he escogido una permutación al azar de los números del 1 al 5 para cada fila. Para saber en qué columna colocar cada uno, necesitaremos las pistas. Usaremos la siguiente notación:

• n=símbolo indica que en la columna n ha de ir el símbolo dado. Por ejemplo, 1=A4 indica que el símbolo A4 se debe colocar en la fila A, columna 1.
• símbolo1=símbolo2 indica que ambos están en la misma columna.
• símbolo1|símbolo2 indica que están en columnas adyacentes.
• símbolo1<símbolo2 indica que símbolo1 está a la izquierda de símbolo2 (no necesariamente adyacentes).

Las pistas equivalentes para este problema (no en el orden original) son:

1. 1=B5
2. 3=E3
3. A1=D2
4. A2=B1
5. A5=E1
6. B2=E4
7. B3=D1
8. B4=C5
9. C4=D3
10. D4=E5
11. A4|B5
12. C1|D5
13. C3|D2
14. A3|A5
15. A3<A5

Y las preguntas son: ¿qué simbolo hay en la fila B en la misma columna donde está E2? ¿Qué símbolo hay en la fila B en la misma columna donde está C2? Es decir, hallar x e y tales que Bx=E2 y By=C2.

Al principio iba a preguntar en qué columna van E2 y C2, pero después me lo he pensado, dado que hay una solución parcial errónea que tiene C2 en la columna correcta, pero no tiene el símbolo bueno en la fila B de dicha columna. Aquí se busca la solución correcta.

Nótese que las dos últimas pistas juntas equivalen a la Nº. 6 del problema original, pero he querido hacerlo más general por si revisitamos este tipo de acertijos en el futuro.

La equivalencia con el problema anterior es: A1=Amarilla, A2=Roja, A3=Marfil, A4=Azul, A5=Verde; B1=Inglés, B2=Ucraniano, B3=Japonés, B4=Español, B5=Noruego; C1=Zorro, C2=Cebra, C3=Caballo, C4=Caracoles, C5=Perro; D1=Philip Morris, D2=Camel, D3=Winston, D4=Lucky Strike, D5=Chesterfield; E1=Café, E2=Agua, E3=Leche, E4=Té, E5=Naranjada.

No intente hacer esto en su oficina

SignPost es otro nuevo juego en la colección de puzles de Simon Tatham. Partiendo de la casilla 1, hay que avanzar un número indeterminado de casillas en cada paso en la dirección de la flecha, hasta acabar en la que tiene una estrella tras haber recorrido el resto del tablero visitando cada casilla una sola vez. A veces se nos indica en qué paso hay que tocar cierta casilla. Durante la resolución, lo normal es que vayamos conectando partes separadas hasta que tengamos todo conectado.

Como de costumbre, genera problemas con solución única.

No me ha enganchado, pero me ha entretenido, que también es importante.

Paintfuck

Ya hablamos en el artículo Lenguajes esotéricos sobre Brainfuck, un lenguaje de ocho instrucciones sumamente popular. Tanto, que existen multitud de variantes de dicho lenguaje. He aquí unos cuantos:

• En COW se representan la mayoría de instrucciones mediante cambios en las mayúsculas de la palabra «Moo». Es una variante de Brainfuck con cinco instrucciones nuevas.

• FukYorBrane es un lenguaje diseñado para que dos programas en Brainfuck compitan entre sí.

• Brainfork añade una instrucción para convertir el Brainfuck en multitarea.

• Boolfuck y Smallfuck son versiones de Brainfuck que operan sobre bits en vez de palabras.

• Dimensifuck utiliza un casillero n-dimensional en vez de bidimensional.

• Quantum brainfuck opera sobre qubits en vez de sobre enteros. Está basado en la teoría de computación cuántica.

• 2L es una variante bidimensional que usa dos símbolos (y el espacio en blanco).

• Hay muchas más variantes; véase Category: Brainfuck derivatives en la wiki de lenguajes esotéricos.

En particular, el Smallfuck opera sobre un casillero donde cada celda es de un bit. Tiene cinco instrucciones: elimina la entrada y la salida y, como no le hace falta incremento y decremento porque las dos operaciones hacen lo mismo, las sustituye por el comando *, que invierte el bit en la celda actual. Es relativamente sencillo convertir un programa en Brainfuck a Smallfuck (salvo por la entrada/salida), sustituyendo el incremento y decremento por subrutinas que manipulan los bits en bloques de, por ejemplo, 8 bits.

Y del Smallfuck surge el Paintfuck. Es una variante creada por Wouter Visser que utiliza un casillero bidimensional en vez de lineal, lo cual en principio no parece nuevo. Lo que lo hace original es que está pensado para que el casillero sea representado en la pantalla, viendo en tiempo real y de forma animada cómo el programa actúa sobre el mismo.

Las instrucciones < y > son sustituidas por n, s, e, w para los cuatro puntos cardinales respectivos. Las demás instrucciones son idénticas a las de Smallfuck, así que consta de siete instrucciones en total. Todo carácter que no sea una instrucción válida (incluyendo las versiones en mayúsculas de los comandos) se considera un comentario y por tanto no interviene en el programa, pero tampoco causa error. Por ello, es común que los comentarios intercalados se escriban en mayúsculas, para evitar escribir accidentalmente alguna de las letras n, s, e o w que influirían en el comportamiento del programa. El espacio de datos está inicialmente vacío (todo ceros).

Aunque es un lenguaje Turing-completo cuando se aplica a casilleros infinitos en al menos una dimensión, lo cierto es que los casilleros toroidales finitos suelen ser más interesantes. Así, este sencillo programa rellena todo el casillero de unos, aunque no para nunca:

*[e[s]*]

¿Qué hace este programa? Primero, cambia la casilla inicial de 0 a 1. Esto le permite entrar en el bucle. Ya dentro del bucle, se mueve hacia el este y, si da con una casilla que no es cero, se mueve hacia el sur hasta que encuentre la primera que es cero. Si se parte de un casillero vacío, eso debería ocurrir en la línea siguiente, salvo que llegue al punto inicial, en cuyo caso se quedará enganchado indefinidamente en ese bucle. Tanto si va al sur como si no, pone a 1 la casilla actual (era 0 seguro, o de lo contrario no habría salido del bucle anterior) y repite.

Programar en Paintfuck tiene el aliciente de que vemos cómo se desarrolla nuestro programa. Además, trabajar con bits es más simple en general. Entre los programas actualmente escritos en Paintfuck hay, por ejemplo, uno para hacer funcionar el autómata del Juego de la Vida de Conway del que hablamos en la entrada sobre autómatas celulares; también hay otro autómata finito llamado la hormiga de Langton y un contador decimal.

El contador decimal, escrito por un servidor de ustedes, representa cada número dentro de un bloque de 3×5, y se basa en una sugerencia dada en el canal de IRC #esoteric sobre realizar tal contador analizando cada dígito para ver de cuál se trata e incrementarlo. Requirió bastante esfuerzo diseñar la fuente, hallar los píxels distintivos únicos de cada número y analizar los cambios que convertían cada dígito en el siguiente. El programa final es este:

PAINTFUCK PROGRAM BY PEDRO GIMENO 2008-12-01.

swwww*es*ww*s*ee*s*ww*sseeee*wwnw*ww
*[*
  nnee[*ww*s*nee]ww[*ee*ww]s
  *[*ne[*w*n*se]w[*e*w]n
    [*ee*e*s*w*w*s*e*e*s*ww*wnn*n]
    s*[*nnee*s*w*es*s*s*e*ww*wnn]*s]
  n*[*
    nee[*ww*s*nee]ww[*ee*ww]s[*nne*ees*w*w*ess*w*w*n]
    s*[*
      nnnee[*ww*s*nee]ww[*ee*ww]s*[*nee*e*s*s*ss*w*w*wn*nn]
      ss*[*
        seee[*www*n*seee]www[*eee*www]n[*e*ee*s*www*n]
        s*[*
          ee[*ww*n*see]ww[*ee*ww]n*[*nnne*ee*sww*sss*e*en*wwws*n]
          s*[*
            nnne[*w*s*ne]w[*e*w]s*[*nnee*sw*s*ee*ss*w*w*wn*n]
            s*[*
              nnne[*w*s*ne]w[*e*w]s[*ne*sss*s*wnn*n]
              s*[*
                nneee[*www*s*neee]www[*eee*www]s[*ne*ees*ww*s*see*sw*w*wnn*n]
                s*[*
                  se[*w*n*se]w[*e*w]n[*eee*ssww*n*w*n]
                  s*[*
                    ne*e*ws*s*wwwwws*nn]n]]s]s]]n]]n]
  sss*[
    [*e*]*wwwww]n
*]

Bueno, en realidad esa es la versión no comentada. La versión comentada es bastante más larga [1].

Pueden verse este y otros programas en acción gracias al intérprete de Paintfuck en JavaScript, que también puede servir para quien quiera escribir sus propios programas en Paintfuck.

Referencias

[1] http://www.formauri.es/personal/pgimeno/temp/esoteric/paintfuck/decimal-counter.pfk

Dibujando curvas de Bézier cúbicas

He actualizado el tutorial de GIMP sobre la aplicación de efectos de forma radial para incorporarle una animación que cuando publiqué la entrada no había puesto a punto, aunque pensaba que sería una buena adición para explicar cómo actúa el filtro Coord. polares de GIMP. La animación en cuestión es esta:

Está hecha con un programa que escribí en mi lenguaje favorito para hacer pequeñas utilidades cuya velocidad no es crucial, es decir, en PHP. Cuando me puse a pensarlo, me di cuenta de que para hacer la animación que tenía en mente me iban a ser muy útiles las curvas de Bézier cúbicas. Sin embargo, al mirar el listado de funciones de la librería GD, descubrí que no contaba con funciones de dibujado de estas curvas.

Tenía, pues, unas pocas opciones. Una era buscar algún otro módulo PHP capaz de dibujarlas. Resulta que el módulo de ImageMagick lo hacía. Pero usar GD tenía sus ventajas para mí, porque va muy al grano y se puede trabajar con imágenes indexadas (es decir, con paleta), y el ImagickDraw no estaba muy bien documentado. Otra era buscar si alguien más había implementado lo mismo. Encontré unas pocas implementaciones, sí, una de ellas de PEAR que parecía que precisaba mucho aprendizaje para usarla, y otra que resultó tener una calidad muy pobre. La tercera opción era hacerme yo una función para dibujarlas. Finalmente me decanté por esa, aprovechando la ocasión para acometer un reto que tenía pendiente desde hace años. Con algún sistema simple me habría bastado, pero quería resolver el problema de forma definitiva para tener una función que dibujara curvas aplicable a cualquier campo, y que me sirviera de referencia en caso de necesitar reescribirla en otro lenguaje.

Métodos iterativos

Así que estuve investigando los métodos que pude encontrar, para hacerme una idea de por dónde atacar el problema. Sabía de antemano que los métodos recursivos daban mejor resultado que el método iterativo simple.

El método iterativo simple

La forma más sencilla de dibujar curvas de Bézier es utilizar la fórmula directamente, escogiendo un incremento de t adecuado que nos permita recorrer el intervalo [0, 1] de forma uniforme, trazando líneas rectas entre cada punto y el anterior. Además, podemos calcular sólo los coeficientes hasta la mitad usando la igualdad B(P₀, P₁, P₂, P₃, t) = B(P₃, P₂, P₁, P₀, 1 - t). Ya conocía este sistema. El problema principal es que no existe un incremento de t adecuado. Si dibujamos demasiados segmentos, podemos encontrarnos con que la línea se engrosa en algunas zonas de forma muy antiestética. Si no dibujamos suficientes, quedarán a la vista los trazos angulosos de los segmentos rectos con que se dibuja la curva. Lo malo es que en ciertas curvas es fácil que se vean ambos defectos a la vez: trazos angulosos y líneas engrosadas. Así que hay que buscar alternativas.

El método iterativo variable

El problema del método iterativo simple radica en que la distancia entre puntos consecutivos (al aplicar un incremento de t constante) no es uniforme. Este problema se podría salvar recurriendo a la fórmula de la velocidad de la curva, que nos da un indicador de cuán grande será el desplazamiento para un t dado. Para una curva que va de P₀ a P₃ con puntos de control P₁ y P₂, la fórmula es:

V(t) = 3·(1 - t)²·(P₁ - P₀) + 6·t ·(1 - t)·(P₂ - P₁) + 3·t²·(P₃ - P₂)

No he probado este método. A primera vista, parece que tiene el problema de que, si los incrementos no son lo suficientemente pequeños, podrían verse los polígonos de nuevo, así que habría que hacerlos lo bastante pequeños. Hacerlos de un píxel puede presentar problemas cuando los trazos son diagonales. Quizá haciéndolos de 2^½ (1,414213...) píxels, que es la distancia entre dos píxels diagonales, o ligeramente superior para evitar problemas de redondeos, fuera suficiente. Tendría que experimentar. Otra pega es que no veo inmediatamente cómo trasladar velocidad a píxels.

Métodos recursivos

En general, los métodos recursivos se basan en subdividir la curva en múltiples segmentos, utilizando el algoritmo de De Casteljau: Sea B(P₀, P₁, P₂, P₃) una curva de Bézier definida por los puntos P₀, P₁, P₂, P₃. Esta curva se puede dividir de forma exacta en dos segmentos, B₀(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B₁(P₀₁₂₃, P₁₂₃, P₂₃, P₃). El punto P₀ y el punto P₃ coinciden con los de la curva original, ya que son los extremos del segmento curvo y lógicamente tienen que estar cada uno en una de las curva subdivididas. El punto de subdivisión, P₀₁₂₃, también forma parte de la curva, pues esa es precisamente la ventaja del método de De Casteljau.

P₀₁ es un punto situado en la recta entre P₀ y P₁, a distancia relativa t. Es decir, P₀₁ = (1 - t)·P₀ + t ·P₁. Análogamente obtenemos P₂₃ = (1 - t)·P₂ + t ·P₃. Para obtener los puntos que faltan es preciso calcular un punto extra, P₁₂ = (1 - t)·P₁ + t ·P₂. Ahora, P₀₁₂ = (1 - t)·P₀₁ + t ·P₁₂ y P₁₂₃ = (1 - t)·P₁₂ + t ·P₂₃. Por último, P₀₁₂₃=(1 - t)·P₀₁₂ + t ·P₁₂₃. La figura siguiente ilustra el proceso. Cuando t = ½, nos basta con calcular medias entre los puntos.

Método de subdivisión de una curva de Bézier cúbica en dos, en el punto t=0,3. La curva B(P₀, P₁, P₂, P₃) puede ser dividida en las dos curvas B(P₀, P₀₁, P₀₁₂, P₀₁₂₃) y B(P₀₁₂₃, P₁₂₃, P₂₃, P₃).

Los algoritmos recursivos realizan esta subdivisión, normalmente en el punto t=½, y continúan haciendo lo mismo recursivamente con cada uno de los subsegmentos obtenidos. Difieren en la elección del caso base de la recursión.

Método de la colinealidad

Las subdivisiones recursivas van aproximando cada vez más el segmento dividido a un segmento de recta. Si conseguimos determinar en qué momento es tan parecido a una recta que no es distinguible a simple vista, podremos trazar una recta en su lugar y obtener así una muy buena aproximación.

La curva es más plana cuanto más próximos estén los dos puntos de control a la recta que une los puntos origen y final, así que el cálculo de esa distancia es una buena forma de determinar si son casi colineales. Para evitar una raíz, se puede calcular el cuadrado de la distancia en lugar de la distancia misma. La fórmula del cuadrado de la distancia es:

d(P₁, P₀P₃)² = ((P_x3-P_x0)·(P_y1-P_y0) - (P_y3-P_y0)·(P_x1-P_x0))²/((P_x3-P_x0)² + (P_y3-P_y0)²)

y lo mismo cambiando P₁ por P₂.

Actualización 2011-03-23: Tengo pendiente examinar otra forma de evaluar el «grado de colinealidad», que se me ha ocurrido al releer esta entrada. La idea sería utilizar la ecuación de la recta que pasa por P₀ y P₃, rotándola 90° si el valor absoluto de la pendiente es > 1, para hallar el valor de y que se correspondería con el valor de x del punto a comprobar, hallando entonces la diferencia con la y de dicho punto. Esto podría ser más rápido que el cálculo de la distancia aquí nombrado y probablemente sería igualmente efectivo.

Que sean casi colineales no es condición suficiente para poder aproximar la curva como un segmento de P₀ a P₃. Hay otra condición adicional, y es que tanto P₁ como P₂ estén comprendidos entre P₀ y P₃. Si no se impone esta condición, tanto P₁ como P₂ pueden estar fuera del segmento P₀P₃ y el resultado teórico sería una curva que desde uno de los extremos va temporalmente en dirección contraria al otro extremo, y ese fragmento no sería dibujado. Por ejemplo, si consideramos la curva B((0,0), (-3,0), (10,0), (10,0)), los puntos P₁ y P₂ son colineales con P₀P₃ y, pese a ello, la curva se extiende un poco hacia el lado de abscisas negativas.

En casos como el indicado, la subdivisión podría requerir infinitos pasos para el subsegmento que contiene el pico. Para evitarlo, se puede dar un margen de error: si P₂ y P₃ están ambos dentro de un cuadrado rectángulo de tamaño (|P_x3-P_x0|+ε, |P_y3-P_y0|+&epsilon), se consideran buenos.

Este es el método que escogí finalmente. Los resultados son muy decentes y el algoritmo es aceptablemente rápido. Como parámetros, la distancia al cuadrado que puse para considerar los puntos colineales es 0,125 píxels y el ε que escogí es 0,25 (un cuarto de píxel).

Método de la longitud

La longitud de una curva de Bézier puede ser calculada numéricamente, no hay una fórmula explícita general para la misma. Además de mediante una integral que requiere métodos numéricos clásicos y complicados, hay una forma recursiva de aproximarla que, además, nos da un método para dibujarla.

Sea L₀ la longitud del segmento P₀P₃ y L₁ la suma de las longitudes de los segmentos restantes, concretamente L₁=|P₀P₁| + |P₁P₂| + |P₂P₃|. Entonces, la media de esos valores, (L₁ + L₀) / 2, da una aproximación a la longitud, y L₁ - L₀ da una medida del error. Dicho error decrece en relación 2^-4m donde m es el número de subdivisiones [1].

Se puede entonces dibujar el segmento de forma que si la longitud del subsegmento actual es lo bastante pequeña, se trace dicho subsegmento como recta.

No he probado este método. En realidad es muy similar al anterior, ya que cuando el error es pequeño, significa que los puntos están próximos a ser colineales, lo cual es casi lo mismo que el método anterior. En este no nos salvamos de calcular al menos cuatro raíces cuadradas, por lo cual lo deseché antes de probarlo.

Otros métodos

Descomposición en cuadráticas

En [2] se da una forma de descomponer una curva cúbica en cuatro segmentos de curva cuadrática. No me ha convencido el resultado, pero al menos he creído oportuno dejar una referencia para quien quiera averiguar más. Con este método, queda abierto el problema de cómo dibujar una curva cuadrática de forma eficiente.

Partición de la derivada por octantes

Para terminar, vamos a considerar un método que ha sido utilizado por METAFONT, el programa de diseño tipográfico de D. E. Knuth. Para leer la documentación del programa METAFONT decentemente, necesitaremos la utilidad Weave, capaz de extraer archivos escritos en TeX (el formato de proceso de texto de Knuth) a partir de archivos WEB (que contienen una mezcla del programa en Pascal y la documentación en TeX). El original está aquí: http://mirror.ctan.org/systems/knuth/dist/mf/mf.web. La explicación, junto con el código correspondiente, comienza en la §384.

La idea del método es similar a la de los círculos de Bresenham: se clasifica la derivada de la curva por octantes y se transforma cada uno de los octantes al primero, de manera que la pendiente (el incremento de y por cada incremento unitario de x) no sea superior a la unidad. Con este método se consigue que cada incremento de x vaya asociado a cero o un incremento de y, con lo cual la curva resultante tiene una fineza superior. El precio a pagar por tanto refinamiento es un programa que cuesta mucho entender, además de que cuesta bastantes cálculos. El beneficio es la curva más perfecta posible, igual que la línea de Bresenham es la recta más perfecta posible.

Referencias

[1] http://steve.hollasch.net/cgindex/curves/cbezarclen.html
[2] http://www.timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm