Dibujar España con círculos: la serie de Fourier explicada
Hay vídeos que te hacen cerrar el portátil un rato y quedarte mirando la pared. Este es de los míos: Bernardo Quintero, fundador de VirusTotal, publicó el 12 de octubre un vídeo de 48 segundos en el que la península ibérica se dibuja sola. Sin imagen, sin vectores a mano. Solo esto:
x(t) = a₀ + Σ [aₖ cos(kt) + bₖ sin(kt)]
y(t) = c₀ + Σ [cₖ cos(kt) + dₖ sin(kt)]
Su explicación cabe en un tuit: cada término es un círculo que gira k vueltas por cada vuelta completa, y con 150 sale la costa. Con 150 círculos tienes España. Vale, sí, a mí también me cabrea no haberlo pensado antes.
Qué es cada término de esa fórmula
Una serie de Fourier dice que cualquier curva cerrada se puede escribir como suma de ondas simples: senos y cosenos de frecuencias enteras (1, 2, 3…). Hasta aquí, mates de carrera.
El truco para verlo es mirar x e y a la vez. Un par (cos(kt), sin(kt)) es un punto dando vueltas en círculo, k vueltas mientras t recorre una vuelta entera. Tienes un círculo con k=1, uno que gira el doble de rápido con k=2, otro el triple con k=3, y así. Cada uno con su tamaño y su ángulo de partida, que son los coeficientes (aₖ, bₖ, cₖ, dₖ).
Ahora los encadenas: el centro del segundo círculo va pegado al borde del primero, el del tercero al borde del segundo. El punto en la punta de la cadena es la suma de todos. Eso son los epiciclos, y es justo lo que explica 3Blue1Brown en su lección sobre la serie de Fourier, con números complejos en lugar de dos fórmulas separadas. Es lo mismo escrito más corto.
De un mapa a una lista de coeficientes
La parte que no se ve en el vídeo es cómo se pasa del dibujo a los números. Son cuatro pasos:
- Sacas el contorno del mapa como una lista de puntos (x, y) en orden, de un tirón y cerrando el bucle.
- Cada punto se trata como un número complejo: x + y·i.
- Aplicas la transformada discreta de Fourier (DFT) a esa lista. Te devuelve un coeficiente complejo por frecuencia: su módulo es el radio del círculo y su argumento, el ángulo de partida.
- Ordenas los círculos de mayor a menor radio y te quedas con los N primeros.
Con la DFT en JavaScript son diez líneas:
// puntos: [{x, y}, ...] con el contorno en orden
function dft(puntos) {
const N = puntos.length;
const coef = [];
for (let k = 0; k < N; k++) {
let re = 0, im = 0;
for (let n = 0; n < N; n++) {
const ang = (2 * Math.PI * k * n) / N;
re += puntos[n].x * Math.cos(ang) + puntos[n].y * Math.sin(ang);
im += puntos[n].y * Math.cos(ang) - puntos[n].x * Math.sin(ang);
}
coef.push({ k: k > N / 2 ? k - N : k, re: re / N, im: im / N });
}
// los más grandes primero
return coef.sort((a, b) => Math.hypot(b.re, b.im) - Math.hypot(a.re, a.im));
}
// punto del dibujo en el instante t (0 a 1), usando solo n círculos
function punto(coef, t, n) {
let x = 0, y = 0;
for (const c of coef.slice(0, n)) {
const ang = 2 * Math.PI * c.k * t;
x += c.re * Math.cos(ang) - c.im * Math.sin(ang);
y += c.re * Math.sin(ang) + c.im * Math.cos(ang);
}
return { x, y };
}
Recorre t de 0 a 1 en pasos pequeños, pinta cada punto en un <canvas> y tienes tu dibujo. Para animar los círculos, en vez de sumar de golpe, dibujas cada uno con su centro en el final del anterior. Si prefieres no escribirlo desde cero, el repositorio ft-drawings tiene una implementación con p5.js que hace justo eso.
Una cosa que sorprende: las frecuencias negativas. Salen de la propia DFT (por eso k - N arriba) y son círculos que giran al revés. Sin ellos solo podrías dibujar curvas que dan vueltas en un sentido, y España no es una espiral.
Cuántos círculos hacen falta
Esto es lo que hace que el vídeo enganche. Con pocos círculos tienes una mancha redondeada que apenas se parece a nada; según vas añadiendo, aparecen primero los grandes rasgos y luego los detalles, porque los círculos de radio grande llevan la forma general y los pequeños, los dientes de sierra de la costa. Quintero dice que con 150 ya sale la costa, y tiene sentido: un contorno suave no necesita miles de frecuencias, uno con muchos entrantes y salientes sí.
No te lo creas, compruébalo. Esto es el código de arriba funcionando con el contorno de España (512 puntos sacados de Natural Earth). Baja a 5 círculos, sube a 150 y mira dónde aparece Galicia:
Tiene además un efecto secundario curioso: la serie nunca llega a ser exactamente el contorno si este tiene esquinas. Cerca de cada pico aparece un pequeño rebote (el fenómeno de Gibbs), y por mucho que añadas círculos no desaparece del todo. Es el precio de aproximar algo con esquinas usando solo curvas suaves.
Cómo sacar el contorno de un mapa
El paso que más se subestima. La DFT es mecánica; lo que te va a dar guerra es conseguir la lista de puntos. Tienes dos caminos: coger un SVG del mapa y muestrear puntos a lo largo del trazado (el navegador te lo da hecho con getPointAtLength), o coger una imagen en blanco y negro y seguir el borde de la silueta con un algoritmo de detección de contornos.
Da igual cuál elijas, hay dos reglas que te ahorran una tarde de depuración. La primera: los puntos tienen que estar repartidos de forma más o menos uniforme, porque la DFT asume que el tiempo avanza a ritmo constante entre muestras y, si en una zona hay mil puntos y en otra diez, la animación va a ir a tirones. La segunda: el contorno tiene que ser UNA sola línea cerrada, sin saltos. Si la península y las islas están en trozos distintos, o las unes con un trazo invisible, o haces una serie para cada una.
Pruébalo tú en un rato
La demo de arriba no tiene más misterio que esto: con las dos funciones y un <canvas> te sobra media hora. Muestrea unos 500 puntos, calcula los coeficientes una vez y luego, en cada fotograma, avanza t un poquito y dibuja la cadena de círculos con punto(coef, t, n) para cada n creciente. Hazte un deslizador que cambie n de 1 a 200 y mira cómo la forma se va afilando. Es de esas cosas que se entienden en el cuerpo, no en la pizarra.
Y si lo quieres hacer con tu logo o con tu propia firma, el proceso es idéntico: un trazo cerrado, una lista de puntos, una DFT. Esa es la gracia, que la fórmula no sabe qué está dibujando.
Por qué me parece algo más que un truco bonito
Esta misma idea, descomponer una señal en frecuencias, es lo que hay detrás de la compresión de imágenes JPEG, del MP3, del reconocimiento de voz y de buena parte del procesado de señal que usas cada día sin saberlo. Quedarte con los 150 círculos más grandes y tirar el resto es, en pequeño, comprimir con pérdida. Y eso, en mi experiencia, significa que entender este vídeo te deja a un paso de entender por qué un JPEG pesa 10 veces menos que el original.
Siendo realistas, además, no hay mejor forma de enseñar mates que esta: una fórmula que da miedo en la pizarra y un mapa de tu país dibujándose solo.
Preguntas frecuentes
¿Hace falta saber números complejos para probarlo?
No. Con el código de arriba basta con sacar los puntos del contorno y llamar a dos funciones. Los números complejos ayudan a entender por qué funciona, pero no para usarlo.
¿Se puede dibujar cualquier forma?
Cualquier contorno cerrado que se pueda recorrer de un tirón, sí. Si el dibujo tiene varias partes separadas (península y Baleares, por ejemplo), hay que unirlas con un trazo o hacer una serie por cada una.
¿Por qué 150 círculos y no 1.000?
Porque a partir de cierto punto los círculos nuevos son tan pequeños que no se ven. Cuanto más detalle tenga el contorno, más hacen falta.
¿Qué diferencia hay entre serie de Fourier y transformada de Fourier?
La serie descompone una señal periódica (como un contorno cerrado, que vuelve al punto de partida) en frecuencias enteras. La transformada generaliza la idea a señales que no se repiten. La DFT es la versión para listas de puntos finitas, que es la que usas en código.
Compártelo si te ha resultado útil.
¿Qué contorno dibujarías tú con círculos? Cuéntame.
Y… a ver quién se atreve con Canarias.
Artículos relacionados
Búsqueda lineal vs binaria: el poder de partir por la mitad
Buscar algo en una colección es el problema más cotidiano de la programación, y hay dos formas de hacerlo que no se parecen en nada. La búsqueda lineal mira uno a uno, de principio a fin: simple, funciona siempre, pero lenta. La búsqueda binaria parte la colección por la mitad una y otra vez y encuentra lo que buscas en un puñado de pasos, aunque haya millones de elementos. En esta segunda entrega de la serie de Algoritmos te explico las dos, su complejidad (O(n) frente a O(log n)), el requisito imprescindible de la binaria, sus versiones iterativa y recursiva, y cuándo usar cada una. Verás en acción esa diferencia brutal entre mirar un millón de cosas o solo veinte.
Qué es un algoritmo y la notación Big-O explicada paso a paso
Arranca la serie de Algoritmos, y lo hace por donde hay que empezar: aprendiendo a medir. Antes de comparar dos formas de resolver un problema necesitas saber cuál es mejor, y para eso está la notación Big-O. En esta primera entrega te explico qué es un algoritmo de verdad, qué es la complejidad temporal y espacial, y cómo leer esa notación que da tanto respeto: O(1), O(log n), O(n), O(n log n), O(n²) y la temida O(2^n). Lo verás con ejemplos cotidianos, sin matemáticas asustaviejas, y entenderás de una vez por qué un algoritmo puede tardar una décima de segundo y otro, con los mismos datos, dejarte el ordenador colgado una hora. Esto es la regla con la que se mide todo lo que viene después.
Algoritmos desde cero: del bubble sort a A*, toda la serie
Si la serie de Fundamentos te enseñó a escribir programas que funcionan, esta te va a enseñar a escribir programas que funcionan bien: rápidos, eficientes y capaces de aguantar montañas de datos sin ahogarse. Arranco la serie de Algoritmos, dieciséis entregas, los lunes, miércoles y viernes, para recorrer los algoritmos y estructuras de datos más famosos y útiles que existen, los que resuelven los problemas de verdad: buscar, ordenar, recorrer grafos, optimizar y trabajar con texto. Empezamos por la notación Big-O (medir si un programa escala o se ahoga) y terminamos en A*, el algoritmo que usan los videojuegos para encontrar caminos. Es lenguaje-agnóstico, con pseudocódigo y ejemplos. Este post es el índice y el calendario completo.