Jugando con Fractales

Si eres un amante de los fractales, la geometría analítica y la programación, en este artículo aprenderás a dibujar fractales utilizando JavaScript. Los fractales son figuras geométricas formadas por repeticiones de un mismo patrón un gran número de veces. Un fractal nos da una representación gráfica de lo comúnmente conocido en la programación como **recursividad**. En este post programaremos algunos de los fractales más famosos. ## Funciones auxiliares Antes de entrar en materia les muestro algunas funciones y librerías complementarias que se utilizaron para simplificar los algoritmos. 1. Se empleó la librería externa [Victor](http://victorjs.org/) que posee un conjunto de funciones necesarias a la hora de trabajar con vectores. 2. Se implementó la clase ```queue``` la cual consta de una implementación muy básica de lo que seria una **cola**. ``` export const queue = function() { this.q = [] this.push = function(ele) { this.q.push(ele) } this.empty = function() { return this.q.length === 0 } this.top = function() { if(!this.empty()) return this.q[0] return null } this.pop = function() { if(!this.empty()) return this.q.shift() return null } } ``` 3. Se creó un archivo ```paint.js``` el cual contiene un conjunto de métodos para simplificar el proceso a la hora de "dibujar" sobre el ```canvas``` de ```html``` ``` export const resetCanvas = (ctx, width, height) => { ctx.fillStyle = '#071a52' ctx.fillRect(0, 0, width, height) ctx.strokeStyle = "#f0f0f0" } export const drawLineVector = (ctx, v) => { for(let i = 0; i < v.length - 1; i++){ ctx.beginPath() ctx.moveTo(v[i].x, v[i].y) ctx.lineTo(v[i+1].x, v[i+1].y) ctx.stroke() ctx.closePath() } } export const drawLine2Point = (ctx, p1, p2) => { ctx.beginPath() ctx.moveTo(p1.x, p1.y) ctx.lineTo(p2.x, p2.y) ctx.stroke() ctx.closePath() } ``` ## Triángulo de Sierpinski  Como se muestra en la figura el fractal se logra repitiendo el mismo triángulo con dimensiones más reducidas. La siguiente figura nos ayudara a comprender el proceso matemático:  1. Creamos el triángulo P1P2P3 2. Calculamos los puntos medios P1', P2' y P3' 3. Creamos los triángulos P1P1'P3', P1'P2P2'y P2'P3P3' 4. Repetimos el proceso con los nuevos triángulos creados. A continuación el código: Importamos las dependencias necesarias. ``` import Victor from 'victor' import {drawLine2Point} from './paint' ``` Creamos una clase ```Triangle``` ``` const Triangle = function(p1, p2, p3, tag) { this.p1 = p1 this.p2 = p2 this.p3 = p3 this.tag = tag this.generated = false this.show = function(ctx){ if(this.tag === 'root'){ drawLine2Point(ctx, this.p1, this.p2) drawLine2Point(ctx, this.p2, this.p3) drawLine2Point(ctx, this.p3, this.p1) }else if(this.tag === 't1'){ drawLine2Point(ctx, this.p2, this.p3) }else if(this.tag === 't2'){ drawLine2Point(ctx, this.p3, this.p1) }else if(this.tag === 't3'){ drawLine2Point(ctx, this.p1, this.p2) } } this.T1 = function() { let t1_p1 = new Victor(this.p1.x, this.p1.y) let t1_p2 = new Victor((this.p1.x + this.p2.x) / 2, (this.p1.y + this.p2.y) / 2) let t1_p3 = new Victor((this.p1.x + this.p3.x) / 2, (this.p1.y + this.p3.y) / 2) let t1 = new Triangle(t1_p1, t1_p2, t1_p3, 't1') return t1 } this.T2 = function() { let t2_p1 = new Victor((this.p1.x + this.p2.x) / 2, (this.p1.y + this.p2.y) / 2) let t2_p2 = new Victor(this.p2.x, this.p2.y) let t2_p3 = new Victor((this.p2.x + this.p3.x) / 2, (this.p2.y + this.p3.y) / 2) let t2 = new Triangle(t2_p1, t2_p2, t2_p3, 't2') return t2 } this.T3 = function() { let t3_p1 = new Victor((this.p1.x + this.p3.x) / 2, (this.p1.y + this.p3.y) / 2) let t3_p2 = new Victor((this.p2.x + this.p3.x) / 2, (this.p2.y + this.p3.y) / 2) let t3_p3 = new Victor(this.p3.x, this.p3.y) let t3 = new Triangle(t3_p1, t3_p2, t3_p3, 't3') return t3 } } ``` Por último creamos la función que genera el fractal: ``` export const Sierpinski = (ctx, p1, p2, p3, n) => { let T = [] let root = new Triangle(p1, p2, p3, 'root') T[0] = root while(n--){ for(let i = T.length - 1; i >= 0; i--){ if(!T[i].generated){ T.push(T[i].T1()) T.push(T[i].T2()) T.push(T[i].T3()) T[i].generated = true } } } for(let i = 0; i < T.length; i++){ T[i].show(ctx) } } ``` Esta función recibe 5 parámetros: 1. ```ctx``` Referencia al contexto del objeto canvas (```canvas.getContext('2d')```) 2. ```p1``` Objeto de tipo ```Victor``` que contiene las coordenadas del punto p1. 3. ```p2``` Objeto de tipo ```Victor``` que contiene las coordenadas del punto p2. 4. ```p3``` Objeto de tipo ```Victor``` que contiene las coordenadas del punto p3. 5. ```n``` Entero que representa el número de niveles. Así quedará nuestro fractal:  ## Curva Dragón Este fractal se construye siguiendo los siguientes pasos: 1. Dado un segmento AB se construye un triángulo isósceles y rectángulo con base AB 2. Se borra el segmento AB. 3. Se repite el procedimiento un número determinado de veces. La siguiente imagen muestra el proceso para los primeros 3 niveles.  A continuación el código: Importamos las dependencias necesarias: ``` import Victor from 'victor' import {queue} from './queue' import {drawLine2Point} from './paint' ``` Creamos una función auxiliar que retorna el punto entre A y B que forma un triángulo isósceles y rectángulo: ``` const mP = (p1, p2) => { return new Victor( (p1.x + p2.x + p1.y - p2.y) / 2, (p2.x - p1.x + p1.y + p2.y) / 2) } ``` Creamos la función que genera el fractal mediante un algoritmo BFS. ``` let Q = new queue(); export const dragon_bfs = (ctx, a, b, n) => { let line = { p1: a, p2: b } if(!n){ drawLine2Point(ctx, line.p1, line.p2) }else{ Q.push(line) let N = Math.pow(2, n) - 1 while(N){ let l = Q.top() Q.pop() let l1 = { p1: l.p1, p2: mP(l.p1, l.p2) } let l2 = { p1: l.p2, p2: mP(l.p1, l.p2) } Q.push(l1) Q.push(l2) N-- } N = Math.pow(2, n) while(N){ drawLine2Point(ctx, Q.top().p1, Q.top().p2) Q.pop() N-- } } } ``` Esta función recibe 4 parámetros: 1. ```ctx``` Referencia al contexto del objeto canvas (```canvas.getContext('2d')```) 2. ```a``` Objeto de tipo ```Victor``` que contiene las cordenadas del punto a. 3. ```b``` Objeto de tipo ```Victor``` que contiene las cordenadas del punto b. 4. ```n``` Entero que representa el número de niveles. Así quedará nuestro fractal:  ## Curva de Von Kock Descubierta por el matemático *Helge Von Koch* en 1904. La curva se construye de la siguiente manera: 1. Dado un segmento AB se divide en tres partes iguales (3 segmentos). 2. Con el segmento del medio construimos un triangulo equilátero. 3. Se repite el proceso para cada uno de los segmentos mas pequeños. Veamos el proceso en la siguiente figura:  Veamos para los dos primeros niveles:  A continuación el código: Importamos las dependencias ``` import {drawLineVector} from './paint' ``` Crearemos dos funciones auxiliares. La primera para determinar los puntos a 1/3 y 2/3 del segmento AB. ``` const getPoint = (a, b, t) => { return { x: a.x * (1 - t) + b.x * t, y: a.y * (1 - t) + b.y * t } } ``` Esta función recibe 3 parámetros: los puntos a y b del segmento a particionar y una proporción t, de tal manera cuando ```t=1/3``` retorna el punto a ```1/3``` del segmento y cuando ```t=2/3``` retorna el punto a 2/3 del segmento. La segunda función recibe tres parámetros: un punto ```p```, un punto ```c``` y un diferencial de angulo ```da``` (en radianes). Lo que hace es rotar el punto ```p``` ```da``` radianes sobre la circunferencia con centro en ```c``` y radio igual a la distancia entre el punto ```p``` y el punto ```c```. ``` const getCirPoint = (p, c, da) => { let dx = p.x - c.x let dy = p.y - c.y let r = Math.sqrt(dx*dx + dy*dy) let a = Math.atan2(dy, dx) a -= da let q = { x: c.x + r * Math.cos(a), y: c.y + r * Math.sin(a) } return q } ``` Finalmente la función que genera la curva: ``` const pi = Math.PI export const vonKock = (ctx, a, b, n) => { let P = [a, a, a, a, b] P[1] = getPoint(P[0], P[4], 1.0/3.0) P[3] = getPoint(P[0], P[4], 2.0/ 3.0) P[2] = getCirPoint(P[3], P[1], pi / 3.0) if(n <= 1){ drawLineVector(ctx, P, true) }else{ for(let i = 0; i < P.length - 1; i++) vonKock(ctx, P[i], P[i + 1], n-1) } } ``` Esta función recibe 4 parámetros: 1. ```ctx``` Referencia al contexto del objeto canvas (```canvas.getContext('2d')```) 2. ```a``` Objeto de tipo ```Victor``` que contiene las cordenadas del punto a. 3. ```b``` Objeto de tipo ```Victor``` que contiene las cordenadas del punto b. 4. ```n``` Entero que representa el número de niveles. A continuación otra implementación que arroja el mismo resultado: ``` const pi = Math.PI export const vonKock = (ctx, a, b, n) => { let P = [a, a, a, a, b] P[1] = { x: a.x + (b.x - a.x) / 3, y: a.y + (b.y - a.y) / 3 } P[3] = { x: b.x + (a.x - b.x) / 3, y: b.y + (a.y - b.y) / 3 } P[2] = { x: (P[1].x + P[3].x) * Math.cos(pi/3) + (P[3].y - P[1].y)*Math.sin(pi/3), y: (P[1].y + P[3].y) * Math.cos(pi/3) - (P[3].x - P[1].x)*Math.sin(pi/3) } if(n <= 1){ drawLineVector(ctx, P) }else{ for(let i = 0; i < P.length - 1; i++) vonKock(ctx, P[i], P[i + 1], n-1) } } ``` Así quedará nuestro fractal:  ## Dibujando árboles Ahora crearemos fractales con forma de árboles. Para crear este tipo de fractales procedemos de la siguiente forma. 1. Dado un segmento AB se crean dos copias con menor tamaño. 2. Se rotan los nuevos segmentos con un determinado angulo. 3. Se trasladan los dos segmentos hasta coincidir con el punto B. 4. Se repite el proceso para cada segmento. En la siguiente figura se muestra el proceso mencionado.  Variando el nuevo tamaño y canda ángulo de rotación se pueden crear infinidad de árboles distintos. Veamos el código: Importamos las dependencias necesarias ``` import Victor from 'victor' import {drawLine2Point} from './paint' ``` Creamos una clase ```Branch``` la cual sera una representación de una rama del árbol y presenta las siguientes propiedades: 1. ```start``` Objeto de tipo ```Victor``` que representa el punto donde comienza la rama. 2. ```end``` Objeto de tipo ```Victor``` que representa el punto donde termina la rama. 3. ```al``` Ángulo de rotación (en radianes) de la rama izquierda (hija). 4. ```ar``` Ángulo de rotación (en radianes) de la rama derecha (hija). 5. ```divl``` Factor de crecimiento de la rama izquierda (hija), 6. ```divr``` Factor de crecimiento de la rama derecha (hija). ``` const Branch = function(start, end, al, ar, divl, divr) { this.start = start this.end = end this.left_angle = al this.right_angle = ar this.divl = divl this.divr = divr this.completed = false this.show = function(ctx) { drawLine2Point(ctx, this.start, this.end) } this.branchA = function() { let dir = new Victor(this.end.x, this.end.y).subtract(this.start) dir.rotate(this.right_angle) dir.divide(new Victor(this.divr, this.divr)) dir.add(this.end) let right = new Branch(this.end, dir, this.left_angle, this.right_angle, this.divl, this.divr) return right } this.branchB = function() { let dir = new Victor(this.end.x, this.end.y).subtract(this.start) dir.rotate(this.left_angle) dir.divide(new Victor(this.divl, this.divl)) dir.add(this.end) let left = new Branch(this.end, dir, this.left_angle, this.right_angle, this.divl, this.divr) return left } } ``` Por último el código que genera el árbol: ``` export const generateTree = (ctx, p1, p2, al, ar, divl, divr, n) => { let T = [] let root = new Branch(p1, p2, al, ar, divl, divr) T[0] = root while(n--){ for(let i = T.length - 1; i >= 0; i--){ if(!T[i].completed){ T.push(T[i].branchA()) T.push(T[i].branchB()) } T[i].completed = true } } for(let i = 0; i< T.length; i++){ T[i].show(ctx) } } ``` Esta función recibe 8 parámetros: 1. ```ctx``` Referencia al contexto del objeto canvas (```canvas.getContext('2d')```) 2. ```p1``` Objeto de tipo ```Victor``` que contiene las coordenadas del punto de inicio del tronco. 3. ```p2``` Objeto de tipo ```Victor``` que contiene las coordenadas del punto donde termina el tronco. 4. ```al``` Ángulo de rotación (en radianes) de las ramas izquierdas. 5. ```ar``` Ángulo de rotación (en radianes) de las ramas derechas. 6. ```divl``` Factor de crecimiento de las ramas izquierdas. 7. ```divr``` Factor de crecimiento de la ramas derechas. 8. ```n``` Entero que representa el número de niveles. Cabe resaltar que el factor de crecimiento debe de estar en el rango de 0 a 1 para que todo tenga sentido. Así quedarán algunos árboles con diferentes parámetros:  ## L-System Por último les comentaré de un algoritmo que generaliza todo lo que hemos visto hasta este momento ya que con el se puede obtener cualquier fractal posible. El algoritmo encuentra gran aplicación a la hora de generar los mapas de los videojuegos (tanto árboles como terrenos). Un sistema L-System consiste de un alfabeto con el cual se generan cadenas de caracteres siguiendo determinadas reglas y comenzando por un ```string``` inicial denominado ```axion``` Veamos un ejemplo: ``` axion = "A" rule1 = {key:"A", value:"AB"} //A =>> AB rule2 = {key:"B", value:"C"} //B ==> C //Esto genera //1. A //2. AB //3. ABA //4. ABAAB //5. ABAABABA //....... ``` Visto esto se puede construir un pequeño intérprete si definimos algunas reglas, por ejemplo: Si nuestra cadena solo contiene los caracteres ```F [ ] + -```, se puede definir que: 1. ```F``` Dibuja una linea vertical 2. ```[``` Guarda en una pila la referencia del ultimo punto del segmento dibujado. 3. ```]``` Sacar de la pila el punto. 4. ```+``` Rotar ```n``` grados en sentido horario el segmento a dibujar. 5. ```-``` Rotar ```n``` grados en sentido anti-horario el segmento a dibujar. Con esto definido lo único que tenemos que hacer es seleccionar correctamente el ```axion``` las reglas y los ángulos para generar cualquier figura deseada. Para la programación crearemos 3 funciones, una que genere el patrón, otra que interprete el patrón generado y la función que dibuje la figura. Primero importamos las dependencias. ``` import Victor from 'victor' import {drawLine2Point} from './paint' ``` Función que genera el patrón: ``` const create_patron = (sentence, rules) => { let nextSentece = '' for(let i = 0; i < sentence.length; i++){ let current = sentence.charAt(i) let found = false for(let r = 0; r < rules.length; r++){ if(current === rules[r].a){ found = true nextSentece += rules[r].b break } } if(!found) nextSentece += current } return nextSentece } ``` Función intérprete ``` const interprete = (ctx, sentence, a, b, angle) => { let stack = [] let l = { p1: a, p2: b } for(let i = 0; i < sentence.length; i++){ let current = sentence.charAt(i) if(current === 'F'){ drawLine2Point(ctx, l.p1, l.p2) let newp1 = l.p2 let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1) newp2.add(l.p2) l = { p1: newp1, p2: newp2 } }else if(current === '+'){ let newp1 = l.p1 let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1) newp2.rotate(angle) newp2.add(newp1) l = { p1: newp1, p2: newp2 } }else if(current === '-'){ let newp1 = l.p1 let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1) newp2.rotate(-angle) newp2.add(newp1) l = { p1: newp1, p2: newp2 } }else if(current === '['){ stack.push(l) }else if(current === ']'){ l = stack.pop() } } } ``` Por último la función que dibuja el fractal: ``` export const Lsystem = (ctx, axion, rules, a, b, angle, factor_scale, n) => { let sentence = axion let scale = 1 while(n--){ sentence = create_patron(sentence, rules) scale *= factor_scale } let dir = new Victor(b.x, b.y).subtract(a) dir.divide(new Victor(scale, scale)) dir.add(a) interprete(ctx, sentence, a, dir, angle) } ``` Esta función recibe 8 parámetros: 1. ```ctx``` Referencia al contexto del objeto canvas (```canvas.getContext('2d')```) 2. ```axion``` ```string``` que representa el axiom. 3. ```rules``` Arreglo que contiene todas las reglas definidas. 4. ```a``` Objeto de tipo ```Victor``` que indica el inicio del segmento. 5. ```b``` Objeto de tipo ```Victor``` que indica el final del segmento. 6. ```angle``` Angulo en radianes que indica la rotación del segmento. 7. ```factor_scale``` Valor que permite ajustar el dibujo a medida que crecen los niveles. 8. ```n``` Entero que representa el número de niveles. A continuación algunos ejemplos: ### Tree  ### Hibiscus a 30 grados  ### Hilbert curve  ### Triangle of Sierpinski  Hasta aquí este artículo puedes revisar el código en [Github](https://github.com/inergarcia/fractalPost). Espero que halla sido de tu agrado.