Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como gerar imagens de árvores usando recursões?

0 votos
318 visitas
perguntada Mar 26, 2016 em Ciência da Computação por danielcajueiro (5,581 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Mar 26, 2016 por danielcajueiro (5,581 pontos)  

Um algoritmo simples é iniciar com uma haste vertical e patir dela gerar novos dois ramos:

Recursive tree

E assim por diante:

Recursive tree

Depois de muitas recursões, chegamos a

A imagem será apresentada aqui.

Podemos também tornar o processo estocástico e o surgimente de cada novo ramo depender de uma probabilidade fixa:

A imagem será apresentada aqui.

Eu fiz esse código para gerar as figuras acima (onde você pode brincar com os parâmetros):

import matplotlib.pyplot as plt
import math
import numpy as np

fig=plt.figure()
plt.hold(True)
plt.axis([-150, 150, -100, 300])
global cont
cont=0

np.random.seed(seed=10)

def eval_rotation_matrix(rotationAngle):
    rotM11=math.cos(rotationAngle)
    rotM12=-math.sin(rotationAngle)    
    rotM21=math.sin(rotationAngle)
    rotM22=math.cos(rotationAngle)        
    return rotM11,rotM12,rotM21,rotM22

def image_rotation(x,y,angle):
    rotM11,rotM12,rotM21,rotM22=eval_rotation_matrix(angle)        
    x,y=x*rotM11+y*rotM12,x*rotM21+y*rotM22
    return x,y


def draw_trees(xIni,yIni,xEnd,yEnd,length,baseSize=1.0,factorSize=1.2,angle=math.pi/12,randomDraw=0.75):
    global cont
    if(length<baseSize):
        pass
    else:
        cont=cont+1
        print "cont",cont
        if(xEnd!=xIni):
            theta=math.atan((yEnd-yIni)/(xEnd-xIni))
        else:
            theta=math.pi/2

        if(theta>=0):
            if((yEnd>=yIni) and (xEnd>=xIni)):
                pass
            else:
                theta=theta+math.pi

        if(theta<0):
            if((yEnd<yIni) and (xEnd>=xIni)):
                pass
            else:
                theta=theta+math.pi



        x=length
        y=0
        if(np.random.uniform()<randomDraw):

            newX1,newY1=image_rotation(x,y,angle)
            newX1,newY1=image_rotation(newX1,newY1,theta)
            newX1,newY1=newX1+xEnd,newY1+yEnd        
            plt.plot([xEnd,newX1],[yEnd,newY1],'b')
            draw_trees(xEnd,yEnd,newX1,newY1,length/factorSize)        

        if(np.random.uniform()<randomDraw):
            newX2,newY2=image_rotation(x,y,-angle)
            newX2,newY2=image_rotation(newX2,newY2,theta)
            newX2,newY2=newX2+xEnd,newY2+yEnd        
            plt.plot([xEnd,newX2],[yEnd,newY2],'b')
            draw_trees(xEnd,yEnd,newX2,newY2,length/factorSize)        






if __name__ == '__main__':

    # Example of Dictionary

    initialSize=64.0
    xIni=0
    yIni=0
    xEnd=xIni
    yEnd=yIni+initialSize
    plt.plot([xIni,xEnd],[yIni,yEnd],'b')
    initialpoint=[xEnd,yEnd]
    draw_trees(xIni,yIni,xEnd,yEnd,initialSize/2.0)
    plt.savefig("treeStochast.png")

Uma outra possibilidade, é fazer a probabilidade de um novo ramo surgir dependendo da geração que ele pertence. Quanto maior a geração, menor a chance:

A imagem será apresentada aqui.

Nesse caso, eu usei esse código que é uma variação do código original:

import matplotlib.pyplot as plt
import math
import numpy as np

fig=plt.figure()
plt.hold(True)
plt.axis([-150, 150, -100, 300])
global cont
cont=0

np.random.seed(seed=10)

def eval_rotation_matrix(rotationAngle):
    rotM11=math.cos(rotationAngle)
    rotM12=-math.sin(rotationAngle)    
    rotM21=math.sin(rotationAngle)
    rotM22=math.cos(rotationAngle)        
    return rotM11,rotM12,rotM21,rotM22

def image_rotation(x,y,angle):
    rotM11,rotM12,rotM21,rotM22=eval_rotation_matrix(angle)        
    x,y=x*rotM11+y*rotM12,x*rotM21+y*rotM22
    return x,y


def draw_trees(xIni,yIni,xEnd,yEnd,length,generation,baseSize=1/8.0,factorSize=1.2,angle=math.pi/12):
    global cont
    if(length<baseSize):
        pass
    else:
        cont=cont+1
        print "cont",cont
        if(xEnd!=xIni):
            theta=math.atan((yEnd-yIni)/(xEnd-xIni))
        else:
            theta=math.pi/2

        if(theta>=0):
            if((yEnd>=yIni) and (xEnd>=xIni)):
                pass
            else:
                theta=theta+math.pi

        if(theta<0):
            if((yEnd<yIni) and (xEnd>=xIni)):
                pass
            else:
                theta=theta+math.pi



        x=length
        y=0
        parameter=0.05
        if(np.random.uniform()<1.0/(1+parameter*generation)):

            newX1,newY1=image_rotation(x,y,angle)
            newX1,newY1=image_rotation(newX1,newY1,theta)
            newX1,newY1=newX1+xEnd,newY1+yEnd        
            plt.plot([xEnd,newX1],[yEnd,newY1],'b')
            draw_trees(xEnd,yEnd,newX1,newY1,length/factorSize,generation+1)        

        if(np.random.uniform()<1.0/(1+parameter*generation)):
            newX2,newY2=image_rotation(x,y,-angle)
            newX2,newY2=image_rotation(newX2,newY2,theta)
            newX2,newY2=newX2+xEnd,newY2+yEnd        
            plt.plot([xEnd,newX2],[yEnd,newY2],'b')
            draw_trees(xEnd,yEnd,newX2,newY2,length/factorSize,generation+1)        






if __name__ == '__main__':

    # Example of Dictionary

    initialSize=64.0
    xIni=0
    yIni=0
    xEnd=xIni
    yEnd=yIni+initialSize
    plt.plot([xIni,xEnd],[yIni,yEnd],'b')
    initialpoint=[xEnd,yEnd]
    draw_trees(xIni,yIni,xEnd,yEnd,initialSize/2.0,0)
    plt.savefig("treeStochastGeneration.png")
comentou Ago 3, 2018 por Taylon (21 pontos)  
Muito interessante mesmo. Meus parabéns professor. O uso de regressão me lembrou muito fractal. Uma pergunta: o código está em qual linguagem? Seria python?
comentou Ago 3, 2018 por danielcajueiro (5,581 pontos)  
Sim, Python! Obrigado
comentou Abr 1, 2020 por Rodrigo Stuckert (66 pontos)  
Professor, reparei que no código tem o comando "pass". Não seria mais adequado inverter as cláusulas dos "if's" a que eles se referem e remover os "else", por simplicidade?
comentou Abr 2, 2020 por danielcajueiro (5,581 pontos)  
Sim, sem duvida.
...