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

Como gerar imagens de árvores usando recursões?

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

1 Resposta

0 votos
respondida Mar 26, 2016 por danielcajueiro (5,251 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")
...