이진 나무

아래와 같은 하나의 줄기에 두개의 가지만 있는 나무 모양의 프랙탈을 이진 나무(Binary Tree)라 한다. 쉽게 짐작할 수 있듯이 많은 자연의 성장 과정이 위와 유사한 구조로 되어 있다. 나무와 하천의 흐름이 가장 쉽게 찾아 볼 수 있는 예이다.

알고리즘

위의 차수가 3 인 이진 나무를 유심히 관찰하자. 구조가 완벽한 재귀적(순환적) 구조이다. 줄기에서 가지를 쳐 나가는 작업을 0 차 가지(잎)에 도달할 때까지 재귀적으로 반복하면 된다. 기본적인 알고리즘은 잡혔다. 이어서는 어떻게 가지를 쳐 나갈 것인가를 결정한다.

1. 길이가 length 인 a 가지를 그린다.

2. 왼쪽으로 30 도 회전하여 길이가 length*0.8 인 b 가지를 그린다.

3. 오른쪽으로 60 도 회전하여 길이가 length*0.8 인 c 가지를 그린다.

4. 3 번 과정을 마친 후 왼쪽으로 30 도 회전하여 진행 방향을 원래대로 환원시킨다.

예를 들어 차수 n = 3 인 경우 위와 같은 처리를 n 을 1 씩 줄여 나가면서 n = 0 이 될때까지 재귀적으로 반복시키면 위의 오른쪽의 나무가 그려진다. 이 때 주의할 점은 예를 들어 b 가지를 그린 후에는 선을 그리는 시작 위치를 b 가지의 시작점인 CP 로 환원시켜야 한다는 점이다. 그래야 위 알고리즘은 c 가지를 정확히 그린다. 이를 위해서 거북이 그래픽 클래스에 현재 거북이의 위치를 저장하는 스택을 포함하였다. 아래 부분은 거북이 클래스에 새로 추가된 함수의 코드이다.

// Header File

typedef stack<Point3D> pstack;

class Turtle
{
private:
    ...
    pstack PointStack; //위치를 저장할 스택
    ...
public:
    ... 
    void MarkCurrentPoint(void); //현재의 위치에 점을 그린다.
    void Push(void); //현재의 위치를 저장한다.
    void Pop(void); //저장한 위치로 돌아간다.
};

// Source File

Turtle::Turtle(void)
{
    //스택 포인터 모두 제거
    while(PointStack.size())
    {
        PointStack.pop();
    }
    ...
}

void Turtle::SetStartPoint(float x, float y, float z)
{
    //스택 포인터 모두 제거
    while(PointStack.size())
    {
        PointStack.pop();
    }
    ... 
} 

void Turtle::MarkCurrentPoint(void)
{
    glPointSize(5.0f);
    glBegin(GL_POINTS);
        glColor3f(1.0f, 0.0f, 0.0f);
        glVertex3f(PointList[PointList.size()-1].x, PointList[PointList.size()-1].y, PointList[PointList.size()-1].z);
        glColor3f(1.0f, 1.0f, 1.0f);
    glEnd();
}

void Turtle::Push(void)
{
    int index = PointList.size()-1;
    Point3D pt(PointList[index].x, PointList[index].y, PointList[index].z);

    //포인트 리스트에 저장되어 있는 마지막 점을 push 한다.
    PointStack.push(pt);
}

void Turtle::Pop(void)
{
    if(PointStack.size())
    {
        Point3D pt(PointStack.top());
        PointStack.pop();
        PointList.push_back(pt);
    }
}

위의 알고리즘을 코드로 표현하면 아래와 같다.

void RenderWindow::BinaryTree(int n, float length)
{
    turtle.Forward(length);
    if(n>0)
    {
        turtle.Push(); //CP 저장
        turtle.Left(30); BinaryTree(n-1, length*0.8);
        turtle.Pop(); //CP 로 이동
        turtle.Right(60); BinaryTree(n-1, length*0.8);
        turtle.Left(30);
    }
}

아래는 이진나무를 표현한 프로그램 결과와 전체 코드이다. 오른쪽 그림은 열매를 맺은 나무이다. n==0 일때 현재의 점을 표시하면 된다.

#include "lib\egl.h"
#include "turtle.h"

using namespace egl;

class RenderWindow : public Window
{
private:
    Turtle turtle;
public:
    void BinaryTree(int n, float length);
    virtual void RenderGLScene(void);
};

void RenderWindow::BinaryTree(int n, float length)
{
    turtle.Forward(length);

    //열매를 그린다.
    if(n==0)
    {
        turtle.MarkCurrentPoint();
    }

    if(n>0)
    {
        turtle.Push();
        turtle.Left(30); BinaryTree(n-1, length*0.8);
        turtle.Pop();
        turtle.Right(60); BinaryTree(n-1, length*0.8);
        turtle.Left(30);
    }
}

void RenderWindow::RenderGLScene(void)
{
    Window::RenderGLScene();

    glTranslatef(0.0f, 0.0f, -7.0f);

    turtle.SetStartPoint(0.0f, -2.0f, 0.0f);
    turtle.Left(90);

    BinaryTree(12, 1.0f);
}

int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
    RenderWindow app;
    if(!app.Create(FALSE, "Fractal - Binary Tree"))
        return EXIT_FAILURE;
    return app.Run();
}